Efficient LSH computation

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.

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.