Systems, methods, and computer program products to reduce computer processing in grid cell size determination for indexing of multidimensional databases
First 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, wherein the levels represent partitions of space at various resolutions of said grids, and wherein a same grid cell size is used for cells of a grid at one level of said levels;
sampling 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, wherein grid cell sizes are estimated on subsequent levels based on sampled grid cell sizes at two or more levels, wherein said number of index entries for said at least one geometric shape represent a number of overlapping grid cells for said at least one geometric shape;
for each said grid;
collecting statistics on a per-level basis to generate information for each said level;
determining an index performance indicator with said information from each said level; and
determining an efficient number of said index entries in said multidimensional database using said index performance indicator to efficiently index said data in said multidimensional database.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
6 Claims
-
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, wherein the levels represent partitions of space at various resolutions of said grids, and wherein a same grid cell size is used for cells of a grid at one level of said levels; sampling 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, wherein grid cell sizes are estimated on subsequent levels based on sampled grid cell sizes at two or more levels, wherein said number of index entries for said at least one geometric shape represent a number of overlapping grid cells for said at least one geometric shape; for each said grid; collecting statistics on a per-level basis to generate information for each said level; determining an index performance indicator with said information from each said level; and determining an efficient number of said index entries in said multidimensional database using said index performance indicator to efficiently index said data in said multidimensional database. - View Dependent Claims (2)
-
-
3. A computer system including a memory 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 being used, wherein the levels represent partitions of space at various resolutions of said grids, and wherein a same grid cell size is used for cells of a grid at one level of said levels; said grid 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 wherein grid cell sizes are estimated on subsequent levels based on sampled grid cell sizes at two or more levels, wherein said number of index entries for said at least one geometric shape represent a number of overlapping grid cells for said at least one geometric shape; for each said grid; statistics being collected on a per-level basis to generate information for each said level; an index performance indicator being determined with said information from each said level; and an efficient number of said index entries in said multidimensional database being determined using said index performance indicator to efficiently index said data in said multidimensional database. - View Dependent Claims (4)
-
-
5. 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, wherein the levels represent partitions of space at various resolutions of said grids, and wherein a same grid cell size 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, wherein grid cell sizes are estimated on subsequent levels based on sampled grid cell sizes at two or more levels, wherein said number of index entries for said at least one geometric shape represent a number of overlapping grid cells for said at least one geometric shape; for each said grid; said computer instructions collect statistics on a per-level basis to generate information for each said level; said computer instructions determine an index performance indicator with said information from each said level; and said computer instructions determine an efficient number of said index entries in said multidimensional database using said index performance indicator to efficiently index said data in said multidimensional database. - View Dependent Claims (6)
-
Specification