Improved search heuristics for the sa-tree
| Autor: | Hanan Samet, Gísli R. Hjaltason |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Cover tree
Theoretical computer science Nearest neighbor search Combinatorics Best bin first Nearest neighbor graph Artificial Intelligence Signal Processing Ball tree Computer Vision and Pattern Recognition Fixed-radius near neighbors Voronoi diagram Software Large margin nearest neighbor MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Pattern Recognition Letters. 24:2785-2795 |
| ISSN: | 0167-8655 |
| DOI: | 10.1016/s0167-8655(03)00122-3 |
| Popis: | The sa-tree is an interesting metric space indexing structure that is inspired by the Voronoi diagram. In essence, the sa-tree records a portion of the Delaunay graph of the data set, a graph whose vertices are the Voronoi cells, with edges between adjacent cells. An improvement is presented on the original search strategy for the sa-tree. This consists of details on the intuition behind the improvement as well as the original search strategy and a proof of their correctness. Furthermore, it is shown how to adapt an incremental nearest neighbor algorithm to the sa-tree, which allows computing nearest neighbor in a progressive manner. Unlike other adaptations, the resulting algorithm does not take the unnecessary steps to ensure that keys of "node" elements are monotonically non-decreasing. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect