Skip to main content
SpringerLink
Log in

Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks

  • Regular Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

In this paper, we study the problem of continuous monitoring of reverse k nearest neighbors queries in Euclidean space as well as in spatial networks. Existing techniques are sensitive toward objects and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor (RkNN) queries by assigning each object and query with a safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a byproduct, our framework also reduces the communication cost in client–server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis for our Euclidean space RkNN algorithm. We show that our techniques can also be applied to answer bichromatic RkNN queries in Euclidean space as well as in spatial networks. Furthermore, we show that our techniques can be extended for the spatial networks that are represented by directed graphs. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Benetis, R., Jensen, C.S., Karciauskas, G., Saltenis, S.: Nearest neighbor and reverse nearest neighbor queries for moving objects. In: IDEAS, pp. 44–53 (2002)

  2. Brinkhoff T.: A framework for generating network-based moving objects. GeoInformatica 6(2), 153–180 (2002)

    Article  MATH  Google Scholar 

  3. Cheema, M.A., Brankovic, L., Lin, X., Zhang, W., Wang, W.: Multi-guarded safe zone: an effective technique to monitor moving circular range queries. In: ICDE, pp. 189–200 (2010)

  4. Cheema, M.A., Brankovic, L., Lin, X., Zhang, W., Wang, W.: Continuous monitoring of distance based range queries. TKDE (2011)

  5. Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Influence zone: efficiently processing reverse k nearest neighbors queries. ICDE (2011)

  6. Cheema, M.A., Lin, X., Zhang, Y., Wang, W.: Lazy updates: an efficient technique to continuously monitoring reverse knn. In: UNSW technical report, 2009. Available at ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0905.pdf

  7. Cheema M.A., LinX. Zhang Y., Wang W., Zhang W.: Lazy updates: an efficient technique to continuously monitoring reverse knn. PVLDB 2(1), 1138–1149 (2009)

    Google Scholar 

  8. Chen, Y., Patel, J.M.: Efficient evaluation of all-nearest-neighbor queries. In: ICDE (2007)

  9. Chen, Z., Shen, H.T., Zhou, X., Yu, J.X.: Monitoring path nearest neighbor in road networks. In: SIGMOD Conference, pp. 591–602 (2009)

  10. Cho, H.-J., Chung, C.-W.: An efficient and scalable approach to cnn queries in a road network. In: VLDB, pp. 865–876 (2005)

  11. Gedik, B., Liu, L.: Mobieyes: distributed processing of continuously moving queries on moving objects in a mobile system. In: EDBT, pp. 67–87 (2004)

  12. Goldstein, J., Ramakrishnan, R., Shaft, U., Yu, J.-B.: Processing queries by linear constraints. In: PODS (1997)

  13. Hasan, M., Cheema, M.A., Lin, X., Zhang, Y.: Efficient construction of safe regions for moving knn queries over dynamic datasets. In: SSTD, pp. 373–379 (2009)

  14. Hasan, M., Cheema, M.A., Qu, W., Lin, X.: Efficient algorithms to monitor continuous constrained nearest neighbor queries. In: DASFAA (1), pp. 233–249 (2010)

  15. Hu, H., Xu, J., Lee, D.L.: A generic framework for monitoring continuous spatial queries over moving objects. In: SIGMOD conference, pp. 479–490 (2005)

  16. Iwerks, G.S., Samet, H., Smith, K.P.: Continuous k-nearest neighbor queries for continuously moving points with updates. In: VLDB, pp. 512–523 (2003)

  17. Jensen, C.S., Kolárvr, J., Pedersen, T.B., Timko, I.: Nearest neighbor queries in road networks. In: GIS, pp. 1–8 (2003)

  18. Kang, J.M., Mokbel, M.F., Shekhar, S., Xia, T., Zhang, D.: Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors. In: ICDE (2007)

  19. Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: VLDB, pp. 840–851 (2004)

  20. Kolahdouzan, M.R., Shahabi, C.: Continuous k-nearest neighbor queries in spatial network databases. In: STDBM, pp. 33–40 (2004)

  21. Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: SIGMOD (2000)

  22. Lazaridis, I., Porkaew, K., Mehrotra, S.: Dynamic queries over mobile objects. In: EDBT, pp. 269–286 (2002)

  23. Lin K.-I., Nolen M., Yang C.: Applying bulk insertion techniques for dynamic reverse nearest neighbor problems.. ideas. 00, 290 (2003)

    Google Scholar 

  24. Liu, F., Do, T.T., Hua, K.A.: Dynamic range query in spatial network environments. In: DEXA, pp. 254–265 (2006)

  25. Mouratidis, K., Hadjieleftheriou, M., Papadias, D.: Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring. In: SIGMOD (2005)

  26. Mouratidis, K., Papadias, D., Bakiras, S., Tao, Y.: A threshold-based algorithm for continuous monitoring of k nearest neighbors. TKDE, 1451–1464 (2005)

  27. Mouratidis, K., Yiu, M.L., Papadias, D., Mamoulis, N.: Continuous nearest neighbor monitoring in road networks. In: VLDB, pp. 43–54 (2006)

  28. Nutanong S., Zhang R., Tanin E., Kulik L.: The v*-diagram: a query-dependent approach to moving knn queries. PVLDB 1(1), 1095–1106 (2008)

    Google Scholar 

  29. Okabe A., Boots B., Sugihara K., Chiu S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, London (1999)

    Google Scholar 

  30. Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network databases. In: VLDB, pp. 802–813 (2003)

  31. Prabhakar S., Xia Y., Kalashnikov D.V., Aref W.G., Hambrusch S.E.: Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51(10), 1124–1140 (2002)

    Article  MathSciNet  Google Scholar 

  32. Safar M., Ebrahimi D., Taniar D.: Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimedia Syst. 15(5), 295–308 (2009)

    Article  Google Scholar 

  33. Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In: SIGMOD conference, pp. 43–54 (2008)

  34. Sankaranarayanan J., Samet H., Alborzi H.: Path oracles for spatial networks. PVLDB 2(1), 1210–1221 (2009)

    Google Scholar 

  35. Shahabi, C., Kolahdouzan, M.R., Sharifzadeh, M.: A road network embedding technique for k-nearest neighbor search in moving object databases. In: ACM-GIS, pp. 94–10 (2002)

  36. Shekhar, S., Yoo, J.S.: Processing in-route nearest neighbor queries: a comparison of alternative approaches. In: GIS, pp. 9–16 (2003)

  37. Singh, A., Ferhatosmanoglu, H., Tosun, A.S.: High dimensional reverse nearest neighbor queries. In: CIKM (2003)

  38. Song, Z., Roussopoulos, N.: K-nearest neighbor search for moving query point. In: SSTD, pp. 79–96 (2001)

  39. Stanoi, I., Agrawal, D., Abbadi, A.E.: Reverse nearest neighbor queries for dynamic databases. In: ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 44–53 (2000)

  40. Stojanovic D., Papadopoulos A.N., Predic B., Djordjevic-Kajan S., Nanopoulos A.: Continuous range monitoring of mobile objects in road networks. Data Knowl. Eng. 64(1), 77–100 (2008)

    Article  Google Scholar 

  41. Sun, H.-L., Jiang, C., Liu, J.-L., Sun, L.: Continuous reverse nearest neighbor queries on moving objects in road networks. In: WAIM, pp. 238–245 (2008)

  42. Tao, Y., Papadias, D., Lian, X.: Reverse knn search in arbitrary dimensionality. In: VLDB (2004)

  43. Tao, Y., Papadias, D., Shen, Q.: Continuous nearest neighbor search. In: VLDB, pp. 287–298 (2002)

  44. Tao, Y., Yiu, M.L., Mamoulis, N.: Reverse nearest neighbor search in metric spaces. TKDE 18(9) (2006)

  45. Tran Q.T., Taniar D., Safar M.: Reverse k nearest neighbor and reverse farthest neighbor search on spatial networks. Trans Large Scale Data Knowl. Cent. Syst. 1, 353–372 (2009)

    Article  Google Scholar 

  46. Wang, H., Zimmermann, R.: Snapshot location-based query processing on moving objects in road networks. In: GIS, p. 50 (2008)

  47. Wu, W., Yang, F., Chan, C.Y., Tan, K.-L.: Continuous reverse k-nearest-neighbor monitoring. In: MDM (2008)

  48. Wu, W., Yang, F., Chan, C.Y., Tan, K.-L.: Finch: Evaluating reverse k-nearest-neighbor queries on location data. In: VLDB (2008)

  49. Xia, T., Zhang, D.: Continuous reverse nearest neighbor monitoring. In: ICDE, p. 77 (2006)

  50. Xiong, X., Mokbel, M.F., Aref, W.G.: Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In: ICDE, pp. 643–654 (2005)

  51. Yang, C., Lin, K.-I.: An index structure for efficient reverse nearest neighbor queries. In: ICDE (2001)

  52. Yiu M.L., Mamoulis N.: Reverse nearest neighbors search in ad hoc subspaces. TKDE 19(3), 412–426 (2007)

    Google Scholar 

  53. Yiu, M.L., Papadias, D., Mamoulis, N., Tao, Y.: Reverse nearest neighbors in large graphs. In: ICDE (2005)

  54. Yu, X., Pu, K.Q., Koudas, N.: Monitoring k-nearest neighbor queries over moving objects. In: ICDE (2005)

  55. Zhang, J., Zhu, M., Papadias, D., Tao, Y., Lee, D.L.: Location-based spatial queries. In: SIGMOD Conference, pp. 443–454 (2003)

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, The University of New South Wales, Kensington, Australia

    Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin & Ying Zhang

  2. Software College, East China Normal University, Shanghai, China

    Xuemin Lin

  3. School of Computer Science, Fudan University, Shanghai, China

    Xuefei Li

Authors
  1. Muhammad Aamir Cheema
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wenjie Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xuemin Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ying Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xuefei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Muhammad Aamir Cheema.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cheema, M.A., Zhang, W., Lin, X. et al. Continuous reverse k nearest neighbors queries in Euclidean space and in spatial networks. The VLDB Journal 21, 69–95 (2012). https://doi.org/10.1007/s00778-011-0235-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-011-0235-9

Keywords

Search

Navigation