Pruning of spatial queries on geodetic data when query window has holes

• US 20050203932A1
• Filed: 05/05/2005
• Published: 09/15/2005
• Est. Priority Date: 06/22/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ravada, Siva, Kothuri, Ravikanth V., Geringer, Daniel, Abugov, Daniel
• Granted Patent: US 7,379,936 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24558 Binary matching operations
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

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.

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.

2. The method of claim 1, wherein modifying the at least one interior circle to exclude the void comprises:

determining a distance from a center of the interior circle to a closest point of the void or to a closest point of a minimum bounding rectangle of the void; and

modifying the interior circle to form a modified interior circle having a same center as the interior circle and having a radius equal to the determined distance.

3. The method of claim 2, wherein using the modified interior circle to evaluate the spatial query comprises:

comparing each of a plurality of candidate data minimum bounding rectangles to the modified interior circle; and

including a data item represented by a data minimum bounding rectangle in a result set of the query, if the data minimum bounding rectangle is inside the modified interior circle.

4. The method of claim 3, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

5. The method of claim 1, wherein the interior circle includes a plurality of voids and modifying the at least one interior circle to exclude the voids comprises:

determining a distance from a center of the interior circle to a closest point of each of the plurality of voids or to a closest point of a minimum bounding rectangle of each of the plurality of voids to form a plurality of determined distances;

selecting a minimum distance from among the plurality of determined distances; and

modifying the interior circle to form a modified interior circle having a same center as the interior circle and having a radius equal to the selected distance.

6. The method of claim 5, wherein using the modified interior circle to evaluate the spatial query comprises:

comparing each of a plurality of candidate data minimum bounding rectangles to the modified interior circle; and

including a data item represented by a data minimum bounding rectangle in a result set of the query, if the data minimum bounding rectangle is inside the modified interior circle.

7. The method of claim 6, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

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.

9. The method of claim 8, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

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.

11. The system of claim 10, wherein modifying the at least one interior circle to exclude the void comprises:

determining a distance from a center of the interior circle to a closest point of the void or to a closest point of a minimum bounding rectangle of the void; and

modifying the interior circle to form a modified interior circle having a same center as the interior circle and having a radius equal to the determined distance.

12. The system of claim 11, wherein using the modified interior circle to evaluate the spatial query comprises:

comparing each of a plurality of candidate data minimum bounding rectangles to the modified interior circle; and

including a data item represented by a data minimum bounding rectangle in a result set of the query, if the data minimum bounding rectangle is inside the modified interior circle.

13. The system of claim 12, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

14. The system of claim 10, wherein the interior circle includes a plurality of voids and modifying the at least one interior circle to exclude the void comprises:

determining a distance from a center of the interior circle to a closest point of each of the plurality of voids or to a closest point of a minimum bounding rectangle of each of the plurality of voids to form a plurality of determined distances;

selecting a minimum distance from among the plurality of determined distances; and

modifying the interior circle to form a modified interior circle having a same center as the interior circle and having a radius equal to the selected distance.

15. The system of claim 14, wherein using the modified interior circle to evaluate the spatial query comprises:

comparing each of a plurality of candidate data minimum bounding rectangles to the modified interior circle; and

including a data item represented by a data minimum bounding rectangle in a result set of the query, if the data minimum bounding rectangle is inside the modified interior circle.

16. The system of claim 15, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

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.

18. The system of claim 17, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

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.

20. The computer program product of claim 19, wherein modifying the at least one interior circle to exclude the void comprises:

determining a distance from a center of the interior circle to a closest point of the void or to a closest point of a minimum bounding rectangle of the void; and

modifying the interior circle to form a modified interior circle having a same center as the interior circle and having a radius equal to the determined distance.

21. The computer program product of claim 20, wherein using the modified interior circle to evaluate the spatial query comprises:

comparing each of a plurality of candidate data minimum bounding rectangles to the modified interior circle; and

including a data item represented by a data minimum bounding rectangle in a result set of the query, if the data minimum bounding rectangle is inside the modified interior circle.

22. The computer program product of claim 21, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

23. The computer program product of claim 19, wherein the interior circle includes a plurality of voids and modifying the at least one interior circle to exclude the void comprises:

determining a distance from a center of the interior circle to a closest point of each of the plurality of voids or to a closest point of a minimum bounding rectangle of each of the plurality of voids to form a plurality of determined distances;

selecting a minimum distance from among the plurality of determined distances; and

modifying the interior circle to form a modified interior circle having a same center as the interior circle and having a radius equal to the selected distance.

24. The computer program product of claim 23, wherein using the modified interior circle to evaluate the spatial query comprises:

comparing each of a plurality of candidate data minimum bounding rectangles to the modified interior circle; and

including a data item represented by a data minimum bounding rectangle in a result set of the query, if the data minimum bounding rectangle is inside the modified interior circle.

25. The computer program product of claim 24, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.

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.

27. The computer program product of claim 26, further comprising:

for each data item not included in the query result set, computing an interior circle for the query window using the center of a data minimum bounding rectangle representing the data item as a center of a new interior circle; and

comparing the new interior circle and the voids included in the query window with a circle that circumscribes the data minimum bounding rectangle representing the data item.