Continuous Visible Nearest Neighbor Query Processing in Spatial Databases

• Main Authors: GAO, Yunjun, ZHENG, Baihua, CHEN, Gencai, LI, Qing, GUO, Xiaofa
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2011
• Subjects: Query processing; Nearest neighbor; Visible; Spatial database; Algorithm; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/1406; https://ink.library.smu.edu.sg/context/sis_research/article/2405/viewcontent/VLDB_D_09_00032_V3__2_.pdf
• Institution: Singapore Management University

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CVNN query returns a set of $${\langle p, R\rangle}$$ tuples such that $${p \in P}$$ is the nearest neighbor to every point r along the interval $${R \subseteq q}$$ as well as pis visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R due to the obstruction of some obstacles in O. In contrast to existing continuous nearest neighbor query, CVNN retrieval considers the impact of obstacles on visibilitybetween objects, which is ignored by most of spatial queries. We formulate the problem, analyze its unique characteristics, and develop efficient algorithms for exact CVNN query processing. Our methods (1) utilize conventional data-partitioning indices (e.g., R-trees) on both P and O, (2) tackle the CVNN search by performing a single query for the entire query line segment, and (3) only access the data points and obstacles relevant to the final query result by employing a suite of effective pruning heuristics. In addition, several interesting variations of CVNN queries have been introduced, and they can be supported by our techniques, which further demonstrates the flexibility of the proposed algorithms. A comprehensive experimental evaluation using both real and synthetic data sets has been conducted to verify the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.