METHOD AND APPARATUS FOR IMPLEMENTING A NEAREST NEIGHBOR SEARCH ON A GRAPHICS PROCESSING UNIT (GPU)

摘要

An apparatus and method are described for implementing a nearest neighbor search on a graphics processing unit. For example, one embodiment of an apparatus comprises: a host processor; and a graphics processor unit (GPU) to execute a nearest neighbor (NN) tree build operation and a NN tree search operation in response to signals from the host processor; the NN tree build operation comprising dividing a first set of data points to define each tree node to form a plurality of buckets, each bucket comprising at least one of the first set of data points, the number of buckets to be limited based on a threshold value, resulting in at least some buckets with multiple data points; and the NN tree search operation comprising traversing the tree by comparing each of a second set of input data points to data points in the tree to identify a bucket and then comparing one of the second data points to data points in the bucket to identify a nearest neighbor data point in the bucket.