Efficient similarity search
AssigneeGSI Technology, Inc.
InventorSamuel LIFSCHES
Life of this patent
Estimating the term…
Abstract
A system for measuring similarity between a binary query vector and a plurality of binary candidate vectors includes a storage unit and a processor. The storage unit stores the binary query vector and the plurality of candidate vectors, and the processor performs Tanimoto calculations in terms of Hamming distances.
Claims27
1-20. (canceled)
A system for measuring similarity between a binary query vector and a plurality of binary candidate vectors, the system comprising:
- an associative memory array having columns storing vectors, at least one column for said binary query vector and at least one column for each one of said plurality of binary candidate vectors;
- and
- a controller to activate said associative memory array to perform Tanimoto distance calculations in terms of Hamming distances using Boolean operations between said binary candidate vectors and said binary query vector.
A system for measuring similarity between a binary query vector and a plurality of binary candidate vectors, the system comprising:
- a pop counter to generate pop counts of said binary candidate vectors, wherein each pop count is a number of occurrences of a selected symbol in at least one of said binary candidate vectors;
- a chunker to group said binary candidate vectors according to their pop counts into chunks;
- a clusterer to use a K-means algorithm to generate clusters of said chunks, each cluster having a centroid;
- and
- a cluster comparator to select at least one of said clusters whose centroid is similar to said binary query vector and to perform Tanimoto calculations in terms of Hamming distances using Boolean operations between said binary candidate vectors of said cluster and said binary query vector.
A method for measuring similarity between a binary query vector and a plurality of binary candidate vectors, the method comprising:
- storing vectors in columns of an associative memory array, at least one column for said binary query vector and at least one column for each one of said plurality of binary candidate vectors;
- and
- activating said associative memory array to perform Tanimoto distance calculations in terms of Hamming distances using Boolean operations between said binary candidate vectors and said binary query vector.
A method for measuring similarity between a binary query vector and a plurality of binary candidate vectors, the method comprising:
- generating pop counts of said binary candidate vectors, wherein each pop count is a number of occurrences of a selected symbol in at least one of said binary candidate vectors;
- grouping said binary candidate vectors according to their pop counts into chunks;
- using a K-means algorithm to generate clusters of said chunks, each cluster having a centroid;
- selecting at least one of said clusters whose centroid is similar to said binary query vector;
- and
- performing Tanimoto calculations in terms of Hamming distances using Boolean operations between said binary candidate vectors of said cluster and said binary query vector.
Dependencies are inferred from the claim text.