Patent ID: 11914669
Assignee: BAIDU USA LLC
Field: nan (nan)
Classification: CPC nan | IPC G

Claim 7:
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.