Methods and apparatus for efficient media indexing

Patent metadata

Field	Value
Publication number	US-12554697-B2
Application number	US-202418824141-A
Country	US
Kind code	B2
Filing date	Sep 4, 2024
Priority date	Sep 6, 2018
Publication date	Feb 17, 2026
Grant date	Feb 17, 2026

Abstract

Methods, apparatus, systems and articles of manufacture are disclosed for efficient media indexing. An example method disclosed herein includes means for initiating a list of hash seeds, the list of hash seeds including at least a first hash seed value and a second hash seed value among other hash seed values, means for generating to generate a first bucket distribution based on the first hash seed value and a first hash function and generate a second bucket distribution based on the second hash seed value used in combination with the first hash seed value, means for determining to determine a first entropy value of the first bucket distribution, wherein data associated with the first bucket distribution is stored in a first hash table and determine a second entropy value of the second bucket distribution.

First claim

What is claimed is:

1 . A computer-implemented method comprising:
determining a first entropy value of a first bucket distribution, wherein the first bucket distribution is associated with a first hash seed value and a first hash function; determining a second entropy value of a second bucket distribution, wherein the second bucket distribution is associated with the first hash seed value and a second hash seed value; determining that the second entropy value is greater than an entropy value associated with an additional bucket distribution, wherein the additional bucket distribution is based on one or more hash seed values in a plurality of additional hash seed values; and retrieving audio fingerprint data using a hash table associated with at least one of: (i) the first entropy value and the first hash seed value; and (ii) the second entropy value and the second hash seed value.

2 . The computer-implemented method of claim 1 , wherein the first hash seed value is associated with a first hash index, and wherein the second hash seed value is associated with a second hash index.

3 . The computer-implemented method of claim 2 , wherein the first hash index is different than the second hash index.

4 . The computer-implemented method of claim 1 , wherein at least one of the first hash seed value and the second hash seed value are based on predetermined list of integer values.

5 . The computer-implemented method of claim 1 , wherein at least one of the first hash seed value and the second hash seed value are generated by a random number generator.

6 . The computer-implemented method of claim 1 , wherein at least one of the first hash seed value or the second hash seed value is used to identify a location of one or more subfingerprints associated with the audio fingerprint data.

7 . The computer-implemented method of claim 6 , wherein at least one of the first entropy value or the second entropy value is associated with a distribution of the one or more subfingerprints.

8 . The computer-implemented method of claim 1 , further comprising generating a group of hash seeds, wherein the group comprises the first hash seed value, the second hash seed value, and the plurality of additional hash seed values, and wherein generating the group of hash seeds comprises generating a list of hash seeds, and wherein the list comprises the first hash seed value, the second hash seed value, and at least one additional hash seed value of the plurality of additional hash seed values.

9 . The computer-implemented method of claim 1 , further comprising storing the first entropy value and the first hash seed value in a first hash table.

10 . The computer-implemented method of claim 1 , further comprising, based on determining that the second entropy value is greater than an entropy value associated with an additional bucket distribution, storing the second entropy value and the second hash seed value in a second hash table.

11 . A tangible non-transitory computer-readable storage medium comprising computer readable instructions that, when executed, cause one or more processors to perform a set of operations comprising:
determining a first entropy value of a first bucket distribution, wherein the first bucket distribution is associated with a first hash seed value and a first hash function; determining a second entropy value of a second bucket distribution, wherein the second bucket distribution is associated with the first hash seed value and a second hash seed value; determining that the second entropy value is greater than an entropy value associated with an additional bucket distribution, wherein the additional bucket distribution is based on one or more hash seed values in a plurality of additional hash seed values; and retrieving audio fingerprint data using a hash table associated with at least one of: (i) the first entropy value and the first hash seed value; and (ii) the second entropy value and the second hash seed value.

12 . The tangible non-transitory computer-readable storage medium of claim 11 , wherein the first hash seed value is associated with a first hash index, and wherein the second hash seed value is associated with a second hash index.

13 . The tangible non-transitory computer-readable storage medium of claim 12 , wherein the first hash index is different than the second hash index.

14 . The tangible non-transitory computer-readable storage medium of claim 11 , wherein at least one of the first hash seed value and the second hash seed value are based on predetermined list of integer values.

15 . The tangible non-transitory computer-readable storage medium of claim 11 , wherein at least one of the first hash seed value and the second hash seed value are generated by a random number generator.

16 . The tangible non-transitory computer-readable storage medium of claim 11 , wherein at least one of the first hash seed value or the second hash seed value is used to identify a location of one or more subfingerprints associated with the audio fingerprint data.

17 . The tangible non-transitory computer-readable storage medium of claim 16 , wherein at least one of the first entropy value or the second entropy value is associated with a distribution of the one or more subfingerprints.

18 . The tangible non-transitory computer-readable storage medium of claim 11 , wherein the set of operations further comprises generating a group of hash seeds, wherein the group comprises the first hash seed value, the second hash seed value, and the plurality of additional hash seed values, and wherein generating the group of hash seeds comprises generating a list of hash seeds, and wherein the list comprises the first hash seed value, the second hash seed value, and at least one additional hash seed value of the plurality of additional hash seed values.

19 . The tangible non-transitory computer-readable storage medium of claim 11 , wherein the set of operations further comprises storing the first entropy value and the first hash seed value in a first hash table and, based on determining that the second entropy value is greater than an entropy value associated with an additional bucket distribution, storing the second entropy value and the second hash seed value in a second hash table.

20 . A computing device comprising:
one or more processors; and a tangible non-transitory computer-readable storage medium comprising computer readable instructions that, when executed, cause one or more processors to perform a set of operations comprising:
determining a first entropy value of a first bucket distribution, wherein the first bucket distribution is associated with a first hash seed value and a first hash function;
determining a second entropy value of a second bucket distribution, wherein the second bucket distribution is associated with the first hash seed value and a second hash seed value;
determining that the second entropy value is greater than an entropy value associated with an additional bucket distribution, wherein the additional bucket distribution is based on one or more hash seed values in a plurality of additional hash seed values; and
retrieving audio fingerprint data using a hash table associated with at least one of: (i) the first entropy value and the first hash seed value; and (ii) the second entropy value and the second hash seed value.

Assignees

• Gracenote Inc

Inventors

• Wilkinson Matthew James
• Scott Jeffrey
• Coover Robert
• Dimitriou Konstantinos Antonios

Classifications

• G06F16/41

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F7/588

  Random number generators, i.e. based on natural stochastic processes · CPC title

• G06F16/2255 Primary

  Hash tables · CPC title