Patent ID: 8069176

Claim:
A method for indexing a set of reference videos comprising: storing a set of reference fingerprints, each reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of a reference video from the set of reference videos; identifying keys contained in the set of reference fingerprints, each key comprising a subset of the fingerprint values; storing, for each identified key, reference identifiers identifying the reference fingerprints that contain the identified key in a bin associated with the identified key; and responsive to the bin storing a number of reference identifiers greater than a threshold number, sub-sampling the reference identifiers stored in the bin according to a sub-sampling factor, wherein sub-sampling the reference identifiers comprises: applying a hash function to an offset value of a reference identifier, wherein the offset value identifies the time-localized portion of the reference video represented by the reference identifier; computing a modulus between an output of the hash function and the sampling index; responsive to the modulus being a non-zero value, discarding the reference identifier from the bin; and responsive to the modulus being zero, retaining the reference identifier in the bin.