Processing Continuous k Nearest Neighbor Queries in Obstructed Space with Voronoi Diagrams

Huaijie Zhu, Xiaochun Yang, Bin Wang, Wang Chien Lee, Jian Yin, Jianliang Xu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


With the emergence and growing popularity of and location-based service (LBS) technologies, the continuous k nearest neighbor (COkNN) query in obstructed space is becoming a very important service. In this article, we study the COkNN in obstructed space, which retrieves k obstructed nearest neighbors (ONNs) for every point on a query segment qI.,. The state-of-the-art approach, called <monospace>Euclidean based CONN (E-CONN)</monospace>, exploits an R-tree to traverse the dataset P in ascending order of their Euclidean distances to qI.,. 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 <monospace>CONN with VO-Grid Acceleration (CONN-VOA)</monospace>, to accelerate the CONN query processing. Moreover, we extend <monospace>CONN-VOA</monospace> to the COkNN 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 <monospace>CONN-VOA</monospace> algorithm substantially outperforms <monospace>E-CONN</monospace> algorithm.

Original languageEnglish (US)
Article number3425955
JournalACM Transactions on Spatial Algorithms and Systems
Issue number2
StatePublished - Feb 2021

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Modeling and Simulation
  • Computer Science Applications
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Processing Continuous k Nearest Neighbor Queries in Obstructed Space with Voronoi Diagrams'. Together they form a unique fingerprint.

Cite this