Sample-based creation of peer summaries for efficient similarity search in scalable peer-to-peer networks

ABSTRACT

In this paper we introduce a simple yet experimentally convincing approach in the research field of source selection for content-based similarity search in P2P networks or, more concretely, in summary-based P2P systems. In these systems, summaries are used for data source selection when performing k-NN queries on distributed collections of documents represented by feature vectors.

We introduce a new type of cluster-based summaries for source selection that can efficiently and cheaply be calculated and distributed in P2P networks. For the summaries generation, a very large number of sample points is used. Each peer in the network assigns its indexing data to their corresponding closest sample points and publishes its constructed summary. We evaluate the quality of these summaries when changing the number of sample points used in experiments on real-world image feature data obtained from a large crawl of the flickr web photo community and show that for higher numbers of sample points we achieve a better retrieval performance. Our experiments show that the proposed summaries yield four times better performance with respect to previous methods. Intuitively, there are some disadvantages to this approach due to the large size of the generated summaries. We show experimentally, that these disadvantages can easily be overcome due to the sparse nature of the generated summaries by simple compression techniques.

REFERENCES

• 1: Farnoush Banaei-Kashani , Cyrus Shahabi, SWAM: a family of access methods for similarity-search in peer-to-peer data networks, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031236]
• 2: M. Bender et al. The Minerva Project: Database Selection in the Context of P2P Search. In BTW, Karlsruhe, pages 125--144, 2005.
• 3: 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]
• 4: Wendy Chang , Gholamhosein Sheikholeslami , Aidong Zhang , Tanveer F. Syeda-Mahmood, Efficient resource selection in distributed visual information systems, Proceedings of the fifth ACM international conference on Multimedia, p.203-213, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266367]
• 5: I. Cox, M. Miller, T. Minka, T. Papathornas, and P. Yianilos. The Bayesian Image Retrieval System, PicHunter: Theory, Implementation, and Psychophysical Experiments. IEEE TIP, 9(1):20--37, 2000.
• 6: F. M. Cuenca-Acuna and T. Nguyen. Text-Based Content Search and Retrieval in ad hoc P2P Communities. Technical Report DCS-TR-483, Dept. for CS, Rutgers University, 2002.
• 7: Martin Eisenhardt , Wolfgang Muller , Andreas Henrich , Daniel Blank , Soufyane El Allali, Clustering-Based Source Selection for Efficient Image Retrieval in Peer-to-Peer Networks, Proceedings of the Eighth IEEE International Symposium on Multimedia, p.823-830, December 11-13, 2006 [doi>10.1109/ISM.2006.47]
• 8: S. El Allali, D. Blank, M. Eisenhardt, A. Henrich, and W. Müller. Untersuchung des Einflusses verschiedener Bild-Features und Distanzmaβe im inhaltsbasierten P2P Information Retrieval. BTW 2007, 12th GI-Fachtagung für Datenbanksysteme in Business, Technologie und Web, pages 382--396, 2007.
• 9: S. El Allali, D. Blank, W. Müller, and A. Henrich. Image data source selection using Gaussian Mixture Models. 5th International Workshop on Adaptive Multimedia Retrieval AMR'07, 2007.
• 10: Prasanna Ganesan , Beverly Yang , Hector Garcia-Molina, One torus to rule them all: multi-dimensional queries in P2P systems, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017081]
• 11: Pawel Garbacki , Alexandru Iosup , Dick Epema , Maarten van Steen, 2Fast: Collaborative Downloads in P2P Networks, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.23-30, September 06-June 08, 2006 [doi>10.1109/P2P.2006.1]
• 12: Gnutella. URL: http://www.gnutella.com.
• 13: A. Henrich and H.-W. Six. How to split buckets in spatial data structures . Int. Conf. on Geographic Database Management Systems, pages 212--244, 1991.
• 14: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 15: Irwin King , Cheuk Hang Ng , Ka Cheung Sia, Distributed content-based visual information retrieval system on peer-to-peer networks, ACM Transactions on Information Systems (TOIS), v.22 n.3, p.477-501, July 2004 [doi>10.1145/1010614.1010619]
• 16: Jia Li , James Z. Wang, Automatic Linguistic Indexing of Pictures by a Statistical Modeling Approach, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.9, p.1075-1088, September 2003 [doi>10.1109/TPAMI.2003.1227984]
• 17: 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]
• 18: Wolfgang Muller , P. Oscar Boykin , Nima Sarshar , Vwani P. Roychowdhury, Comparison of Image Similarity Queries in P2P Systems, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.98-105, September 06-June 08, 2006 [doi>10.1109/P2P.2006.8]
• 19: W. Müller, M. Eisenhardt, and A. Henrich. Scalable summary based retrieval in P2P networks. In CIKM, pages 586--593, 2005.
• 20: Wolfgang Müller , Andreas Henrich, Fast retrieval of high-dimensional feature vectors in P2P networks using compact peer data summaries, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California [doi>10.1145/973264.973278]
• 21: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, ACM SIGCOMM Computer Communication Review, v.31 n.4, p.161-172, October 2001
• 22: O. D. Sahin , A. Gulbeden , F. Emekci , D. Agrawal , A. El Abbadi, PRISM: indexing multi-dimensional data in P2P networks using reference vectors, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101349]
• 23: Nima Sarshar , P. Oscar Boykin , Vwani P. Roychowdhury, Percolation Search in Power Law Networks: Making Unstructured Peer-to-Peer Networks Scalable, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, p.2-9, August 25-27, 2004 [doi>10.1109/P2P.2004.39]
• 24: Efficient Semantic-Based Content Search in P2P Network, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.813-826, July 2004 [doi>10.1109/TKDE.2004.1318564]
• 25: Chunqiang Tang , Zhichen Xu , Mallik Mahalingam, pSearch: information retrieval in structured overlays, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.89-94, January 2003 [doi>10.1145/774763.774777]
• 26: Nuno Miguel Borges De Pinho Cruz De Vasconcelos , Andrew B. Lippman, Bayesian models for visual information retrieval, Massachusetts Institute of Technology, 2000
• 27: R. C. Veltkamp and M. Tanase. Content-based image retrieval systems: A survey. Technical Report UU-CS-2000-34, Department of Computing Science, Utrecht University, 2002.
• 28: James Z. Wang , Jia Li , Gio Wiederhold, SIMPLIcity: Semantics-Sensitive Integrated Matching for Picture LIbraries, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.947-963, September 2001 [doi>10.1109/34.955109]
• 29: B. Yang and H. Garcia-Molina. Designing a Super-peer Network. In 17th International Conference on Data Engineering, ICDE, pages 49--60, 2003.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process
      H.3.5 On-line Information Services
          Subjects: Data sharing

General Terms:
Algorithms, Experimentation, Performance

Keywords:
CBIR, P2P, source selection