Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-2014

Abstract

Spatial queries such as range query and kNN query in road networks have received a growing number of attention in real life. Considering the large population of the users and the high overhead of network distance computation, it is extremely important to guarantee the efficiency and scalability of query processing. Motivated by the scalable and secure properties of wireless broadcast model, this paper presents an air index called Network Partition Index (NPI) to support efficient spatial query processing in road networks via wireless broadcast. The main idea is to partition the road network into a number of regions and then build the index to carry some pre-computation information of each region. We also propose multiple client-side algorithms to facilitate the processing of different spatial queries such as kNN query, range query and CNN query. A comprehensive experimental study has been conducted to demonstrate the efficiency of our scheme.

Keywords

Wireless data broadcast, kNN query, air indexing, road network

Discipline

Computer Sciences | Databases and Information Systems | Transportation

Publication

IEEE Transactions on Knowledge and Data Engineering (TKDE)

Volume

27

Issue

2

First Page

382

Last Page

395

ISSN

1041-4347

Identifier

10.1109/TKDE.2014.2330836

Publisher

IEEE

Additional URL

https://doi.org/10.1109/TKDE.2014.2330836

Download

Share

COinS