反向最近鄰聯(lián)合查詢技術的研究.pdf

1、隨著GPS設備的不斷普及，基于位置的服務逐漸走進我們的日常生活。反向k最近鄰(Reverse k Nearest Neighbor，RkNN)查詢作為基于位置服務的支持技術之一，已經成為當前的一個研究熱點問題。RkNN查詢檢索的是以查詢點為k最近鄰的對象集合，目前研究主要集中在單色反向k最近鄰查詢上，而對于雙色反向k最近鄰查詢研究較少，且現(xiàn)有的算法不能高效地處理查詢發(fā)起者為一個集合的雙色反向k最近鄰查詢問題。針對現(xiàn)有查詢算法的不足，本文

2、提出了一種基于集合的雙色反向k最近鄰查詢——雙色反向k最近鄰聯(lián)合查詢(Bichromatic Reverse k Nearest Neighbor Combined query，CBRkNN query)，并給出了高效的CBRkNN查詢算法。
　　首先，在分析和總結現(xiàn)有RkNN查詢算法的基礎上，本文提出了CBRkNN查詢問題，并且給出了基于Finch的CBRkNN查詢算法。算法首先根據查詢集合構造出查詢區(qū)域，然后檢索出落入該區(qū)域內

3、的用戶構成候選集，最后對候選集中每個用戶進行確認，排除錯誤的查詢結果。實驗驗證了算法的高效性。
　　其次，通過對基于Voronoi圖的BRNN查詢算法的深入研究，本文引入了影響區(qū)域的概念并提出了基于影響區(qū)域的CBRNN查詢算法。算法將查詢集合與Voronoi圖結合，給出了組Voronoi圖的定義。算法利用組Voronoi圖構造出查詢集合的影響區(qū)域，檢索出落入該區(qū)域內的用戶構成結果集。實驗驗證了基于影響區(qū)域的CBRNN查詢算法比基于

4、Finch的CBRNN查詢算法效率更高。
　　最后，本文引入k級影響區(qū)域的概念并利用該區(qū)域減小搜索空間，給出了基于k級影響區(qū)域的CBRkNN查詢算法(k>1)。算法根據查詢集合劃分平面，引入凸多邊形級別的定義，搜索出級別小于k的凸多邊形構成k級影響區(qū)域，最后檢索出落入該區(qū)域內的用戶構成結果集。實驗驗證了基于k級影響區(qū)域的CBRkNN查詢算法比基于Finch的CBRkNN查詢算法效率更高。
　　綜上所述，本文針對現(xiàn)有BRkNN