Reducing index size for multi-level grid indexes
First Claim
Patent Images
1. A computer-implemented method of reducing the 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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
30 Claims
-
1. A computer-implemented method of reducing the 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. 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 an indicator of the object 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. - View Dependent Claims (12)
-
-
13. 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. - View Dependent Claims (14, 15, 16, 17)
-
-
18. 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 cells designated in a query that respective first objects in the index overlap;
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. - View Dependent Claims (19, 20)
-
-
21. 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. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28)
-
-
29. 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. - View Dependent Claims (30)
-
Specification