Abstract
A reverse nearest neighbour (RNN) query returns every object for which the query is its nearest neighbour. Recently, a new useful variant of the RNN query has emerged, called reverse nearest neighbourhood (RNNH) query, to discover the neighbourhood that find query point is the nearest facilities among all other fa- cilities. However, the existing research focuses on computing RNNH in Euclidean space and, to the best of our knowledge, there does not exist any technique to compute RNNH in road networks. The existing techniques designed for Euclidean space cannot be applied for road networks mainly because all objects and facilities of interest are connected on a road network. Thus, there is a need for techniques specifically designed for computing RNNH in road networks. In this paper, we introduce the reverse nearest neighbourhood concept for road networks (RNNH-RN) where a neighbourhood is a collection of at least m chained objects such that the maximum road network distance between any pair of objects is at most d. We demonstrate the flexibility and effectiveness of the proposed RNNH-RN query through extensive experiments based on real-world, road network data for Melbourne, Victoria. Our experimental results demonstrate that our solutions are feasible for networks with low, medium or high levels of object density.
Similar content being viewed by others
Notes
It should be noted that there could be zero or more reverse nearest neighbourhoods of a query facility q in a given dataset P ∪ F as opposed to the nearest neighbourhood
References
Abeywickrama, T., Cheema, M.A., Taniar, D.: K-nearest neighbors on road networks: a journey in experimentation and in-memory implementation. arXiv:1601.01549 (2016)
Achtert, E., Böhm, C., Kröger, P., Kunath, P., Pryakhin, A., Renz, M.: Efficient reverse k-nearest neighbor search in arbitrary metric spaces. In: Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pp. 515–526 (2006)
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. ACM (2009)
Allheeib, N., Islam, M.S., Taniar, D., Shao, Z., Cheema, M.A.: Density-based reverse nearest neighbourhood search in spatial databases. J. Ambient Intell. Human. Comput. 1–12 (2018)
Allheeib, N., Taniar, D., Al-Khalidi, H., Islam, M.S., Adhinugraha, K.M.: Safe regions for moving reverse neighbourhood queries in a peer-to-peer environment. IEEE Access 8, 50285–50298 (2020)
Bernecker, T., Emrich, T., Kriegel, H.P., Renz, M., Zankl, S., Züfle, A.: Efficient probabilistic reverse nearest neighbor query processing on uncertain data. PVLDB 4(10), 669–680 (2011)
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)
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(4), 550–564 (2010)
Cheema, M. A., Lin, X., Zhang, Y., Wang, W., Zhang, W.: Lazy updates: An efficient technique to continuously monitoring reverse knn. PVLDB 2 (1), 1138–1149 (2009)
Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Influence zone: Efficiently processing reverse k nearest neighbors queries. In: ICDE, pp 577–588. IEEE (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(1), 69–95 (2012)
Choi, D.W., Chung, C.W.: Nearest neighborhood search in spatial databases. In: ICDE, pp 699–710. IEEE (2015)
Dellis, E., Seeger, B.: Efficient computation of reverse skyline queries. In: VLDB, vol. 7, pp 291–302 (2007)
Deng, K., Sadiq, S., Zhou, X., Xu, H., Fung, G.P.C., Lu, Y.: On group nearest group query processing. IEEE Trans. Knowl. Data Eng. 24 (2), 295–308 (2010)
Emrich, T., Franzke, M., Mamoulis, N., Renz, M., Züfle, A.: Geo-social skyline queries. In: DASFAA, pp 77–91. Springer (2014)
Emrich, T., Kriegel, H.P., Kröger, P., Renz, M., Züfle, A.: Incremental reverse nearest neighbor ranking in vector spaces. In: SSTD, pp 265–282. Springer (2009)
Gao, Y., Liu, Q., Miao, X., Yang, J.: Reverse k-nearest neighbor search in the presence of obstacles. Inform. Sci. 330, 274–292 (2016)
Gao, Y., Miao, X., Chen, G., Zheng, B., Cai, D., Cui, H.: On efficiently finding reverse k-nearest neighbors over uncertain graphs. VLDB J. 26(4), 467–492 (2017)
Gao, Y., Qin, X., Zheng, B., Chen, G.: Efficient reverse top-k boolean spatial keyword queries on road networks. Ieee Trans. Knowl. Data Eng. 27(5), 1205–1218 (2014)
Gonzalez, H., Han, J., Li, X., Myslinska, M., Sondag, J.P.: Adaptive fastest path computation on a road network: a traffic mining approach. In: 33rd International Conference on Very Large Data Bases, VLDB 2007, pp 794–805. Association for Computing Machinery, Inc (2007)
Haidar, A.K., Taniar, D., Safar, M.: Approximate algorithms for static and continuous range queries in mobile navigation. Computing 95(10-11), 949–976 (2013)
Hidayat, A., Cheema, M.A., Lin, X., Zhang, W., Zhang, Y.: Continuous monitoring of moving skyline and top-k queries. The VLDB Journal (2021)
Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. (CSUR) 40(4), 1–58 (2008)
Korn, F., Muthukrishnan, S.: Influence sets based on reverse nearest neighbor queries. In: ACM SIGMOD Record, vol. 29, pp 201–212. ACM (2000)
Lee, K.C., Lee, W.C., Zheng, B.: Fast object search on road networks. In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pp. 1018–1029 (2009)
Lee, K.C., Lee, W.C., Zheng, B., Tian, Y.: Road: A new spatial object search framework for road networks. IEEE Trans. Knowl. Data Eng. 24 (3), 547–560 (2010)
Li, H., Lu, H., Huang, B., Huang, Z.: Two ellipse-based pruning methods for group nearest neighbor queries. In: Proceedings of the 13th annual ACM international workshop on Geographic information systems, pp. 192–199 (2005)
Li, L., Zhang, M., Hua, W., Zhou, X.: Fast query decomposition for batch shortest path processing in road networks. In: 2020 IEEE 36th International Conference on Data Engineering (ICDE), pp 1189–1200. IEEE (2020)
Li, X., Hidayat, A., Taniar, D., Cheema, M.A.: Reverse approximate nearest neighbor queries on road network. World Wide Web 1–18 (2020)
Li, F., Yao, B., Kumar, P.: Group enclosing queries. IEEE Trans. Knowl. Data Eng. 23(10), 1526–1540 (2010)
Papadias, D., Shen, Q., Tao, Y., Mouratidis, K.: Group nearest neighbor queries. In: Proceedings. 20th International Conference on Data Engineering, pp 301–312. IEEE (2004)
Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: ACM Sigmod Record, vol. 24, pp 71–79. ACM (1995)
Safar, M., Ibrahimi, D., Taniar, D.: Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimed. Syst. 15(5), 295–308 (2009)
Shang, S., Yuan, B., Deng, K., Xie, K., Zhou, X.: Finding the most accessible locations: reverse path nearest neighbor query in road networks. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 181–190 (2011)
Shen, Z., Cheema, M.A., Lin, X., Zhang, W., Wang, H.: A generic framework for top-k pairs and top-k objects queries over sliding windows. IEEE Trans. Knowl. Data Eng. 26(6), 1349–1366 (2012)
Singh, A., Ferhatosmanoglu, H., Tosun, A.Ş.: High dimensional reverse nearest neighbor queries. In: CIKM, pp 91–98. ACM (2003)
Stanoi, I., Agrawal, D., El Abbadi, A.: Reverse nearest neighbor queries for dynamic databases. In: ACM SIGMOD workshop on research issues in data mining and knowledge discovery, pp. 44–53 (2000)
Stanoi, I., Riedewald, M., Agrawal, D., El Abbadi, A.: Discovery of influence sets in frequently updated databases. In: VLDB, vol. 2001, pp 99–108 (2001)
Taniar, D., Safar, M., Tran, Q.T., Rahayu, W., Park, J.H.: Spatial network rnn queries in gis. Comput. J. 54(4), 617–627 (2011)
Tao, Y., Papadias, D., Lian, X.: Reverse knn search in arbitrary dimensionality. In: VLDB, vol. 30, pp 744–755. VLDB Endowment (2004)
Tran, Q.T., Taniar, D., Safar, M.: Reverse k nearest neighbor and reverse farthest neighbor search on spatial networks. In: Transactions on large-scale data-and knowledge-centered systems I, pp 353–372. Springer (2009)
Tran, Q.T., Taniar, D., Safar, M.: Bichromatic reverse nearest-neighbor search in mobile systems. IEEE Syst. J. 4(2), 230–242 (2010)
Vlachou, A., Doulkeridis, C., Kotidis, Y., Nørvåg, K.: Reverse top-k queries. In: 365–376, p IEEE (2010)
Wu, W., Yang, F., Chan, C.Y., Tan, K.L.: Finch: Evaluating reverse k-nearest-neighbor queries on location data. PVLDB 1(1), 1056–1067 (2008)
Xu, X.J., Bao, J.S., Yao, B., Zhou, J.Y., Tang, F.L., Guo, M.Y., Xu, J.Q.: Reverse furthest neighbors query in road networks. J. Comput. Sci. Technol. 32(1), 155–167 (2017)
Xuan, K., Zhao, G., Taniar, D., Rahayu, W., Safar, M., Srinivasan, B.: Voronoi-based range and continuous range query processing in mobile databases. J. Comput. Syst. Sci. 77(4), 637–651 (2011)
Xuan, K., Zhao, G., Taniar, D., Srinivasan, B., Safar, M., Gavrilova, M.: Network voronoi diagram based range search. In: 2009 International Conference on Advanced Information Networking and Applications, pp 741–748. IEEE (2009)
Yang, S., Cheema, M.A., Lin, X., Wang, W.: Reverse k nearest neighbors query processing: experiments and analysis. PVLDB 8(5), 605–616 (2015)
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. IEEE (2014)
Yang, S., Cheema, M.A., Lin, X., Zhang, Y., Zhang, W.: Reverse k nearest neighbors queries and spatial reverse top-k queries. The VLDB J. 26(2), 151–176 (2017)
Yiu, M.L., Papadias, D., Mamoulis, N., Tao, Y.: Reverse nearest neighbors in large graphs. IEEE Trans. Knowl. Data Eng. 18(4), 540–553 (2006)
Zhang, M., Li, L., Hua, W., Zhou, X.: Efficient batch processing of shortest path queries in road networks. In: 2019 20th IEEE International Conference on Mobile Data Management (MDM), pp 100–105. IEEE (2019)
Zhao, J., Gao, Y., Chen, G., Jensen, C.S., Chen, R., Cai, D.: Reverse top-k geo-social keyword queries in road networks. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp 387–398. IEEE (2017)
Zhao, G., Xuan, K., Rahayu, W., Taniar, D., Safar, M., Gavrilova, M.L., Srinivasan, B.: Voronoi-based continuous k nearest neighbor search in mobile navigation. IEEE Trans. Ind. Electron. 58(6), 2247–2257 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Allheeib, N., Adhinugraha, K., Taniar, D. et al. Computing reverse nearest neighbourhood on road maps. World Wide Web 25, 99–130 (2022). https://doi.org/10.1007/s11280-021-00969-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11280-021-00969-1