Patent ID: 8392427

Claim:
A computer-implemented method for retrieving data from a reference index, the method performed by one or more processors, the method comprising: receiving an input key comprising a subset of values from an input fingerprint, the input fingerprint representing a time-localized portion of an input video; identifying a bin associated with the input key in a reference index table; retrieving a set of reference identifiers stored in the bin associated with the input key, the set of reference identifiers identifying time-localized segments of reference videos having reference fingerprints that comprise a reference key matching the input key; sub-sampling the set of reference identifiers according to a sub-sampling factor responsive to the bin storing more reference identifiers than a predefined threshold, wherein sub-sampling the reference identifiers comprises: applying a hash function to an offset value of a given reference identifier, wherein the offset value identifies the time-localized portion of the given 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 given reference identifier from the retrieved set of reference identifiers; and responsive to the modulus being zero, retaining the given reference identifier in the retrieved set of reference identifiers.