Quantization-based fast inner product search
US10255323B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 8, 2015 |
| Grant date | Apr 9, 2019 |
| Priority date | — |
| Expiry date | Mar 28, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/285
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Implementations provide an improved system for efficiently calculating inner products between a query item and a database of items. An example method includes 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 occur at the same vector position, 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. Generating a codebook for a particular subspace can include clustering the search item subspaces that correspond to the particular subspace, finding a cluster center for each cluster, and storing the cluster center as the codebook entry.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.