Approximate nearest neighbor search for single instruction, multiple thread (SIMT) or single instruction, multiple data (SIMD) type processors
Approximate nearest neighbor (ANN) searching is a fundamental problem in computer science with numerous applications in area such as machine learning and data mining. For typical graph-based ANN methods, the searching method is executed iteratively, and the execution dependency prohibits graphics processor unit (GPU)/GPU-type processor adaptations. Presented herein are embodiments of a novel framework that decouples the searching on graph methodology into stages, in order to parallel the performance-crucial distance computation. Furthermore, in one or more embodiments, to obtain better parallelism on GPU-type components, also disclosed are novel ANN-specific optimization methods that eliminate dynamic memory allocations and trade computations for less memory consumption. Embodiments were empirically compared against other methods, and the results confirm the effectiveness.
1. A computer-implemented method for performing, using one or more SIMT (Single Instruction, Multiple Thread)-type or SIMD (Single Instruction, Multiple Data)-type processors, an approximate nearest neighbor search for a query point given a proximity graph comprising vertices, which represent points, and edges, which represent neighbor vertices, the method comprising:
initializing a binary min-heap as a first priority queue, which orders vertices ascendingly by distance relative to the query point and a hash set with a default starting vertex from the proximity graph;
constructing an empty binary max-heap as a second priority queue;
responsive to the first priority queue not being empty:
extracting from the first priority queue a vertex and the vertex's distance to the query point;
responsive to the extracted vertex's distance being greater than distances associated with vertices in the second priority queue and the second priority queue is full, not adding the extracted vertex to the second priority queue;
responsive to the extracted vertex's distance not being greater than a distance associated with at least one vertex in the second priority queue or responsive to the second priority queue not being full, adding the extracted vertex to the second priority queue based upon its distance to the query point; and
for each vertex in the proximity graph that is a neighbor of the extracted vertex and has not already been visited:
computing the vertex's distance to the query point;
adding the vertex to the hash set; and
adding the vertex to the first priority queue in order of distance to the query point; and
responsive to the first priority queue being empty, outputting the second priority queue comprising one or more vertices as nearest neighbors or approximate nearest neighbors in the proximity graph to the query point.
2. The computer-implemented method of claim 1 wherein computing the vertex's distance to the query point is performed using a bulk distance computation in which the distance for each vertex of a plurality of vertices from the first priority queue is computed using a plurality of threads of the one or more processors, in which each thread uses a subset of dimensions of a vertex to compute a partial distance and a thread of the processor aggregates the partial distances into a distance value for each vertex of the plurality of vertices.
3. The computer-implemented method of claim 1 further comprising:
storing at least a portion of the proximity graph as a fixed-degree adjacency list to eliminate use of an additional index look-up.
4. The computer-implemented method of claim 3 wherein a vertex is located by multiplying its index with a fixed size of a vertex.
5. The computer-implemented method of claim 1 further comprising:
explicitly copying the query point into an on-chip shared memory to reduce processor global memory reading.
6. The computer-implemented method of claim 1 wherein the first and second priority queues and the hash set are maintained by a single thread.
7. The computer-implemented method of claim 1 wherein the steps of adding the vertex to the hash set and adding the vertex to the first priority queue in order of its distance to the query point further comprise:
adding, subject to one or more processes, the vertex to the hash set; and
adding, subject to one or more processes, the vertex to the first priority queue in order of its distance to the query point;
wherein the one or more processes comprise one or more of:
a bounded memory process;
a selected insertion process; and
a visited deletion process.
8. A computer-implemented method for performing, using one or more SIMT (Single Instruction, Multiple Thread)-type or SIMD (Single Instruction, Multiple Data)-type processors, an approximate nearest neighbor search for a batch of query points given a proximity graph comprising vertices, which represent points, and edges, which represent neighbor vertices, the method comprising:
for each query point in the batch of query points:
initializing a binary min-heap as a first priority queue, which orders vertices ascendingly by distance relative to the query point and a hash set with a default starting vertex from the proximity graph; and
constructing an empty binary max-heap as a second priority queue;
responsive to not all of the query points in the batch having finished processing:
for a query point from the batch of query points that has not finished processing:
extracting from the first priority queue corresponding to the query point a vertex and the vertex's distance to the query point;
responsive to the extracted vertex's distance being greater than distances associated with vertices in the second priority queue and the second priority queue is full, not adding the extracted vertex to the second priority queue and marking query point being finished; and
responsive to the extracted vertex's distance not being greater than a distance associated with at least one vertex in the second priority queue or responsive to the second priority queue not being full, adding the extracted vertex to the second priority queue based upon its distance to the query point; and
for a query point from the batch of query points that has not finished processing:
initializing a candidate set corresponding to the query point;
for each vertex in the proximity graph that is a neighbor of the extracted vertex and has not already been visited, adding the vertex to the candidate set; and
for each vertex that is a member of the candidate set:
computing the vertex's distance to the query point;
adding the vertex to the hash set; and
adding the vertex to the first priority queue in order of its distance to the query point; and
responsive to all of the query points in the batch having finished processing, outputting for each query point in the batch its second priority queue comprising one or more vertices as nearest neighbors or approximate nearest neighbors in the proximity graph to the query point.
9. The computer-implemented method of claim 8 wherein computing the vertex's distance to the query point is performed using a bulk distance computation in which the distance for each vertex of a plurality of vertices from the candidate set is computed using a plurality of threads of the one or more processors, in which each thread uses a subset of dimensions of a vertex to compute a partial distance and a thread of the processor aggregates the partial distances into a distance value for each vertex of the plurality of vertices.
10. The computer-implemented method of claim 8 further comprising:
storing at least a portion of the proximity graph as a fixed-degree adjacency list to eliminate use of an additional index look-up.
11. The computer-implemented method of claim 10 wherein a vertex is located by multiplying its index with a fixed size of a vertex.
12. The computer-implemented method of claim 8 further comprising:
explicitly copying the query point into an on-chip shared memory to reduce processor global memory reading.
13. The computer-implemented method of claim 8 wherein the first and second priority queues and the hash set are maintained by a single thread.
14. The computer-implemented method of claim 8 wherein the steps of adding the vertex to the hash set and adding the vertex to the first priority queue in order of its distance to the query point further comprise:
adding, subject to one or more processes, the vertex to the hash set; and
adding, subject to one or more processes, the vertex to the first priority queue in order of its distance to the query point;
wherein the one or more processes comprise one or more of:
a bounded memory process;
a selected insertion process; and
a visited deletion process.
15. The computer-implemented method of claim 8 wherein each vertex in the candidate set is allocated using a fixed-length array in shared memory.
16. A non-transitory computer-readable medium or media comprising one or more sequences of instructions which, when executed by one or more SIMT (Single Instruction, Multiple Thread)-type or SIMD (Single Instruction, Multiple Data)-type processors, causes steps for performing an approximate nearest neighbor search for a query point given a proximity graph comprising vertices, which represent points, and edges, which represent neighbor vertices, the steps comprising:
initializing a binary min-heap as a first priority queue, which orders vertices ascendingly by distance relative to the query point and a hash set with a default starting vertex from the proximity graph;
constructing an empty binary max-heap as a second priority queue;
responsive to the first priority queue not being empty:
extracting from the first priority queue a vertex and the vertex's distance to the query point;
responsive to the extracted vertex's distance being greater than distances associated with vertices in the second priority queue and the second priority queue is full, not adding the extracted vertex to the second priority queue;
responsive to the extracted vertex's distance not being greater than a distance associated with at least one vertex in the second priority queue or responsive to the second priority queue not being full, adding the extracted vertex to the second priority queue based upon its distance to the query point; and
for each vertex in the proximity graph that is a neighbor of the extracted vertex and has not already been visited:
computing the vertex's distance to the query point;
adding the vertex to the hash set; and
adding the vertex to the first priority queue in order of its distance to the query point; and
responsive to the first priority queue being empty, outputting the second priority queue comprising one or more vertices as nearest neighbors or approximate nearest neighbors in the proximity graph to the query point.
17. The non-transitory computer-readable medium or media of claim 16 wherein computing the vertex's distance to the query point is performed using a bulk distance computation in which the distance for each vertex of a plurality of vertices from the first priority queue is computed using a plurality of threads of the one or more processors, in which each thread uses a subset of dimensions of a vertex to compute a partial distance and a thread of the processor aggregates the partial distances into a distance value for each vertex of the plurality of vertices.
18. The non-transitory computer-readable medium or media of claim 16 wherein the steps further comprise:
storing at least a portion of the proximity graph as a fixed-degree adjacency list to eliminate use of an additional index look-up.
19. The non-transitory computer-readable medium or media of claim 16 wherein the first and second priority queues and the hash set are maintained by a single thread.
20. The non-transitory computer-readable medium or media of claim 16 wherein the steps of adding the vertex to the hash set and adding the vertex to the first priority queue in order of its distance to the query point further comprise:
adding, subject to one or more processes, the vertex to the hash set; and
adding, subject to one or more processes, the vertex to the first priority queue in order of its distance to the query point;
wherein the one or more processes comprise one or more of:
a bounded memory process;
a selected insertion process; and
a visited deletion process.