A system and method are presented for optimization of audio fingerprint search. In an embodiment, the audio fingerprints are organized into a recursive tree with different branches containing fingerprint sets that are dissimilar to each other. The tree is constructed using a clustering algorithm based on a similarity measure. The similarity measure may comprise a Hamming distance for a binary fingerprint or a Euclidean distance for continuous valued fingerprints. In another embodiment, each fingerprint is stored at a plurality of resolutions and clustering is performed hierarchically. The recognition of an incoming fingerprint begins from the root of the tree and proceeds down its branches until a match or mismatch is declared. In yet another embodiment, a fingerprint definition is generalized to include more detailed audio information than in the previous definition.