Reducing index size for multi-level grid indexes

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 whether one or more index entries of the first objects satisfy a query;
• 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.

A computer system for querying an index of first objects comprised of a plurality of index entries and a pool of second objects, comprising:

• means for 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;
• means for adding second objects from the pool to said group of possible candidates to produce an interim group of possible candidates:
• means for 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
• means 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.