Reducing index size for multi-level grid indexes

• US 20060036628A1
• Filed: 10/20/2005
• Published: 02/16/2006
• Est. Priority Date: 05/10/2002
• Status: Active Grant

• Current Assignee: Hulu LLC (The Walt Disney Company)
• Original Assignee: International Business Machines Corporation
• Inventors: Stolze, Knut, Adler, David William
• Granted Patent: US 7,379,944 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The number of index entries in a grid index for indexing geometric shapes is reduced by establishing a pool storage area for geometric shapes, selecting a threshold number of grid cells which a geometric shape may overlap, storing the shape in the grid index if a geometric shape overlaps a number of grid cells not exceeding the threshold number, and storing the shape in the pool storage area if the geometric shape overlaps a number of grid cells which exceeds the threshold number.

Claims

1. A computer-implemented method of reducing a number of index entries for use in an index associated with an object, comprising:

determining a number of index entries for the object;

if the number of index entries does not exceed a threshold number, storing the index entries in the index; and

if the number of index entries exceeds the threshold number, storing an indicator of the object in a pool storage area.

2. The computer-implemented method of claim 1, wherein the index is a grid index comprised of a plurality of grid cells, the object is a geometric shape, and said determining a number of index entries is based on how many cells the object overlaps.

3. The computer-implemented method of claim 2, further comprising

selecting the threshold number of grid cells that a geometric shape may overlap;

and

establishing the pool storage area for storing indicators of geometric shapes overlapping the number of grid cells exceeding the threshold number.

4. The computer-implemented method of claim 2, wherein the geometric shapes are from a database of geometric shapes.

5. The computer-implemented method of claim 4, wherein an indicator for each geometric shape in the database that overlaps a number of grid cells exceeding the threshold number is stored in the pool storage area.

6. The computer-implemented method of claim 2, wherein the grid index includes a data structure and if one of said geometric shapes is placed in the pool storage area, an identifier representative of such geometric shape is placed in the data structure of the grid index.

7. The computer-implemented method of claim 2, wherein the grid index is a multilevel grid index and wherein the threshold number of grid cells is related to the coarsest level of the grid index.

8. A computer program for reducing the number of index entries for use in an index for indexing an object, the computer program having program instructions executable by a computer and recorded on a computer-readable medium, the computer program comprising:

program instructions for determining a number of index entries for the object;

program instructions for storing the index entries in the index if the number of index entries does not exceed a threshold number; and

program instructions for storing an indicator of the object in a pool storage area if the number of index entries exceeds the threshold number.

9. The computer-program of claim 8, wherein the index is a grid index comprised of a plurality of grid cells and the object is a geometric shape, and said determining a number of index entries is based on how many cells the object overlaps.

10. The computer-program of claim 9, further comprising:

program instructions for selecting the threshold number of grid cells that a geometric shape may overlap; and

program instructions for establishing the pool storage area for storing indicators of geometric shapes overlapping the number of grid cells exceeding the threshold number.

11. The computer-program of claim 9, wherein the geometric shapes are from a database of geometric shapes.

12. The computer-program of claim 11, wherein an indicator for each geometric shape in the database that overlaps a number of grid cells exceeding the threshold number is stored in the pool storage area.

13. The computer-program of claim 9, wherein the grid index includes a data structure and if one of said geometric shapes is placed in the pool storage area, an identifier representative of such geometric shape is placed in the data structure of the grid index.

14. The computer-program of claim 9, wherein the grid index is a multilevel grid index and wherein the threshold number of grid cells is related to the coarsest level of the grid index.

15. A computer system for indexing objects, comprising:

an index comprised of a plurality of index entries for storing indicators of first objects; and

a pool storage area for storing an indicator of second objects that are not stored in the index, wherein a number of index entries for the second objects if stored in the index is greater than a threshold number.

16. The computer system of claim 15, wherein the index is a grid index comprising a plurality of grid cells, the first and second objects are geometric shapes.

17. The computer system of claim 16, wherein the pool storage area is for storing indicators of geometric shapes that overlap more than a preselected threshold number of grid cells if the grid index is laid over said geometric shapes.

18. The computer system of claim 17, wherein the grid index contains stored geometric shapes and wherein the pool storage area contains said larger geometric shapes.

19. The computer system of claim 18, wherein the grid index includes a data structure and for each geometric shape in the pool storage area there is an identifier in the data structure of the grid index.

20. The computer system of claim 19, wherein the grid index is a multi-level grid index.

21. The computer system of claim 17, further comprising:

means for determining how many grid cells a geometric shape overlies;

means for storing the shape in the grid index if a geometric shape overlaps a number of cells that does not exceed the threshold number; and

means for storing the shape in the pool storage area if a geometric shape overlaps a number of grid cells exceeding the threshold number.