DETERMINING AN OPTIMAL GRID INDEX SPECIFICATION FOR MULTIDIMENSIONAL DATA
First Claim
1. A computer program product having a plurality of instruction codes stored in a computer-usable storage medium executed by a computer for performing the 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.
1 Assignment
0 Petitions
Accused Products
Abstract
A system 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.
83 Citations
8 Claims
-
1. A computer program product having a plurality of instruction codes stored in a computer-usable storage medium executed by a computer for performing the 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. - View Dependent Claims (2, 3, 4)
-
-
5. A system for determining an optimal grid index specification for multidimensional data, comprising:
-
a processor; and a memory coupled to the processor, the memory comprising a plurality of instruction codes executable by the processor for; 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. - View Dependent Claims (6, 7, 8)
-
Specification