Patent ID: 7475071
Filing Date: 2009-01-06
Classification: G06F,G06K,Y10S

Abstract:
1. A method for performing a nearest-neighbor matching operation using a tree data structure, comprising: receiving the tree data structure, where the tree data structure comprises decision nodes and leaf nodes; wherein the decision nodes logically partition a set of objects stored in two or more computing devices; wherein a given decision node defines a partition boundary between two subsets of the set of objects; wherein a given leaf node corresponds to the objects stored on a given computing device; receiving a target object for which a nearest neighbor is to be found in the set of objects; determining one or more leaf nodes associated with the target object by traversing the decision nodes, starting from the top node, of the tree data structure; wherein a first leaf node corresponds to a first subset of objects; wherein a second leaf node corresponds to a second subset of objects; wherein the first subset and the second subset may include overlapping objects that are in proximity to a partition boundary between the first subset and the second subset, wherein the partition boundary corresponds to a decision node that is the parent of the first and second leaf nodes; when the first subset and the second subset include the set of overlapping objects, searching for a nearest neighbor for the target object in either the first or second subset, based on the partition boundary corresponding to the decision node; and when the first subset and the second subset do not include the set of overlapping objects and the target object is in proximity to the partition boundary, searching for a nearest neighbor for the target object in both the first and second subsets.