Dynamic Spatial Approximation Trees with clusters for secondary memory

Abstract

Metric space searching is an emerging technique to address the problem of e cient 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. From the few dynamic indexes, even fewer work well in secondary memory. That is, most of them need the index in main memory in order to operate e ciently. In this paper we introduce a secondary-memory variant of the Dynamic Spatial Approximation Tree with Clusters (DSACL-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. The resulting index is a much more practical data structure that can be useful in a wide range of database applications.