While k-d trees have been widely studied and used, their theoretical 
advantages are often not realized due to ineffective search strategies 
and generally poor performance in high dimensional spaces.  In this paper 
we outline an effective search algorithm for k-d trees that combines an 
optimal depth-first branch and bound (DFBB) strategy with a unique method 
for path ordering and pruning.  Our initial method was developed for 
improving nearest neighbor (NN) search, but has also proven effective for 
k-NN search and approximate k-NN classification.