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.
Wireless data broadcast, kNN query, air indexing, road network
Computer Sciences | Databases and Information Systems | Transportation
Data Management and Analytics
IEEE Transactions on Knowledge and Data Engineering (TKDE)
SUN, Weiwei; CHEN, Chunan; ZHENG, Baihua; CHEN, Chong; and LIU, Peng.
An Air Index for Proximity Query Processing in Road Networks. (2015). IEEE Transactions on Knowledge and Data Engineering (TKDE). 27, (2), 382-395. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/2454
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.