Patent ID: 7779038

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