No Access

A Safe-Region Approach to a Moving k-RNN Queries in a Directed Road Network

Kamil Zeberga

Department of Software, Ajou University, Worldcupro 206, Yeongtong-gu, Suwon 16499, Republic of Korea

E-mail Address: kamil@ajou.ac.kr

Search for more papers by this author

Rize Jin

Department of Software, Ajou University, Worldcupro 206, Yeongtong-gu, Suwon 16499, Republic of Korea

E-mail Address: rizejin@ajou.ac.kr

Search for more papers by this author

Hyung-Ju Cho

Department of Software, Kyungpook National University, Gyeongsang-daero 2559, Sangju-si, Gyeongsangbuk-do 37224, Republic of Korea

E-mail Address: hyungju@knu.ac.kr

Search for more papers by this author

, and

Tae-Sun Chung

Department of Software, Ajou University, Worldcupro 206, Yeongtong-gu, Suwon 16499, Republic of Korea

E-mail Address: tschung@ajou.ac.kr

Search for more papers by this author

https://doi.org/10.1142/S0218126617500712Cited by:9 (Source: Crossref)

Abstract

In road networks, $k$ $k$ -range nearest neighbor ( $k$ $k$ -RNN) queries locate the $k$ $k$ -closest neighbors for every point on the road segments, within a given query region defined by the user, based on the network distance. This is an important task because the user's location information may be inaccurate; furthermore, users may be unwilling to reveal their exact location for privacy reasons. Therefore, under this type of specific situation, the server returns candidate objects for every point on the road segments and the client evaluates and chooses exact $k$ $k$ nearest objects from the candidate objects. Evaluating the query results at each timestamp to keep the freshness of the query answer, while the query object is moving, will create significant computation burden for the client. We therefore propose an efficient approach called a safe-region-based approach (SRA) for computing a safe segment region and the safe exit points of a moving nearest neighbor (NN) query in a road network. SRA avoids evaluation of candidate answers returned by the location-based server since it will have high computation cost in the query side. Additionally, we applied SRA for a directed road network, where each road network has a particular orientation and the network distances are not symmetric. Our experimental results demonstrate that SRA significantly outperforms a conventional solution in terms of both computational and communication costs.

This paper was recommended by Regional Editor Tongquan Wei.

Keywords:

References

