A Dynamic Grid File for High-Dimensional Data Cube Storage and Range-Sum Querying

摘要

In this article, the authors propose to use the grid file to store multi-dimensional data cubes and answer range-sum queries. The grid file is enhanced with a dynamic splitting mechanism to accommodate insertions of data. It overcomes the drawback of the traditional grid file in storing uneven data while enjoying its advantages of simplicity and efficiency. The space requirement grows linearly with the dimension of the data cube, compared with the exponential growth of conventional methods that store pre-computed aggregate values for range-sum queries. The update cost is O(I), much faster than the pre-computed data cube approaches, which generally have exponential update cost. The grid file structure can also respond to range queries quickly. They compare it with an approach that uses the R*-tree structure to store the data cube. The experimental results show that the proposed method performs favorably in file size, update speed, construction time, and query response time for both evenly and unevenly distributed data.