Reducing index size for multi-level grid indexes
First Claim
Patent Images
1. A computer system for indexing objects, comprising:
- an index comprised of a plurality of index entries for storing indicators of first objects, wherein the index is a grid index comprising a plurality of grid cells, the first and second objects are geometric shapes;
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, 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;
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;
means for storing the shape in the pool storage area if a geometric shape overlaps a number of grid cells exceeding the threshold number;
means for querying the grid index by initially evaluating the grid index to produce a group of one or more possible candidates based on the grid cells that respective geometric shapes in the index overlap;
means for querying the pool by adding the geometric shapes stored in the pool to said group of possible candidates to produce an interim group of possible candidates;
means for detecting geometric shapes in the grid index and pool that overlap a query area by filtering the interim group of possible candidates by comparing minimum bounding rectangles of the interim group of possible candidates with the query area to produce filtered candidates; and
means for determining geometric shapes among the filtered candidates that overlap the query area.
3 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.
77 Citations
7 Claims
-
1. A computer system for indexing objects, comprising:
-
an index comprised of a plurality of index entries for storing indicators of first objects, wherein the index is a grid index comprising a plurality of grid cells, the first and second objects are geometric shapes; 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, 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; 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; means for storing the shape in the pool storage area if a geometric shape overlaps a number of grid cells exceeding the threshold number; means for querying the grid index by initially evaluating the grid index to produce a group of one or more possible candidates based on the grid cells that respective geometric shapes in the index overlap; means for querying the pool by adding the geometric shapes stored in the pool to said group of possible candidates to produce an interim group of possible candidates; means for detecting geometric shapes in the grid index and pool that overlap a query area by filtering the interim group of possible candidates by comparing minimum bounding rectangles of the interim group of possible candidates with the query area to produce filtered candidates; and means for determining geometric shapes among the filtered candidates that overlap the query area.
-
-
2. A computer program for reducing a 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, 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; program instructions for, 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 (3, 4)
-
-
5. A computer system for reducing a number of index entries for use in an index for indexing an object, comprising:
-
an index capable of storing a plurality of index entries; and a pool storage area capable of storing indicators of objects; means for determining a number of index entries for the object; means for, 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; means for, if the number of index entries exceeds the threshold number, storing an indicator of the object in a pool storage area; means for 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; means for 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 means for 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 (6, 7)
-
Specification