Decomposability of DiSAT for Index Dynamization

Abstract

The Distal Spatial Approximation Tree (DiSAT) is one of the most competitive indexes for exact proximity searching. The absence of parameters, the most salient feature, makes the index a suitable choice for a practitioner. The most serious drawback is the static nature of the index, not allowing further insertions once it is built. On the other hand, there is an old approach from Bentley and Saxe (BS) allowing the dynamization of decomposable data structures. The only requirement is to provide a decomposition operation. This is precisely our contribution, we define a decomposition operation allowing the application of the BS technique. The resulting data structure is competitive against the static counterparts.

Keywords

• similarity search
• dynamism
• metric spaces
• non-conventional databases