%0 Journal Article %J Pattern Recognition Letters %D 2003 %T Improved search heuristics for the sa-tree %A Hjaltason,Gı́sli R. %A Samet, Hanan %K distance-based indexing %K Metric spaces %K Nearest neighbor algorithms %X 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. %B Pattern Recognition Letters %V 24 %P 2785 - 2795 %8 2003/11// %@ 0167-8655 %G eng %U http://www.sciencedirect.com/science/article/pii/S0167865503001223 %N 15 %R 10.1016/S0167-8655(03)00122-3