An Efficient Alternative for Deletions in Dynamic Spatial Approximation Trees
Fuente:
Redalyc
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Artículo científico |
| Sprache: | en |
| Veröffentlicht: |
Universidad Nacional de La Plata
2014
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1876456743675887616 |
|---|---|
| author | Fernando Kasián |
| author_facet | Fernando Kasián |
| contents | An Efficient Alternative for Deletions in Dynamic Spatial Approximation Trees Fernando Kasián Verónica Ludueña Nora Reyes Patricia Roggero Computación indexing algorithms metric spaces similarity search Multimedia databases 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. 2014 artículo científico 1666-6046 https://www.redalyc.org/articulo.oa?id=638067273003 en http://www.redalyc.org/revista.oa?id=6380 Journal of Computer Science and Technology application/pdf Universidad Nacional de La Plata Journal of Computer Science and Technology (Argentina) Num.01 Vol.14 |
| format | Artículo científico |
| id | redalyc_638067273003 |
| institution | Redalyc |
| language | en |
| publishDate | 2014 |
| publisher | Universidad Nacional de La Plata |
| spellingShingle | An Efficient Alternative for Deletions in Dynamic Spatial Approximation Trees Fernando Kasián Computación indexing algorithms metric spaces similarity search Multimedia databases An Efficient Alternative for Deletions in Dynamic Spatial Approximation Trees Fernando Kasián Verónica Ludueña Nora Reyes Patricia Roggero Computación indexing algorithms metric spaces similarity search Multimedia databases 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. 2014 artículo científico 1666-6046 https://www.redalyc.org/articulo.oa?id=638067273003 en http://www.redalyc.org/revista.oa?id=6380 Journal of Computer Science and Technology application/pdf Universidad Nacional de La Plata Journal of Computer Science and Technology (Argentina) Num.01 Vol.14 |
| title | An Efficient Alternative for Deletions in Dynamic Spatial Approximation Trees |
| topic | Computación indexing algorithms metric spaces similarity search Multimedia databases |
| url | https://www.redalyc.org/articulo.oa?id=638067273003 |