Local orthogonal decomposition for maximum inner product search
US11354287B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 16, 2019 |
| Grant date | Jun 7, 2022 |
| Priority date | — |
| Expiry date | Jun 10, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/16
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Techniques of indexing a database and processing a query involve decomposing the residual term according to a projection matrix that is based on a given direction v. For example, for each database element of a partition, the residual for that database element is split into a component parallel to a given direction and a component perpendicular to that direction. The parallel component lies in a one-dimensional subspace spanned by the direction and may be efficiently quantized with a scalar quantization. The perpendicular component is quantized using multiscale quantization techniques. The quantized residual components and the center elements of each partition define the indexed database. Upon receipt of a query from a user, the inner products of q with the residual may be computed efficiently using the quantized residual components. From these inner products, the database elements that are most similar to the query are selected and returned to the user.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.