Enlarging Nodes to Improve Dynamic Spatial Approximation Trees
Marcelo Barroso, Nora Reyes, and Rodrigo Paredes
The metric space model allows abstracting many similarity search
problems. Similarity search has multiple
applications especially in the multimedia databases area. The idea is to
index the database so as to accelerate similarity queries. Although there
are several promising indexes, few
of them are dynamic, i.e., once created very few allow to perform
insertions and deletions of elements at a reasonable cost.
The Dynamic Spatial Approximation Trees (DSA-trees) have shown
to be a suitable data structure for searching high dimensional metric
spaces or queries with low selectivity (i.e., large radius), and are also
completely dynamic.
The performance of DSA-trees is directly related to the amount of
backtracking
in search time. To boost the performance in this data structure a
sufficient condition is to maintain in the nodes elements
close-to-each-other. In this work we propose to obtain a new data structure
for searching
in metric spaces, based on the DSA-trees, which holds its virtues
and
takes advantage of element clusters, which are present in many metric
spaces, and
can also make better use of available memory to improve searches. In fact,
we use these element clusters to improve the spatial approximation.