Patent ID: 7539657
Filing Date: 2009-05-26
Classification: G06F,G06K,Y10S

Abstract:
1. A method for building a parallel hybrid spill tree to facilitate parallel nearest-neighbor matching operations, comprising: receiving a set of objects to be stored in the parallel hybrid spill tree, wherein the size of the set of objects is larger than the available memory of a computing device; selecting a subset of objects from the set of objects, wherein the subset of objects fits in the available memory of the computing device; using the selected subset of objects to create a “top tree” that partitions the set of objects; wherein the top tree is structured as a hybrid spill tree, and each leaf node in the top tree defines an associated partition for the parallel hybrid spill tree; using the top tree to associate each object in the set of objects with one or more corresponding partitions of the parallel hybrid spill tree; for each partition of the parallel hybrid spill tree, building an associated “leaf sub-tree” for objects in the partition, wherein each leaf sub-tree is structured as a hybrid spill tree; wherein the partitioned subsets of objects associated with the leaf nodes in the top tree are distributed across multiple computing devices; and using the parallel hybrid spill tree to perform and display the results of a nearest-neighbor matching operation for the set of objects.