Within-distance query pruning in an R-tree index

1. A method for determining a within-distance relationship between a first geometry object and a second geometry object, the method comprising:

receiving a query; and

providing the query to a first filter configured to:

define an exterior approximation of the first geometry and the second geometry;

compute a distance between the exterior approximations;

compare the computed distance with a first predetermined distance to determine whether the second geometry satisfies a first filter condition with respect to the first geometry, and

if the first filter condition is satisfied, providing the second geometry to a query result set,

otherwise, defining an interior approximation of the first geometry;

expanding the interior approximation by a second predetermined distance; and

comparing the expanded interior approximation with the second geometry to determine if the second geometry satisfies the first filter condition with respect to the first geometry; and

if the first filter condition is satisfied, providing the second geometry to a query result set,

otherwise, providing the first geometry and the second geometry to a second filter configured to perform an exact mathematical comparison of the first geometry and the second geometry to determine whether the second geometry satisfies a second filter condition with respect to the first geometry; and

if the second filter condition is satisfied, providing the second geometry to the query result set,

otherwise, excluding the second geometry from the query result set, wherein the result set specifies that the within-distance relationship between the first geometry object and the second geometry object is satisfied.

2. The method according to claim 1 , wherein the first filter condition is satisfied if the second geometry is inside the expanded interior.

3. The method according to claim 1 , wherein the exact mathematical comparison includes computing an exact distance between the first geometry and the second geometry to determine if the second geometry satisfies the first filter condition with respect to the first geometry.

4. The method according to claim 1 , wherein the exterior approximation comprises a minimum bounding rectangle.

5. The method according to claim 4 , further comprising:

the first filter further operable to:

compute circle that circumscribes the minimum bounding rectangle; and

compare the circle with the second geometry to determine if the second geometry satisfies the first filter condition with respect to the first geometry.

6. The method according to claim 1 , wherein defining the approximation of the first geometry comprises:

identifying a center of the first geometry;

identifying a minimum distance from the center to a boundary of the first geometry; and

defining a circle having the minimum distance as its radius and the center of the first geometry as its center;

wherein determining whether the second geometry satisfies a first filter condition with respect to the first geometry comprises comparing the circle with a second geometry.

7. The method according to claim 6 , wherein defining the approximation of the first geometry further comprises:

identifying a maximum span line of the first geometry;

identifying a minimum distance from a plurality of points along the maximum span line to a boundary of the first geometry; and

defining about each of the plurality of points a circle having the minimum distance as its radius;

wherein determining whether the second geometry satisfies a first filter condition with respect to the first geometry comprises comparing each circle with a second geometry.

8. The method according to claim 6 , wherein a circle is defined about eleven points equidistantly spaced along the maximum span line.

9. The method according to claim 6 , wherein a circle is defined about to points equidistantly spaced along the maximum span dimension.

10. The method according to claim 1 , wherein each circle is entirely contained within the first geometry.

11. The method according to claim 6 , wherein the first filter condition comprises the second geometry lies entirely within one of the circles.

12. The method according to claim 1 , wherein defining the exterior approximation comprises:

defining a minimum bounding rectangle.

13. The method according to claim 6 , wherein the center is a centroid.

14. The method according to claim 1 , wherein the first geometry and the second geometry are described by geodetic data.

15. The method according to claim 1 , wherein the first geometry and the second geometry are described by non-geodetic data.

16. The method according to claim 1 , wherein the interior approximation comprises at least one tile.

17. A computer program product for performing a process of determining within-distance relationships among objects represented in a database, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of:

receiving a query; and

providing the query to a first filter configured to:

define an exterior approximation of the first geometry and the second geometry;

compute a distance between the exterior approximations;

compare the computed distance with a first predetermined distance to determine whether the second geometry satisfies a first filter condition with respect to the first geometry, and

if the first filter condition is satisfied, providing the second geometry to a query result set,

otherwise, defining an interior approximation of the first geometry;

expanding the interior approximation by a second predetermined distance; and

comparing the expanded interior approximation with the second geometry to determine if the second geometry satisfies the first filter condition with respect to the first geometry; and

if the first filter condition is satisfied, providing the second geometry to a query result set,

otherwise, providing the first geometry and the second geometry to a second filter configured to perform an exact mathematical comparison of the first geometry and the second geometry to determine whether the second geometry satisfies a second filter condition with respect to the first geometry; and

if the second filter condition is satisfied, providing the second geometry to the query result set,

otherwise, excluding the second geometry from the query result set, wherein the result set specifies that the within-distance relationship between the first geometry object and the second geometry object is satisfied.

18. A system for performing a process of determining relationships among objects represented in a database, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of:

receiving a query; and

providing the query to a first filter con figured to:

define an exterior approximation of the first geometry and the second geometry;

compute a distance between the exterior approximations;

compare the computed distance with a first predetermined distance to determine whether the second geometry satisfies a first filter condition with respect to the first geometry, and

if the first filter condition is satisfied, providing the second geometry to a query result set,

otherwise, defining an interior approximation of the first geometry;

expanding the interior approximation by a second predetermined distance; and

comparing the expanded interior approximation with the second geometry to determine if the second geometry satisfies the first filter condition with respect to the first geometry; and

if the first filter condition is satisfied, providing the second geometry to a query result set,

otherwise, providing the first geometry and the second geometry to a second filter configured to perform an exact mathematical comparison of the first geometry and the second geometry to determine whether the second geometry satisfies a second filter condition with respect to the first geometry; and

if the second filter condition is satisfied, providing the second geometry to the query result set,

otherwise, excluding the second geometry from the query result set wherein the result set specifies that the within-distance relationship between the first geometry object and the second geometry object is satisfied.