Method for approximate k-nearest-neighbor search on parallel hardware accelerators

Patent metadata

Field	Value
Publication number	US-11645585-B2
Application number	US-202217582267-A
Country	US
Kind code	B2
Filing date	Jan 24, 2022
Priority date	Nov 18, 2015
Publication date	May 9, 2023
Grant date	May 9, 2023

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.

First claim

What is claimed is:

1. A method, implemented at least in part via a processor, comprising:
selecting quantization parameters based, at least in part, on a size of shared memory of a hardware accelerator of a computing device, wherein the quantization parameters comprise coordinate and associated length information;
generating one or more distance tables based, at least in part, on at least one quantization parameter of the quantization parameters, wherein the one or more distance tables store results of computations corresponding to a query data point and a subset of a plurality of clusters determined based, at least in part, on the query data point; and
storing the one or more distance tables in the shared memory of the hardware accelerator.

2. The method as recited in claim 1 , comprising:
determining, for each of the subset of the plurality of clusters, a query residual; and
communicating the query residual for each of the subset of the plurality of clusters to the hardware accelerator.

3. The method as recited in claim 1 , wherein the generating the one or more distance tables is performed, at least in part, by a plurality of threads of the hardware accelerator.

4. The method as recited in claim 1 , comprising:
determining a plurality of data points using the one or more distance tables.

5. The method as recited in claim 1 , wherein the selecting the quantization parameters is performed, at least in part, by a machine learning process.

6. The method as recited in claim 1 , wherein the one or more distance tables include a plurality of distance tables, each of the plurality of distance tables corresponding to a cluster in the subset of the plurality of clusters.

7. The method as recited in claim 6 , wherein the hardware accelerator includes a plurality of multiprocessors, the method comprising:
generating, by each of the plurality of multiprocessors, a corresponding one of the plurality of distance tables.

8. A computer readable storage medium comprising instructions that when executed by a processor perform operations, the operations comprising:
generating one or more distance tables, wherein the one or more distance tables store results of computations corresponding to a subset of a plurality of clusters determined based, at least in part, on a query data point;
determining a plurality of data points using the one or more distance tables;
providing one or more query results pertaining to at least a portion of the plurality of data points;
subdividing a data point in the subset of the plurality of clusters into a plurality of subvectors;
quantizing the plurality of subvectors to generate a compressed data point, wherein a coordinate of the compressed data point corresponds to a subvector of the plurality of subvectors; and
mapping the plurality of subvectors to one or more coordinates of the compressed data point.

9. The computer readable storage medium as recited in claim 8 , the operations comprising:
determining, for each of the subset of the plurality of clusters, a query residual; and
communicating the query residual for each of the subset of the plurality of clusters to a hardware accelerator of a computing device.

10. The computer readable storage medium as recited in claim 8 , wherein the generating the one or more distance tables is performed, at least in part, by a plurality of threads of a hardware accelerator of a computing device.

11. The computer readable storage medium as recited in claim 8 , wherein the determining the plurality of data points is performed, at least in part, by a plurality of threads of a hardware accelerator of a computing device.

12. The computer readable storage medium as recited in claim 8 , wherein the generating one or more distance tables is performed based, at least in part, on quantization parameters.

13. The computer readable storage medium as recited in claim 8 , wherein the one or more distance tables include a plurality of distance tables, each of the plurality of distance tables corresponding to a cluster in the subset of the plurality of clusters.

14. The computer readable storage medium as recited in claim 13 , the operations comprising:
storing the one or more distance tables in shared memory of a hardware accelerator of a computing device; and
generating, by each of a plurality of multiprocessors, a corresponding one of the plurality of distance tables.

15. A system comprising:
a processor; and
memory comprising instructions that when executed by the processor perform operations, the operations comprising:
selecting quantization parameters based, at least in part, on a size of shared memory of a hardware accelerator of a computing device;
generating one or more distance tables based, at least in part, on at least one quantization parameter of the quantization parameters, wherein the one or more distance tables store results of computations corresponding to a query data point and a subset of a plurality of clusters determined based, at least in part, on the query data point; and
subdividing a data point in the subset of the plurality of clusters into a plurality of subvectors.

16. The system as recited in claim 15 , the operations comprising:
quantizing the plurality of subvectors to generate a compressed data point, wherein a coordinate of the compressed data point corresponds to a subvector of the plurality of subvectors.

17. The system as recited in claim 16 , the operations comprising:
mapping the plurality of subvectors to one or more coordinates of the compressed data point.

18. The system as recited in claim 15 , the operations comprising:
determining a plurality of data points using the one or more distance tables.

19. The system as recited in claim 15 , wherein the selecting the quantization parameters is performed, at least in part, by a machine learning process.

20. The system as recited in claim 15 , wherein the hardware accelerator comprises a graphics processing unit (GPU).

Assignees

• Verizon Patent & Licensing Inc

Inventors

• Bortnikov Edward
• Libov Alexander
• Shacham Ohad

Classifications

• G06V10/94

  Hardware or software architectures specially adapted for image or video understanding · CPC title

• G06F18/24147

  Distances to closest patterns, e.g. nearest neighbour classification · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06N20/00 Primary

  Machine learning · CPC title

• G06V10/764

  using classification, e.g. of video objects · CPC title