Reducing index size for multi-level grid indexes
First Claim
Patent Images
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.
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
3 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. - View Dependent Claims (2, 3)
-
Specification