Probabilistic file indexing and searching in unstructured peer-to-peer networks

ABSTRACT

Thanks to the advance of network and computing technology, Peer-to-Peer (P2P) has become a popular way for file sharing. A huge amount of files can now be directly accessed and downloaded by a simple mouse click. Among the types of P2P networks, unstructured architecture has been proven quite successful, mainly due to its simplicity and robustness. However, searching for distant and rare files is still a challenging problem in unstructured P2P networks. Existing approaches either have poor response time, or generate too much network traffic.In this paper we propose a simple, practical, yet powerful index scheme to enhance search in unstructured P2P networks. The index scheme uses a data structure "Bloom filters" to index files shared at each node, and then lets nodes gossip to one another to exchange their Bloom filters. In effect, each node indexes a random set of files in the network, thereby allowing every query to have a constant probability to be successfully resolved within a fixed search space. The experimental results show that our approach can improve the search in Gnutella by an order of magnitude. For example, in a typical Gnutella network consisting of about 89,000 nodes, by replicating a node's Bloom filter to less than 0.45% of the nodes in the network, 70% of the queries can be resolved within a search space of 200 nodes. In contrast, within the same search space size, only 1.6% of the queries can be resolved without the index scheme; or, alternatively, more than 48,000 nodes need to be searched in Gnutella in order to reach the same success rate as our index scheme.

REFERENCES

• 1: {1} L.A. Adamic, R.M. Lukose, A.R. Puniyani, B.A. Huberman, Search in power-law networks, Physical Review E 64 (4) (2001) 046135.
• 2: {2} E. Adar, B.A. Huberman, Free riding on Gnutella, First Monday, 5(10), October 2000. Available from: 〈http:// firstmonday.org/issues/issue5_10/adar/index.html〉.
• 3: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 4: {4} I. Clarke, O. Sandberg, B. Wiley, T.W. Hong, Freenet: a distributed anonymous information storage and retrieval system, in: Proceedings of the 2000 International Workshop on Design Issues in Anonymity and Unobservability (DIAU 2000)Lecture Notes in Computer Science, vol. 2009, Springer-Verlag, 2001, pp. 41-66.
• 5: {5} CNN, Available from: 〈http://www.cnn.com/2001/tech} internet/06/28napster .usage/〉.
• 6: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
• 7: 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
• 8: {8} Gnutella, Available from: 〈http://www.gnutella.com〉.
• 9: {9} M.A. Jovanovic, F.S. Annexstein, K.A. Berman, Scalability issues in large peer-to-peer networks--a case study of Gnutella, Technical report, University of Cincinnati, 2001.
• 10: Vana Kalogeraki , Dimitrios Gunopulos , D. Zeinalipour-Yazti, A local search mechanism for peer-to-peer networks, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584842]
• 11: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 12: {12} R. Mahajan, M. Castro, A. Rowstron, Controlling the cost of reliability in peer-to-peer overlays, in: Proceedings of Second International Workshop on Peer-to-Peer Systems (IPTPS 2003)Lecture Notes in Computer Science, vol. 2735, Springer-Verlag, 2003, pp. 21-32.
• 13: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: Universal Topology Generation from a User''s Perspective, Boston University, Boston, MA, 2001
• 14: {14} Napster, Available from: 〈http://www.napster.com〉.
• 15: {15} Sharman Networks. KaZaA, Retrieved July 27, 2004 from 〈http://www.kazaa.com〉.
• 16: Murali Krishna Ramanathan , Vana Kalogeraki , Jim Pruyne, Finding Good Peers in Peer-to-Peer Networks, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.158, April 15-19, 2002
• 17: 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
• 18: {18} P. Reynolds, A. Vahdat, Efficient peer-to-peer keyword searching, in: Proceedings of the 2003 ACM/IFIP/USE-NIX International Middleware Conference (Middleware 2003), Lecture Notes in Computer Science, vol. 2672, Springer-Verlag, 2003, pp. 21-40.
• 19: {19} S. Rhea, J. Kubiatowicz, Probabilistic location and routing, in: Proceedings of Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), vol. 3, pp. 1248-1257, June 2002.
• 20: M. Ripeanu, [15] Peer-to-Peer Architecture Case Study: Gnutella Network, Proceedings of the First International Conference on Peer-to-Peer Computing (P2P'01), p.99, August 27-29, 2001
• 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: {22} S. Saroiu, P. Krishna Gummadi, S.D. Gribble, A measurement study of peer-to-peer file sharing systems, in: Proceedings of the 2002 Multimedia Computing and Networking (MMCN 2002), The International Society of Optical Engineering, January 2002.
• 23: {23} K. Sripanidkulchai, Bruce, H. Zhang, Efficient content location using interest-based locality in peer-to-peer systems, in: Proceedings of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), vol. 3, pp. 216-2176, March/ April 2003.
• 24: 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
• 25: {25} Web Traces and Logs. Available from: 〈http://www.web-caching.com/traces-logs.html〉.
• 26: 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
• 27: {27} B.Y. Zhao, L. Huang, S.C. Rhea, J. Stribling, A.D Joseph, J.D. Kubiatowicz, Tapestry: a resilient global-scale overlay for service deployment, IEEE Journal on Selected Areas in Communications 22 (1) (2004) 1-15, Special Issue on Service Overlay Networks.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Design, Performance, Theory

Keywords:
Gnutella, P2P file sharing, bloom filter, file search, keyword search, probabilistic file indexing, unstructured peer-to-peer network