Diverse peer selection in collaborative web search

ABSTRACT

Effective peer selection for intelligent query routing is a challenge in collaborative peer-based Web search systems, especially unstructured networks that do not have any centralized control of peer document collections. In particular, routing a query to multiple peers that provide the same results is a waste of resources. To deal with overlapping document collections we propose a diverse peer selection approach for adaptive query routing. This approach takes into account not only which neighbors are the best resource providers for a given query, but also which combinations of neighbors can provide the least redundant results. We validate the feasibility of our proposed algorithm by presenting several simulation experiments conducted with different configurations of peer network environments. Two novel evaluation measures, distributed precision and distributed recall, are also introduced to provide an effective comparison of different peer network systems. These two performance measures extend the well known IR measures of precision and recall by integrating network costs, namely bandwidth and latency. Our algorithm finds results of equivalent quality using less time and generating less traffic in the presence of varying amounts of document duplication.

REFERENCES

• 1: R. Akavipat , L.-S. Wu , F. Menczer , A.G. Maguitman, Emerging semantic communities in peer web search, Proceedings of the international workshop on Information retrieval in peer-to-peer networks, November 11-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183579.1183581]
• 2: Mayank Bawa , Roberto J. Bayardo, Jr. , Sridhar Rajagopalan , Eugene J. Shekita, Make it fresh, make it quick: searching a network of personal webservers, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775234]
• 3: Matthias Bender , Sebastian Michel , Peter Triantafillou , Gerhard Weikum , Christian Zimmer, Improving collection selection with overlap awareness in P2P search engines, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076049]
• 4: 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]
• 5: A. Crespo and H. Garcia-Molina. Semantic overlay networks for P2P systems. Technical report, Computer Science Department, Stanford University, 2002.
• 6: P. Haase, R. Siebes, and F. van Harmelen. Peer selection in peer-to-peer networks with semantic topologies. In ICSNW, pages 108--125, 2004.
• 7: 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]
• 8: Sam Joseph, NeuroGrid: Semantically Routing Queries in Peer-to-Peer Networks, Revised Papers from the NETWORKING 2002 Workshops on Web Engineering and Peer-to-Peer Computing, p.202-214, May 19-24, 2002
• 9: I. A. Klampanos, V. Poznański, J. M. Jose, and P. Dickman. A suite of testbeds for the realistic evaluation of peer-to-peer information retrieval systems. Lecture Notes in Computer Science, 3408:38--51, 2005.
• 10: Joon Ho Lee, Analyses of multiple evidence combination, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.267-276, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 11: Jie Lu , Jamie Callan, Content-based retrieval in hybrid peer-to-peer networks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956903]
• 12: J. A. Shaw and E. A. Fox. Combination of multiple searches. In Text REtrieval Conference, pages 0--, 1994.
• 13: C. Suel, T amd 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 Intl. Workshop on the Web and Databases (WebDB), 2003.
• 14: 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]
• 15: Christoph Tempich , Steffen Staab , Adrian Wranik, Remindin': semantic query routing in peer-to-peer networks based on social metaphors, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988759]
• 16: L.-S. Wu, R. Akavipat, and F. Menczer. 6S: Distributing crawling and searching across Web peers. In Proc. of the IASTED Intl. Conf. on Web technologies, Applications, and Services, Calgary, Canada, 2005.

INDEX TERMS

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

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

Keywords:
coverage, distributed precision and recall, overlap, peer collaborative search, peer selection