Method for approximate k-nearest-neighbor search on parallel hardware accelerators
US11244245B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 16, 2019 |
| Grant date | Feb 8, 2022 |
| Priority date | — |
| Expiry date | Feb 25, 2040 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06V10/94
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
In one embodiment, a processor of a computing device receives a query. The computing device may compare a centroid of each of a plurality of clusters to the query such that a subset of the plurality of clusters is selected, each of the plurality of clusters having a set of data points. An assignment of the subset of the plurality of clusters may be communicated to a hardware accelerator of the computing device. A plurality of threads of the hardware accelerator of the computing device may generate one or more distance tables that store results of intermediate computations corresponding to the query and the subset of the plurality of clusters. The distance tables may be stored in shared memory of the hardware accelerator. A plurality of threads of the hardware accelerator may determine a plurality of data points using the distance tables. The processor may provide query results pertaining to at least a portion of the plurality of data points.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.