@article {16892,
	title = {Improved search heuristics for the sa-tree},
	journal = {Pattern Recognition Letters},
	volume = {24},
	year = {2003},
	month = {2003/11//},
	pages = {2785 - 2795},
	abstract = {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 {\textquotedblleft}node{\textquotedblright} elements are monotonically non-decreasing.},
	keywords = {distance-based indexing, Metric spaces, Nearest neighbor algorithms},
	isbn = {0167-8655},
	doi = {10.1016/S0167-8655(03)00122-3},
	url = {http://www.sciencedirect.com/science/article/pii/S0167865503001223},
	author = {Hjaltason,G{\i}́sli R. and Samet, Hanan}
}
