System and method for determining an optimal grid index specification for multidimensional data

• US 20060129529A1
• Filed: 12/07/2004
• Published: 06/15/2006
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Adler, David William
• Granted Patent: US 7,389,283 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A system, method, and associated computer product improve the search of multidimensional databases. The present system determines a near-optimal grid index that is used to locate a geometric shape in a spatial database. More particularly, the present system improves the technique of sampling data for defining the grid cell size in a grid for a given data set, minimizing the number times the data set needs to be sampled, thereby reducing the time to compute the cost of alternative grid index parameters.

Claims

1. A method of determining an optimal grid index specification for multidimensional data, comprising:

defining multiple levels associated with one or more grid sizes to support multi-dimensional data that are represented by coordinates;

summarizing the multi-dimensional data as a set of statistics;

defining a query region as a subset of a minimum coordinate and a maximum coordinate of the data coordinates;

estimating the number of index entries based on the query region and the set of statistics of the multi-dimensional data; and

returning the grid sizes of all levels that produce a minimum number of index entries.

2. The method of claim 1, further comprising determining query region sizes of a set of query regions based on the set of statistics.

3. The method of claim 2, further comprising computing a set of grid sizes at a first level of the multiple levels.

4. The method of claim 3, further comprising computing grid sizes for at least one additional level of the multiple levels based on the first level.

5. The method of claim 4, wherein for each query region of the set of query regions estimating a minimum number of index entries for each of the first level and the additional level, to identify optimal grid sizes.

6. The method of claim 3, wherein computing grid sizes for the at least one additional level comprises computing grid sizes for a second level and a third level of the multiple levels, based on the first level.

7. The method of claim 6, wherein for each query region of the set of query regions estimating a minimum number of index entries for each of the first level, the second level, and the third level, to identify optimal grid sizes.

8. The method of claim 1, wherein determining the sizes of the set of query regions comprises defining values for the grid sizes for each of the levels.

9. The method of claim 1, wherein the one or more grid sizes comprise increasing grid sizes.

20. The system of claim 1, wherein the index-solver module further determines query region sizes of a set of query regions based on the set of statistics.

10. A computer program product having a plurality of instruction codes for determining an optimal grid index specification for multidimensional data, comprising:

a set of instruction codes for defining multiple levels associated with one or more grid sizes to support multi-dimensional data that are represented by coordinates;

a second set of instruction codes for summarizing the multi-dimensional data as a set of statistics;

a third set of instruction codes for defining a query region as a subset of a minimum coordinate and a maximum coordinate of the data coordinates;

a fourth set of instruction codes for estimating the number of index entries based on the query region and the set of statistics of the multi-dimensional data; and

a fifth set of instruction codes for returning the grid sizes of all levels that produce a minimum number of index entries.

11. The computer program product of claim 10, further comprising a sixth set of instruction codes for determining query region sizes of a set of query regions based on the set of statistics.

12. The computer program product of claim 11, further comprising a seventh set of instruction codes for computing a set of grid sizes at a first level of the multiple levels.

13. The computer program product of claim 12, further comprising an eight set of instruction codes for computing grid sizes for at least one additional level of the multiple levels based on the first level.

14. The computer program product of claim 13, wherein for each query region of the set of query regions a ninth set of instruction codes estimates a minimum number of index entries for each of the first level and the additional level, to identify~optimal grid sizes.

15. The computer program product of claim 14, wherein the eight set of instruction codes computes grid sizes for the at least one additional level by computing grid sizes for a second level and a third level of the multiple levels, based on the first level.

16. The computer program product of claim 15, wherein for each query region of the set of query regions a tenth set of instruction codes estimates a minimum number of index entries for each of the first level, the second level, and the third level, to identify optimal grid sizes.

17. The computer program product of claim 10, wherein the sixth set of instruction codes determines the sizes of the set of query regions by defining values for the grid sizes for each of the levels.

18. The computer program product of claim 10, wherein the one or more grid sizes comprise increasing grid sizes.

19. A system for determining an optimal grid index specification for multidimensional data, comprising:

a multidimensional data cube that defines multiple levels associated with one or more grid sizes to support multi-dimensional data that are represented by coordinates; and

an index-solver module that;

summarizes the multi-dimensional data as a set of statistics|;

defines a query region as a subset of a minimum coordinate and a maximum coordinate of the data coordinates;

estimates the number of index entries based on the query region and the set of statistics of the multi-dimensional data; and

returns the grid sizes of all levels that produce a minimum number of index entries.