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.