摘要
提供與物體位置有關的查詢服務稱為位置為基礎的服務(Location Based Services-LBSs)。提供關於LBSs的查詢，我們稱為位置有關的查詢(Location-Dependent Queries-LDQs)。LDQs的應用包括了範圍查詢(Range query)、最近者查詢(Nearest Neighbor-NN query)、k個最近者查詢(K-Nearest Neighbor-KNN query)以及反向最近者查詢(Reverse Nearest Neighbor-RNN query)等。LBSs的行動服務應用包括提供如交通資訊與attractions等與位置相關的資訊存取以及如找尋最近的餐廳、找尋五百公尺以內的加油站等查詢服務。雖然LDQ的問題在傳統有線以磁碟為基礎的主從架構(disk based client-server)環境有很好的研究，目前在無線的廣播環境只處理特定如最近者的LDQ並沒有處理同時支援各種不同類型的LDQ的問題。本論文中，我們討論如何在無線廣播的環境有效的組識與位置相關的資料以及可以同時提供多種不同形態的LDQ查詢的問題。無線廣播線性存取以及行動裝置必需考量節省電力的特性使得這個問題更具挑戰性。我們針對無線廣播提出一個可適應線性存取與有效節省電力稱為Jump-Rdnn tree的索引架構與相對的LDQ查尋演算法。我們設計了大量的實驗來驗證我們的方法，實驗結果驗證我們方法在效能方面有顯著的提升。
並列摘要
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). LDQ contains Range query, Nearest Neighbor (NN) query, K-Nearest Neighbor (KNN) query and Reverse Nearest Neighbor (RNN) query etc. Example of mobile LBSs include location-dependent information access (e.g., traffic reports and attractions) and nearest neighbor queries (e.g., finding the nearest restaurant).While the LDQ 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 LDQ 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.