Paper Info
Title
Searching continuous nearest neighbors in road networks on the air
Abstract
Recently, people have begun to deal with location-based queries (LBQs) under broadcast environments. To the best of our knowledge, most of the existing broadcast-based LBQ methods are aimed at Euclidean spaces and cannot be readily extended to road networks. This paper takes the first step toward processing Continuous Nearest Neighbor queries in road Networks under wireless Broadcast environments (CN^3B). Our method leverages the key properties of Network Voronoi Diagram (NVD). We first present an efficient method to partition the NVD structure of the underlying road networks into a set of grid cells and number the grid cells obtained, based on which we further propose an NVD-based Distributed air Index (NVD-DI) to support CN^3B query processing. Finally, we propose an efficient algorithm on the client side to process CN^3B queries. Extensive simulation experiments have been conducted to demonstrate the efficiency of our approach. The results show that our proposed method is about 4 and 7.6 times more efficient than a less-sophisticated D-tree air index based method, in access latency and tuning time, respectively.
Year
DOI
Venue
2014
10.1016/j.is.2014.01.003
Inf. Syst.
Keywords
Field
DocType
continuous nearest neighbor,road network,nvd structure,existing broadcast-based lbq method,grid cell,efficient method,air index,road networks,efficient algorithm,underlying road network
k-nearest neighbors algorithm,Client-side,Data mining,Broadcasting,Road networks,Latency (engineering),Computer science,Theoretical computer science,Voronoi diagram,Euclidean geometry,Partition (number theory),Database
Journal
Volume
ISSN
Citations 
42,
0306-4379
8
PageRank 
References 
Authors
0.45
22
6
Name
Order
Citations
PageRank
Yanhong Li16010.94
Jianjun Li27314.05
Lihchyun Shu313017.32
Qing Li43222433.87
Li Guohui544776.53
Fumin Yang6284.73