Title: An effective and efficient indexing scheme for audio fingerprinting
Author: Guang-Ho Cha
Address: Department of Computer Engineering, Seoul National University of Science and Technology, 232 Gongreung-ro, Nowon-gu, Seoul 139-743, Republic of Korea
Abstract: With the proliferation of multimedia data, there is an increasing need to support the ability to automatically analyse and interpret their contents. In this paper, we propose a new effective and efficient indexing scheme for a fingerprint database that stores songs. A song is represented by a fingerprint extracted from the audio fingerprinting technique and it can be recognised by matching an extracted fingerprint to a database of known audio fingerprints. We are given a fingerprint database of songs and focus our attention on the problem of effective and efficient database search. However, the nature of high dimensionality of fingerprints suffers from the curse of dimensionality, i.e., as the dimension increases, the search performance decreases exponentially. In order to tackle this problem, we propose a new indexing scheme based on the inverted file and duplicate fingerprint indexes with toggled bits. In addition, we also present a new search algorithm based on the offset match principle to avoid expensive random disk accesses. Through extensive tests using a database of 2,000 songs containing approximately 4,000,000 sub-fingerprints, we find that our method shows a substantial improvement with respect to speed and accuracy.
Keywords: audio fingerprinting; inverted files; inverted lists; similarity search; dimensionality curse; fingerprint database; multimedia data; songs; audio fingerprints; indexing schemes.
Int. J. of Information Technology, Communications and Convergence, 2012 Vol.2, No.3, pp.268 - 280
Available online: 14 Nov 2012