Reducing index size for multi-level grid indexes

• US 7,373,353 B2
• Filed: 05/10/2002
• Issued: 05/13/2008
• Est. Priority Date: 05/10/2002
• Status: Expired due to Term

• Current Assignee: Hulu LLC (The Walt Disney Company)
• Original Assignee: International Business Machines Corporation
• Inventors: Stolze, Knut, Adler, David William
• Primary Examiner(s): WOO, ISAAC M
• Application Number:
  US10/141,919
• Publication Number:
  US 20030212650A1
• Time in Patent Office: 2,195 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 382/123, 382/154, 382162-180
• 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, 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 grid cells the object overlaps;

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

subsequent to the storing of an indicator of a geometric shape in the pool storage area and in response to a query, evaluating the grid index to produce a group of one or more possible candidates based on grid cells that respective geometric shapes in the index overlap;

adding the geometric shapes stored in the pool storage area to said group of possible candidates to produce an interim group of possible candidates; and

filtering the interim group of possible candidates by comparing approximations of the geometric shapes of the interim group of possible candidates with a query area specified in the query to produce filtered candidates.

2. The computer-implemented method of claim 1, wherein the approximations of the possible candidates are minimum bounded rectangles (MBRs) of the possible candidates, and said filtering is performed by comparing for each possible candidate, the MBR of the candidate with the query area and designating the candidate as a final candidate if the MBR of the candidate and the query area overlap.

3. The computer-implemented method of claim 2, further comprising determining for each final candidate if the geometric shape corresponding to the final candidate overlaps the query area.