A log square average case algorithm to make insertions in fast similarity search
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/53301
Title: | A log square average case algorithm to make insertions in fast similarity search |
---|---|
Authors: | Micó, Luisa | Oncina, Jose |
Research Group/s: | Reconocimiento de Formas e Inteligencia Artificial |
Center, Department or Service: | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos |
Keywords: | Similarity search | Metric space | Dynamic index | Insertions |
Knowledge Area: | Lenguajes y Sistemas Informáticos |
Issue Date: | 1-Jul-2012 |
Publisher: | Elsevier |
Citation: | Pattern Recognition Letters. 2012, 33(9): 1060-1065. doi:10.1016/j.patrec.2012.01.016 |
Abstract: | 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. |
Sponsor: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Rights: | © 2012 Elsevier B.V. |
Peer Review: | si |
Publisher version: | http://dx.doi.org/10.1016/j.patrec.2012.01.016 |
Appears in Collections: | INV - GRFIA - Artículos de Revistas Research funded by the EU |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2012_Mico_Oncina_PatRecLet_final.pdf | Versión final (acceso restringido) | 511,26 kB | Adobe PDF | Open Request a copy |
2012_Mico_Oncina_PatRecLet_preprint.pdf | Preprint (acceso abierto) | 193,34 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.