Stanford InfoLab Publication Server

Optimizing Search Strategies in k-d Trees

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
Subjects:Computer Science
Related URLs:Project Homepage
ID Code:723
Deposited By:Import Account
Deposited On:27 Apr 2001 17:00
Last Modified:27 Dec 2008 10:49

Available Versions of this Item

Download statistics

Repository Staff Only: item control page