鄰近密集區域查詢之研究

A Study of Nearest Dense Window Query

梁從慶(Tsung-Ching Liang)

指導教授 ： 黃俊龍

國立交通大學/資訊學院/網路工程研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00838

摘要

近年來，隨著智慧型裝置的崛起以及行動網路的普及，地理位置服務 (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.

並列關鍵字

nearest dense window query ； spatial query processing ； location-based service ； spatial database

參考文獻

[1] A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proceedings

and robust access method for points and rectangles,” in Proceedings of the 1990

[4] N. Roussopoulos, S. Kelley, and F. Vincent, “Nearest neighbor queries,” SIGMOD

[5] G. R. Hjaltason and H. Samet, “Distance browsing in spatial databases,” ACM Trans.

Database Syst., vol. 24, pp. 265–318, June 1999.