Dynamic Spatial Approximation Trees

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 static, that is, few of them tolerate insertion or deletion of elements at reasonable cost over an existing index.

The Spatial Approximation Tree (sa-tree) [VLDBJ 2002] has been experimentally shown to provide a good tradeoff between construction cost, search cost, and space requirement. However, the sa-tree is static, which renders it unsuitable for many database applications.

In this paper we study different methods to handle insertions and deletions on the sa-tree at low cost. In many cases, the dynamic construction (by successive insertions) is even faster than the previous static construction, and both are similar elsewhere. In addition, the dynamic version significantly improves the search performance of sa-trees in virtually all cases. The result is a much more practical data structure that can be useful in a wide range of database applications.