Peer-to-peer similarity search over widely distributed document collections

ABSTRACT

This paper addresses the challenging problem of similarity search over widely distributed ultra-high dimensional data. Such an application is retrieval of the top-k most similar documents in a widely distributed document collection, as in the case of digital libraries. Peer-to-peer (P2P) systems emerge as a promising solution to delve with content management in cases of highly distributed data collections. We propose a self-organizing P2P approach in which an unstructured P2P network evolves into a super-peer architecture, with super-peers responsible for peers with similar content. Our approach is based on distributed clustering of peer contents, thus managing to create high quality clusters that span the entire network. More importantly, we show how to efficiently process similarity queries capitalizing on the newly constructed, clustered super-peer network. During query processing, the query is propagated only to few carefully selected super-peers that are able to return results of high quality. We evaluate the performance of our approach and demonstrate its advantages through simulation experiments on two document collections.

REFERENCES

• 1: K. Aberer, P. Cudré-Mauroux, M. Hauswirth, and T. V. Pelt. Gridvine: Building Internet-Scale Semantic Overlay Networks. In Proceedings of ISWC'2004, 2004.
• 2: V. Cholvi, P. Felber, and E. Biersack. Efficient search in unstructured peer-to-peer networks. Technical report, Institut EURECOM, 2003.
• 3: A. Crespo and H. Garcia-Molina. Semantic overlay networks for P2P systems. In Proceedings of AP2PC'04, 2004.
• 4: 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, p.236, June 22-24, 2003
• 5: Inderjit S. Dhillon , Dharmendra S. Modha, Concept decompositions for large sparse text data using clustering, Machine Learning, v.42 n.1/2, p.143-175, Jan. 2001 [doi>10.1023/A:1007612920971]
• 6: C. Doulkeridis, K. Nørvåg, and M. Vazirgiannis. DESENT: Decentralized and distributed semantic overlay generation in P2P networks. IEEE Journal on Selected Areas in Communications (J-SAC), 25(1):25--34, 2007.
• 7: Christos Doulkeridis , Akrivi Vlachou , Yannis Kotidis , Michalis Vazirgiannis, Peer-to-peer similarity search in metric spaces, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 8: Pawel Garbacki , Dick H. J. Epema , Maarten van Steen, Optimizing Peer Relationships in a Super-Peer Network, Proceedings of the 27th International Conference on Distributed Computing Systems, p.31, June 25-27, 2007 [doi>10.1109/ICDCS.2007.126]
• 9: Claudio Gennaro , Matteo Mordacchini , Salvatore Orlando , Fausto Rabitti, Processing complex similarity queries in peer-to-peer networks, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1363803]
• 10: C. Gkantsidis, M. Mihail, and A. Saberi. Hybrid search schemes for unstructured peer-to-peer networks. In Proceedings of INFOCOM'05, 2005.
• 11: Alessandro Linari , Gerhard Weikum, Efficient peer-to-peer semantic overlay networks based on statistical language models, Proceedings of the international workshop on Information retrieval in peer-to-peer networks, November 11-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183579.1183582]
• 12: F. Liu, M. Li, and L. Huang. Distributed information retrieval based on hierarchical semantic overlay network. In Proceedings of GCC'04, 2004.
• 13: Jie Lu , Jamie Callan, Full-text federated search of text-based digital libraries in peer-to-peer networks, Information Retrieval, v.9 n.4, p.477-498, September 2006 [doi>10.1007/s10791-006-6388-2]
• 14: Jianming Lv , Xueqi Cheng, WonGoo: A Pure Peer-to-Peer Full Text Information Retrieval System Based On Semantic Overlay Networks, Proceedings of the Network Computing and Applications, Third IEEE International Symposium, p.47-54, August 30-September 01, 2004
• 15: S. Michel, P. Triantafillou, and G. Weikum. MINERVA Infinity: A Scalable Efficient Peer-to-Peer Search Engine. In Proceedings of Middleware'05, 2005.
• 16: Wolfgang Nejdl , Martin Wolpers , Wolf Siberski , Christoph Schmitz , Mario Schlosser , Ingo Brunkhorst , Alexander Löser, Super-peer-based routing and clustering strategies for RDF-based peer-to-peer networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775229]
• 17: David Novak , Pavel Zezula, M-Chord: a scalable distributed similarity search structure, Proceedings of the 1st international conference on Scalable information systems, p.19-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146866]
• 18: J. X. Parreira, S. Michel, and G. Weikum. p2pDating: Real Life Inspired Semantic Overlay Networks for Web Search. In Proceedings of SIGIR'2005 HDIR Workshop, 2005.
• 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: O. D. Sahin, F. Emekci, D. Agrawal, and A. E. Abbadi. Content-based similarity search over peer-to-peer systems. In Proceedings of DBISP2P'04, 2004.
• 21: Gleb Skobeltsyn , Toan Luu , Ivana Podnar Žarko , Martin Rajman , Karl Aberer, Query-driven indexing for scalable peer-to-peer text retrieval, Proceedings of the 2nd international conference on Scalable information systems, June 06-08, 2007, Suzhou, China
• 22: T. Suel et al. ODISSEA: A Peer-to-Peer Architecture for Scalable Web Search and Information Retrieval. In Proceedings of WebDB'2003, 2003.
• 23: Chunqiang Tang , Sandhya Dwarkadas, Hybrid global-local indexing for effcient peer-to-peer information retrieval, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.16-16, March 29-31, 2004, San Francisco, California
• 24: 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]
• 25: 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]
• 26: Jiangong Zhang , Torsten Suel, Efficient Query Evaluation on Large Textual Collections in a Peer-to-Peer Environment, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.225-233, August 31-September 02, 2005 [doi>10.1109/P2P.2005.7]

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.1 Content Analysis and Indexing

General Terms:
Algorithms, Design, Performance

Keywords:
distributed and peer-to-peer search, semantic overlay networks