Reducing index size for multi-level grid indexes

• US 20060041551A1
• Filed: 10/20/2005
• Published: 02/23/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,860,891 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

Techniques of querying an index of first objects comprised of a plurality of index entries and a pool of second objects are provided. The techniques include evaluating the index of the first objects to produce a group of one or more possible candidates based on whether one or more index entries of the first objects satisfy a query, adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates, filtering the interim group of possible candidates by comparing approximations of the candidates of the interim group with the query to produce filtered candidate objects, and determining if the filtered candidate objects satisfy the query by comparing the first and second objects corresponding to the filtered candidate objects with the query.

Claims

1. A computer-implemented method of querying an index of first objects comprised of a plurality of index entries and a pool of second objects, the method comprising:

evaluating the index of the first objects to produce a group of one or more possible candidates based on whether one or more index entries of the first objects satisfy a query;

adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates;

filtering the interim group of possible candidates by comparing approximations of the candidates of the interim group with the query to produce filtered candidate objects; and

determining if the filtered candidate objects satisfy the query by comparing the first and second objects corresponding to the filtered candidate objects with the query.

2. The computer-implemented method of claim 1, wherein the index is a grid index comprised of a plurality of grid cells, the first and second objects are geometric shapes, and the second objects are larger than the first objects.

3. The computer-implemented method of claim 2, wherein all geometric shapes from the pool are added to said group of possible candidates to produce the interim group of possible candidates.

4. The computer-implemented method of claim 2, wherein the approximations of the candidate objects are minimum bounding rectangles of the geometric shapes corresponding to the candidate objects.

5. The computer-implemented method of claim 4, wherein said determining if the filtered candidate objects satisfy the query includes comparing the geometric shapes corresponding to the filtered candidate objects with a query area specified in the query.

6. A computer program for querying an index of first objects comprised of a plurality of cells and a pool of second objects, the computer program having program instructions executable by a computer and recorded on a computer-readable medium, the computer program comprising:

program instructions for evaluating the index of the first objects to produce a group of one or more possible candidates based on whether one or more index entries of the first objects satisfy a query;

program instructions for adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates;

program instructions for filtering the interim group of possible candidates by comparing the query with approximations of the candidates of the interim group with the query to produce filtered candidate objects; and

program instructions for determining if the filtered candidate objects satisfy the query by comparing the first and second objects corresponding to the filtered candidate objects with the query.

7. The computer program of claim 6, wherein the index is a grid index comprised of a plurality of grid cells, the first and second objects are geometric shapes, and the second objects are larger than the first objects.

8. The computer program of claim 7, wherein all geometric shapes from the pool are added to said group of possible candidates to produce the interim group of possible candidates.

9. The computer program of claim 7, wherein the approximations of the candidate objects are minimum bounding rectangles of the geometric shapes corresponding to the candidate objects.

10. The computer program of claim 9, wherein said determining if the filtered candidate objects satisfy the query includes comparing the geometric shapes corresponding to the filtered candidate objects with a query area specified in the query.

11. A computer system for querying an index of first objects comprised of a plurality of index entries and a pool of second objects, comprising:

means for evaluating the index of the first objects to produce a group of one or more possible candidates based on whether one or more index entries of the first objects satisfy a query;

means for adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates;

means for filtering the interim group of possible candidates by comparing approximations of the candidates of the interim group with the query to produce filtered candidate objects; and

means for determining if the filtered candidate objects satisfy the query by comparing the first and second objects corresponding to the filtered candidate objects with the query.

12. The computer-implemented method of claim 11, wherein the index is a grid index comprised of a plurality of grid cells, the first and second objects are geometric shapes, and the second objects are larger than the first objects.

13. The computer-implemented method of claim 12, wherein all geometric shapes from the pool are added to said group of possible candidates to produce the interim group of possible candidates.

14. The computer-implemented method of claim 12, wherein the approximations of the candidate objects are minimum bounding rectangles of the geometric shapes corresponding to the candidate objects.

15. The computer-implemented method of claim 14, wherein said determining if the filtered candidate objects satisfy the query includes comparing the geometric shapes corresponding to the filtered candidate objects with a query area specified in the query.

16. A computer system for indexing geometric shapes, comprising:

grid index means for storing geometric shapes; and

means for storing a pool of geometric shapes which are larger than the geometric shapes stored in the grid index means.

17. The computer system of claim 16, wherein the grid index means includes a plurality of grid cells, the computer system further comprising:

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

means for storing the shape in the pool if the geometric shape overlaps a number of grid cells that exceeds the threshold number.