Conference Proceeding Article
In this paper, we study a novel form of continuous nearest neighbor queries in the presence of obstacles, namely continuous obstructed nearest neighbor (CONN) search. It considers the impact of obstacles on the distance between objects, which is ignored by most of spatial queries. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CONN query retrieves the nearest neighbor of each point on q according to the obstructed distance, i.e., the shortest path between them without crossing any obstacle. We formulate CONN search, analyze its unique properties, and develop algorithms for exact CONN query processing, assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle the CONN retrieval by performing a single query for the entire query segment, and only process the data points and obstacles relevant to the final result, via a novel concept of control points and an efficient quadratic-based split point computation algorithm. In addition, we extend our solution to handle the continuous obstructed k-nearest neighbor (COkNN) search, which finds the k (?1)nearest neighbors to every point along q based on obstructed distances. A comprehensive experimental evaluation using both real and synthetic datasets has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms.
continuous nearest neighbor, continuous obstructed nearest neighbor, nearest neighbor, obstacle, spatial database
Databases and Information Systems | Numerical Analysis and Scientific Computing
Data Management and Analytics
SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data: Providence, Rhode Island, USA, June 29-July 2, 2009
City or Country
GAO, Yunjun and ZHENG, Baihua.
Continuous Obstructed Nearest Neighbor Queries in Spatial Databases. (2009). SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data: Providence, Rhode Island, USA, June 29-July 2, 2009. 577-590. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/308
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.