Abstract
Given a set of users U, a set of facilities F, and a query facility q, a reverse nearest neighbors (RNN) query retrieves every user u for which q is its closest facility. Since q is the closest facility of u, the user u is said to be influenced by q. In this paper, we propose a relaxed definition of influence where a user u is said to be influenced by not only its closest facility but also every other facility that is almost as close to u as its closest facility is. Based on this definition of influence, we propose relaxed reverse nearest neighbors (RRNN) queries. Formally, given a value of \(x>1\), an RRNN query q returns every user u for which \(dist(u,q) \le x\times NNDist(u)\) where NNDist(u) denotes the distance between a user u and its nearest facility. Based on effective pruning techniques and several non-trivial observations, we propose an efficient RRNN query processing algorithm. Our extensive experimental study conducted on several real and synthetic data sets demonstrates that our algorithm is several orders of magnitude better than a naïve algorithm as well as a significantly improved version of the naïve algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: SIGMOD, pp. 201–212 (2000)
Stanoi, I., Agrawal, D., Abbadi, A.E.: Reverse nearest neighbor queries for dynamic databases. In: ACM SIGMOD Workshop, pp. 44–53 (2000)
Cheema, M.A., Lin, X., Wang, W., Zhang, W., Pei, J.: Probabilistic reverse nearest neighbor queries on uncertain data. IEEE Trans. Knowl. Data Eng. 22, 550–564 (2010)
Stanoi, I., Riedewald, M., Agrawal, D., Abbadi, A.E.: Discovery of influence sets in frequently updated databases. In: PVLDB, pp. 99–108 (2001)
Tao, Y., Papadias, D., Lian, X.: Reverse knn search in arbitrary dimensionality. In: PVLDB, pp. 744–755 (2004)
Yang, S., Cheema, M.A., Lin, X., Wang, W.: Reverse k nearest neighbors query processing: experiments and analysis. In: PVLDB, pp. 605–616 (2015)
Wu, W., Yang, F., Chan, C.Y., Tan, K.L.: FINCH: evaluating reverse k-nearest-neighbor queries on location data. In: PVLDB, pp. 1056–1067 (2008)
Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Influence zone: efficiently processing reverse k nearest neighbors queries. In: ICDE, pp. 577–588 (2011)
Cheema, M.A., Zhang, W., Lin, X., Zhang, Y., Li, X.: Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. VLDB J. 21, 69–95 (2012)
Yang, S., Cheema, M.A., Lin, X., Zhang, Y.: SLICE: reviving regions-based pruning for reverse k nearest neighbors queries. In: ICDE, pp. 760–771 (2014)
Vlachou, A., Doulkeridis, C., Kotidis, Y., Nørvåg, K.: Reverse top-k queries. In: ICDE, pp. 365–376 (2010)
Cheema, M.A., Shen, Z., Lin, X., Zhang, W.: A unified framework for efficiently processing ranking related queries. In: EDBT, pp. 427–438 (2014)
Beckmann, N., Kriegel, H., Schneider, R., Seeger, B.: The r*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, 23–25 May, pp. 322–331 (1990)
Emrich, T., Kriegel, H.-P., Kröger, P., Renz, M., Züfle, A.: Incremental reverse nearest neighbor ranking in vector spaces. In: Mamoulis, N., Seidl, T., Pedersen, T.B., Torp, K., Assent, I. (eds.) SSTD 2009. LNCS, vol. 5644, pp. 265–282. Springer, Heidelberg (2009)
Singh, A., Ferhatosmanoglu, H., Tosun, A.S.: High dimensional reverse nearest neighbor queries. In: CIKM (2003)
Achtert, E., Kriegel, H.P., Kröger, P., Renz, M., Züfle, A.: Reverse k-nearest neighbor search in dynamic and general metric databases. In: EDBT, pp. 886–897 (2009)
Sharifzadeh, M., Shahabi, C.: Vor-tree: R-trees with voronoi diagrams for efficient processing of spatial nearest neighbor queries. PVLDB 3(1), 1231–1242 (2010)
Cheema, M.A., Lin, X., Zhang, Y., Wang, W., Zhang, W.: Lazy updates: an efficient technique to continuously monitoring reverse knn. In: PVLDB, pp. 1138–1149 (2009)
Bernecker, T., Emrich, T., Kriegel, H.P., Renz, M., Züfle, S.Z.A.: Efficient probabilistic reverse nearest neighbor query processing on uncertain data. In: PVLDB, pp. 669–680 (2011)
Wu, W., Yang, F., Chan, C.Y., Tan, K.L.: Continuous reverse k-nearest-neighbor monitoring. In: MDM, pp. 132–139 (2008)
Cheema, M.A., Zhang, W., Lin, X., Zhang, Y.: Efficiently processing snapshot and continuous reverse k nearest neighbors queries. VLDB J. 21(5), 703–728 (2012)
Taniar, D., Rahayu, W.: A taxonomy for nearest neighbour queries in spatial databases. J. Comput. Syst. Sci. 79(7), 1017–1039 (2013)
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)
Cheema, M.A., Brankovic, L., Lin, X., Zhang, W., Wang, W.: Continuous monitoring of distance-based range queries. IEEE Trans. Knowl. Data Eng. 23(8), 1182–1199 (2011)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction to Algorithms, vol. 2. MIT Press, Cambridge (2001)
Acknowledgments
The research of Muhammad Aamir Cheema is supported by ARC DE130101002 and DP130103405.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Hidayat, A., Cheema, M.A., Taniar, D. (2015). Relaxed Reverse Nearest Neighbors Queries. In: Claramunt, C., et al. Advances in Spatial and Temporal Databases. SSTD 2015. Lecture Notes in Computer Science(), vol 9239. Springer, Cham. https://doi.org/10.1007/978-3-319-22363-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-22363-6_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-22362-9
Online ISBN: 978-3-319-22363-6
eBook Packages: Computer ScienceComputer Science (R0)