Method and system for performing range-sum queries on a data cub

Details Method and system for performing range-sum queries on a data cub Method and system for performing range-sum queries on a data cub

1996-12-12

1998-08-25

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

G06F 1730

Patent

active

057993009

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.

REFERENCES:
patent: 5257365 (1993-10-01), Powers et al.
patent: 5359724 (1994-10-01), Earle
patent: 5404512 (1995-04-01), Powers et al.
patent: 5404513 (1995-04-01), Powers et al.
patent: 5499360 (1996-03-01), Barbara et al.
patent: 5604854 (1997-02-01), Glassey
patent: 5729662 (1998-03-01), Rozmus
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.
B. Chazelle, Lower bounds for orthogonal range searching: II. the arithmetic model. J. ACM, 37(3):439-463, Jul. 1990.
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. 1995.

Affiliated with

Also associated with

Rating

Method and system for performing range-sum queries on a data cub does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for performing range-sum queries on a data cub, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing range-sum queries on a data cub will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-46782