 |
|
|
|
|
|
 Title: |
US5799300:
Method and system for performing range-sum queries on a data cube
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Ho, Ching-Tien; San Jose, CA
Srikant, Ramakrishnan; San Jose, CA
|
| Assignee: |
International Business Machines Corporations, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1998-08-25
/ 1996-12-12
|
| Application Number: |
US1996000764564
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S8M; G06F17/30S4P4P1A;
|
| U.S. Class: |
Current:
707/005;
Original:
707/005;
|
| Field of Search: |
707/001,2,3,4,5,6,100,200,503,504
345/342
364/282.1,282.3
001/001
|
| Priority Number: |
| 1996-12-12 |
US1996000764564 |
|
| 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.
|
| Attorney, Agent or Firm: |
Tran, Khanh Q. ;
|
| Primary / Asst. Examiners: |
Amsbury, Wayne; Ho, Ruay Lian
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 36 claims |
What is claimed is:
1. A method for performing a range-sum query in a database in which data include a plurality of attributes and are represented as a d-dimensional data cube having a plurality of cells, the dimensions of the data cube corresponding respectively to the attributes, each cell having an aggregate value of the corresponding data attribute values, and the range-sum query including a range of values for each data attribute, the method comprising the steps of:
- selecting a subset of the dimensions of the data cube;
- computing a plurality of prefix-sums along the selected dimensions, based on the aggregate values corresponding to the ranges of values of the data attributes; and
- generating a range-sum result based on the data represented by the computed prefix-sums.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 56 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| 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.
(25 pages)
Cited by 2 patents
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.
(9 pages)
Cited by 5 patents
[ISI abstract]
B. Chazelle, Lower bounds for orthogonal range searching: II. the arithmetic model. J. ACM, 37(3):439-463, Jul. 1990.
(25 pages)
Cited by 2 patents
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.
(17 pages)
Cited by 49 patents
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.
(21 pages)
Cited by 2 patents
A. Yao, On the complexity of maintaining partial sums. SIAM J. Computing, 14(2):277-288, May 1985.
(12 pages)
Cited by 3 patents
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.
|
|
 Nominate this for the Gallery...
|
|
