# US 2003/0212677 A1 · Systems, methods, and computer program products to reduce computer processing in grid cell size determination for indexing of multidimensional databases

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0212677 A1
- Document ID: US20030212677A1
- Status: Published application
- Kind: A1
- Application number: 10/144,389
- Filed: 2002-05-10
- Published: 2003-11-13
- Earliest claimed: 2002-05-10
- Assignees: International Business Machines Corporation
- Inventors: Ying Chen; Fang Yan Rao; Knut Stolze
- Web page: https://patentgrep.com/patent/US20030212677A1

## CPC

- G06F 16/2264: {Multidimensional index structures}
- Y10S 707/99933: Query processing, i.e. searching
- Y10S 707/99934: Query formulation, input preparation, or translation
- Y10S 707/99942: Manipulating data structure, e.g. compression, compaction, compilation
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## 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

### Claim 1

A computer-implemented method for reducing a number of index entries for efficiently indexing data in a multidimensional database, said multidimensional database having at least one associated grid, comprising:
using levels associated with two or more said grids;
sampling said grid at a first said level;
determining sizes for said sampled grid;
optimizing at least one said size for said sampled grid;
estimating said number of index entries associated with two or more said levels; and
using 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1 further wherein estimating said number of said index entries comprises;
determining a said size for said grids for each of at least two said levels;
determining a ratio of said sizes of said grids of said at least two levels; and
using said ratio to estimate said number of index entries.

### Claim 4

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;
said two or more grids being sampled at a first said level said sampled grid having sizes;
at least one said sampled grid size being optimized;
an estimated said number of index entries associated with two or more said levels; 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.

### Claim 5 (depends on 4)

The computer system of claim 4 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.

### Claim 6 (depends on 4)

The computer system of claim 4 further 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; and
said ratio being used to estimate said number of index entries.

### Claim 7

An article of manufacture comprising a computer usable 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;
said computer instructions sample said grid at a first said level;
said computer instructions determine sizes for said sampled grid;
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; 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.

### Claim 8 (depends on 7)

The article of manufacture of claim 7 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.

### Claim 9 (depends on 7)

The article of manufacture of claim 7 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; and
said computer instructions use said ratio to estimate said number of index entries.
