Systems, methods and computer program products to improve indexing of multidimensional databases

• US 20030212689A1
• Filed: 05/10/2002
• Published: 11/13/2003
• 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
• Granted Patent: US 7,383,275 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/957 Multidimensional
• 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 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 determining a grid index in a multidimensional database, comprising:

sampling a grid associated with said multidimensional database;

determining an index performance indicator associated with said sampled grid; and

determining an improved said index performance indicator thereby determining said grid index.

2. The computer-implemented method of claim 1 further comprising determining sizes for at least one grid cell associated with said grid based on said improved index performance indicator.

3. The computer-implemented method of claim 1 wherein said improved index performance indicator is a minimum said index performance indicator.

4. The computer-implemented method of claim 1 further comprising determining said improved index performance indicator by using a key generator function.

5. The computer-implemented method of claim 4 further comprising:

said multidimensional database being a spatial said multidimensional database that represents at least one geometric shape;

using said key generator function to generate at least one index entry that is associated with said at least one geometric shape; and

determining said improved index performance indicator when minimum said index entries are associated with each said at least one geometric shape.

6. The computer-implemented method of claim 1 further comprising determining said improved index performance indicator by using a query box.

7. The computer-implemented method of claim 1 wherein said multidimensional database is a spatial said multidimensional database.

8. A computer-implemented method for determining a grid index in a multidimensional database, comprising:

sampling a plurality of grids associated with said multidimensional database;

determining an index performance indicator associated with each said sampled grid; and

determining an improved said index performance indicator that is the sum of said each grid index performance indicator thereby determining said grid index.

9. A computer system for determining a grid index in a multidimensional database, comprising:

a grid that is associated with said multidimensional database and that is sampled;

an index performance indicator associated with said sampled grid; and

an improved said index performance indicator that is used to determine said grid index.

10. The computer system of claim 9 further comprising sizes for at least one grid cell associated with said grid that are determined by said improved index performance indicator.

11. The computer system of claim 9 wherein said improved index performance indicator is a minimum said index performance indicator.

12. The computer system of claim 9 further comprising said improved index performance indicator that is determined by using a key generator function.

13. The computer system of claim 12 further comprising:

said multidimensional database that is a spatial said multidimensional database and that 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 improved index performance indicator being determined when minimum said index entries are associated with each said at least one geometric shape.

14. The computer system of claim 9 further comprising said improved index performance indicator that is determined by using a query box.

15. The computer system of claim 9 wherein said multidimensional database is a spatial said multidimensional database.

16. A computer system for determining a grid index in a multidimensional database, comprising:

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

an improved said index performance indicator that is the sum of said each grid index performance indicator and that is used to determine said grid index.

17. An article of manufacture comprising a computer-usable medium readable by said computer and embodying one or more instructions executable by said computer for determining a grid index in a multidimensional database, wherein:

computer-readable program code samples a grid associated with said multidimensional database;

computer-readable program code determines an index performance indicator associated with said sampled grid; and

computer-readable program code determines an improved said index performance indicator thereby determining said grid index.

18. The article of manufacture of claim 17 wherein computer-readable program code determines sizes for at least one grid cell associated with said grid based on said improved index performance indicator.

19. The article of manufacture of claim 17 wherein said improved index performance indicator is a minimum said index performance indicator.

20. The article of manufacture of claim 17 wherein computer-readable program code determines said improved index performance indicator by using a key generator function.

21. The article of manufacture of claim 20 wherein:

said multidimensional database is a spatial said multidimensional database that represents at least one geometric shape;

computer-readable program code uses said key generator function to generate at least one index entry that is associated with said at least one geometric shape; and

computer-readable program code determines said improved index performance indicator when minimum said index entries are associated with each said at least one geometric shape.

22. The article of manufacture of claim 17 wherein computer-readable program code determines said improved index performance indicator by using a query box.

23. The article of manufacture of claim 17 wherein said multidimensional database is a spatial said multidimensional database.

24. An article of manufacture comprising a computer-usable medium readable by said computer and embodying one or more instructions executable by said computer for determining a grid index in a multidimensional database, wherein:

computer-readable program code samples a plurality of grids associated with said multidimensional database;

computer-readable program code determines an index performance indicator associated with each said sampled grid; and

computer-readable program code determines an improved said index performance indicator that is the sum of said each grid index performance indicator thereby determining said grid index.