Audio fingerprinting: nearest neighbor search in high dimensional binary spaces

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.