Optimizing Search Strategies in k-d Trees
Neal Sample, Matthew J. Haines, Mark G. Arnold, Timothy J. Purcell · 2001
: 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. Introduction Search is an important technique in many fields, and various search methods are continually being refined. There are several types of search that are of interest in different disciplines. Nearest neighbor (NN) search is important to many case-based reasoning (CBR) as well as various classification and matching problems [9]. Approximate nearest neighbor search is important to many AI systems, and in systems where there is an accept...