Back to results
US 9,054,876 B1Granted
Fast efficient vocabulary computation with hashed vocabularies applying hash functions to cluster centroids that determines most frequently used cluster centroid IDs
AssigneeGoogle Inc.
InventorJay Yagnik
Life of this patent
Estimating the term…
Abstract
The disclosed embodiments describe a method, an apparatus, an application specific integrated circuit, and a server that provides a fast and efficient look up for data analysis. The apparatus and server may be configured to obtain data segments from a plurality of input devices. The data segments may be individual unique subsets of the entire data set obtained by a plurality input devices. A hash function may be applied to an aggregated set of the data segments. A result of the hash function may be stored in a data structure. A codebook may be generated from the hash function results.
Claims15
A method comprising:
- receiving data at a device, wherein the data is represented as a vector;
- performing, by a processor in the device, vector quantization to identify clusters of data vectors and the centroids of the clusters of data vectors, wherein the centroids of the clusters of data vectors are represented as vectors;
- applying a plurality of hash functions to the cluster centroids;
- indexing the output of the plurality of hash functions into a plurality of respective hash tables;
- generating a code book from each of the plurality of hash tables, wherein each entry in the code book contains at least one identifier of a cluster centroid;
- receiving signal data to be analyzed;
- applying the plurality of hash functions to the received data to be analyzed, wherein the application of the applied plurality of hash functions generates a hash index;
- accessing the respective codebooks using the hash index;
- retrieving cluster centroid identifiers from the respective codebooks;
- determining which of the cluster centroid identifiers is most frequently retrieved;
- and
- outputting a signal identifying the most frequently retrieved cluster centroid identifier.
9 more elements
A system comprising:
- a processor configured to:
- receive data at a device, wherein the data is represented as a vector;
- perform vector quantization to identify clusters of data vectors and the centroids of the clusters of data vectors, wherein the centroids of the clusters of data vectors are represented as vectors;
- apply a plurality of hash functions to the cluster centroids;
- index the output of the plurality of hash functions into a plurality of respective hash tables;
- generate a code book from each of the plurality of hash tables, wherein each entry in the code book contains at least one identifier of a cluster centroid;
- receive signal data to be analyzed;
- apply the plurality of hash functions to the received data to be analyzed, wherein the application of the applied plurality of hash functions generates a hash index;
- access the respective codebooks using the hash index;
- retrieve cluster centroid identifiers from the respective codebooks;
- determine which of the cluster centroid identifiers is most frequently retrieved;
- and
- output a signal identifying the most frequently retrieved cluster centroid identifier.
10 more elements
A non-transitory computer-readable storage medium with an executable program stored thereon, wherein the program instructs a processor to perform the following steps:
- receiving data at a device, wherein the data is represented as a vector;
- performing, by a processor in the device, vector quantization to identify clusters of data vectors and the centroids of the clusters of data vectors, wherein the centroids of the clusters of data vectors are represented as vectors;
- applying a plurality of hash functions to the cluster centroids;
- indexing the output of the plurality of hash functions into a plurality of respective hash tables;
- generating a code book from each of the plurality of hash tables, wherein each entry in the code book contains at least one identifier of a cluster centroid;
- receiving signal data to be analyzed;
- applying the plurality of hash functions to the received data to be analyzed, wherein the application of the applied plurality of hash functions generates a hash index;
- accessing the respective codebooks using the hash index;
- retrieving cluster centroid identifiers from the respective codebooks;
- determining which of the cluster centroid identifiers is most frequently retrieved;
- and
- outputting a signal identifying the most frequently retrieved cluster centroid identifier.
9 more elements
Dependencies are inferred from the claim text.