Pruning of spatial queries on geodetic data when query window has holes
First Claim
1. A method for evaluating a spatial query comprising:
- receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
modifying the at least one interior circle to exclude the void; and
using the modified interior circle to evaluate the spatial query.
1 Assignment
0 Petitions
Accused Products
Abstract
Quicker and more efficient processing of spatial queries is provided when the query window has holes. A method for evaluating a spatial query comprises receiving a spatial query defining a query window including a void, identifying an interior circle for the query window, wherein the interior circle includes a void, and processing the spatial query efficiently in one of the following two alternate ways: (1) modifying the at least one interior circle to exclude the void, and using the modified interior circle to evaluate the spatial query by checking if a data mbr is inside the modified interior circle and if it does, including the data item in the query result set. Or (2) by checking for a data MBR is inside the interior circle and if so, checking if the data MBR intersects the MBRs of any of the voids, and including the data item in the query result set if there is no intersection.
-
Citations
27 Claims
-
1. A method for evaluating a spatial query comprising:
-
receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
modifying the at least one interior circle to exclude the void; and
using the modified interior circle to evaluate the spatial query. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for evaluating a spatial query comprising:
-
receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
determining a minimum bounding rectangle for the void;
comparing the minimum bounding rectangle for the void with the interior circle for the query window to determine whether the minimum bounding rectangle for the void is inside the interior circle for the query window;
comparing each of a plurality of candidate data minimum bounding rectangles to the interior circle to determine whether the data minimum bounding rectangle is inside the interior circle for the query window;
comparing each data minimum bounding rectangle that is inside the interior circle for the query window with a void for which the minimum bounding rectangle for the void is inside the interior circle for the query window to determine whether the data minimum bounding rectangle intersects with the void; and
including a data item in a result set of the query, if the data minimum bounding rectangle of the data item is inside the interior circle, but does not intersect the void. - View Dependent Claims (9)
-
-
10. A system for evaluating a spatial query comprising:
-
a processor operable to execute computer program instructions;
a memory operable to store computer program instructions executable by the processor; and
computer program instructions stored in the memory and executable to perform the steps of;
receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
modifying the at least one interior circle to exclude the void; and
using the modified interior circle to evaluate the spatial query. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. A system for evaluating a spatial query comprising:
-
a processor operable to execute computer program instructions;
a memory operable to store computer program instructions executable by the processor; and
computer program instructions stored in the memory and executable to perform the steps of;
receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
determining a minimum bounding rectangle for the void;
comparing the minimum bounding rectangle for the void with the interior circle for the query window to determine whether the minimum bounding rectangle for the void is inside the interior circle for the query window;
comparing each of a plurality of candidate data minimum bounding rectangles to the interior circle to determine whether the data minimum bounding rectangle is inside the interior circle for the query window;
comparing each data minimum bounding rectangle that is inside the interior circle for the query window with a void for which the minimum bounding rectangle for the void is inside the interior circle for the query window to determine whether the data minimum bounding rectangle intersects with the void; and
including a data item in a result set of the query, if the data minimum bounding rectangle of the data item is inside the interior circle, but does not intersect the void. - View Dependent Claims (18)
-
-
19. A computer program product for evaluating a spatial query comprising:
-
a computer readable medium;
computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
modifying the at least one interior circle to exclude the void; and
using the modified interior circle to evaluate the spatial query. - View Dependent Claims (20, 21, 22, 23, 24, 25)
-
-
26. A computer program product for evaluating a spatial query comprising:
-
a computer readable medium;
computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of receiving a spatial query defining a query window including a void;
identifying an interior circle for the query window, wherein the interior circle includes a void;
determining a minimum bounding rectangle for the void;
comparing the minimum bounding rectangle for the void with the interior circle for the query window to determine whether the minimum bounding rectangle for the void is inside the interior circle for the query window;
comparing each of a plurality of candidate data minimum bounding rectangles to the interior circle to determine whether the data minimum bounding rectangle is inside the interior circle for the query window;
comparing each data minimum bounding rectangle that is inside the interior circle for the query window with a void for which the minimum bounding rectangle for the void is inside the interior circle for the query window to determine whether the data minimum bounding rectangle intersect with the void; and
including a data item in a result set of the query, if the data minimum bounding rectangle of the data item is inside the interior circle, but does not intersect the void. - View Dependent Claims (27)
-
Specification