Processing complex similarity queries in peer-to-peer networks

ABSTRACT

Similarity search for content-based retrieval (where content can be any combination of text, image, audio/video, etc.) has gained importance in recent years, also because of the advantage of ranking the retrieved results according to their proximity to a query. However, to use similarity search in real world applications, we need to tackle the problem of huge volumes of such mixed multimedia data (e.g., coming from Web sites) and the problem of their distribution on multiple cooperating nodes. The proposed approach is being used in two running projects: SAPIR and NeP4B.

In this paper we approach this problem by considering a scenario of a network of autonomous peers maintaining a local collection of metric objects (i.e., mixed mode multimedia content). This network forms a distributed Peer-to-Peer (P2P) search engine for similarity search based on the paradigm of Routing Index. Each peer in the network thus maintains both an index of its local resources and a table for every neighbor, summarizing the objects that are reachable from it. The paper presents techniques that aim to make our P2P similarity-based search system viable, trading approximate results for scalable solutions. Results of simulations that use real collections of images are discussed.

REFERENCES

• 1: 2006. Gnutella protocol development. http://rfc-gnutella.sourceforge.net/.
• 2: Michal Batko , David Novak , Fabrizio Falchi , Pavel Zezula, On scalability of the similarity search in the world of peers, Proceedings of the 1st international conference on Scalable information systems, p.20-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146867]
• 3: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 4: 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
• 5: M. Marzolla. libcppsim: a simula-like, portable process-oriented simulation library in C++. In G. Horton, editor, Proc. of ESM04, the 18th European Simulation Multiconference, Magdeburg, DE, 2004. SCS-European Publishing House.
• 6: 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
• 7: Ion Stoica , Robert Morris , David Liben-Nowell , David R. Karger , M. Frans Kaashoek , Frank Dabek , Hari Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for internet applications, IEEE/ACM Transactions on Networking (TON), v.11 n.1, p.17-32, February 2003 [doi>10.1109/TNET.2002.808407]
• 8: Michael J. Swain , Dana H. Ballard, Color indexing, International Journal of Computer Vision, v.7 n.1, p.11-32, Nov. 1991 [doi>10.1007/BF00130487]
• 9: Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , Michal Batko, Similarity Search: The Metric Space Approach (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2005

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Keywords:
P2P, multimedia, similarity search, unstructured network