TY - JOUR
T1 - Processing Continuous k Nearest Neighbor Queries in Obstructed Space with Voronoi Diagrams
AU - Zhu, Huaijie
AU - Yang, Xiaochun
AU - Wang, Bin
AU - Lee, Wang Chien
AU - Yin, Jian
AU - Xu, Jianliang
N1 - Funding Information:
This work is partially supported by the NSF of China under grant No. 61902438, 61532021ï¼U1736104, the Fundamental Research Funds for the Central Universities (No. N171602003), the Postdoctoral fund (2018M643307), Young Teacher Training Project of Sun Yat-sen University under Grant 19lgpy214, and the Natural Science Foundation of Guangdong Province under Grant 2019A1515011704. Jianliang Xu’s work is supported by RGC GRF Project 12200817 and Guangdong Basic and Applied Basic Research Foundation (2019B1515130001). Authors’ addresses: H. Zhu, Sun Yat-Sen University, School of Computer Science and Engineering and Northeastern University, China; email: [email protected]; X. Yang and B. Wang, The Department of Computer Science at North-eastern University, China; emails: {yangxc, bwang}@mail.neu.edu.cn; W.-C. Lee, The Computer Science and Engineering, Penn State University; email: [email protected]; J. Yin, Sun Yat-Sen University, China; email: [email protected]; J. Xu, The Department of Computer Science, School of Computer Science and Engineering, Hong Kong Baptist University; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2020 Association for Computing Machinery. 2374-0353/2020/12-ART8 $15.00 https://doi.org/10.1145/3425955
PY - 2021/2
Y1 - 2021/2
N2 - 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 Euclidean based CONN (E-CONN), 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 CONN with VO-Grid Acceleration (CONN-VOA), to accelerate the CONN query processing. Moreover, we extend CONN-VOA 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 CONN-VOA algorithm substantially outperforms E-CONN algorithm.
AB - 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 Euclidean based CONN (E-CONN), 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 CONN with VO-Grid Acceleration (CONN-VOA), to accelerate the CONN query processing. Moreover, we extend CONN-VOA 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 CONN-VOA algorithm substantially outperforms E-CONN algorithm.
KW - Location-based services
KW - nearest neighbor queries
KW - obstructed space
KW - spatial query processing
UR - http://www.scopus.com/inward/record.url?scp=85100837334&partnerID=8YFLogxK
U2 - 10.1145/3425955
DO - 10.1145/3425955
M3 - Journal article
AN - SCOPUS:85100837334
SN - 2374-0353
VL - 7
JO - ACM Transactions on Spatial Algorithms and Systems
JF - ACM Transactions on Spatial Algorithms and Systems
IS - 2
M1 - 8
ER -