# US 11,442,914 B1 · Efficient LSH computation

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

- Number: US 11,442,914 B1
- Document ID: US11442914B1
- Status: Granted
- Kind: B1
- Application number: 16/417,479
- Filed: 2019-05-20
- Granted: 2022-09-13
- Earliest claimed: 2019-05-20
- Assignees: Pinterest, Inc.
- Applicants: Pinterest, Inc.
- Inventors: Vitaliy Kulikov
- Web page: https://patentgrep.com/patent/US11442914B1

## CPC

- G06F 16/2255: {Hash tables}
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and methods are presented for efficient and effective computation of LSH hashing functions for use in various environments, including nearest-neighbor search. A corpus of items is maintained, with each item of the corpus being associated with information identifying one of a plurality of LSH partitions to which the item has been mapped or hashed. In response to an input item, the input item is projected one or more times into an orthoplex inscribed within a multi-dimensional space. For each mapping, a determination is made as to the nearest vertex of the orthoplex to the projected input item, and the LSH partitions associated with the nearest vertex are aggregated and associated with the input item as the input item's LSH partition.

## Claims

### Claim 1

A computer implemented method for hashing an input item to a locality sensitive hashing (LSH) partition containing likely similar items from a corpus of items, the method comprising:
maintaining a corpus of items, wherein each item of the corpus of items is associated with an embedding vector generated for the item and a partition of a plurality of LSH partitions;
inscribing an orthoplex into a multi-dimensional space, wherein the orthoplex partitions the multi-dimensional space into symmetrical Voronoi surfaces, wherein each Voronoi surface has as its centroid a vertex of the orthoplex, and wherein each vertex is associated with one of the plurality of LSH partitions;
receiving a request for items from the corpus of items that are similar to the input item;
generating, using an embedding vector generator, an input embedding vector for the input item;
for a predetermined number of iterations:
mapping, using an executable LSH mapper, the input embedding vector into the orthoplex;
identifying the closest vertex of the orthoplex to the mapped input embedding vector; and
identifying a partition of the plurality of LSH partitions associated with the identified vertex of the orthoplex as a partial LSH signature;
aggregating the partial LSH signatures as the LSH signature for the input item;
identifying those items of the corpus of items that are associated with the LSH signature as the likely similar items to the input item;
generating, using an executable similarity scorer, a similarity score for each identified item according to a similarity to the input item; and
identifying a subset of items from the identified items, wherein the subset of items includes items of the identified items having the highest similarity scores.

### Claim 2 (depends on 1)

The computer implemented method of claim 1:
wherein mapping the input embedding vector into the orthoplex comprises partitioning the input embedding vector into a plurality of partitions, and for each partition, mapping the partition into the orthoplex in the multi-dimensional space;
wherein identifying the closest vertex of the orthoplex to the mapped input item comprises, for each partition, identifying the closest vertex of the orthoplex to the mapped partition;
wherein identifying the partition of the plurality of LSH partitions associated with the identified vertex of the orthoplex as a partial LSH signature comprises aggregating the closest vertices of the mapped partitions as the partial LSH signature for the embedding vector.

### Claim 3 (depends on 1)

The computer implemented method of claim 1, wherein:
the partition associated with each item within the corpus of items is determined according to the associated embedding vector of the item.

### Claim 4 (depends on 3)

The computer implemented method of claim 3 further comprising conducting at least one pseudo-random rotation to orient the embedding vector associated with the input item with the orthoplex.

### Claim 5 (depends on 4)

The computer implemented method of claim 4, wherein each rotation of the at least one pseudo-random rotation is carried out using a Fast Hadamard Transform.

### Claim 6 (depends on 5)

The computer implemented method of claim 5, wherein each of the at least one pseudo-random rotation is carried out using the Fast Hadamard Transform on one or more graphic processing units (GPUs).

### Claim 7

The computer implemented method of 1, wherein generating the similarity score for each of the identified items comprises, for each of the identified items:
determining a score for an identified item according to the similarity between the embedding vectors of the identified item and the input embedding vector of the input item.

### Claim 8 (depends on 1)

The computer implemented method of claim 1, wherein determining the score for the identified item according to the similarity between the embedding vectors of the identified item and the input embedding vector of the input item comprises determining the score according to a cosine similarity between the embedding vectors of the identified item and the input embedding vector of the input item.

### Claim 9

