A Fast Retrieval Algorithm Based on Fibonacci Hashing for Audio Fingerprinting Systems

In audio fingerprinting system, the database consists of hundreds of millions of sub-fingerprints. How to find out the most similar audio in the shortest time and use less memory in huge repository of sub-fingerprints is a hot topic of research. Recently, Philips introduced an effective search method based on hash table. In this paper, a fast retrieval algorithm based on the Fibonacci Hashing is proposed as an extension of Philips's method. The algorithm uses Fibonacci Hashing function which can adjust the size of hash table according to capacity of memory, provide a good distribution of hash value, and save memory. The performance of presented algorithm has been evaluated by experiments. Index Terms - audio retrieval, Fibonacci Hashing, audio fingerprint, hash table.