Abstract
Given a query point Q, a Reverse Nearest Neighbor (RNN) Query returns all points in the database having Q as their nearest neighbor. The problem of RNN query has received much attention in a centralized database. However, not so much work has been done on this topic in the context of Peer-to-Peer (P2P) systems. In this paper, we shall do pioneering work on supporting distributed RNN query in large distributed and dynamic P2P networks. Our proposed RNN query algorithms are based on a distributed multi-dimensional index structure, called P2PRdNN-tree, which is relying on a super-peer-based P2P overlay. The results of our performance evaluation with real spatial data sets show that our proposed algorithms are indeed practically feasible for answering distributed RNN query in P2P systems.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Korn, F., Muthukrishnan, S.: Influence Sets Based on Reverse Nearest Neighbor Queries. In: SIGMOD (2000)
Yang, C., Lin, K.I.: An Index Structure for Efficient Reverse Nearest Neighbor Queries. In: ICDE (2001)
Stanoi, I., Agrawal, D., Abbadi, A.E.: Reverse Nearest Neighbor Queries for Dynamic Databases. In: SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (2000)
Stanoi, I., Riedewald, M., Agrawal, D., Abbadi, A.E.: Discovery of Influence Sets in Frequently Updated Databases. In: VLDB (2001)
Benetis, R., Jensen, C.S., Karciauskas, G., Saltenis, S.: Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. In: IDEAS (2002)
Korn, F., Muthukrishnan, S., Srivastava, D.: Reverse Nearest Neighbor Aggregates Over Data Streams. In: VLDB (2002)
Singh, A., Ferhatosmanoglu, H., Tosun, A.S.: High Dimensional Reverse Nearest Neighbor Queries. In: CIKM (2003)
Tao, Y., Papadias, D., Lian, X.: Reverse kNN Search in Arbitrary Dimensionality. In: VLDB (2004)
Xia, T., Zhang, D., Kanoulas, E., Du, Y.: On Computing Top-t Most Inuential Spatial Sites. In: VLDB (2005)
Yiu, M., Mamoulis, N.: Reverse Nearest Neighbors Search in Ad-hoc Subspaces. In: ICDE (2006)
Jagadish, H.V., Ooi, B.C., Vu, Q.H., Zhang, R., Zhou, A.: VBI-Tree: A Peer-to-Peer Framework for Supporting Multi-Dimensional Indexing Schemes. In: ICDE (2006)
Mondal, A., Yilifu, Y., Kitsuregawa, M.: P2PR-Tree: An R-Tree-Based Spatial Index for Peer-to-Peer Environments. In: Lindner, W., Mesiti, M., Türker, C., Tzitzikas, Y., Vakali, A.I. (eds.) EDBT 2004. LNCS, vol. 3268, pp. 516–525. Springer, Heidelberg (2004)
Demirbas, M., Ferhatosmanoglu, H.: Peer-to-peer spatial queries in sensor networks. In: P2P (2003)
Tang, C., Xu, Z., Dwarkadas, S.: Peer-to-peer information retrieval using self-organizing semantic overlay networks. In: SIGCOMM (2003)
Lee, J., Lee, H., Kang, S., Choe, S., Song, J.: CISS: An efficient object clustering framework for DHT-based peer-to-peer applications. In: Ng, W.S., Ooi, B.-C., Ouksel, A.M., Sartori, C. (eds.) DBISP2P 2004. LNCS, vol. 3367, pp. 215–229. Springer, Heidelberg (2005)
Zhang, C., Krishnamurthy, A., Wang, R.Y.: Skipindex: Towards a scalable peer-to-peer index service for high dimensional data. Technical report, Princeton University (2004)
Shu, Y., Tan, K.-L., Zhou, A.: Adapting the content native space for load balanced indexing. In: Ng, W.S., Ooi, B.-C., Ouksel, A.M., Sartori, C. (eds.) DBISP2P 2004. LNCS, vol. 3367, pp. 122–135. Springer, Heidelberg (2005)
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: ACM SIGMOD International Conference on Management of Data (1984)
Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-Tree: An efficient and robust access method for points and rectangles. In: ACM SIGMOD International Conference on Management of Data (1990)
Sellis, T., Roussopoulos, N., Faloutsos, C.: The R+-tree: A dynamic index for multi-dimensional objects. In: VLDB (1987)
Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: ACM Annual Conference of the Special Interest Group on Data Communication (2001)
Bentley, J.L.: Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9), 509–517 (1975)
Hinrichs, K., Nievergelt, J.: The grid file: A data structure designed to support proximity queries on spatial objects. In: Proceedings of the International Workshop on Graphtheoretic Concepts in Computer Science (1983)
Berchtold, S., Keim, D.A., Kriegel, H.-P.: The X-tree: An index structure for high-dimensional data. In: VLDB (1996)
White, D.A., Jain, R.: Similarity indexing with the SStree. In: ICDE (1996)
Ciaccia, P., Patella, M., Zezula, P.: M-tree: An efficient access method for similarity search in metric spaces. In: VLDB (1997)
Sahin, O.D., Gupta, A., Agrawal, D., El Abbadi, A.: A peer-to-peer framework for caching range queries. In: ICDE (2004)
Aspnes, J., Shah, G.: Skip graphs. In: Annual ACM-SIAM Symposium on Discrete Algorithms (2003)
Schlosser, M., Sintek, M., Decker, S., Nejdl, W.: HyperCup-Hypercubes, Ontologies and efficient search on P2P networks. In: International workshop on agents and peer-to-peer computing (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, D., Zhou, J., Le, J. (2006). Reverse Nearest Neighbor Search in Peer-to-Peer Systems. In: Larsen, H.L., Pasi, G., Ortiz-Arroyo, D., Andreasen, T., Christiansen, H. (eds) Flexible Query Answering Systems. FQAS 2006. Lecture Notes in Computer Science(), vol 4027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11766254_8
Download citation
DOI: https://doi.org/10.1007/11766254_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34638-8
Online ISBN: 978-3-540-34639-5
eBook Packages: Computer ScienceComputer Science (R0)