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 journalJournal articlepeer-review

1 Citation (Scopus)


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
Article number8
Number of pages27
JournalACM Transactions on Spatial Algorithms and Systems
Issue number2
Early online date8 Dec 2020
Publication statusPublished - Feb 2021

Scopus Subject Areas

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

User-Defined Keywords

  • Location-based services
  • nearest neighbor queries
  • obstructed space
  • spatial query processing


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