在廣播環境查詢反向最近鄰居

Abstract

提供與物體位置有關的查詢服務被稱為Location Based Services(LBSs)。Reverse NearestNeighbor(RNN) queries，即是屬於這類服務。RNN queries應用相當廣泛，包括決策支援系統、市場決策、資料庫文件搜尋、生物資訊等。雖然RNN的問題在傳統有線以磁碟為基礎的主從架構(disk based client-server)環境有很好的研究，在無線的廣播環境並沒有處理過RNN的問題。\n本論文中，我們討論如何在無線廣播的環境有效的組織與位置相關的資料以及回答RNN查詢的問題。無線廣播線性存取以及行動裝置必需考量節省電力的特性使得這個問題特別有趣也更具挑戰性。我們針對無線廣播提出一個可適應線性存取與有效節省電力稱為Jump-Rdnn tree的索引架構與相對的RNN查尋演算法。我們設計了大量的實驗來驗證我們的方法，實驗結果驗證我們方法在效能方面有顯著的提升。