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
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:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
SIMBAS2011_rev.pdf | Versión revisada (acceso abierto) | 179,16 kB | Adobe PDF | Abrir Vista previa |
SIMBAD2011_final.pdf | Versión final (acceso restringido) | 255,82 kB | Adobe PDF | Abrir Solicitar una copia |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.