Update methods for maintainability of a multidimensional index on non-ordered discrete vector data

Abstract

There are numerous applications nowadays such as bioinformatics, cybersecurity, and social media that demand to efficiently process various types of queries on multidimensional (vector) data with values coming from a non-ordered discrete (categorical) domain for each dimension. The BoND-tree index scheme was recently developed to efficiently process so-called box queries on a large dataset in disk from such a vector data space. The index construction (insertion) and query algorithms were introduced in the original work. To maintain such an efficient index structure for a large dynamic dataset, one has to develop efficient and effective methods to support other operations including deletions, updates, and bulk loading. Although studies on deletions and bulk loading for the BoND-tree have been reported in early work, how to efficiently and effectively update the BoND-tree remains an open problem. In this paper, we first present a general update procedure which covers all scenarios including special cases for insertions and deletions. We then examine two approaches to updating the BoND-tree. The relevant algorithms and experimental evaluations are presented. Our study shows that using the bottom-up update method can provide improved efficiency, comparing to the traditional top-down update method, especially when the number of dimensions for a vector that need to be updated is small. On the other hand, our study also shows that the two update methods have a comparable effectiveness, which indicates that the bottom-up update method is generally more advantageous.