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

• US 7,379,936 B2
• Filed: 05/05/2005
• Issued: 05/27/2008
• Est. Priority Date: 06/22/2001
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Geringer, Daniel, Abugov, Daniel, Ravada, Siva, Kothuri, Ravikanth V.
• Primary Examiner(s): Vital; Pierre
• Assistant Examiner(s): Nofal; Christopher P
• Application Number:
  US11/122,011
• Publication Number:
  US 20050203932A1
• Time in Patent Office: 1,118 Days
• Field of Search: 340/825.37, 345/419, 382/261, 707/1, 707/3, 707/6, 707/100, 707/102, 707/104.1, 707/2, 707/5, 707/101, 703/2, 701/208
• 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

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 by either (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 whether a data MBR is inside the modified interior circle and when it does, including the data item in the query result set, or (2) by checking whether a data MBR is inside the interior circle and when it does, checking whether the data MBR intersects the MBRs of any of the voids, and including the data item in the query result set when there is no intersection.

Claims

1. A computer-implemented method for evaluating a spatial query comprising:

receiving a spatial query defining a query window including a void;

identifying at least one interior circle for the query window, wherein the at least one interior circle includes a void;

modifying the at least one interior circle to exclude the void;

using the at least one modified interior circle to determine data items that satisfy the spatial query from among a plurality of data items; and

outputting a result set of the query, the result set including those data items that satisfy the spatial query.

2. The computer-implemented 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 at least one 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 at least one interior circle to form a modified interior circle having a same center as the at least one interior circle and having a radius equal to the determined distance.

3. The computer-implemented method of claim 2, wherein using the at least one modified interior circle to evaluate the spatial query comprises:

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

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

4. The computer-implemented 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

5. The computer-implemented method of claim 1, wherein the at least one 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 at least one 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 at least one interior circle to form a modified interior circle having a same center as the at least one interior circle and having a radius equal to the selected distance.

6. The computer-implemented method of claim 5, wherein using the at least one modified interior circle to evaluate the spatial query comprises:

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

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

7. The computer-implemented 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

8. A computer-implemented 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 avoid;

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;

including a data item in the result set of the query, when the data minimum bounding rectangle of the data item is inside the interior circle, but does not intersect the void; and

outputting the result set of the query including the data items included in the result set.

9. The computer-implemented 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

10. A computerized 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 at least one interior circle for the query window, wherein the at least one interior circle includes a void;

modifying the at least one interior circle to exclude the void;

using the at least one modified interior circle to determine data items that satisfy the spatial query from among a plurality of data items; and

outputting a result set of the query, the result set including those data items that satisfy the spatial, query.

11. The computerized 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 at least one 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 at least one interior circle to form a modified interior circle having a same center as the at least one interior circle and having a radius equal to the determined distance.

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

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

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

13. The computerized 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

14. The computerized system of claim 10, wherein the at least one 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 at least one 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 at least one interior circle to form a modified interior circle having a same center as the at least one interior circle and having a radius equal to the selected distance.

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

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

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

16. The computerized 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

17. A computerized 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;

including a data item in a result set of the query, when the data minimum bounding rectangle of the data item is inside the interior circle, but does not intersect the void; and

outputting the result set of the query including the data items included in the result set.

18. The computerized 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

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 at least one interior circle for the query window, wherein the at least one interior circle includes a void;

modifying the at least one interior circle to exclude the void;

using the at least one modified interior circle to determine data items that satisfy the spatial query from among a plurality of data items; and

outputting a result set of the query, the result set including those data items that satisfy 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 at least one 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 at least one interior circle to form a modified interior circle having a same center as the at least one interior circle and having a radius equal to the determined distance.

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

comparing each of a plurality of candidate data minimum bounding rectangles to the at least one modified interior circle, and

including a data item represented by a data minimum bounding rectangle in a result set of the query, when the data minimum bounding rectangle is inside the at least one 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

23. The computer program product of claim 19, wherein the at least one 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 at least one 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 at least one interior circle to form a modified interior circle having a same center as the at least one interior circle and having a radius equal to the selected distance.

24. The computer program product of claim 23, wherein using the at least one modified interiorcircie to evaluate the spatial query comprises:

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

including a data item represented by a data minimum bounding rectangle in a result set of the query, when the data minimum bounding rectangle is inside the at least one 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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.

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 avoid;

detennining a minimum bounding rectangle for the void;

comparing the minimum bounding rectangle for the void with the interior circle for the query window to detennine 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;

including a data item in a result set of the query, when the data minimum bounding rectangle of the data item is inside the interior circle, but does not intersect the void; and

outputting the result set of the query, based on the evaluation of the spatial query.

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; and

including the data item in a result set of the query, when the data minimum bounding rectangle is inside the new interior circle.