Loading...
Please wait, while we are loading the content...
Similar Documents
Approximate best bin first k-d tree all nearest neighbor search with incremental updates (2010).
| Content Provider | CiteSeerX |
|---|---|
| Author | Kybic, Jan |
| Abstract | We describe an approximate algorithm to find all nearest neighbors (NN) for a set of points in moderate to high-dimensional spaces. Al-though the method is generally applicable, it is tailored to our main application, which is a NN-based entropy estimation for an image similarity criterion for image registration. Our algorithm is unique for having simultaneously the following features: (i) It is usable for millions of data points in several tens of dimensions. (ii) It can deal with multiple points. (iii) It offers a speedup of the all-NN search task with respect to repeating a NN search for each query point. (iv) It allows exact as well as approximate search when reduced search time is needed. (v) The search tree can be updated incrementally when the change of values of the data points is small. The method is based on creating a balanced k-d tree, which is then searched using the best-bin-first strategy. The tree nodes contain both tight and loose bounding boxes. The method is presented using NN defined in an ` ∞ norm but can be applied to the `2 norm, too. We present a number of experiments demonstrating the behavior of our algorithm. We compare the presented method with a state-of-the-art approximate nearest neighbor search library ANN and we observe that the new method is superior for exact search and high number of points as well as for approximate search in small to mod-erate dimensions or when a fast approximation is needed. 1 1 |
| File Format | |
| Publisher Date | 2010-01-01 |
| Access Restriction | Open |
| Subject Keyword | Incremental Update Approximate Search Data Point High-dimensional Space Main Application Search Tree High Number Presented Method Several Ten State-of-the-art Approximate Nn-based Entropy Estimation Approximate Algorithm Following Feature Image Similarity Criterion Multiple Point Balanced K-d Tree New Method Fast Approximation Nn Search Neighbor Search Library Ann Best-bin-first Strategy All-nn Search Task Loose Bounding Box Search Time Exact Search Image Registration Mod-erate Dimension Tree Node Query Point |
| Content Type | Text |
