Improved search heuristics for the sa-tree

TitleImproved search heuristics for the sa-tree
Publication TypeJournal Articles
Year of Publication2003
AuthorsHjaltason GR, Samet H
JournalPattern Recognition Letters
Pagination2785 - 2795
Date Published2003/11//
ISBN Number0167-8655
Keywordsdistance-based indexing, Metric spaces, Nearest neighbor algorithms

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.