sample, neal and haines, matthew and arnold, mark and purcell, timothy (2001) Optimizing Search Strategies in k-d Trees. In: 5th WSES/IEEE World Multiconference on Circuits, Systems, Communications & Computers (CSCC 2001), July 8-15, 2001, Crete, Greece.
This is the latest version of this item.
K-d trees have been widely studied and used, yet their theoretical advantages are often not realized due to ineffective search strategies and degrading performance in high dimensional spaces. 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. This technique was developed for improving nearest neighbor (NN) search, but has also proven effective for k-NN search and approximate k-NN queries.
|Item Type:||Conference or Workshop Item (Paper)|
|Uncontrolled Keywords:||k-d trees, search, high dimensionality, DFBB, nearest neighbor, k-NN|
|Related URLs:||Project Homepage||http://infolab.stanford.edu/CHAIMS/|
|Deposited By:||Import Account|
|Deposited On:||27 Apr 2001 17:00|
|Last Modified:||27 Dec 2008 10:49|
Available Versions of this Item
- Hybrid Search for Optimization of High-Dimensional k-d Trees. (deposited 25 Feb 2000 16:00)
- Optimizing Search Strategies in k-d Trees. (deposited 27 Apr 2001 17:00) [Currently Displayed]
Repository Staff Only: item control page