One embodiment of the present invention provides a method and a system for performing a nearest-neighbor matching operation using a parallel hybrid spill tree. During operation, the system receives an object to be compared to a set of objects stored in the parallel hybrid spill tree. The system first searches a "top tree" of the parallel hybrid spill tree to identify a partition that is likely to contain a nearest neighbor of the object. Each node in the top tree defines an associated partition for the parallel hybrid spill tree. The system then searches a "leaf sub-tree" of the parallel hybrid spill tree that corresponds to the associated partition in an attempt to identify the nearest neighbor of the object.