Method for determining an optimal grid index specification for multidimensional data

• US 7,389,283 B2
• Filed: 12/07/2004
• Issued: 06/17/2008
• Est. Priority Date: 12/07/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Adler, David William
• Primary Examiner(s): Pham; Khanh B.
• Assistant Examiner(s): Le; Jessica N
• Application Number:
  US11/007,132
• Publication Number:
  US 20060129529A1
• Time in Patent Office: 1,288 Days
• Field of Search: 707/1, 707/6, 707/100, 707/104
• 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:

creating a geometry histogram by scanning geometries to determine minimum and maximum extents, computing bucket sizes of buckets, and scanning the geometries to generate the geometry histogram using the buckets, wherein the bucket sizes are computed by dividing a size of a largest maximum bounding rectangle into a number of intervals;

computing a set of query region sizes;

for each size of a set of query region sizes, computing a minimum performance indicator by, for each of the buckets of the geometry histogram, estimating a number of index entries for each of multiple grid size levels by computing bucket intersections; and

returning an optimal grid size for each size of the query region.

2. The method of claim 1, further comprising:

computing a set of grid sizes at a first level of the multiple grid size levels.

3. The method of claim 2, wherein computing the minimum performance indicator further comprises:

computing a matrix of grid size levels for the first level;

for each matrix row of the matrix,

computing the number of index entries; and

in response to determining that the number of index entries is less than minimum number of index entries, setting the minimum number of index entries to the determined number of index entries.

4. The method of claim 3, wherein computing the number of index entries further comprises:

computing estimated intersections for each of multiple grid sizes.