David Novak
Pavel Zezula
ABSTRACT
The need for a retrieval based not on the attribute values but on the very data content has recently led to rise of the metric-based similarity search. The computational complexity of such a retrieval and large volumes of processed data call for distributed processing which allows to achieve scalability. In this paper, we propose M-Chord, a distributed data structure for metric-based similarity search. The structure takes advantage of the idea of a vector index method iDistance in order to transform the issue of similarity searching into the problem of interval search in one dimension. The proposed peer-to-peer organization, based on the Chord protocol, distributes the storage space and parallelizes the execution of similarity queries. Promising features of the structure are validated by experiments on the prototype implementation and two real-life datasets.
- J. Aspnes and G. Shah. Skip graphs. In Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 384 393, 2003. Google Scholar
Digital Library
- F. Banaei-Kashani and C. Shahabi. SWAM: A family of access methods for similarity-search in peer-to-peer data networks. In Proceedings of CIKM 2004, pages 304 313. ACM Press, 2004. Google ScholarDigital Library
- M. Batko, C. Gennaro, and P. Zezula. A scalable nearest neighbor search in P2P systems. In Proceedings of DBISP2P 2004, Toronto, Canada, Revised Selected Papers, volume 3367 of LNCS, pages 79 92. Springer, 2004. Google Scholar
- M. Batko, C. Gennaro, and P. Zezula. Similarity grid for searching in metric spaces. In DELOS Workshop: Digital Library Architectures, volume 3664/2005 of LNCS, pages 25 44. Springer, 2005. Google ScholarDigital Library
- M. Batko, D. Novak, F. Falchi, and P. Zezula. On scalability of the similarity search in the world of peers. In Proceedings of INFOSCALE 2006, Hong Kong. IEEE Computer Society, 2006. Google ScholarDigital Library
- A. R. Bharambe, M. Agrawal, and S. Seshan. Mercury: Supporting scalable multi-attribute range queries. SIGCOMM Comput. Commun. Rev., 34(4):353 366, 2004. Google ScholarDigital Library
- B. Bustos, G. Navarro, and E. Chavez. Pivot selection techniques for proximity searching in metric spaces. Pattern Recognition Letters, 24(14):2357 2366, 2003. Google ScholarDigital Library
- M. Cai, M. Frank, J. Chen, and P. Szekely. MAAN: A multi-attribute addressable network for grid information services. In Proceedings of GRID 2003, pages 184 191, Washington, DC, USA. IEEE Computer Society, 2003. Google ScholarDigital Library
- P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of VLDB 1997, Athens, Greece, pages 426 435. Morgan Kaufmann, 1997. Google Scholar
- V. Dohnal, C. Gennaro, P. Savino, and P. Zezula. D-index: Distance searching index for metric data sets. Multimedia Tools Appl., 21(1):9 33, 2003. Google ScholarDigital Library
- F. Falchi, C. Gennaro, and P. Zezula. A content-addressable network for similarity search in metric spaces. In Proceedings of DBISP2P 2005, Trondheim, Norway, pages 126 137, 2005. Google ScholarDigital Library
- P. Ganesan, B. Yang, and H. Garcia-Molina. One torus to rule them all: Multi-dimensional queries in p2p systems. In Proceedings of WebDB 2004, New York, USA, pages 19 24. ACM Press, 2004. Google ScholarDigital Library
- A. K. Garg and C. C. Gotlieb. Order-preserving key transformations. ACM Trans. Database Syst., 11(2):213 234, 1986. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Index-driven similarity search in metric spaces. ACM Trans. Database Syst., 28(4):517 580, 2003. Google ScholarDigital Library
- H. V. Jagadish, B. C. Ooi, K.-L. Tan, C. Yu, and R. Zhang. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Transactions on Database Systems (TODS 2005), 30(2):364 397, 2005. Google ScholarDigital Library
- V. I. Levenshtein. Binary codes capable of correcting spurious insertions and deletions of ones. Problems of Information Transmission, 1:8 17, 1965.Google Scholar
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of SIGCOMM 2001, San Diego, USA, pages 149 160. ACM Press, 2001. Google ScholarDigital Library
- C. Tang, Z. Xu, and S. Dwarkadas. Peer-to-peer information retrieval using self-organizing semantic overlay networks. Technical report, HP Labs, 2002.Google Scholar
- E. Tanin, A. Harwood, and H. Samet. A distributed quadtree index for peer-to-peer settings. In ICDE, pages 254 255. IEEE Computer Society, 2005. Google ScholarDigital Library
- E. Tanin, D. Nayar, and H. Samet. An efficient nearest neighbor algorithm for p2p settings. In Proceedings of the 2005 national conference on Digital government research, pages 21 28. Digital Government Research Center, 2005. Google ScholarDigital Library
- P. Zezula, G. Amato, V. Dohnal, and M. Batko. Similarity Search: The Metric Space Approach, volume 32 of Advances in Database Systems. Springer-Verlag, 2006. Google ScholarDigital Library
Index Terms
- M-Chord: a scalable distributed similarity search structure
Recommendations
An alignment based system for chord sequence retrieval
JCDL '09: Proceedings of the 9th ACM/IEEE-CS joint conference on Digital librariesMusic retrieval systems for Western tonal music digital ibraries have to consider rhythmic, timbral, melodic and harmonic information. Most existing retrieval systems only take into account melodies. Melody comparison may induce errors since two musical ...
Scalable Content-Based Music Retrieval Using Chord Progression Histogram and Tree-Structure LSH
With more and more multimedia content made available on the Internet, music information retrieval is becoming a critical but challenging research topic, especially for real-time online search of similar songs from websites. In this paper we study how to ...
Comparing approaches to the similarity of musical chord sequences
CMMR'10: Proceedings of the 7th international conference on Exploring music contentsWe present a comparison between two recent approaches to the harmonic similarity of musical chords sequences. In contrast to earlier work that mainly focuses on the similarity of musical notation or musical audio, in this paper we specifically use on ...
Comments