Peer-to-peer information retrieval using self-organizing semantic overlay networks

ABSTRACT

Content-based full-text search is a challenging problem in Peer-to-Peer (P2P) systems. Traditional approaches have either been centralized or use flooding to ensure accuracy of the results returned.In this paper, we present pSearch, a decentralized non-flooding P2P information retrieval system. pSearch distributes document indices through the P2P network based on document semantics generated by Latent Semantic Indexing (LSI). The search cost (in terms of different nodes searched and data transmitted) for a given query is thereby reduced, since the indices of semantically related documents are likely to be co located in the network.We also describe techniques that help distribute the indices more evenly across the nodes, and further reduce the number of nodes accessed using appropriate index distribution as well as using index samples and recently processed queries to guide the search.Experiments show that pSearch can achieve performance comparable to centralized information retrieval systems by searching only a small number of nodes. For a system with 128,000 nodes and 528,543 documents (from news, magazines, etc.), pSearch searches only 19 nodes and transmits only 95.5KB data during the search, whereas the top 15 documents returned by pSearch and LSI have a 91.7% intersection.

REFERENCES

• 1: 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]
• 2: Chris Buckley, Implementation of the SMART Information Retrieval System, Cornell University, Ithaca, NY, 1985
• 3: E. Cohen, A. Fiat, and H. Kaplan. Associative Search in Peer to Peer Networks: Harnessing Latent Semantics. In IEEE INFOCOM'03, April 2003.
• 4: Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: 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
• 6: Francisco Matias Cuenca-Acuna , Thu D. Nguyen, Text-Based Content Search and Retrieval in Ad-hoc P2P Communities, Revised Papers from the NETWORKING 2002 Workshops on Web Engineering and Peer-to-Peer Computing, p.220-234, May 19-24, 2002
• 7: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by Latent Semantic Analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 8: S. Dumais. Using LSI for information filtering: TREC-3 experiments. In the Third Text REtrieval Conference (TREC3), 1995.
• 9: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 10: FastTrack. http://www.fasttrack.nu.
• 11: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 12: George Karypis , Eui-Hong (Sam) Han, Fast supervised dimensionality reduction algorithm with applications to document categorization & retrieval, Proceedings of the ninth international conference on Information and knowledge management, p.12-19, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354772]
• 13: R. Lempel and S. Moran. Optimizing Result Prefetching in Web Search Engines with Segmented Indices. In VLDB'01, 2001.
• 14: Todd A. Letsche , Michael W. Berry, Large-scale information retrieval with latent semantic indexing, Information Sciences: an International Journal, v.100 n.1-4, p.105-137, Aug. 1997 [doi>10.1016/S0020-0255(97)00044-3]
• 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'03, February 2003.
• 16: Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
• 17: C. D. Prete, J. T. McArthur, R. L. Villars, I. L. Nathan Redmond, and D. Reinsel. Industry developments and models, Disruptive Innovation in Enterprise Computing: storage. IDC, February 2003.
• 18: Prabhakar Raghavan, Information retrieval algorithms: a survey, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.11-18, January 05-07, 1997, New Orleans, Louisiana, United States
• 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: S. Rhea and J. Kubiatowicz. Probabilistic Location and Routing. In IEEE INFOCOM'02, June 2002.
• 21: M. Schwartz. A Scalable, Non-Hierarchical Resource Discovery Mechanism Based on Probabilistic Protocols. Technical Report CU-CS-474-90, University of Colorado, 1990.
• 22: Kunwadee Sripanidkulchai , Bruce Maggs , Hui Zhang, Enabling efficient content location and retrieval in peer-to-peer systems by exploiting locality in interests, ACM SIGCOMM Computer Communication Review, v.32 n.1, January 2002 [doi>10.1145/510726.510754]
• 23: SVDPACK. http://www.netlib.org/svdpack.
• 24: C. Tang, Z. Xu, and M. Mahalingam. pSearch: Information Retrieval in Structured Overlays. In HotNets-I, October 2002. Expanded version available as HP technical report HPL-2002-198, "PeerSearch: Efficient Information Retrieval in Peer- to-Peer Networks".
• 25: Text Retrieval Conference (TREC). http://trec.nist.gov.
• 26: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 27: Zhichen Xu , Chunqiang Tang , Zheng Zhang, Building Topology-Aware Overlays Using Global Soft-State, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.500, May 19-22, 2003
• 28: J. D. Zakis and Z. J. Pudlowski. The World Wide Web as Universal Medium for Scholarly Publication, Information Retrieval and Interchange. Global Journal of Engineering Education, 1(3), 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Design, Experimentation, Management, Performance

Keywords:
information retrieval, overlay network, peer-to-peer system