Processing Continuous k Nearest Neighbor Queries in Obstructed Space with Voronoi Diagrams
| Autor: | Bin Wang, Jianliang Xu, Xiaochun Yang, Huaijie Zhu, Wang-Chien Lee, Jian Yin |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Traverse
Theoretical computer science Computer science Grid file 02 engineering and technology Grid Computer Science Applications k-nearest neighbors algorithm 020204 information systems Modeling and Simulation Signal Processing Location-based service Euclidean geometry 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Point (geometry) Geometry and Topology Voronoi diagram Information Systems |
| Zdroj: | ACM Transactions on Spatial Algorithms and Systems. 7:1-27 |
| ISSN: | 2374-0361 2374-0353 |
| Popis: | With the emergence and growing popularity of and location-based service (LBS) technologies, the continuous k nearest neighbor (CO k NN) query in obstructed space is becoming a very important service. In this article, we study the CO k NN in obstructed space, which retrieves k obstructed nearest neighbors (ONNs) for every point on a query segment q̄ . The state-of-the-art approach, called Euclidean based CONN (E-CONN), exploits an R-tree to traverse the dataset P in ascending order of their Euclidean distances to q̄ . Taking a different point of view, in this article, we explore the idea of Voronoi diagram to define the notion of obstructed Voronoi diagram (OVD) . The Voronoi cells with obstacles are divided into visible and invisible regions for quickly answering nearest neighbor queries. To facilitate efficient retrieval of Voronoi cells and processing of continuous nearest neighbor (CONN) queries, we propose a new grid-based index, called Voronoi diagram with Obstacles in Grid (VO-Grid) , which indexes Voronoi cells and associated obstacle information with a grid file. Based on VO-Grid, we propose an efficient algorithm, called CONN with VO-Grid Acceleration (CONN-VOA), to accelerate the CONN query processing. Moreover, we extend CONN-VOA to the CO k NN query, which also explores effective filtering and early termination for reducing redundant access of data objects. A comprehensive performance evaluation using both real and synthetic datasets is conducted to validate the proposed ideas and demonstrate the efficiency of our algorithms. The experimental results show that the CONN-VOA algorithm substantially outperforms E-CONN algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|