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.
Abstract
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 |
|---|
| Projects: | Miscellaneous |
|---|
| Related URLs: | Project Homepage | http://infolab.stanford.edu/ |
|---|
| 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
- Hybrid Search for Optimization of High-Dimensional k-d Trees. (deposited 25 Feb 2000 16:00) [Currently Displayed]
Download statistics
Repository Staff Only: item control page
![[img]](/style/images/fileicons/application_pdf.png)
