US 12,670,193 B2Granted

Sparse embedding index for search

AssigneeAdobe Inc.

InventorsTung Mai, Saayan Mitra, Ryan A. Rossi, Gaurav Gupta, Anup Rao, Xiang Chen

Life of this patent

Estimating the term…

Loading patent…

Abstract

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.

Claims20

Dependent claims

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.

5 more elements

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.

4 more elements

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.

5 more elements

Dependencies are inferred from the claim text.