Selection of hash lookup keys for efficient retrieval
AssigneeGoogle Inc.
InventorsMichele Covell, Sergey Ioffe, Shumeet Baluja, David Marwood
Life of this patent
Estimating the term…
Abstract
Videos are received and indexed based on fingerprints generated for the videos, using lookup keys which correspond to sub portions of the reference fingerprints. Specifically, a set of lookup keys is selected such that the number of reference fingerprints such that the clumping associated with the associated each of the lookup keys is minimized. Clumping occurs when a number of reference identifiers associated with a lookup key exceeds a maximum value.
Claims21
A computer-implemented method for indexing a set of reference videos, the method executed by one or more computer systems and comprising:
- accessing a plurality of reference fingerprints, each reference fingerprint uniquely associated with a corresponding one of the set reference videos and comprising a sequence of fingerprint values representing a time localized portion of the associated reference video;
- generating a reference index for indexing the set of reference videos based on a set of keys, each key comprising a subset of the fingerprint values of a reference fingerprint, by selecting the set of keys using a reward function that minimizes an amount of clumping associated with the set of keys;
- and
- storing the reference index.
A non-transitory computer-readable storage medium encoded with executable computer program code for indexing a set of reference videos, the program code comprising program code for:
- accessing a plurality of reference fingerprints, each reference fingerprint uniquely associated with a corresponding one of the set reference videos and comprising a sequence of fingerprint values representing a time localized portion of the associated reference video;
- generating a reference index for indexing the set of reference videos based on a set of keys, each key comprising a subset of the fingerprint values of a reference fingerprint, by selecting the set of keys using a reward function that minimizes an amount of clumping associated with the set of keys;
- and
- storing the reference index.
A computer system for indexing a set of reference videos, the computer system comprising:
- a memory;
- a processor;
- and
- a training module stored in the memory and executable by the processor to:
- access a plurality of reference fingerprints, each reference fingerprint uniquely associated with a corresponding one of the set reference videos and comprising a sequence of fingerprint values representing a time localized portion of the associated reference video;
- generating a reference index for indexing the set of reference videos based on a set of keys, each key comprising a subset of the fingerprint values of a reference fingerprint, by selecting the set of keys using a reward function that minimizes an amount of clumping associated with the set of keys;
- and
- store the reference index.
Dependencies are inferred from the claim text.