×

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
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.

View all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×