 |
|
|
|
|
|
 Title: |
US5926820:
Method and system for performing range max/min 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
Megiddo, Nimrod; Palo Alto, 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-07-20
/ 1997-02-27
|
| Application Number: |
US1997000808046
|
| IPC Code: |
Advanced:
G06F 17/30;
Core:
more...
IPC-7:
G06F 17/30;
|
| ECLA Code: |
G06F17/30S2P3; G06F17/30S2P7; G06F17/30S4P4P1A;
|
| U.S. Class: |
Current:
707/200;
707/005;
Original:
707/200;
707/005;
|
| Field of Search: |
707/001,2,3,4,5,6,200,503,504
|
| Priority Number: |
| 1997-02-27 |
US1997000808046 |
|
| Abstract: |
A method for performing a range max/min query in a database, in which the data is represented as a multi-dimensional data cube, is disclosed. The method comprises the steps of: partitioning the data cube into multi-level multi-dimensional blocks which are represented by a tree structure; determining the index to the maximum or minimum value for each block; generating a range max/min result from the values of the cells selected from the cells in the query region Q, and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q, using the tree structure and determined cell indexes. A branch-and-bound method is used to repeatedly reduce the size of the query region from a cell within the region, based on sub-trees whose roots are cells in the region. To further improve the method performance, one or more reference arrays may also be used to quickly traverse the tree in determining the max/min cell indexes.
|
| Attorney, Agent or Firm: |
Tran, Khanh Q. ;
|
| Primary / Asst. Examiners: |
Kulik, Paul V.; Wallace, Jr., Michael J.
|
| 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 max/min query in a database represented as a d-dimensional data cube having a plurality of cells, each cell having a value and identified by an index, the range max/min query corresponding to a region Q of the data cube, the method comprising the steps of:
- partitioning the data cube into a plurality of multi-level d-dimensional blocks;
- representing the blocks as a multi-level tree structure having a plurality of nodes, the n-level nodes of the tree corresponding respectively to the n-level blocks;
- for each block, determining the index of a cell with a max/min value among the cells in the block;
- storing the determined cell indexes for the blocks into the corresponding nodes; and
- generating a range max/min result from the values of the cells selected from the cells in the query region Q and the cells referenced by the indexes at the nodes corresponding to the cells in the query region Q.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 54 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G1999-429163
DERABS G1999-429163
|
| 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.
J. L. Bentley, Multidimensional divide and conquer. Comm. ACM, 23(4):214-229, 1980.
(16 pages)
L. G. Mitten, Branch-and-Bound Methods: General Formulation and Properties, University of British Columbia, Vancouver, Canada, (Received Nov. 12, 1968).
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.
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, 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.
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
|
|
 Nominate this for the Gallery...
|
|