A non-transitory computer readable medium bearing computer executable instructions which, when executed on a computing system comprising at least a processor executing the instructions, carry out a method for identifying a subset of items of a corpus of items having a high likelihood of similarity to an input item, the method comprising:
maintaining a corpus of items, wherein each item within the corpus of items is associated with an embedding vector generated for the item and a partition of a plurality of locality sensitive hashing (LSH) partitions;
inscribing an orthoplex into a multi-dimensional space, wherein the orthoplex partitions the multi-dimensional space into symmetrical Voronoi surfaces, wherein each Voronoi surface has as its centroid a vertex of the orthoplex, and wherein each vertex is associated with one of the plurality of LSH partitions;
receiving an input item;
generating, using an executable embedding vector generator, an input embedding vector for the input item;
for a predetermined number of iterations:
projecting, using an executable LSH mapper, the input item into the orthoplex according to the input embedding vector based on an LSH mapping function corresponding to the current iteration;
identifying the closest vertex of the orthoplex to the mapped input item; and
identifying a partition of the plurality of LSH partitions associated with the identified vertex of the orthoplex as a partial LSH signature for the input embedding vector;
aggregating the partial LSH signatures as the LSH signature for the input embedding vector;
identifying a first set of items of the corpus of items that are associated with the LSH signature;
generating, using an executable similarity scorer, a similarity score for each item of the first set items according to their similarity to the input item; and
providing a subset of the first set items as the most similar items to the input item, wherein the subset of the identified items comprises those identified items of the corpus of items having the highest similarity score to the input item.

### Claim 10 (depends on 9)

The non-transitory computer readable medium of claim 9, wherein:
each item within the corpus of items is further associated with an embedding vector generated for the associated item; and
the partition associated with each item within the corpus of items is determined according to a projection of the associated embedding vector of the item into the orthoplex.

### Claim 11 (depends on 10)

The non-transitory computer readable medium of claim 10, wherein generating a similarity score for each item of the first set items according to their similarity to the input item comprises generating a second similarity score for an identified item according to the similarity between the embedding vectors of the identified item and the input embedding vector.

### Claim 12 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein generating the second similarity score for an identified item according to the similarity between the embedding vectors of the identified item and the input embedding vector comprises determining the second similarity score according to a cosine similarity between the embedding vectors of the identified item and the input embedding vector.

### Claim 13 (depends on 12)

The non-transitory computer readable medium of claim 12, wherein the method further comprises conducting at least one pseudo-random rotation to orient the input embedding vector associated with the input item with an orientation of the orthoplex.

### Claim 14 (depends on 13)

The non-transitory computer readable medium of claim 13, wherein each rotation of the at least one pseudo-random rotation is carried out using a Fast Hadamard Transform.

### Claim 15 (depends on 14)

The non-transitory computer readable medium of claim 14, wherein each of the at least one pseudo-random rotation is carried out using the Fast Hadamard Transform on one or more graphic processing units (GPUs).

### Claim 16 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the method further comprises conducting three pseudo-random rotations to orient the input embedding vector associated with the input item with the orientation of the orthoplex.

### Claim 17

A computer system for hashing an input item to a locality sensitive hashing (LSH) partition containing likely similar items from a corpus of items, the system comprising a processor and a memory, wherein the processor executes instructions stored in the memory as part of or in conjunction with additional components to hash the input item to a locality sensitive hashing (LSH) partition, the additional components comprising:
a data store storing a corpus of items, wherein each item within the corpus of items is associated with an embedding vector generated for the associated item, and wherein each item within the corpus of items is associated with one partition of a plurality of LSH partitions;
an executable embedding vector generator that, in execution upon the computer system, generates an embedding vector for the input item;
an executable LSH mapper that, in execution on the computer system:
inscribes the embedding vector for the input item into an orthoplex projected into a multi-dimensional space, and wherein the projected orthoplex subdivides the multi-dimensional space into symmetric Voronoi surfaces, wherein each Voronoi surface has as its centroid a vertex of the orthoplex, and wherein each vertex is associated with one of the plurality of LSH partitions;
for each of a predetermined number of iterations:
identifies a closest vertex of the orthoplex to the projected input item; and
associates the partition associated with the vertex as a partial LSH signature of the input item; and
aggregates the partial LSH signatures as an LSH signature for the input item; and
an executable similarity scorer that, in execution on the computer system:
identifies a first set of items of the corpus of items, wherein each item in the first set of items is associated with LSH partition of the input item;
generates a similarity score for each item of the first set of items according to the embedding vectors of an item of the first set of items and the input item; and
identifies a subset of the first set of items, the subset of the first set of items comprising those items of the first set of items having the highest similarity score.

### Claim 18 (depends on 17)

The computer system of claim 17, wherein the similarity scorer further generates for each item of the first set of items according to a cosine similarity function of the embedding vectors of an item of the first set of items and the input item.