PRISM: indexing multi-dimensional data in P2P networks using reference vectors

ABSTRACT

Peer-to-peer (P2P) systems research has gained considerable attention recently with the increasing popularity of file sharing applications. Since these applications are used for sharing huge amounts of data, it is very important to efficiently locate the data of interest in such systems. However, these systems usually do not provide efficient search techniques. Existing systems offer only keyword search functionality through a centralized index or by query flooding. In this paper, we propose a scheme based on reference vectors for sharing multi-dimensional data in P2P systems. This scheme effectively supports a larger set of query operations (such as k-NN queries and content-based similarity search) than current systems, which generally support only exact key lookups and keyword searches.The basic idea is to store multiple replicas of an object's index at different peers based on the distances between the object's feature vector and the reference vectors. Later, when a query is posed, the system identifies the peers that are likely to store the index information about relevant objects using reference vectors. Thus the system is able to return accurate results by contacting a small fraction of the participating peers.

REFERENCES

• 1: Mayank Bawa , Gurmeet Singh Manku , Prabhakar Raghavan, SETS: search enhanced by topic segmentation, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860491]
• 2: Michael W. Berry , Zlatko Drmac , Elizabeth R. Jessup, Matrices, Vector Spaces, and Information Retrieval, SIAM Review, v.41 n.2, p.335-362, June 1999 [doi>10.1137/S0036144598347035]
• 3: Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502546]
• 4: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 5: Francisco Matias Cuenca-Acuna , Christopher Peery , Richard P. Martin , Thu D. Nguyen, PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC'03), p.236, June 22-24, 2003
• 6: S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science 41(6):391--407,1990.
• 7: S. El-Ansary, L. O. Alima, P. Brand, and S. Haridi. Efficient broadcast in structured p2p networks. In IPTPS pages 304--314,2003.
• 8: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 9: O. D. Gnawali. A eyword-set search system for peer-to-peer networks. Master 's thesis, Massachusetts Institute of Technology, 2002.
• 10: Gnutella. http://www.gnutella.com/.
• 11: I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Renesse. Kelips: Building an efficient and stable P2P DHT through increased memory and bac ground overhead. In IPTPS pages 160--169, 2003.
• 12: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 13: Panos Kalnis , Wee Siong Ng , Beng Chin Ooi , Kian-Lee Tan, Answering similarity queries in peer-to-peer networks, Information Systems, v.31 n.1, p.57-72, March 2006 [doi>10.1016/j.is.2004.09.003]
• 14: David R. Karger , Matthias Ruhl, Simple efficient load balancing algorithms for peer-to-peer systems, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007919]
• 15: J. Li, B. T. Loo, J. Hellerstein, F. Kaashoek, D. R. Karger, and R. Morris. On the feasibility of peer-to-peer web indexing and search. In IPTPS pages 207--215,2003.
• 16: Wolfgang Müller , Andreas Henrich, Fast retrieval of high-dimensional feature vectors in P2P networks using compact peer data summaries, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California [doi>10.1145/973264.973278]
• 17: Napster. http://www.napster.com/.
• 18: Till Quack , Ullrich Mönich , Lars Thiele , B. S. Manjunath, Cortina: a system for large-scale, content-based web image retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027650]
• 19: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 20: P. Reynolds and A. Vahdat. Efficient peer-to-peer keyword searching. In Middleware pages 21--40, 2003.
• 21: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 22: O. D. Sahin, F. Emekci, D. Agrawal, and A. E. Abbadi. Content-based similarity search over peer-to-peer systems. In DBISP2P pages 46--63,2004.
• 23: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 24: T. Suel, C. Mathur, J.-W. Wu, J. Zhang, A. Delis, M. Kharrazi, X. Long, and K. Shanmugasundaram. Odissea: A peer-to-peer architecture for scalable web search and information retrieval. In WebDB pages 67--72,2003.
• 25: C. Tang and S. Dwarkadas. Hybrid global-local indexing for efficient peer-to-peer information retrieval. In NSDI pages 211--224,2004.
• 26: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 27: Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002
• 28: B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A global-scale overlay for rapid service deployment. IEEE Journal on Selected Areas in Communications 22(1): 41--53,2004.
• 29: Yingwu Zhu , Honghao Wang , Yiming Hu, Integrating Semantics-Based Access Mechanisms with P2P File Systems, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.118, September 01-03, 2003

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Algorithms, Design, Experimentation

Keywords:
peer-to-peer systems, reference vectors, similarity search