Impact of the initialization in tree-based fast similarity search techniques
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/20234
Title: | Impact of the initialization in tree-based fast similarity search techniques |
---|---|
Authors: | Serrano Díaz-Carrasco, Aureo | Micó, Luisa | Oncina, Jose |
Research Group/s: | Reconocimiento de Formas e Inteligencia Artificial | Informática Industrial y Redes de Computadores |
Center, Department or Service: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | Universidad de Alicante. Instituto Universitario de Investigación Informática |
Keywords: | Fast similarity search techniques | Pivot selection techniques | Tree-based |
Knowledge Area: | Lenguajes y Sistemas Informáticos |
Issue Date: | 2011 |
Publisher: | Springer Berlin / Heidelberg |
Citation: | 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 |
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. |
Sponsor: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/bookPart |
Rights: | The original publication is available at www.springerlink.com |
Peer Review: | si |
Publisher version: | http://dx.doi.org/10.1007/978-3-642-24471-1_12 |
Appears in Collections: | INV - GRFIA - Capítulos de Libros Research funded by the EU |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
SIMBAS2011_rev.pdf | Versión revisada (acceso abierto) | 179,16 kB | Adobe PDF | Open Preview |
SIMBAD2011_final.pdf | Versión final (acceso restringido) | 255,82 kB | Adobe PDF | Open Request a copy |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.