Abstract

A method for performing a range-sum query in a database, in which the data is represented as a multi-dimensional data cube, is disclosed. The method comprises the steps of: selecting a subset of the dimensions of the data cube; computing a set of prefix-sums along the selected dimensions, based on the aggregate values in the cube corresponding the queried ranges; and generating a range-sum result based on the computed prefix-sums. Two d-dimensional arrays A and P are used for representing the data cube and the prefix-sums of the data cube, respectively. By maintaining the prefix-sum array P of the same size as the data cube, all range queries for a given cube can be answered in constant time, irrespective of the size of the sub-cube circumscribed by a query, using the inverse binary operator of the SUM operator. Alternatively, only auxiliary information for any user-specified fraction of the size of the d-dimensional data cube is maintained, to minimize the required system storage. The answer to a range query may now require access to some cells of the data cube in addition to the auxiliary information, but the average time complexity is still reduced significantly.

Other References

• S. Agarwal et al., On the computation of multidimentional aggregates. In Proc. of the 22nd Int'l Conference on Very Large Databases, pp. 506-521, Mumbai (Bombay), India, Sep. 1996
• B. Chazelle, Lower bounds for orthogonal range searching: II. the arithmetic model. J. ACM, 37(3):439-463, Jul. 1990
• N. Beckmann et al., The R*-tree; an efficient and robust access method for points and rectangles. In Proc. of ACM SIGMOD, pp. 322-331, Atlantic City, NJ, May 1990
• M. Berger et al., An algorithm for point clustering and grid generation. IEEE transactions on Systems, Man and Cybernetics, 21(5):1278-86, 1991
• E. F. Codd, Providing OLAP (on-line analytical processing) to user analysis: An IT mandate. Technical report, E. F. Codd and Associates, 1993
• D. Comer, The ubiquitous B-tree. ACM Computing Surveys, 11(2):121-138, Jun. 1979
• B. Chazelle et al., Computing partial sums in multidimensional arrays. In Proc. of the ACM Symp. on Computational Geometry, pp. 131-139, 1989
• S. Chaudhuri et al., Including group-by in query optimization. In Proc. of the 20th Int'l Conference on Very Large Databases, pp. 354-366, Satiago, Chile, Sep. 1994
• J. Gray et al., Data Cube: A relational aggregation operator generalizing group-by, cross-tabs and sub totals. In Proc. of the 12th Int'l Conference on Data Engineering, pp. 152-159, 1996. (also published as a Microsoft Technical Report, as submitted herewith
• V. Harinarayan et al., Implementing data cubes efficiently. In Proc. of the ACM SIGMOD Conference on Management of Data, Jun. 1996
• J.K. Jain et al., Algorithms for clustering data. Prentice Hall, pp. 55-142 1988
• J. Shafer et al., SPRINT: A scalable parallel classifier for data mining. In Proc. of the 22nd Int'l Conference on Very Large Databases, Bombay, India, Sep. 1996
• A. Shukla et al., Storage estimation for multidimensional aggregates in the presence of hierarchies. In Proc. of the 22nd Int'l Conference on Very Large Databases, pp. 522-531, Mumbai (Bombay), India, Sep. 1996
• J. Srivastava et al., TBSAM: An access method for efficient processing of statistical queries. IEEE Transactions on Knowledge and Data Engineering, 1(4), 1989
• P. M. Vaidya, Space-time tradeoffs for orthogonal range queries. In Proc. 17th Annual ACM Symp. on Theory of Comput., pp. 169-174, 1985
• D. E. Willard et al., Adding range restriction capability to dynamic data structures. J. ACM, 32(3):597-617, 1985
• A. Yao, On the complexity of maintaining partial sums. SIAM J. Computing, 14(2):277-288, May 1985
• A. Gupta et al., Aggregate-query processing in data warehouse environments. In Proceedings of the 21st VLDB Conference, pp. 358-369, Zurich, Switzerland, Sep. 199