Dynamic Spatial Approximation Trees for Massive Data
Gonzalo Navarro and Nora Reyes
Metric space searching is an emerging technique to address the problem of
efficient similarity searching in many applications, including multimedia
databases and other repositories handling complex objects. Although promising,
the metric space approach is still immature in several aspects that are well
established in traditional databases. In particular, most indexing schemes are
not dynamic, that is, few of them tolerate insertion of elements at reasonable
cost over an existing index and only few indexes are designed to work
efficiently in secondary memory.
In this paper we introduce a secondary-memory variant of the {\em Dynamic
Spatial Approximation Tree}, which has shown to be competitive in main
memory. The resulting index handles well the secondary memory
scenario and is competitive with the state of the art, becoming a useful
alternative in a wide range of database applications. Moreover, our ideas are
applicable to other secondary-memory trees where there is little control over
the tree shape.