在無線廣播環境查詢反向最近者

 

Search RNN on Air

 

林聯發

高苑科技大學資訊傳播系

中山路1821

高雄縣821路竹鄉

lienfa@cc.kyu.edu.tw

 

Lien-Fa Lin   

Dept. of Information Communication, University of Kao Yuan

No.1821, Jhongshan Rd.,

Lujhu Township, Kaohsiung County 821

lienfa@cc.kyu.edu.tw

 

摘要

提供與物體位置有關的查詢服務被稱為 Location Based Services (LBSs),而支援LBS 的查詢稱為與位置相關查詢(Location Dependent Queries-LDQ)。反向最近鄰居的查詢(Reverse Nearest Neighbor Queries-RNN),即是屬於這類服務。就如最近鄰居查詢(Nearest Neighbor Queries-NN)RNN 查詢也出現在很多的實際應用方面,包括決策支援系統、市場決策、資料庫文件搜尋、生物資訊等。因此提供有效率的方法來處理資料庫RNN查詢有其必要性。雖然RNN的問題在傳統有線以磁碟為基礎的主從架構(disk based client-server)環境有很好的研究,在無線的廣播環境並沒有處理過RNN 的問題。

本論文中,我們討論如何在無線廣播的環境有效的組織與位置相關的資料以及回答 RNN 查詢的問題。無線廣播線性存取以及行動裝置必需考量節省電力的特性使得這個問題特別有趣也更具挑戰性。我們針對無線廣播環境提出一個可適應線性存取與有效節省電力稱為Jump-Rdnn tree 的索引架構以及相對的RNN查詢演算法。我們設計了大量的實驗來驗證我們的方法,實驗結果驗證我們方法在效能方面有顯著的提升。

 

關鍵詞索引結構,資料廣播,能源管理,行動計算

 

Abstract

Location-based services (LBSs) provide information based on location information specified in a query. Queries that support for LBS are called Location-Dependent Queries (LDQ). One such query is the Reverse Nearest Neighbor (RNN) query that returns the objects that have a query object as their closest object. Just like the Nearest Neighbor (NN) queries, the RNN queries appear in many practical applications such as decision support system, continuous referral systems, profile-based marketing, maintaining document repositories, bioinformatics, etc. Thus efficient methods for the RNN queries in database are required. While the RNN is well studied in the traditional wired, disk-based client-server environment; it has not been tackled in a wireless broadcast environment. In this paper, the issues involved with organizing location dependent data and answering RNN queries on air are investigated. The linear property of wireless broadcast media and power conserving requirement of mobile devices make the problem particularly interesting and challenging. An efficient data organization, called Jump-Rdnn Tree, and the corresponding search algorithm are proposed. Performance of the proposed Jump-Rdnn Tree and other traditional indexes (enhanced for wireless broadcast) is evaluated using both uniform and skew data. The result shows that Jump-Rdnn Tree substantially outperforms the traditional indexes.

 

Keywords: index structure, data broadcast, energy-conserving, mobile computing