Patent ID: 7580927

Claim:
A computer implemented method for determining positional relationships among objects represented in a database, the method comprising: receiving a query including at least a first object in the database and a desired positional relationship between the first object and a second object in the database; in response to receiving the query performing the steps of: identifying, for the first object, one or more tiles in a plurality of tiles defined in a spatial index in the database that are interior tiles of the first object and one or more tiles in the plurality of tiles that are boundary tiles of the first object; identifying, for the second object, one or more tiles in the plurality of tiles that are interior tiles of the second object and tiles in the plurality of tiles that are boundary tiles of the second object; and providing the query to a primary filter operable to: compare tiles of the first object with tiles of the second object to determine whether at least one tile of the first object intersects with at least one tile of the second object; and determine whether the at least one tile of the second object with which the at least one tile of the first object intersects is an interior tile of the second object; if so, providing the first object to a result set of objects that satisfy the desired positional relationship, otherwise, providing the first object and second object to a secondary filter operable to: compare the second object with the first object; and if the first object fulfills the desired positional relationship, include the first object in the result set of objects that satisfy the desired positional relationship; otherwise, exclude the first object from the result set of objects that satisfy the desired positional relationship.