Systems, methods, and computer program products to reduce computer processing in grid cell size determination for indexing of multidimensional databases

• US 7,143,098 B2
• Filed: 05/10/2002
• Issued: 11/28/2006
• Est. Priority Date: 05/10/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Ying, Stolze, Knut, Rao, Fang Yan
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US10/144,389
• Publication Number:
  US 20030212677A1
• Time in Patent Office: 1,663 Days
• Field of Search: 707100-1041, 707/103.R, 707/3, 707/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Systems, methods, and computer products that improve the techniques used to search multidimensional databases over techniques of the past. The preferred embodiment of the present invention advantageously improves the technique of determining a grid index that is used to locate a geometric shape in a spatial database. More particularly, the preferred embodiment of the present invention improves the technique of sampling data for defining the grid cell size in a grid for a given data set, thereby improving the grid indexing process that locates a particular minimum-bounding rectangle and the associated geometric shape.

Claims

1. A computer-implemented method for identifying related data that is associated with selected data, said selected data that is implemented in a subject multidimensional database, said selected data being obtained by use of index data that is implemented in an index multidimensional database, comprising:

identifying related index data from said index data by creating a query and executing said query against said index data; and

identifying said related data from said selected data by use of said related index data.

2. The computer-implemented method of claim 1 further comprising:

determining an index performance indicator associated with said optimized size; and

using said index performance indicator to determine said efficient number of index entries by use of said index performance indicator.

3. A computer system that reduces a number of index entries for efficiently indexing data in a multidimensional database, said multidimensional database having at least one associated grid, comprising:

two or more said grids that are associated with levels, wherein the levels represent partitions of space at various resolutions of said grids, and wherein each grid cell has a same grid cell size that is used for cells of a grid at one level of said levels;

said two or more grids being sampled at a first said level to produce an estimated number of index entries for at least one geometric shape as if said at least one geometric shape were indexed at said first level while determining sizes for said sampled grid at each level;

at least one said sampled grid size being optimized;

an estimated said number of index entries associated with two or more said levels, comprising;

a said size for said grids for each of at least two said levels;

a ratio of said sizes of said grids of said at least two levels, wherein said ratio represents at least said size at a level i compared to said size at a level (i−

1) of said at least two levels; and

said ratio being used to estimate said number of index entries; and

said at least one optimized size and said estimated number of index entries that determine an efficient number of said index entries in said multidimensional database thereby efficiently indexing said data in said multidimensional database.

4. The computer system of claim 3 further comprising an index performance indicator that is associated with said optimized size and that is used to determine said efficient number of index entries by use of said index performance indicator.

5. An article of manufacture comprising a computer usable storage medium embodying one or more instructions executable by said computer for causing said computer to reduce a number of index entries for efficiently indexing data in a multidimensional database, said multidimensional database having at least one associated grid, wherein:

said computer instructions use levels associated with two or more said grids, wherein the levels represent partitions of space at various resolutions of said grids, and wherein each grid cell has a same grid cell size that is used for cells of a grid at one level of said levels;

said computer instructions sample said grid at a first said level to produce an estimated number of index entries for at least one geometric shape as if said at least one geometric shape were indexed at said first level while determining sizes for said sampled grid at each level;

said computer instructions optimize at least one said size for said sampled grid;

said computer instructions estimate said number of index entries associated with two or more said levels, wherein;

said computer instructions determine a said size for said grids for each of at least two said levels;

said computer instructions determine a ratio of said sizes of said grids of said at least two levels, wherein said ratio represents at least said size at a level i compared to said size at a level (i−

1) of said at least two levels; and

said computer instructions use said ratio to estimate said number of index entries; and

said computer instructions use said at least one optimized size and said estimated number of index entries to determine an efficient number of said index entries in said multidimensional database thereby efficiently indexing said data in said multidimensional database.

6. The article of manufacture of claim 5 wherein:

said computer instructions determine an index performance indicator associated with said optimized size; and

said computer instructions use said index performance indicator to determine said efficient number of index entries by use of said index performance indicator.