An efficient alternative for deletions in dynamic spatial approximation trees
Metric space searching is an emerging technique to address the problem of similarity searching in many applications. In order to efficiently answer similarity queries, the database must be indexed. In some interesting real applications dynamism is an indispensable property of the index. There are v...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2014
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/34547 http://journal.info.unlp.edu.ar/wp-content/uploads/JCST-Apr14-6.pdf |
| Aporte de: |
| id |
I19-R120-10915-34547 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Informáticas multimedia databases metric spaces similarity search indexing algorithms |
| spellingShingle |
Ciencias Informáticas multimedia databases metric spaces similarity search indexing algorithms Kasián, Fernando Ludueña, Verónica Reyes, Nora Susana Roggero, Patricia An efficient alternative for deletions in dynamic spatial approximation trees |
| topic_facet |
Ciencias Informáticas multimedia databases metric spaces similarity search indexing algorithms |
| description |
Metric space searching is an emerging technique to address the problem of similarity searching in many applications. In order to efficiently answer similarity queries, the database must be indexed. In some interesting real applications dynamism is an indispensable property of the index.
There are very few actually dynamic indexes that support not only searches, but also insertions and deletions of elements. The dynamic spatial approximation tree (DSAT) is a data structure specially designed for searching in metric spaces, which compares favorably against other data structures in high dimensional spaces or queries with low selectivity.
Insertions are efficient and easily supported in DSAT, but deletions degrade the structure over time.
Several methods are proposed to handle deletions over the DSAT. One of them has shown to be superior to the others, in the sense that it permits controlling the expected deletion cost as a proportion of the insertion cost and searches does not overly degrade after several deletions.
In this paper we propose and study a new alternative deletion method, based on the better existing strategy. The outcome is a fully dynamic data structure that can be managed through insertions and deletions over arbitrarily long periods of time without any significant reorganization. |
| format |
Articulo Articulo |
| author |
Kasián, Fernando Ludueña, Verónica Reyes, Nora Susana Roggero, Patricia |
| author_facet |
Kasián, Fernando Ludueña, Verónica Reyes, Nora Susana Roggero, Patricia |
| author_sort |
Kasián, Fernando |
| title |
An efficient alternative for deletions in dynamic spatial approximation trees |
| title_short |
An efficient alternative for deletions in dynamic spatial approximation trees |
| title_full |
An efficient alternative for deletions in dynamic spatial approximation trees |
| title_fullStr |
An efficient alternative for deletions in dynamic spatial approximation trees |
| title_full_unstemmed |
An efficient alternative for deletions in dynamic spatial approximation trees |
| title_sort |
efficient alternative for deletions in dynamic spatial approximation trees |
| publishDate |
2014 |
| url |
http://sedici.unlp.edu.ar/handle/10915/34547 http://journal.info.unlp.edu.ar/wp-content/uploads/JCST-Apr14-6.pdf |
| work_keys_str_mv |
AT kasianfernando anefficientalternativefordeletionsindynamicspatialapproximationtrees AT luduenaveronica anefficientalternativefordeletionsindynamicspatialapproximationtrees AT reyesnorasusana anefficientalternativefordeletionsindynamicspatialapproximationtrees AT roggeropatricia anefficientalternativefordeletionsindynamicspatialapproximationtrees AT kasianfernando efficientalternativefordeletionsindynamicspatialapproximationtrees AT luduenaveronica efficientalternativefordeletionsindynamicspatialapproximationtrees AT reyesnorasusana efficientalternativefordeletionsindynamicspatialapproximationtrees AT roggeropatricia efficientalternativefordeletionsindynamicspatialapproximationtrees |
| bdutipo_str |
Repositorios |
| _version_ |
1764820470033547266 |