Query prunning using exterior tiles in an R-tree index
First Claim
1. A computer-implemented method for determining relationships among objects represented in a database, the method comprising:
- providing a first filter operable to;
a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times;
if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to;
carry out mathematical comparison of the first geometry and the second geometry; and
pass the second geometry to a result set based on the result of the mathematical comparison;
otherwise, excluding the second geometry from the result set.
1 Assignment
0 Petitions
Accused Products
Abstract
Determining relationships among objects represented in a database includes defining a plurality of tiles in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction a plurality of times. A second geometry is analyzed to determine if it fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry. If the second geometry fulfills the first filter condition with respect to any of the tiles defined in the first geometry carrying out a mathematical comparison of the first geometry and the second geometry.
-
Citations
20 Claims
-
1. A computer-implemented method for determining relationships among objects represented in a database, the method comprising:
-
providing a first filter operable to; a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times; if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to; carry out mathematical comparison of the first geometry and the second geometry; and pass the second geometry to a result set based on the result of the mathematical comparison; otherwise, excluding the second geometry from the result set. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computer-implemented method for determining relationships among objects represented in a database, the method comprising:
-
providing a first filter operable to; receive an a minimum bounding rectangle defined for a first geometry having; a plurality of tiles defined in the minimum bounding rectangle of he first geometry by recursively dividing the minimum bounding rectangle into two parts a plurality of times in an x-dimension and y-dimension; if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to; carry out a mathematical comparison of the first geometry and the second geometry; and pass the second geometry to a result set based on the result of the mathematical comparison; otherwise, excluding the second geometry from the result set. - View Dependent Claims (14, 15)
-
-
16. A computer program product for performing a process for determining relationships among objects represented in a database, comprising:
-
a computer readable medium; and computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of providing a first filter operable to; receive an approximation defined for a first geometry having; a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times; if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to; carry out a mathematical comparison of the first geometry and the second geometry; and pass the second geometry to a result set based on the result of the mathematical comparison; otherwise, excluding the second geometry from the result set. - View Dependent Claims (17, 18)
-
-
19. A system for performing a process for 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; providing a first filter operable to; receive an approximation defined for a first geometry having; a plurality of tiles defined in the approximation of the first geometry by dividing the approximation of the first geometry in a first direction a plurality of times and dividing the approximation of the first geometry in a second direction perpendicular to the first direction the plurality of times; if a second geometry fulfills a first filter condition with respect to any of the tiles defined in the approximation of the first geometry providing the first geometry and the second geometry to a second filter operable to; carry out a mathematical comparison of the first geometry and the second geometry; and pass the second geometry to a result set based on the result of the mathematical comparison; otherwise, excluding the second geometry from the result set. - View Dependent Claims (20)
-
Specification