A bulk-loading algorithm for the BoND-Tree index scheme for non-ordered discrete data spaces

Abstract

Recent years have witnessed an increasing demand to process queries on large datasets in Non-ordered Discrete Data Spaces (NDDS) from numerous applications. A number of index trees have been proposed in the literature to support efficient queries on large datasets in an NDDS. However, the conventional tuple-loading method for building the index trees, takes too much time. Although numerous bulk-loading techniques have been proposed to efficiently build index trees for large datasets in Continuous Data Spaces (CDS), limited work has been done to efficiently bulk-load an index tree for a large dataset in an NDDS. In this paper, we present a bulk-loading method to efficiently build the recently proposed BoND-tree for a large dataset in an NDDS. A number of effective strategies have been incorporated in the method to facilitate the efficient bulk-loading process. Experimental results demonstrate that the proposed bulk-loading method is quite promising in efficiently building a BoND-tree for a large non-ordered discrete dataset.