 |
|
|
|
|
|
 Title: |
US5890151:
Method and system for performing partial-sum queries on a data cube
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Agrawal, Rakesh; San Jose, CA
Bruck, Jehoshua; La Canada, CA
Ho, Ching-Tien; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1999-03-30
/ 1997-05-09
|
| Application Number: |
US1997000853750
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S2P1; G06F17/30S2P7; G06F17/30S4P4P1A;
|
| U.S. Class: |
Current:
707/005;
707/001;
707/002;
707/003;
707/004;
707/006;
707/100;
707/200;
715/234;
Original:
707/005;
707/001;
707/002;
707/003;
707/004;
707/006;
707/100;
707/200;
707/503;
707/504;
354/342;
364/282.1;
364/282.3;
|
| Field of Search: |
707/005,1,2,3,4,100,200,503,504
345/342
364/282.1,282.3
|
| Priority Number: |
| 1997-05-09 |
US1997000853750 |
|
| Abstract: |
Disclosed is a method and system for performing a partial-sum query in a database in which the data is represented as a multi-dimensional data cube. The data cube is partitioned into multi-dimensional blocks. One or more covering codes are then selected for each block, and a group of partial-sums is computed for each block based on its covering codes. At query time, the query result is generated by combining the partial-sums for those blocks that intersect with the query subset. To improve the query response time and reduce system storage requirements, the covering codes are preferably augmented as single-weight extended covering codes or composition-extended covering codes. Also, a second partial-sum may also be computed for each block to efficiently find its partial sum, based on the block's first partial-sums and the bit-position differences between selected codewords for the block and bit strings representing the cell indexes of the blocks intersecting with the query subset.
|
| Attorney, Agent or Firm: |
Tran, Khanh Q. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Corrielus, Jean M.
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 42 claims |
What is claimed is:
1. A method for performing a partial-sum query in a database represented as a d-dimensional data cube, the data cube having a plurality of cells each having a value and identified by an index, the partial-sum query corresponding to a subset I of the data cube, the method comprising the steps of:
- partitioning the data cube into a plurality of d-dimensional blocks;
- selecting at least one covering code for each block i of the data cube, each covering code having a code length that is a function of the size of the block i;
- computing a plurality of first sums for the block i, based on the respective covering codes selected for the block i; and
- generating a partial-sum result from the first sums corresponding to those blocks of the data cube that intersect with the subset I.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 44 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other References: |
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.
A. Yao, On the complexity of maintaining partial sums. SIAM J. Computing, 14(2): 277-288, May 1985.
(12 pages)
Cited by 3 patents
G. D. Cohen, et al., Covering radius 1985-1994. Appeared in Journal of Applicable Algebra in Engineering, Communication and Computing, special issue, 1996.
G. D. Cohen, et al. Further results on the covering radius of codes. IEEE Trans. Information Theory, IT-32(5):680-694, Sept. 1986.
(15 pages)
R. L. Graham et al., On the covering radius of codes. IEEE Trans. Information Theory, IT-31(3):385-401, May 1985.
(17 pages)
C. T. Ho et al., Range Queries in OLAP Data Cubes, IBM Research Report, To be presented at 1997 ACM SIGMOD Internation Conference on Management of Data, May 13, 1997-May 15, 1997 at Tucson, Az.
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, Santiago, 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.
A. Gupta et al., Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21st VLDB Conf. Zurich, Switzerland, 1995, pp. 358-369.
V. Harinarayan et al., Implementing data cubes efficiently. In Proc. of the ACM SIGMOD Conference on Management of Data, Jun. 1996.
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.
E. F. Codd, Providing OLAP (on-line Analytical Processing) to user Analysis: An IT mandate. Technical report, E.F. Codd and Associates, 1993.
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.
|
|
 Nominate this for the Gallery...
|
|
