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

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