One embodiment of the present invention provides a method and a system for
building a parallel hybrid spill tree to facilitate parallel
nearest-neighbor matching operations. During operation, the system
receives a set of objects to be stored in the parallel hybrid spill tree.
The system selects a subset of objects from the set of objects, and then
uses this subset to create a "top tree." Each node in the top tree
defines an associated partition for the parallel hybrid, spill tree. The
system uses the top tree to associate each object in the set of objects
with a corresponding partition of the parallel hybrid spill tree. Then,
the system builds for each partition of the parallel hybrid spill tree an
associated "leaf sub-tree" containing the objects in the partition, with
each leaf sub-tree structured as a spill tree.