Hierarchical quantization for fast inner product search
US10719509B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 11, 2016 |
| Grant date | Jul 21, 2020 |
| Priority date | — |
| Expiry date | Jul 14, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F18/24137
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Implementations provide an efficient system for calculating inner products between high-dimensionality vectors. An example method includes clustering database items represented as vectors, selecting a cluster center for each cluster, and storing the cluster center as an entry in a first layer codebook. The method also includes, for each database item, calculating a residual based on the cluster center for the cluster the database item is assigned to and projecting the residual into subspaces. The method also includes determining, for each of the subspaces, an entry in a second layer codebook for the subspace, and storing the entry in the first layer codebook and the respective entry in the second layer codebook for each of the subspaces as a quantized vector for the database item. The entry can be used to categorize an item represented by a query vector or to provide database items responsive to a query vector.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.