An Efficient Indexing Structure for Multidimensional Categorical Range Aggregation Query

• Jian Yang,
• Chongchong Zhao,
• Chao Li,
• Chunxiao Xing,

Vol. 13, No. 2, February 27, 2019
10.3837/tiis.2019.02.007, Download Paper (Free):

• Categorical
• Multidimensional Indexing
• Query
• MCRI-Tree

Abstract

Categorical range aggregation, which is conceptually equivalent to running a range aggregation query separately on multiple datasets, returns the query result on each dataset. The challenge is when the number of dataset is as large as hundreds or thousands, it takes a lot of computation time and I/O. In previous work, only a single dimension of the range restriction has been solved, and in practice, more applications are being used to calculate multiple range restriction statistics. We proposed MCRI-Tree, an index structure designed to solve multi-dimensional categorical range aggregation queries, which can utilize main memory to maximize the efficiency of CRA queries. Specifically, the MCRI-Tree answers any query in O(nkn-1) I/Os (where n is the number of dimensions, and k denotes the maximum number of pages covered in one dimension among all the n dimensions during a query). The practical efficiency of our technique is demonstrated with extensive experiments.

Statistics

Cite this article