UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Audio fingerprinting: Nearest neighbor search in high dimensional binary spaces

Miller, ML; Rodriguez, MA; Cox, IJ; (2002) Audio fingerprinting: Nearest neighbor search in high dimensional binary spaces. In: PROCEEDINGS OF THE 2002 IEEE WORKSHOP ON MULTIMEDIA SIGNAL PROCESSING. (pp. 182 - 185). IEEE

Full text not available from this repository.

Abstract

Audio fingerprinting is an emerging research field in which a song must be recognized by matching an extracted "fingerprint" to a database of known fingerprints. Audio fingerprinting must solve the two key problems of representation and search. In this paper, we are given an 8192-bit binary representation of each five second interval of a song and therefore focus our attention on the problem of high-dimensional nearest neighbor search. High dimensional nearest neighbor search is known to suffer from the curse of dimensionality, i.e. as the dimension increases, the computational or memory costs increase exponentially. However, recently, there has been significant work on efficient, approximate, search algorithms. We build on this work and describe preliminary results of a probabilistic search algorithm. We describe the data structures and search algorithm used and then present experimental results for a database of 1,000 songs containing 12,217,111 fingerprints.

Type:Proceedings paper
Title:Audio fingerprinting: Nearest neighbor search in high dimensional binary spaces
Event:5th IEEE Workshop on Multimedia Signal Processing (MMSP 2002)
Location:ST THOMAS, VIRGIN ISLANDS
Dates:2002-12-09 - 2002-12-11
ISBN:0-7803-7713-3
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record