Audio fingerprinting: Nearest neighbor search in high dimensional binary spaces.
PROCEEDINGS OF THE 2002 IEEE WORKSHOP ON MULTIMEDIA SIGNAL PROCESSING.
(pp. 182 - 185).
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.
|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|
|UCL classification:||UCL > School of BEAMS > Faculty of Engineering Science > Computer Science|
Archive Staff Only