鄰近密集區域查詢之研究

Abstract

近年來，隨著智慧型裝置的崛起以及行動網路的普及，地理位置服務 (Location Based Service LBS) 因其所提供的便利性而急速成長，各種有趣的 spatial query 及應用相繼被提出。 在本篇論文中，我們著眼於 Nearest Dense Window Query (NDW) 的研究， NDW 是一種針對資料密集程度的查詢，使用者可以輸入一個查詢點、欲返回的區域大小以及希望的資料數量門檻， NDW 會回傳最靠近查詢點且符合給定大小的區域，並且該區域內含的資料點數大於等於給定的資料數量門檻，因為查詢結果須符合給定的資料密度，因此稱做 dense window 。 我們研究了原有的 NDW 演算法，發現其兩個加速機制 (SRR & DIP) 在地圖上的資料點較稀疏時容易產生 worst case 而失去效用，因此我們另外提出了兩個新的加速機制 (IWP & DEP)：分別在 memory 中額外儲存少量的資訊，不但可以克服原 NDW 演算法的弱點，更可以增加執行效率，從實驗結果得知，在不考慮原 NDW 演算法遇到 worst case 的情況下，我們提出的方法最多可以減少 89.3% 的執行時間。 另一方面，為了提供多樣化的查詢結果，我們將原有的 NDW 演算法擴充成為 kNDW(k-Nearest Dense Window Query)，以查詢地圖上符合條件的最近的 k 個 dense window ，讓使用者可以依照喜好從這些結果中做選擇。 同時我們也擴充了 NDW 中對於 distance metric 的定義，讓 NDW 和 kNDW 都可以有更廣泛的應用。

Recently, thanks to the ubiquity of mobile device and growth of wireless network, location based services (LBS) are growing vigorously. For the reason above, various interesting spatial queries and applications are proposed. In this paper, we focus on the study of Nearest Dense Window Query (NDW). An NDW query retrives a nearest dense window of specified size containing at least specified number of objects. However, we found that the two optimized techniques (SRR and DIP) of the original NDW algorithm are weak against sparse datasets. To overcome this problem, we proposed two optimize techniques called IWP and DEP. With a few memory overhead, the proposed method can easily prevent from the worst case of SRR and DIP. Moreover, even not in worst cases, the experiment result shows that by combining the 4 optimized techniques, the NDW alogrithm can reduce at most 89.3% I/O overhead from accessing R-tree index. In addition, To offer more flexible queries, we extend NDW to kNDW which can be used to retrive k nearest dense windows. Finally, to adopt to general usage, we extend the distance metric of NDW.