SETS: search enhanced by topic segmentation

ABSTRACT

We present SETS, an architecture for efficient search in peer-to-peer networks, building upon ideas drawn from machine learning and social network theory. The key idea is to arrange participating sites in a topic-segmented overlay topology in which most connections are short-distance, connecting pairs of sites with similar content. Topically focused sets of sites are then joined together into a single network by long-distance links. Queries are matched and routed to only the topically closest regions. We discuss a variety of design issues and tradeoffs that an implementor of SETS would face. We show that SETS is efficient in network traffic and query processing load.

REFERENCES

• 1: Daniel Barbará , Chris Clifton, Information Brokers: Sharing Knowledge in a Heterogeneous Distributed System, Proceedings of the 4th International Conference on Database and Expert Systems Applications, p.80-91, September 06-08, 1993
• 2: C. Mic Bowman , Peter B. Danzig , Darren R. Hardy , Udi Manber , Michael F. Schwartz, The Harvest information discovery and access system, Computer Networks and ISDN Systems, v.28 n.1-2, p.119-125, Dec. 1995 [doi>10.1016/0169-7552(95)00098-5 ]
• 3: Brendon Cahoon , Kathryn S. McKinley, Performance evaluation of a distributed architecture for information retrieval, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.110-118, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243238]
• 4: J. Callan. Distributed information retrieval. Advances in Information Retrieval, pages 127--150, 2000.
• 5: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 6: Citeseer: Scientific literature digital library (http://citeseer.nj.nec.com/cs).
• 7: E. Cohen, H. Kaplan, and A. Fiat. Associative search in peer-to-peer networks: Harnessing latent semantics. In Proc. IEEE Infocom, 2003.
• 8: J. G. Conrad, X. S. Guo, P. Jackson, and M. Meziou. Database selection using actual physical and acquired logical collection resources in a massive domain-specific operational environment. In Proc. 28th Conf. on Very Large Data Bases (VLDB), pages 71--82, 2002.
• 9: 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
• 10: Peter B. Danzig , Jongsuk Ahn , John Noll , Katia Obraczka, Distributed indexing: a scalable mechanism for distributed information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.220-229, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122883]
• 11: S. Feld. Social structural determinants of similarity among associates. In American Sociological Review (47), 1982.
• 12: James C. French , Allison L. Powell , Jamie Callan , Charles L. Viles , Travis Emmitt , Kevin J. Prey , Yun Mou, Comparing the performance of database selection algorithms, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.238-245, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312684]
• 13: Susan Gauch , Jianying Wang, A corpus analysis approach for automatic query expansion, Proceedings of the sixth international conference on Information and knowledge management, p.278-284, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266910]
• 14: M. S. Granovetter. The strength of weak ties: A network theory revisited. In Sociological Theory (1), 1983.
• 15: 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]
• 16: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 17: Gurmeet Singh Manku, Routing networks for distributed hash tables, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.133-142, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872054]
• 18: G. S. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS), pages 127--140, 2003.
• 19: S. Milgram. The small world problem. In Psychology Today 1(67), 1967.
• 20: S. Milliner, M. Papazoglou, and H. Weigand. Linguistic tool based information elicitation in large heterogeneous database networks. In Proc. Workshop on Natural Language and Databases (NLDB), 1996.
• 21: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 22: C. H. Ng and K. C. Sia. Peer clustering and firework query model. In Poster in 11th Conf. on World Wide Web (WWW), 2002.
• 23: J. J. Ordille and B. P. Miller. Distributed active catalogs and meta-data caching in descriptive name services. In Proc. Conf. on Distributed Computing Systems (ICDCS), pages 120--129, 1993.
• 24: Mike P. Papazoglou , Henderik A. Proper , Jian Yang, Landscaping the information space of large multi-database networks, Data & Knowledge Engineering, v.36 n.3, p.251-281, March 2001 [doi>10.1016/S0169-023X(00)00050-1 ]
• 25: 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
• 26: Hinrich Schütze , Craig Silverstein, Projections for efficient document clustering, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-81, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 27: Mark A. Sheldon , Andrzej Duda , Ron Weiss , James W. O'Toole, Jr. , David K. Gifford, Content routing for distributed information servers, Proceedings of the 4th international conference on extending database technology on Advances in database technology, p.109-122, May 1994, Cambridge, United Kingdom
• 28: Luo Si , Rong Jin , Jamie Callan , Paul Ogilvie, A language modeling framework for resource selection and results merging, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584856]
• 29: P. Simpson, Query processing in a heterogeneous retrieval network, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.359-370, May 1988, Grenoble, France [doi>10.1145/62437.62475]
• 30: 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
• 31: C. Tang, Z. Xu, and M. Mahalingam. Peersearch: Efficient information retrieval in peer-to-peer networks. In HotNets-I, 2002.
• 32: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 33: Charles L. Viles , James C. French, Dissemination of collection wide information in a distributed information retrieval system, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.12-20, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215327]
• 34: Ellen M. Voorhees , Narendra K. Gupta , Ben Johnson-Laird, Learning collection fusion strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-179, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215357]
• 35: Ron Weiss , Bienvenido Vélez , Mark A. Sheldon, HyPursuit: a hierarchical network search engine that exploits content-link hypertext clustering, Proceedings of the the seventh ACM conference on Hypertext, p.180-193, March 16-20, 1996, Bethesda, Maryland, United States [doi>10.1145/234828.234846]
• 36: Jinxi Xu , Jamie Callan, Effective retrieval with distributed collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.112-120, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290974]
• 37: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 38: 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

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Selection process
      H.3.4 Systems and Software
          Subjects: Distributed systems; Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Performance

Keywords:
distributed information retrieval, peer-to-peer (P2P), small world networks, topic segments, topic-driven query routing