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

Patent metadata

Field	Value
Publication number	US-10510017-B2
Application number	US-201514945221-A
Country	US
Kind code	B2
Filing date	Nov 18, 2015
Priority date	Nov 18, 2015
Publication date	Dec 17, 2019
Grant date	Dec 17, 2019

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:
obtaining a query data point representing a query object;
selecting a subset of a plurality of clusters based upon a comparison of a centroid of a cluster of the plurality of clusters to the query data point, wherein the cluster comprises a set of data points;
communicating an assignment of the subset of the plurality of clusters to a hardware accelerator of a computing device;
selecting quantization parameters based, at least in part, on a size of shared memory of the hardware accelerator, wherein the quantization parameters comprise:
a first quantization parameter indicative of a number of coordinates in at least one compressed data point; and
a second quantization parameter indicative of a subvector length associated with at least one coordinate;

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 the query data point and the subset of the plurality of clusters;
storing the one or more distance tables in the shared memory of the hardware accelerator;
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 of the subvector length;
quantizing the plurality of subvectors to generate a compressed data point having the number of coordinates, 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.

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 , wherein the determining the plurality of data points is performed, at least in part, by a plurality of threads of the hardware accelerator.

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:
obtaining a query data point representing a query object;
selecting a subset of a plurality of clusters based upon a comparison of a centroid of a cluster of the plurality of clusters to the query data point, wherein the cluster comprises a set of data points;
communicating an assignment of the subset of the plurality of clusters to a hardware accelerator of a computing device;
selecting quantization parameters based, at least in part, on a size of shared memory of the hardware accelerator, wherein the quantization parameters comprise:
a first quantization parameter indicative of a number of coordinates in at least one compressed data point; and
a second quantization parameter indicative of a subvector length associated with at least one coordinate;

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 the query data point and the subset of the plurality of clusters;
storing the one or more distance tables in the shared memory of the hardware accelerator;
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 of the subvector length;
quantizing the plurality of subvectors to generate a compressed data point having the number of coordinates, 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 the hardware accelerator.

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 the hardware accelerator.

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 the hardware accelerator.

12. The computer readable storage medium as recited in claim 8 , wherein the selecting the quantization parameters is performed, at least in part, by a machine learning process.

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 , wherein the hardware accelerator includes a plurality of multiprocessors, the operations comprising:
generating, by each of the 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:
obtaining a query data point representing a query object;
selecting a subset of a plurality of clusters based upon a comparison of a centroid of a cluster of the plurality of clusters to the query data point, wherein the cluster comprises a set of data points;
communicating an assignment of the subset of the plurality of clusters to a hardware accelerator of a computing device;
selecting quantization parameters based, at least in part, on a size of shared memory of the hardware accelerator, wherein the quantization parameters comprise:
a first quantization parameter indicative of a number of coordinates in at least one compressed data point; and
a second quantization parameter indicative of a subvector length associated with at least one coordinate;

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 the query data point and the subset of the plurality of cl

Assignees

• Oath Inc

Inventors

• Bortnikov Edward
• Libov Alexander
• Shacham Ohad

Classifications

• G06F17/10

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

• G06F16/90335

  Query processing · CPC title

• G06V10/764

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

• G06V10/763

  Non-hierarchical techniques, e.g. based on statistics of modelling distributions · CPC title

• G06F18/24147

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