Searching continuous nearest neighbors in road networks on the air

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

16 Scopus Citations
View graph of relations

Author(s)

  • Yanhong Li
  • Jianjun Li
  • Lihchyun Shu
  • Guohui Li
  • Fumin Yang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)177-194
Journal / PublicationInformation Systems
Volume42
Online published22 Jan 2014
Publication statusPublished - Jun 2014

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 (CN3B). 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 CN3B 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. © 2014 Elsevier Ltd.

Research Area(s)

  • CN3B, CNN queries, Road networks, Wireless broadcast

Citation Format(s)

Searching continuous nearest neighbors in road networks on the air. / Li, Yanhong; Li, Jianjun; Shu, Lihchyun; Li, Qing; Li, Guohui; Yang, Fumin.

In: Information Systems, Vol. 42, 06.2014, p. 177-194.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review