›› 2013, Vol. 28 ›› Issue (4): 585-596.doi: 10.1007/s11390-013-1359-8

Special Issue: Data Management and Data Mining; Computer Networks and Distributed Computing

• Special Section of EDB2012 • Previous Articles     Next Articles

k-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks

Hyeong-Il Kim1 and Jae-Woo Chang1,2   

  1. 1. Department of Computer Engineering, Chonbuk National University, Chonju 570-752, Korea;
    2. Cloud Open R&D Center, Chonbuk National University, Chonju 570-752, Korea
  • Received:2012-09-09 Revised:2013-05-06 Online:2013-07-05 Published:2013-07-05
  • Supported by:

    This research was supported by the Korea Institute of Science and Technology Information (KISTI). The preliminary version of the paper was published in the Proceedings of EDB2012.

Recent development of wireless communication technologies and the popularity of smart phones are making location-based services (LBS) popular. However, requesting queries to LBS servers with users' exact locations may threat the privacy of users. Therefore, there have been many researches on generating a cloaked query region for user privacy protection. Consequently, an efficient query processing algorithm for a query region is required. So, in this paper, we propose k-nearest neighbor query (k-NN) processing algorithms for a query region in road networks. To efficiently retrieve k-NN points of interest (POIs), we make use of the Island index. We also propose a method that generates an adaptive Island index to improve the query processing performance and storage usage. Finally, we show by our performance analysis that our k-NN query processing algorithms outperform the existing k-Range Nearest Neighbor (kRNN) algorithm in terms of network expansion cost and query processing time.

[1] Warrior J, McHenry E, McGee K. They know where you are.IEEE Spectrum, 2003, 40(7): 20-25.

[2] Voelcker J. Stalked by satellite: An alarming rise in GPS-enabled harassment. IEEE Spectrum, 2006, 43(7): 15-16.

[3] Mokbel M F, Chow C, ArefWG. The new casper: Query pro-cessing for location services without compromising privacy. InProc. the 32nd Int. Conf. Very Large Data Bases, Septem-ber 2006, pp. 763-774.

[4] Ghinita G, Kalnis P, Skiadopoulos S. MOBIHIDE: A mobileapeer-to-peer system for anonymous location-based queries. InProc. the 10th Int. Symposium on Advances in Spatial andTemporal Databases, July 2007, pp. 221-238.

[5] Kim H, Shin Y, Chang J. A grid-based cloaking scheme forcontinuous queries in distributed systems. In Proc. the 11thInt. Computer and Information Technology, August 2011,pp. 75-82.

[6] Lee H, Oh B, Kim H, Chang J. Grid-based cloaking area cre-ation scheme supporting continuous location-based services.In Proc. the 27th ACM Symposium on Applied Computing,March 2012, pp. 537-543.

[7] Ku W, Chen Y, Zimmermann R. Privacy protected spatialquery processing for advanced location based services. Wire-less Personal Communications, 2009, 51(1): 53-65.

[8] Bao J, Chow C, Mokbel M F, Ku W. Efficient evaluation ofk-range nearest neighbor queries in road networks. In Proc.the 11th Int. Conf. Mobile Data Management, May 2010,pp. 115-124.

[9] Huang X, Jensen C S, ? Sltenis S. The islands approach tonearest neighbor querying in spatial networks. In Proc. the9th Int. Symposium on Advances in Spatial and TemporalDatabases, August 2005, pp. 73-90.

[10] Wang T, Liu L. Privacy-aware mobile services over road net-works. PVLDB, 2009, 2(1): 1042-1053.

[11] Kalnis P, Ghinita G, Mouratidis K, Papadias D. Prevent-ing location-based identity inference in anonymous spatialqueries. IEEE Transactions on Knowledge and Data Engi-neering, 2007, 19(12): 1719-1733.

[12] Chow C, Mokbel M F, Naps J, Nath S. Approximate evalua-tion of range nearest neighbor queries with quality guarantee.In Proc. the 11th Int. Symposium on Advances in Spatialand Temporal Databases, July 2009, pp.283-301.

[13] Xu J, Tang X, Hu H, Du J. Privacy-conscious location-basedqueries in mobile environments. IEEE Transactions on Par-allel and Distributed Systems, 2010, 21(3): 313-326.

[14] Um J, Kim Y, Lee H, Jang M, Chang J. k-nearest neighborquery processing algorithm for cloaking regions towards userprivacy protection in location-based services. Journal of Sys-tems Architecture, 2012, 58(9): 354-371.

[15] Brinkhoff T. A framework for generating network-based mov-ing objects. GeoInformatica, 2002, 6(2): 153-180.
No related articles found!
Full text



[1] Liu Weiyi;. An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases[J]. , 1990, 5(3): 236 -240 .
[2] Ma Jun; Ma Shaohan;. An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph[J]. , 1994, 9(1): 86 -91 .
[3] Liao Xianzhi; Jin Lan;. Rendezvous Facilities in a Distributed Computer System[J]. , 1995, 10(2): 188 -192 .
[4] Chen Yiyun;. Head Boundedness of Nonterminating Rewritings[J]. , 1995, 10(3): 281 -284 .
[5] Fu Yuxi;. Reaction Graph[J]. , 1998, 13(6): 510 -530 .
[6] LI Xiaoshan;. Decidability of Mean Value Calculus[J]. , 1999, 14(2): 173 -180 .
[7] QI Yuesheng; WANG Baozhong; KANG Lishan;. Genetic Programming with Simple Loops[J]. , 1999, 14(4): 429 -433 .
[8] Cliff Reader. AVS Intellectual Property Rights (IPR) Policy[J]. , 2006, 21(3): 306 -309 .
[9] Wen Zheng, Jun-Hai Yong, and Jean-Claude Paul. Visual Simulation of Multiple Unmixable Fluids[J]. , 2007, 22(1): 156 -160 .
[10] Pierre Bourque, Serge Oligny, Alain Abran, and Bertrand Fournier. Developing Project Duration Models in Software Engineering[J]. , 2007, 22(3): 348 -357 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved