Quantization-based fast inner product search

A method comprising:

• for each respective search item of search items in a database, each search item being represented as a vector of elements, re-ordering the elements of the vector using a random permutation,
• generating a plurality of subspaces from the search items, a subspace being a block of elements from each search item that occur at the same vector positions;
• generating a codebook for each subspace within soft constraints that are based on example queries;
• assigning each subspace of each search item an entry in the codebook for the subspace, the assignments for all subspaces of a search item representing a quantized search item;
• and
• storing the codebooks and the quantized search items.

A method comprising:

• generating a plurality of subspaces from search items in a database, the search items being represented as vectors of elements, a subspace being a block of elements from each search item that occurs at the same vector positions;
• learning a codebook for each subspace by optimizing a task-dependent objective function that minimizes quantization error within soft constraints established by example queries, wherein the example queries are used to identify violated constraints and adjust the codebooks over iterative rounds, the learning resulting in assignment of each block of elements for each search item to an entry in the codebook, generating a quantized search item;
• projecting a query vector into the plurality of subspaces;
• using the query vector, the quantized search items and the codebooks to perform an inner product search for search items responsive to the query;
• and
• providing at least the search item with the highest similarity score as responsive to the query.