Stanford InfoLab Publication Server

Hybrid Search for Optimization of High-Dimensional k-d Trees

Sample, N. and Haines, M. and Arnold, M. and Purcell, T. (1999) Hybrid Search for Optimization of High-Dimensional k-d Trees. Technical Report. Stanford.

WarningThere is a more recent version of this item available.



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.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:similarity search, high dimensionality search, nearest neighbor, optimizations
Subjects:Computer Science
Related URLs:Project Homepage
ID Code:371
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:28 Dec 2008 10:14

Available Versions of this Item

Download statistics

Repository Staff Only: item control page