Searching continuous nearest neighbors in road networks on the air

Yanhong Li, Jianjun Li, Lih-Chyun Shu, Qing Li, Guohui Li, Fumin Yang

Research output: Contribution to journalArticle

14 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)177-194
Number of pages18
JournalInformation Systems
Volume42
DOIs
Publication statusPublished - 2014 Jun 1

Fingerprint

Query processing
Air
Tuning
Processing
Experiments

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture

Cite this

Li, Yanhong ; Li, Jianjun ; Shu, Lih-Chyun ; Li, Qing ; Li, Guohui ; Yang, Fumin. / Searching continuous nearest neighbors in road networks on the air. In: Information Systems. 2014 ; Vol. 42. pp. 177-194.
@article{4b8bfe43d65e4ac188fd4dcf863433bd,
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 (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.",
author = "Yanhong Li and Jianjun Li and Lih-Chyun Shu and Qing Li and Guohui Li and Fumin Yang",
year = "2014",
month = "6",
day = "1",
doi = "10.1016/j.is.2014.01.003",
language = "English",
volume = "42",
pages = "177--194",
journal = "Information Systems",
issn = "0306-4379",
publisher = "Elsevier Limited",

}

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

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

Research output: Contribution to journalArticle

TY - JOUR

T1 - Searching continuous nearest neighbors in road networks on the air

AU - Li, Yanhong

AU - Li, Jianjun

AU - Shu, Lih-Chyun

AU - Li, Qing

AU - Li, Guohui

AU - Yang, Fumin

PY - 2014/6/1

Y1 - 2014/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893820411&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893820411&partnerID=8YFLogxK

U2 - 10.1016/j.is.2014.01.003

DO - 10.1016/j.is.2014.01.003

M3 - Article

VL - 42

SP - 177

EP - 194

JO - Information Systems

JF - Information Systems

SN - 0306-4379

ER -