Improving collection selection with overlap awareness in P2P search engines

ABSTRACT

Collection selection has been a research issue for years. Typically, in related work, precomputed statistics are employed in order to estimate the expected result quality of each collection, and subsequently the collections are ranked accordingly. Our thesis is that this simple approach is insufficient for several applications in which the collections typically overlap. This is the case, for example, for the collections built by autonomous peers crawling the web. We argue for the extension of existing quality measures using estimators of mutual overlap among collections and present experiments in which this combination outperforms CORI, a popular approach based on quality estimation. We outline our prototype implementation of a P2P web search engine, coined MINERVA, that allows handling large amounts of data in a distributed and self-organizing manner. We conduct experiments which show that taking overlap into account during collection selection can drastically decrease the number of collections that have to be contacted in order to reach a satisfactory level of recall, which is a great step toward the feasibility of distributed web search.

REFERENCES

• 1: Karl Aberer , Magdalena Punceva , Manfred Hauswirth , Roman Schmidt, Improving Data Access in P2P Systems, IEEE Internet Computing, v.6 n.1, p.58-67, January 2002 [doi>10.1109/4236.978370]
• 2: 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]
• 3: E. Buchmann and K. Böhm. How to Run Experiments with Large Peer-to-Peer Data Structures. In Proceedings of the 18th International Parallel and Distributed Processing Symposium, Santa Fe, USA, Apr. 2004.
• 4: John Byers , Jeffrey Considine , Michael Mitzenmacher , Stanislav Rost, Informed content delivery across adaptive overlay networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 5: J. Callan. Distributed information retrieval. Advances in information retrieval, Kluwer Academic Publishers., pages 127--150, 2000.
• 6: 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]
• 7: Soumen Chakrabarti, Mining the Web: Discovering Knowledge from HyperText Data, Science & Technology Books, 2002
• 8: F. M. Cuenca-Acuna, C. Peery, R. P. Martin, and T. D. Nguyen. PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities. Technical Report DCS-TR-487, Rutgers University, Sept. 2002.
• 9: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 10: Daniela Florescu , Daphne Koller , Alon Y. Levy, Using Probabilistic Information in Data Integration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.216-225, August 25-29, 1997
• 11: Norbert Fuhr, A decision-theoretic approach to database selection in networked IR, ACM Transactions on Information Systems (TOIS), v.17 n.3, p.229-249, July 1999 [doi>10.1145/314516.314517]
• 12: Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872790]
• 13: Torsten Grabs , Klemens Böhm , Hans-Jörg Schek, PowerDB-IR: information retrieval on top of a database cluster, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502655]
• 14: 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]
• 15: Thomas Hernandez , Subbarao Kambhampati, Improving text collection selection with coverage and overlap statistics, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062902]
• 16: Sergey Melink , Sriram Raghavan , Beverly Yang , Hector Garcia-Molina, Building a distributed full-text index for the web, ACM Transactions on Information Systems (TOIS), v.19 n.3, p.217-241, July 2001 [doi>10.1145/502115.502116]
• 17: Michael Mitzenmacher, Compressed bloom filters, IEEE/ACM Transactions on Networking (TON), v.10 n.5, p.604-612, October 2002 [doi>10.1109/TNET.2002.803864]
• 18: Z. Nie, S. Kambhampati, and T. Hernandez. Bibfinder/statminer: Effectively mining and using coverage and overlap statistics in data integration. In VLDB, pages 1097--1100, 2003.
• 19: Henrik Nottelmann , Norbert Fuhr, Evaluating different methods of estimating retrieval quality for resource selection, 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.860489]
• 20: 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
• 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: 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]
• 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. Wu, J. Zhang, A. Delis, M. Kharrazi, X. Long, and K. Shanmugasunderam. Odissea: A peer-to-peer architecture for scalable web search and information retrieval. Technical report, Polytechnic Univ., 2003.
• 25: Text REtrieval Conference (TREC). http://trec.nist.gov/.
• 26: Y. Wang, L. Galanis, and D. J. de Witt. Galanx: An efficient peer-to-peer search engine system. Available at http://www.cs.wisc.edu/~yuanwang.
• 27: 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]
• 28: Yi Zhang , Jamie Callan , Thomas Minka, Novelty and redundancy detection in adaptive filtering, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564393]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Selection process
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
distributed IR, overlap estimation, peer-to-peer information systems, query routing