# US 2023/0273933 A1 · Efficient similarity search

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0273933 A1
- Document ID: US20230273933A1
- Status: Published application
- Kind: A1
- Application number: 18/311,938
- Filed: 2023-05-04
- Published: 2023-08-31
- Earliest claimed: 2020-03-17
- Assignees: GSI Technology, Inc.
- Applicants: GSI Technology Inc.
- Inventors: Samuel LIFSCHES
- Web page: https://patentgrep.com/patent/US20230273933A1

## CPC

- G06F 16/2468: {Fuzzy queries}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/24558: {Binary matching operations}
- G06F 16/285: {Clustering or classification}
- G06F 18/23213: with fixed number of clusters, e.g. K-means clustering
- G06F 18/24147: {Distances to closest patterns, e.g. nearest neighbour classification}
- G16C 20/40: Searching chemical structures or physicochemical data
- H03M 13/1575: {Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance}
- H03M 13/2942: {wherein a block of parity bits is computed only from combined information bits or only from parity bits, e.g. a second block of parity bits is computed from a first block of parity bits obtained by systematic encoding of a block of information bits, or a block of parity bits is obtained by an XOR combination of sub-blocks of information bits}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G16C: COMPUTATIONAL CHEMISTRY; CHEMOINFORMATICS; COMPUTATIONAL MATERIALS SCIENCE
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## 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.

## Claims

### Claim at position 1

1-20. (canceled)

### Claim 21

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.

### Claim 22 (depends on 21)

The system of claim 21 wherein said Boolean operations are pop count operations and Boolean XOR functions between said binary candidate vectors and said binary query vector.

### Claim 23 (depends on 21)

The system of claim 21 wherein said controller comprises:
a pop counter to count a number of occurrences of a selected symbol in at least one of said binary vectors; and
a Hamming threshold calculator to calculate a Hamming threshold from pop counts of said binary query vector and one of said binary candidate vectors.

### Claim 24 (depends on 21)

The system according to claim 21 and also comprising:
a chunker to group said binary candidate vectors according to their pop counts into chunks; and
a chunk comparator to reject those said chunks which cannot contain said binary candidate vectors similar to said binary query vector and to provide non-rejected chunks to a Hamming measurer.

### Claim 25 (depends on 24)

The system of claim 24 wherein said chunker comprises:
a pop counter to count a pop count of said binary candidate vectors; and
a vector sorter to group said binary candidate vectors into chunks with homogeneous pop counts.

### Claim 26 (depends on 24)

The system of claim 24 wherein said chunk comparator comprises:
a pop counter to count a pop count of said chunks; and
a Hamming minimum comparator to compare said pop count of said chunks with a Hamming threshold and reject said chunks that have a pop count higher than said Hamming threshold.

### Claim 27 (depends on 24)

The system according to claim 24 and also comprising:
a clusterer to group said binary candidate vectors in said chunks into clusters with prototypical centroids by means of a clustering algorithm; and
a cluster comparator to select at least one of said clusters with said centroids similar to said binary query vector.

### Claim 28 (depends on 27)

The system according to claim 27 wherein said clustering algorithm is one of:
a K-means and a K nearest neighbor algorithm.

### Claim 29 (depends on 27)

The system of claim 27 wherein said cluster comparator comprises:
said Hamming measurer to measure a Hamming distance between said binary query vector and one of said centroids; and
a Hamming comparator to select only said clusters with said centroid within a Hamming threshold of said binary query vector and said at least one of said chunks.

### Claim 30

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.

### Claim 31 (depends on 30)

The system of claim 30 wherein said cluster comparator comprises:
a Hamming measurer to measure a Hamming distance between said binary query vector and said centroid; and
a Hamming comparator to select only said clusters whose centroid is within a Hamming measurement threshold of said binary query vector and said at least one of said chunks.

### Claim 32 (depends on 30)

The system of claim 30 and also 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, wherein at least one of said chunks is stored in a section of said associative memory array.

### Claim 33 (depends on 32)

The system of claim 32 wherein at least one said cluster is stored together within its said chunk.

### Claim 34

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.

### Claim 35 (depends on 34)

The method of claim 34 wherein said Boolean operations are pop count operations and Boolean XOR functions between said binary candidate vectors and said binary query vector.

### Claim 36 (depends on 34)

The method of claim 34 wherein said activating comprises:
counting a number of occurrences of a selected symbol in at least one of said binary vectors; and
calculating a Hamming threshold from pop counts of said binary query vector and one of said binary candidate vectors.

### Claim 37 (depends on 34)

The method according to claim 34 and also comprising:
grouping said binary candidate vectors according to their pop counts into chunks;
rejecting those said chunks which cannot contain said binary candidate vectors similar to said binary query vector; and
outputting non-rejected chunks.

### Claim 38 (depends on 37)

The method of claim 37 wherein said grouping comprises:
counting a pop count of said binary candidate vectors; and
vector sorting said binary candidate vectors into chunks with homogeneous pop counts.

### Claim 39 (depends on 37)

The method of claim 37 wherein said rejecting comprises:
counting a pop count of said chunks;
comparing said pop count of said chunks with a Hamming threshold; and
rejecting said chunks that have a pop count higher than said Hamming threshold.

### Claim 40 (depends on 37)

The method according to claim 37 and also comprising:
clustering said binary candidate vectors in said chunks into clusters with prototypical centroids by means of a clustering algorithm; and
selecting at least one of said clusters whose centroid is similar to said binary query vector.

### Claim 41 (depends on 40)

The method according to claim 40 wherein said clustering algorithm is one of:
a K-means and a K nearest neighbor algorithm.

### Claim 42 (depends on 40)

The method of claim 40 wherein said selecting comprises:
measuring said Hamming distance between said binary query vector and said centroid; and
selecting only said clusters whose centroid within said Hamming measurement threshold of said binary query vector and said at least one of said chunks.

### Claim 43

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.

### Claim 44 (depends on 43)

The method of claim 43 wherein said selecting comprises:
measuring a Hamming distance between said binary query vector and said centroid; and
selecting only said clusters whose centroid is within a Hamming measurement threshold of said binary query vector and said at least one of said chunks.

### Claim 45 (depends on 43)

The method of claim 43 and also comprising, in 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, storing at least one of said chunks in a section of said associative memory array.

### Claim 46 (depends on 45)

The method of claim 45 wherein said storing comprises storing together at least one said cluster within its said chunk.
