Sparse embedding index for search
A search system facilitates efficient and fast near neighbor search given item vector representations of items, regardless of item type or corpus size. To index an item, the search system expands an item vector for the item to generate an expanded item vector and selects elements of the expanded item vector. The item is index by storing an identifier of the item in posting lists of an index corresponding to the position of each selected element in the expanded item vector. When a query is received, a query vector for the item is expanded to generate an expanded query vector, and elements of the expanded query vector are selected. Candidate items are identified based on posting lists corresponding to the position of each selected element in the expand query vector. The candidate items may be ranked, and a result set is returned as a response to the query.
1 . One or more computer storage media storing computer-useable instructions that, when used by a computing device, cause the computing device to perform operations, the operations comprising:
providing a plurality of expanded item vectors for a plurality of items, wherein each expanded item vector from the plurality of expanded item vectors represents a corresponding item from the plurality of items as a corresponding array of N elements;
providing an inverted index having a plurality of posting lists, the plurality of posting lists including N positing lists, wherein the N posting lists have a one-to-one correspondence with array positions of the N elements in the plurality of expanded item vectors including a first posting list for a first array position and a second posting list for a second array position, wherein each of the N posting lists stores item identifiers for one or more items from the plurality of items based on selected elements in each expanded item vector;
expanding an item vector representing a first item not in the plurality of items to generate a first expanded item vector representing the first item as a first array of N elements;
selecting a first element at the first array position in the first expanded item vector and a second element at the second array position in the first expanded item vector;
based on selecting the first element at the first array position in the expanded item vector and the second element at the second array position in the first expanded item vector:
identifying, from the N posting lists, the first posting list for the first array position and the second posting list for the second array position,
storing an item identifier for the first item in the first posting list for the first array position, the first posting list also including an item identifier for each of one or more items from the plurality of items, and
storing the item identifier for the first item in the second posting list for the second array position, the second posting list also including an item identifier for each of one or more items from the plurality of items.
2 . The computer storage media of claim 1 , wherein expanding the item vector to generate the first expanded item vector comprises multiplying a matrix to the item vector, wherein the matrix comprises a sparse random binary matrix.
3 . The computer storage media of claim 1 , wherein the item vector comprises an embedding generated by a neural network using an input data regarding the first item.
4 . The computer storage media of claim 1 , wherein selecting the first element of the first expanded item vector and the second element of the first expanded item vector comprises sparsifying the first expanded item vector.
5 . The computer storage media of claim 4 , wherein sparsifying the first expanded item vector comprises:
setting one or more elements of the first expanded item vector to a non-zero value; and
setting a value of one or more other elements of the first expanded item vector to zero.
6 . The computer storage media of claim 1 , wherein the operations further comprise:
expanding a query vector representing a query to generate an expanded query vector comprising a second array of N elements;
selecting a first element at the first array position of the expanded query vector and a second element at the second array position of the expanded query vector; and
based on selecting the first element at the first array position of the expanded query vector and the second element at the second array position of the expanded query vector:
identifying from the N posting lists from the inverted index, the first posting list for the first array position and the second posting list for the second array position,
accessing a first set of item identifiers from the first posting list and a second set of item identifiers from the second posting list, and
determining a plurality of items using the first set of item identifiers and the second set of item identifiers.
7 . The computer storage media of claim 6 , wherein selecting the first element of the expanded query vector and the second element of the expanded query vector comprises sparsifying the expanded query vector.
8 . The computer storage media of claim 7 , wherein sparsifying the expanded query vector comprises:
setting one or more elements of the expanded query vector to a non-zero value; and
setting a value of one or more other elements of the expanded query vector to zero.
9 . The computer storage media of claim 6 , wherein the operations further comprise:
ranking each item from the plurality of items based on a comparison of a corresponding item vector representing each item from the plurality of items and the query vector; and
providing an output based on ranking the plurality of items.
10 . The computer storage media of claim 1 , wherein the operations further comprise:
determining an attribute of the first item;
identifying, from the plurality of posting lists in the inverted index, a third posting list for the attribute, wherein the third posting list is not in the N posting lists, wherein the third posting list stores an item identifier for one or more items from the plurality of items that have the attribute; and
storing the item identifier for the first item in the third posting list.
11 . A computerized method comprising:
expanding a query vector representing a query to generate an expanded query vector comprising an array of N elements, wherein each of the N elements in the expanded query vector has an array position in the expanded query vector;
selecting a first element at a first array position in the expanded query vector and a second element at a second array position in the expanded query vector;
based on selecting the first element at the first array position of the expanded query vector and the second element at the second array position of the expanded query vector:
accessing an inverted index having a plurality of posting lists, the plurality of posting lists including N positing lists, wherein the N posting lists have a one-to-one correspondence with the array positions of the N elements in the expanded query vector including a first posting list for the first array position and a second posting list for the second array position, wherein each of the N posting lists stores item identifiers for one or more items from a plurality of items,
identifying, from the N posting lists in the inverted index, the first posting list for the first array position and the second posting list for the second array position,
accessing a first set of item identifiers from the first posting list and a second set of item identifiers from the second posting list, and
determining a plurality of items using the first set of item identifiers and the second set of item identifiers.
12 . The computerized method of claim 11 , wherein selecting the first element at the first array position in the expanded query vector and the second element at the second array position in the expanded query vector comprises sparsifying the expanded query vector.
13 . The computerized method of claim 12 , wherein sparsifying the expanded query vector comprises:
setting one or more elements of the expanded query vector to a non-zero value; and
setting a value of one or more other elements of the expanded query vector to zero.
14 . The computerized method of claim 11 , wherein the method further comprises:
ranking each item from the plurality of items based on a comparison of a corresponding item vector representing each item and the query vector; and
providing an output based on ranking the plurality of items.
15 . A computer system comprising:
a processor; and
one or more computer storage media storing computer-useable instructions that, when used by the processor, causes the computer system to perform operations comprising:
expanding, by an item expansion module, an item vector for an item to generate an expanded item vector comprising a first array of N elements, the N elements having array positions in the expanded item vector, wherein a subset of the N elements in the expanded item vector comprise selected elements including a first element at a first array position in the expanded item vector and a second element at a second array position in the expanded item vector;
storing, by an item indexing module, an item identifier of the item in each of a subset of a plurality of posting lists of an inverted index based on the selected elements in the expanded item vector, the plurality of posting lists including N positing lists having a one-to-one correspondence to the array positions in the expanded item vector, wherein the item identifier is stored in a first posting list for the first array position and in a second posting list for the second array position;
expanding, by a query expansion module, a query vector representing a query to generate an expanded query vector comprising a second array of N elements; and
determining, by a querying module, a plurality of candidate items identified in at least a portion of the N posting lists corresponding with one or more array positions of one or more selected elements in the expanded query vector.
16 . The computer system of claim 15 , wherein the item expansion module expands the item vector to generate the expanded item vector by multiplying a matrix to the item vector.
17 . The computer system of claim 15 , wherein the item vector comprises an embedding generated by a neural network using an input data regarding the item.
18 . The computer system of claim 15 , wherein the item expansion module selects the selected elements of the expanded item vector by sparsifying the expanded item vector by setting one or more elements of the expanded item vector to a non-zero value and setting a value of one or more other elements of the expanded item vector to zero.
19 . The computer system of claim 15 , wherein the query expansion module selects the selected elements of the expanded query vector by: sparsifying the expanded query vector by setting the selected elements of the expanded query vector to a non-zero value and setting a value of one or more other elements of the expanded query vector to zero.
20 . The computer system of claim 15 , wherein the querying module ranks each candidate item based on a comparison of a corresponding item vector representing each candidate item and the query vector, and provides an output based on ranking the candidate items.