Impact of the initialization in tree-based fast similarity search techniques

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10045/20234
Información del item - Informació de l'item - Item information
Título: Impact of the initialization in tree-based fast similarity search techniques
Autor/es: Serrano Díaz-Carrasco, Aureo | Micó, Luisa | Oncina, Jose
Grupo/s de investigación o GITE: Reconocimiento de Formas e Inteligencia Artificial | Informática Industrial y Redes de Computadores
Centro, Departamento o Servicio: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | Universidad de Alicante. Instituto Universitario de Investigación Informática
Palabras clave: Fast similarity search techniques | Pivot selection techniques | Tree-based
Área/s de conocimiento: Lenguajes y Sistemas Informáticos
Fecha de publicación: 2011
Editor: Springer Berlin / Heidelberg
Cita bibliográfica: 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
Resumen: 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.
Patrocinador/es: The authors thank the Spanish CICyT for partial support of this work through projects TIN2009-14205-C04-C1, the Ist Programme of the European Community, under the Pascal Network of Excellence, (Ist– 2006-216886), and the program Consolider Ingenio 2010 (Csd2007-00018).
URI: http://hdl.handle.net/10045/20234
ISBN: 978-3-642-24470-4
ISSN: 0302-9743 (Print) | 1611-3349 (Online)
DOI: 10.1007/978-3-642-24471-1_12
Idioma: eng
Tipo: info:eu-repo/semantics/bookPart
Derechos: The original publication is available at www.springerlink.com
Revisión científica: si
Versión del editor: http://dx.doi.org/10.1007/978-3-642-24471-1_12
Aparece en las colecciones:INV - GRFIA - Capítulos de Libros
Investigaciones financiadas por la UE

Archivos en este ítem:
Archivos en este ítem:
Archivo Descripción TamañoFormato 
ThumbnailSIMBAS2011_rev.pdfVersión revisada (acceso abierto)179,16 kBAdobe PDFAbrir Vista previa
ThumbnailSIMBAD2011_final.pdfVersión final (acceso restringido)255,82 kBAdobe PDFAbrir    Solicitar una copia


Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.