1. J. Bao, C.-Y. Chow, M. F. Mokbel and W. Ku, Efficient evaluation of k-range nearest neighbor queries in road networks, Proc. 11th Int. Conf. Mobile Data Management (2010), Kanas City, Missouri, USA, 23–26 May 2010. IEEE Computer Society, pp. 115–124. Google Scholar
2. C.-Y. Chow, M. F. Mokbel, J. Naps and S. Nath, Approximate evaluation of range nearest neighbor queries with quality guarantee, Proc. 11th Symp. Advances in Spatial and Temporal Databases (2009), Aalborg, Denmark, July 8–10, 2009, Springer, Berlin Heidelberg, pp. 283–301. Google Scholar
3. B. Zheng, J. Xu, W.-C. Lee and D. L. Lee, Grid-partition index: A hybrid method for nearest-neighbor queries in wireless location-based services, VLDB J. 15, (2006), pp. 21–39. Crossref, Web of Science, Google Scholar
4. D. Papadias, J. Zhang, N. Mamoulis and Y. Tao, Query processing in spatial network databases, Proc. 29th Int. Conf. VLDB (2003), Berlin, Germany, September 09–12, 2003, VLDB Endowment, pp. 802–813. Google Scholar
5. U. Demiryurek, F. B. Kashani and C. Shahabi, Efficient continuous nearest neighbor query in spatial networks using Euclidean restriction, Proc. 11th Symp. Advances in Spatial and Temporal Databases (2009), Aalborg, Denmark, July 8–10, 2009, Springer, Berlin Heidelberg, pp. 25–43. Google Scholar
6. H. Hu, D. L. Lee and J. Xu, Fast nearest neighbor search on road networks, Proc. 10th International Conference on Extending Database Technology, Munich, Germany, March 26–31, 2006, pp. 186–203. Google Scholar
7. T. de Almeida and R. H. Güting, Supporting uncertainty in moving objects in network databases, Proc. 13th Int. Workshop on, GIS (ACM, Berlin, Germany, 2005), pp. 31–40. Google Scholar
8. D. Pfoser and C. S. Jensen, Capturing the uncertainty of moving-object representations, Proc. 6th Int. Symp. Advances in Spacial Database, SSD (Springer, Berlin, 1999), pp. 111–132. Google Scholar
9. M. L. Yiu, N. Mamoulis, X. Dai, Y. Tao and M. Vaitis, Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data, IEEE Trans. Knowl. Data Eng. 21 (2009) 108–122. Crossref, Web of Science, Google Scholar
10. Y. Cai and T. Xu, Design, analysis, and implementation of a large-scale real-time location-based information sharing system, Proc. 6th International Conference on Mobile Systems, Applications, and Services (2008), Breckenridge, CO, USA, June 17–20, 2008, pp. 106–117. Google Scholar
11. O. Wolfson, H. Cao, H. Lin, G. Trajcevski, F. Zhang and N. Rishe, Management of dynamic location information in domino, Proc. 8th International Conference on Extending Database Technology: Advances in Database Technology (2002), Prague, Czech Republic, March 25–27, 2002, pp. 769–771. Google Scholar
12. K. Mouratidis and M. L. Yiu, Anonymous query processing in road networks, IEEE Trans. Knowl. Data Eng. 22 (2010) 2–15. Crossref, Web of Science, Google Scholar
13. W.-S. Ku, Y. Chen and R. Zimmermann, Privacy protected spatial query processing for advanced location based services, Wirel. Personal Commun. 51 (2009) 53–65. Crossref, Web of Science, Google Scholar
14. J. Bao, H. Chen and W.-S. Ku, Pros: A peer-to-peer system for location privacy protection on road networks, Proc. 17th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (2009), Seattle, Washington, USA, November 4–6, 2009, pp. 552–553. Google Scholar
15. T. Wang and L. Liu, Privacy-aware mobile services over road networks, Proc. VLDB Endowment, Vol. 2 (2009) pp. 1042–1053. Google Scholar
16. H. Cho, R. Jin and T. Chung, A collaborative approach to moving $k$ $k$ -nearest neighbor queries in directed and dynamic road networks, Pervasive and Mobile Computing 17 (2015) 139–156. Crossref, Web of Science, Google Scholar
17. S. Papadopoulos, S. Bakiras and D. Papadias, Nearest Neighbor Search with Strong Location Privacy, Proc. VLDB Endowment 3 (2010) 619–629. Crossref, Google Scholar
18. Y. Gao, B. Zheng, G. Chen, Q. Li and X. Guo, Continuous visible nearest neighbor query processing in spatial databases, VLDB J. 20 (2011) 371–396. Crossref, Web of Science, Google Scholar
19. M. Hasan, M. Cheema, W. Qu and X. Lin, Efficient algorithms to monitor continuous constrained k nearest neighbor queries, Database Systems for Advanced Applications Vol. 5981 (2010), Springer Berlin Heidelberg, pp. 233–249. Google Scholar
20. Y. Tao and D. Papadias, Time-parameterized queries in spatio-temporal databases, Proc. of ACM SIGMOD International Conference on Management of Data (2002), Madison, Wisconsin, June 03–06, 2002, pp. 334–345. Google Scholar
21. Y. Tao, D. Papadias and Q. Shen, Continuous nearest neighbor search, Proc. 28th Int. Conf. VLDB (2002), Hong Kong, China, August 20–23, 2002, VLDB Endowment, pp. 287–298. Google Scholar
22. Z. Chen, H. Shen, X. Zhou and J. Yu, Monitoring path nearest neighbor in road networks, Proc. of ACM SIGMOD International Conference on Management of Data (2009), Providence, Rhode Island, USA, June 29–July 02, 2009, pp. 591–602. Google Scholar
23. H. Cho and C. Chung, An efficient scalable approach to CNN queries in a road network, Proc. 31th Int. Conf. VLDB (2005), Trondheim, Norway, August 30–September 02, 2005, VLDB Endowment, pp. 865–876. Google Scholar
24. M. Kolahdouzan and C. Shahabi, Voronoi-based K nearest neighbor search for spatial network databases, Proc. 30th Int. Conf. VLDB (2004), Toronto, Canada, August 31–September 03, 2004, VLDB Endowment, pp. 840–851. Google Scholar
25. D. Papadias, J. Zhang, N. Mamoulis and Y. Tao, Query processing in spatial network databases, Proc. 29th Int. Conf. VLDB (2003), Berlin, Germany, September 09–12, 2003, VLDB Endowment, pp. 802–813. Google Scholar
26. E. Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959) 269–271. Crossref, Google Scholar
27. H. Samet, J. Sankaranarayanan and H. Alborzi, Scalable network distance browsing in spatial databases, SIGMOD (2008), pp. 43–54. Google Scholar
28. D. Yung, M. Yiu and E. Lo, A safe-exit approach for efficient network-based moving range queries, Data Knowl. Eng. 72 (2012) 126–147. Crossref, Web of Science, Google Scholar
29. A. R. Beresford and F. Stajano, Mix zones: User privacy in location-aware services, Proc. of IEEE Annual Conference on Pervasive Computing and Communications Workshops (2004), Orlando, Florida, USA, 14–17 March 2004, IEEE Computer Society, pp. 127–131. Google Scholar
30. M. Gruteser and D. Grunwald, Anonymous usage of location-based services through spatial and temporal cloaking, Proc. International Conference on Mobile Systems, Applications and Services (2003), San Francisco, California, USA, May 05–08, 2003, pp. 31–42. Google Scholar