A log square average case algorithm to make insertions in fast similarity search
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/53301
Título: | A log square average case algorithm to make insertions in fast similarity search |
---|---|
Autor/es: | Micó, Luisa | Oncina, Jose |
Grupo/s de investigación o GITE: | Reconocimiento de Formas e Inteligencia Artificial |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Palabras clave: | Similarity search | Metric space | Dynamic index | Insertions |
Área/s de conocimiento: | Lenguajes y Sistemas Informáticos |
Fecha de publicación: | 1-jul-2012 |
Editor: | Elsevier |
Cita bibliográfica: | Pattern Recognition Letters. 2012, 33(9): 1060-1065. doi:10.1016/j.patrec.2012.01.016 |
Resumen: | To speed up similarity based searches many indexing techniques have been proposed in order to address the problem of efficiency. However, most of the proposed techniques do not admit fast insertion of new elements once the index is built. The main effect is that changes in the environment are very costly to be taken into account. In this work, we propose a new technique to allow fast insertions of elements in a family of static tree-based indexes. Unlike other techniques, the resulting index is exactly equal to the index that would be obtained by building it from scratch. Therefore there is no performance degradation in search time. We show that the expected number of distance computations (and the average time complexity) is bounded by a function that grows with log2(n) where n is the size of the database. In order to check the correctness of our approach some experiments with artificial and real data are carried out. |
Patrocinador/es: | This work has been supported in part by Grants TIN2009-14205-C04-01 from the Spanish CICYT (Ministerio de Ciencia e Innovación), the IST Programme of the European Community, under the Pascal Network of Excellence, IST-2002-506778, and the program CONSOLIDER INGENIO 2010 (CSD2007-00018). |
URI: | http://hdl.handle.net/10045/53301 |
ISSN: | 0167-8655 (Print) | 1872-7344 (Online) |
DOI: | 10.1016/j.patrec.2012.01.016 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2012 Elsevier B.V. |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1016/j.patrec.2012.01.016 |
Aparece en las colecciones: | INV - GRFIA - Artículos de Revistas Investigaciones financiadas por la UE |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2012_Mico_Oncina_PatRecLet_final.pdf | Versión final (acceso restringido) | 511,26 kB | Adobe PDF | Abrir Solicitar una copia |
2012_Mico_Oncina_PatRecLet_preprint.pdf | Preprint (acceso abierto) | 193,34 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.