US Patent 9236056 Variable length local sensitivity hash index

Implementations are provided herein relating to audio matching. A variable length local sensitivity hash (“LSH”) index can be created through a careful examination of existing LSH bands in the LSH index. LSH bands with offset lists that meet a band size threshold can be lengthened repeatedly until a maximum length threshold is reached or an offset list associated with a lengthened LSH band fails to meet the band size threshold. The LSH index can be further tuned by down-sampling or discarding LSH bands that reach a maximum length threshold and still lack discriminate properties.