Query pruning using interior circles for geodetic data in an R-tree index

• US 7,185,023 B2
• Filed: 03/27/2003
• Issued: 02/27/2007
• 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: Kothuri, Ravi Kanth V.
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/397,530
• Publication Number:
  US 20040193566A1
• Time in Patent Office: 1,433 Days
• Field of Search: 707 1- 7, 707/100, 707/104.1, 382/261, 345/441, 345/419
• 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 determining relationships among data representing regions on a surface of a body. The method includes identifying a center of a first geometry. A minimum distance is identified from the center to a boundary of the first geometry. A first circle is defined on the surface of the body having the minimum distance as its radius and the center of the first geometry as its center. The first circle is compared with a second geometry to determine if the second geometry fulfills a first filter condition with respect to the first geometry.

Claims

1. A computer implemented method for determining relationships among data representing regions on a surface of a body, the method comprising:

identifying a center of a first geometry representing data;

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

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

comparing the first circle with a second geometry representing data to determine if there is an interaction between the second geometry and the first geometry, wherein the comparing eliminates the second geometry if there is no interaction.

2. The method according to claim 1, further comprising prior to the identifying a center of the first geometry:

identifying a minimum bounding volume for the first geometry;

identifying a minimum bounding volume for the second geometry; and

comparing the minimum bounding volume of the first geometry with the minimum bounding volume of the second geometry to determine if the second geometry fulfills a second filter condition with respect to the first geometry.

3. The method according to claim 2, wherein the minimum bounding volume comprises a rectangular solid.

4. The method according to claim 3, wherein identifying the minimum bounding volume comprises:

identifying a point within the first geometry; and

defining a plane at each location where three orthogonal axes passing through the point, each plane being perpendicular to the axis at each location.

5. The method according to claim 1, wherein identifying a center of the first geometry comprises:

determining a center of a minimum bounding volume of the first geometry.

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

projecting the center of the first geometry onto a surface of the body.

7. The method according to claim 6, wherein the circle is defined on the surface of the body about the projected center point.

8. The method according to claim 6, wherein the body comprises a sphere, the first geometry comprises a region on a surface of the sphere and the center is projected onto the surface of the sphere.

9. The method according to claim 6, further comprising:

identifying for the second geometry a minimum bounding rectangle that lies in a plane perpendicular to a radius of the sphere;

identifying a center of the minimum bounding rectangle;

projecting the center of the minimum bounding rectangle onto the surface of the sphere;

determining a minimum distance between the center of the minimum bounding rectangle and the boundary of the second geometry;

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

comparing the circle with the first geometry to determine if the first geometry fulfills a second filter condition with respect to the second geometry.

10. The method according to claim 6, wherein the body is the earth.

11. The method according to claim 1, further comprising:

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;

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

comparing each circle with a second geometry to determine if the second geometry fulfills a first filter condition with respect to the first geometry.

12. The method according to claim 11, wherein the maximum span line passes through the center of the first geometry and is parallel to one of the x axis and y axis.

13. The method according to claim 11, wherein the circles are defined along the maximum span line at points one-quarter, one-half, and three-quarters of the length of the maximum span distance.

14. The method according to claim 11, wherein the circles are defined at eleven positions along the maximum span line.

15. The method according to claim 14, wherein the eleven positions are equidistantly spaced along the maximum span line.

16. The method according to claim 1, wherein the three-dimensional objects comprise non-planar surfaces.

17. The method according to claim 1, wherein the first filter condition is fulfilled if the second geometry lies entirely within the circle.

18. The method according to claim 17, wherein the second filter condition comprises any intersection of the second geometry with the circle.

19. The method according to claim 18, further comprising:

mathematically comparing the first geometry and the second geometry if the second geometry fulfills the second filter condition.

20. The method according to claim 1, further comprising:

determining whether the second geometry fulfills a second filter condition with respect to the circle if the second geometry does not fulfill the first filter condition.

21. The method according to claim 1, wherein the center of the first geometry is a centroid.

22. The method according to claim 1, wherein the surface of the sphere is irregular.

23. The method according to claim 1, wherein the body is an ellipsoid.

24. The method according to claim 1, further comprising:

defining a minimum bounding rectangle of the second geometry;

determining a center of the minimum bounding rectangle of the second geometry;

determining a minimum distance from the center of the minimum bounding rectangle of the second geometry to a boundary of the first geometry; and

comparing the minimum distance from the center of the minimum bounding rectangle of the second geometry to a boundary of the first geometry with a maximum distance from the center of the minimum bounding rectangle to a corner of the minimum bounding rectangle to determine if the second geometry fulfills a second filter condition with respect to the first geometry.

25. The method according to claim 1, wherein comparing the circle with the second geometry comprises:

determining a distance from the center of the first geometry to the center of the minimum bounding rectangle of the second geometry;

determining a maximum distance from the center of the minimum bounding rectangle of the second geometry to a corner of the minimum bounding rectangle of the second geometry; and

comparing the radius of the interior circle of the first geometry to the sum of the above two distances computed using the second geometry.

26. A computer program product for performing a process of determining relationships among objects represented in a database, the computer product comprising:

a computer readable medium; and

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of;

identifying a center of a first geometry representing data;

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

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

comparing the first circle with a second geometry representing data to determine if the second geometry interacts with the first geometry, wherein the comparing eliminates the second geometry if there is in interaction.

27. 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;

identifying a center of a first geometry representing data;

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

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

comparing the first circle with a second geometry representing data to determine if the second geometry interacts with the first geometry, wherein the comparing eliminates the second geometry if there is no interaction.