Serrano Díaz-Carrasco, Aureo, Micó, Luisa, Oncina, Jose
Impact of the initialization in tree-based fast similarity search techniques
SERRANO, Aureo; MICÓ, Luisa; ONCINA, Jose. "Impact of the initialization in tree-based fast similarity search techniques". En: Similarity based pattern recognition : First International Workshop, SIMBAD 2011, Venice, Italy, September 28-30, 2011 / Marcello Pelillo, Edwind R. Hancock (Eds.). Berlin : Springer, 2011. (Lecture Notes in Computer Science; 7005/2011). ISBN 978-3-642-24470-4, pp. 163-176
URI: http://hdl.handle.net/10045/20234
DOI: 10.1007/978-3-642-24471-1_12
ISSN: 0302-9743 (Print)
ISBN: 978-3-642-24470-4
Abstract: 
Many fast similarity search techniques relies on the use of pivots (specially selected points in the data set). Using these points, specific structures (indexes) are built speeding up the search when queering. Usually, pivot selection techniques are incremental, being the first one randomly chosen. This article explores several techniques to choose the first pivot in a tree-based fast similarity search technique. We provide experimental results showing that an adequate choice of this pivot leads to significant reductions in distance computations and time complexity. Moreover, most pivot tree-based indexes emphasizes in building balanced trees. We provide experimentally and theoretical support that very unbalanced trees can be a better choice than balanced ones.
Keywords:Fast similarity search techniques, Pivot selection techniques, Tree-based
Springer Berlin / Heidelberg
info:eu-repo/semantics/bookPart