An Efficient Dynamic Version of the Distal Spatial Approximation Trees

Abstract

Metric space indices make searches for similar objects more efficient in various applications, including multimedia databases and other repositories which handle complex and unstructured objects. Although there are a plethora of indexes to speed up similarity searches, the Distal Spatial Approximation Tree (DiSAT) has shown to be very efficient and competitive. Nevertheless, for its construction, we need to know all the database objects beforehand, which is not necessarily possible in many real applications. The main drawback of the DiSAT is that it is a static data structure. That means, once built, it is difficult to insert new elements into it. This restriction rules it out for many exciting applications. In this paper, we overcome this weakness. We propose and study a dynamic version of DiSAT that allows handling lazy insertions and, at the same time, improves its good search performance. Therefore, our proposal provides a good tradeoff between construction cost, search cost, and space requirement. The result is a much more practical data structure that can be useful in a wide range of database applications.