Method and system for performing range max/min queries on a data

Details Method and system for performing range max/min queries on a data Method and system for performing range max/min queries on a data

1997-02-27

1999-07-20

Kulik, Paul V.

Data processing: database and file management or data structures

Database design

Data structure types

707 5, G06F 1730

Patent

active

059268204

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.

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: 5442784 (1995-08-01), Powers et al.
patent: 5572644 (1996-11-01), Liaw et al.
patent: 5592666 (1997-01-01), Perez
patent: 5647058 (1997-07-01), Agrawal et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5745894 (1998-04-01), Burrows et al.
patent: 5758353 (1998-05-01), Marguis
patent: 5761529 (1998-06-01), Raji et al.
patent: 5799300 (1998-08-01), Agrawal et al.
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.
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.
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, 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.
A. Yao, On the complexity of maintaining partial sums. SIAM J. Computing, 14(2):277-288, May 1985.

Affiliated with

Also associated with

Rating

Method and system for performing range max/min queries on a data 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 max/min queries on a data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing range max/min queries on a data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1331782