System and computer program products to improve indexing of multidimensional databases
View Patent ↗Systems 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 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.
1. A computer system for determining a grid index in a multidimensional database, comprising:
a memory;
a grid that is associated with said multidimensional database and that is sampled;
an index performance indicator associated with said sampled grid; and
hardware for:
generating said index performance indicator that is used to determine said grid index, wherein said index performance indicator describes a number of index entries that are evaluated in said grid index during a search of said multidimensional database; and
determining sizes for at least one grid cell associated with said sampled grid based on said index performance indicator.
2. The computer system of claim 1 , wherein said index performance indicator represents a minimum number of index entries that are evaluated.
3. The computer system of claim 1 further comprising said index performance indicator that is determined by using a key generator function.
4. The computer system of claim 3 further comprising:
said multidimensional database that is a spatial database and represents at least one geometric shape;
at least one index entry that is associated with said at least one geometric shape and that is determined by using said key generator function; and
said index performance indicator being determined when minimum said index entries are associated with each said at least one geometric shape.
5. The computer system of claim 1 further comprising said index performance indicator that is determined by using a query box.
6. The computer system of claim 1 , wherein said multidimensional database is a spatial database.
7. A computer system for determining a grid index in a multidimensional database, comprising:
a memory;
a plurality of grids that are associated with said multidimensional database and that are sampled;
an index performance indicator that is associated with each said sampled grid; and
hardware for:
generating said index performance indicator that is the sum of said each grid index performance indicator and that is used to determine said grid index, wherein said index performance indicator describes a number of index entries that are evaluated in said grid index during a search of said multidimensional database; and
determining sizes for at least one grid cell associated with said sampled grid based on said index performance indicator.
8. An article of manufacture comprising a computer-usable medium readable by a computer and embodying one or more instructions stored in a memory that, when executed by said computer for determining a grid index in a multidimensional database, cause the computer to:
sample a grid associated with said multidimensional database;
determine an index performance indicator associated with said sampled grid; and
generate said index performance indicator thereby determining said grid index, wherein said index performance indicator describes a number of index entries that are evaluated in said grid index during a search of said multidimensional database; and
determine sizes for at least one grid cell associated with said sampled grid based on said index performance indicator.
9. The article of manufacture of claim 8 wherein said index performance indicator represents a minimum number of index entries that are evaluated.
10. The article of manufacture of claim 8 , wherein said one or more instructions that, when executed by said computer, cause the computer to determine said index performance indicator by using a key generator function.
11. The article of manufacture of claim 10 wherein:
said multidimensional database is a spatial database that represents at least one geometric shape; and wherein said one or more instructions that, when executed by said computer, cause the computer to:
use said key generator function to generate at least one index entry that is associated with said at least one geometric shape; and
determine said index performance indicator when minimum said index entries are associated with each said at least one geometric shape.
12. The article of manufacture of claim 8 , wherein said one or more instructions that, when executed by said computer, cause the computer to determine said index performance indicator by using a query box.
13. The article of manufacture of claim 8 wherein said multidimensional database is a spatial database.
14. An article of manufacture comprising a computer-usable medium readable by a computer and embodying one or more instructions stored in a memory that, when executed by said computer for determining a grid index in a multidimensional database, cause the computer to:
sample a plurality of grids associated with said multidimensional database;
determine an index performance indicator associated with each said sampled grid; and generate an said index performance indicator that is the sum of said each grid index performance indicator thereby determining said grid index, wherein said index performance indicator describes a number of index entries that are evaluated in said grid index during a search of said multidimensional database; and
determine sizes for at least one grid cell associated with said sampled grid based on said index performance indicator.