Large data methods for multimedia

ABSTRACT

This tutorial describes techniques essential for searching the large multimedia databases that are now common on the Internet. There are up to 10 million songs in commercial music catalogues and over 300 million images stored in online photo services such as Flickr. How can we find the music, videos or images we want? How can we organize such large collections: find duplicates, create links between similar documents, extract and annotate semantic structures from complex audiovisual documents? Conventional methods for handling large data sets, such as hashing, get us part of the way, but those methods may not straightforwardly be used for similarity-based matching and retrieval in audiovisual document collections. On the other hand, several elaborate methods from multimedia retrieval are available for semantic document analysis. Unfortunately, those methods generally do not scale for large data sets. Instead, new classes of algorithms combining the best of the two worlds of large data methods and semantic analysis are needed to handle large multimedia databases. Innovative methods such as locality sensitive hashing, which are based on randomized probes, are the new workhorses. This tutorial covers methods for multimedia retrieval on large document collections. Starting with audio retrieval, we describe both the theory (i.e., randomized algorithms for hashing) and the implementation details (how do you store hash values for millions of songs?). A special focus is on how to combine large data methods with semantically meaningful descriptors in order to facilitate efficient similarity-based retrieval. Besides audio, the tutorial also covers image, 3d motion and video retrieval.

REFERENCES

• 1: E. Allamanche, J. Herre, B. Fröba, and M. Cremer. AudioID: Towards Content-Based Identification of Audio Material. In Proc. 110th AES Convention, Amsterdam, NL, 2001.
• 2: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 3: M. Casey and M. Slaney. The importance of sequences for music similarity. In Proc. ICASSP, 2006.
• 4: M. Casey and M. Slaney. Song intersection by approximate nearest neighbours. In Proc. ISMIR, 2006.
• 5: M. Casey and M. Slaney. Fast recognition of remixed music audio. In Proc. ICASSP, 2007.
• 6: M. Clausen, R. Engelbrecht, D. Meyer, and J. Schmitz. Proms: A web-based tool for searching in polyphonic music. In Proc. ISMIR, 2000.
• 7: M. Clausen, H. Kࣆrner, and F. Kurth. An Efficient Indexing and Search Technique for Multimedia Databases. In SIGIR Workshop on Multimedia Retrieval, Toronto, Canada, 2003.
• 8: M. Clausen and F. Kurth. Content-Based Information Retrieval by Group Theoretical Methods. In NATO (ASI), Lucca, Italy, 2003.
• 9: M. Clausen and F. Kurth. A unified approach to content-based and fault tolerant music recognition. IEEE Transactions on Multimedia, 6(5):717--731, October 2004.
• 10: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 11: J. Haitsma and T. Kalker. A Highly Robust Audio Fingerprinting System. In Proc. ISMIR, 2002.
• 12: J. Herre, E. Allamanche, O. Hellmuth, and T. Kastner. Robust identification/fingerprinting of audio signals using spectral flatness features. In Journal of the Acoustical Society of America, volume 111, 2002.
• 13: F. Kurth, M. Müller, D. Damm, C. Fremerey, A. Ribbrock, and M. Clausen. Syncplayer - an advanced system for content-based audio access. In Proc. ISMIR, London, GB, 2005.
• 14: M. Müller, F. Kurth, and M. Clausen. Audio matching via chroma-based statistical features. In Proc. ISMIR, London, GB, 2005.
• 15: Meinard Müller , Tido Röder , Michael Clausen, Efficient content-based retrieval of motion capture data, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 16: T. Röder, F. Kurth, A. Mosig, and M. Clausen. A Group Theoretical Approach to Content-based Image Retrieval. NATO Advanced Study Institute (ASI), Lucca, Italy, 2003. Available via email to the authors.
• 17: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 18: A. Wang. An industrial strength audio search algorithm. In Proc. ISMIR, 2003.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Keywords:
index-based multimedia retrieval, large data methods, locality sensitive hashing