Locality sensitive hashing using bitmap index
A data item identification service may use locality sensitive hashing to identify data items which are relevant to a search based on a hash of a search vector based on the search. Hashes of vectors based on data items may be stored using a set of bitmaps, where a given bitmap corresponds to a given bit position of a hash. Data items with matching or similar hashes may be related to each other. The data item identification service may perform searches by generating a hash for a search vector and comparing the hash to hashes for data items using one or more logical operations on the set of bitmaps to identify related data items.
1 . A system, comprising:
one or more computing devices configured to:
obtain vectors for respective data items;
generate hashes based on positions of the vectors relative to a set of hyperplanes;
generate an inverted index, wherein:
the inverted index comprises a set of bitmaps;
a given bitmap is associated with a respective bit position of a set of hashes; and
a given bit position of the set of bitmaps is associated with a respective data item;
cause the inverted index and the set of hyperplanes to be durably stored; and
instantiate an ephemeral computing instance, configured via executable instructions, to:
receive, in response to a request to perform a search of the data items, a search vector, the set of hyperplanes, and a copy of the inverted index;
generate a search hash based on a position of the search vector relative to the set of hyperplanes; and
provide an identification of a particular data item which is associated with a particular hash of the set of hashes by performing one or more logical operations on the set of bitmaps of the inverted index, wherein the particular hash indicates that the particular data item is associated with a vector that is among a set of nearest neighbor vectors to the search vector.
2 . The system of claim 1 , wherein said generating the inverted index further comprises generating a translator, wherein the translator stores indications of associations between the data items and the bit positions of the set of bitmaps.
3 . The system of claim 1 , wherein the one or more computing devices are further configured to generate additional sets of hyperplanes and additional inverted indexes which comprise additional hashes which are based on the positions of the vectors relative to the additional sets of hyperplanes.
4 . The system of claim 3 , wherein the ephemeral computing instance has further instructions to:
generate additional search hashes based on the position of the search vector relative to the additional sets of hyperplanes;
receive the additional inverted indexes; and
provide the identification of the particular data item which is associated with a set of particular hashes by performing one or more logical operations on bitmaps of the inverted indexes, wherein the particular hashes indicate that the particular data item is associated with a vector that is among sets of nearest neighbor vectors to the search vector.
5 . The system of claim 1 , wherein to perform said identifying the particular data item, the ephemeral computing instance has further instructions to determine a cosine similarity between the search vector and a vector of the particular data item.
6 . The system of claim 1 , wherein the inverted index is stored using lossless bitmap compression techniques.
7 . A method, comprising:
obtaining, at one or more computing devices, vectors for respective data items;
generating, at the one or more computing devices, hashes based on positions of the vectors relative to a set of hyperplanes;
generating, at the one or more computing devices, an inverted index representing associations between respective data items, wherein:
the inverted index comprises a set of bitmaps;
a given bitmap is associated with a respective bit position of a set of hashes; and
a given bit position of the set of bitmaps is associated with a respective data item;
causing the inverted index and the set of hyperplanes to be durably stored; and
providing a copy of the inverted index and a copy of the set of hyperplanes to a computing instance in response to a request to provide an identification of a particular data item based on a search vector.
8 . The method of claim 7 , further comprising:
generating a search vector in response to the request;
generating a search hash based on a position of the search vector relative to the set of hyperplanes; and
provide an identification of the particular data item, which is associated with a particular hash of the set of hashes, by performing one or more logical operations on the set of bitmaps of the inverted index, wherein the particular hash indicates that the particular data item is associated with a vector that is among a set of nearest neighbor vectors to the search vector.
9 . The method of claim 8 , wherein said identifying the particular data item comprises determining:
a cosine similarity between the search vector and a vector of the particular data item; or
a Hamming distance between the search hash and the particular hash.
10 . The method of claim 7 , wherein the inverted index is associated with a translator which stores indications of associations between the data items and the bit positions of the set of bitmaps.
11 . The method of claim 7 , further comprising:
generating additional sets of hyperplanes and additional inverted indexes which comprise additional hashes which are based on the positions of the vectors relative to the additional sets of hyperplanes.
12 . The method of claim 11 , further comprising:
generating additional search hashes based on the position of the search vector relative to the additional sets of hyperplanes; and
providing the identification of the particular data item which is associated with a set of particular hashes by performing one or more logical operations on bitmaps of the additional inverted indexes, wherein the particular hashes indicate that the particular data item is associated with a vector that is among sets of nearest neighbor vectors to the search vector.
13 . The method of claim 7 , wherein the inverted index is stored using lossless bitmap compression techniques.
14 . One or more non-transitory, computer-readable storage media storing program instructions which, when executed on or across one or more processors, cause the one or more processors to:
generate a search vector in response to a request to perform a search of data items;
generate a search hash based on a position of the search vector relative to a set of hyperplanes;
receive a copy of a durably stored inverted index, wherein:
the inverted index comprises a set of bitmaps;
a given bitmap is associated with a respective bit position of a set of hashes; and
a given bit position of the set of bitmaps is associated with a respective data item; and
provide an identification of a particular data item which is associated with a particular hash of the set of hashes by performing one or more logical operations on the set of bitmaps of the inverted index, wherein the particular hash indicates that the particular data item is associated with a vector that is among a set of nearest neighbor vectors to the search vector.
15 . The non-transitory, computer-readable storage media of claim 14 , wherein the program instructions, when executed on or across the one or more processors, further cause the one or more processors to:
obtain, at one or more computing devices, vectors for respective data items;
generate hashes based on positions of the vectors relative to a set of hyperplanes;
generate an inverted index; and
cause the inverted index and the set of hyperplanes to be durably stored.
16 . The non-transitory, computer-readable storage media of claim 15 , wherein the program instructions, when executed on or across the one or more processors, further cause the one or more processors to generate a translator, wherein the translator stores indications of associations between the data items and the bit positions of the set of bitmaps.
17 . The non-transitory, computer-readable storage media of claim 14 , wherein the program instructions, when executed on or across the one or more processors, further cause the one or more processors to generate additional sets of hyperplanes and additional inverted indexes which comprise additional hashes which are based on the positions of the vectors relative to the additional sets of hyperplanes.
18 . The non-transitory, computer-readable storage media of claim 17 , the program instructions, when executed on or across the one or more processors, further cause the one or more processors to:
generate additional search hashes based on the position of the search vector relative to the additional sets of hyperplanes;
receive the additional inverted indexes; and
provide the identification of the particular data item which is associated with a set of particular hashes by performing one or more logical operations on bitmaps of the additional inverted indexes, wherein the particular hashes indicate that the particular data item is associated with a vector that is among sets of nearest neighbor vectors to the search vector.
19 . The non-transitory, computer-readable storage media of claim 14 , wherein to perform said identifying the particular data item, the program instructions, when executed on or across the one or more processors, further cause the one or more processors to determine a Hamming distance between the search hash and the particular hash.
20 . The non-transitory, computer-readable storage media of claim 14 , wherein the inverted index is stored using lossless bitmap compression techniques.