在新興環境下對反向最近相鄰者搜尋之探討

現今的地理資訊系統包含了許多重要的搜尋服務，例如最近相鄰者(NN) 搜尋, k個最近相鄰者(kNN) 搜尋及反向最近相鄰者(RNN)搜尋，本篇論文以探討反向最近相鄰(RNN)為主。最近反向相鄰(RNN)搜尋是找出一組物件，而這些物件的最近相鄰者即查詢者，其相關運用包括計程車叫車服務或是救護車派遣等相關服務。參考以往有關RNN搜尋的相關文獻，針對我們提出了一些方法在不同環境中可以快速解決RNN搜尋，首先我們以靜態物件進行RNN搜尋為來探討，但是隨著科技的進步，現今物件的特性由靜態轉向動態，因此探討物件在移動過程中還能進行RNN搜尋便為一個很值得探討的議題。除此之外，用資料廣播來提供資訊服務受到許多研究者的探討，使用者只須擁有行動裝置即可透過廣播的方式來接收資料並且進行搜尋。在本論文中我們首先提出了靜態物件的查詢方式，再進而研究物件與查詢者移動的相互關係。論文中我們亦針對不同的環境提出不同的衡量方式，在靜態的RNN搜尋方面主要是以I/O次數及所計算物件的數量來衡量，我們透過過濾的方式減少RNN搜尋的時間，使搜尋的過程中可以避免不必要的檢查；然而以物件為動態的情況來說，節省伺服器的更新次數為我們主要的目的，希望伺服器能夠估計出時間而不需物件移動就進行更新；最後利用資料廣播進行RNN搜尋，我們利用了不同的空間填充曲線(space-filling curves)產生廣播排程來保持資料的方位性，實驗結果發現方位性對於RNN搜尋並不是那麼重要，然而螺旋曲線對於RNN搜尋有助於減少延遲時間(Latency)及查詢時間(Tuning Time)。最後我們對所有提出的作法皆進行大量的實驗模擬，而實驗結果符合我們的預期。

關鍵字

最近相鄰者(Nearest Neighbors) ；反向最近相鄰者(Reverse Nearest Neighbors) ； Quad-trees ；資料廣播； I/O次數；延遲時間(Latency) ；查詢時間(Tuning time) ；空間填充曲線(Space-filling Curves) ； Voronoi Diagram

並列摘要

With the emerging technologies on wireless communications, networking, and global positioning systems, people can access information any time any where and the Location Based Services (LBS) becomes more popular. In LBS,the reverse nearest neighbors(RNN) search is one of important information services. The RNN search is to determine a set of objects, in a given data set, where the query point is the nearest neighbor of each object respectively. There are many applications such as calling for taxis, despatching ambulances could use the RNN search. We refer to some related papers and propose efficient RNN query processes in various environments. First, we explore the RNN search when the query point and all objects are static. However, In real world all objects such as taxi and people continuously move at any time. Hence, dynamic objects and the query point are worthy to explore issue for RNN searches. Besides, Data broadcasting is an effective way to disseminate information to a large amount of mobile clients in wiarless mobile environments. Users only possess mobile devices could receive information by data broadcasting. RNN searches in the wireless mobile environment is also part of our discussion. In this paper, we have different measurements for various experiments. The computing time and number of I/Os are measured in the static environment. For the dynamic query and objects, we consider that the server does not continuously update when objects change its position. Therefore, update is as we measure in the dynamic environment. Finally, We explore how to execute the RNN search in wireless mobile environments and use different broadcasting schedules such as space-filling curves for our experiments. The result satisfies our expectation via great experiment simulation.

並列關鍵字

Nearest Neighbors ； Reverse Nearest Neighbors ； Space-filling Curves ； Data Broadcasting ； Number of I/Os ； Latency ； Tuning Time ； Voronoi Diagram, ； Quad-trees

參考文獻

[1] Baihua Zheng, Jianliang Xu, Wang-Chien Lee, and Dik Lun Lee. Grid-partition index: a hybrid method for nearest neighbor queries in wireless location-based services.The Very Large Data Bases Journal, 15(1):21–39, 2006.

[2] Yunjun Gao, Baihua Zheng,Wang-Chien Lee, and Gencai Chen. Continuous visible nearest neighbor queries. In EDBT ’09: Proceedings of the 12th International Conference

[4] Chuan-Ming Liu and Shu-Yu Fu. Effective protocols for knn search on broadcast multi-dimensional index trees. Information Systems, 33(1):18–35, 2008.

[5] Chuan-Ming Liu, Kai-Yun Ho, and Wei-Chih Yeh. A knn search protocol using a voronoi diagram in wireless broadcast environments. In Proceedings of the 2009

[6] Hanan Samet. K-nearest neighbor finding using maxnearestdist. IEEE Transactions on Pattern Analysis and Machine Intelligence, 30:243–252, 2008.

國際替代計量

在新興環境下對反向最近相鄰者搜尋之探討

全文下載

主題瀏覽