New Dynamic Metric Indices for Secondary Memory
Gonzalo Navarro and Nora Reyes
Metric indices support efficient similarity searches in metric spaces. This
problem is central to many applications, including multimedia databases and
repositories handling complex objects. Most metric indices are designed for
main memory, and also most of them are static, that is, do not support
insertions and deletions of objects.
In this article we introduce new metric indices for secondary memory that
support updates, that is, they are dynamic. First, we show how the dynamic and
memory-based Dynamic Spatial Approximation Tree (DSAT) can be extended
operate on secondary memory. Second, we design a dynamic and
secondary-memory-based version of the static List of Clusters (LC),
which performs well on
high-dimensional spaces. The new structure is called Dynamic LC (DLC).
Finally, we combine the DLC with the in-memory version of DSAT to create a
structure, Dynamic Set of Clusters (DSC), which improves upon the other
two in various cases. We compare the new structures with the state of the art,
showing that they are competitive and outstand in several scenarios,
especially on spaces of medium and high dimensionality.