Delayed distance computations for nearest-neighbor queries in an R-tree index

• US 7,181,467 B2
• Filed: 03/27/2003
• Issued: 02/20/2007
• Est. Priority Date: 03/27/2003
• Status: Active Grant

• 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,529
• Publication Number:
  US 20040193615A1
• Time in Patent Office: 1,426 Days
• Field of Search: 707 1- 7, 707/100, 707/104.1, 707/101, 707/102
• 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/29 Geographical information databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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 locating neighboring data geometries of a query geometry. A minimum bounding rectangle of the query geometry is determined. A minimum bounding rectangle of each data geometry is determined. Candidate data geometries are identified by determining if a distance between the minimum bounding rectangle of the query geometry and the data geometry is less than a threshold distance. A distance between the query geometry and the candidate data geometry is mathematically calculated when a number of candidate data geometries equals a threshold number or when no more data geometries remain.

Claims

1. In a database system, a computer-implemented method for locating neighboring geometric elements and geographic objects, represented as data geometries stored in the database system, of a query geometry, the method comprising:

storing in the database data geometries representing geometric elements, geographic objects, or both;

determining a minimum bounding rectangle of the query geometry;

determining a minimum bounding rectangle of each data geometry;

identifying as candidate data geometries those data geometries for which a distance between the minimum bounding rectangle of the query geometry and the minimum bounding rectangle of the data geometry is less than a threshold distance; and

determining a distance between the query geometry and only each candidate data geometry when a number of candidate data geometries equals a threshold number.

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

continuously updating the threshold distance to a value equal to one of the distances between the query geometry and a candidate data geometry.

3. The method according to claim 2, wherein the threshold distance is updated to a smallest distance between the query geometry and a candidate data geometry.

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

ordering the candidate data geometries by distance from the query geometry.

5. The method according to claim 1, wherein the data geometries are included in a database organized with an R-tree index, wherein the data geometries are mathematically compared with the query geometry when all nodes in the R-tree index have been searched.

6. The method according to claim 1, wherein the threshold number of geometries is 1000.

7. The method according to claim 1, wherein the data geometries are included in a database organized with an R-tree index, the method further comprising:

determining a distance from each R-tree node processed to the query geometry;

comparing the distance from the R-tree node to a distance between the candidate geometry closest to the query geometry; and

mathematically calculating a distance between the query geometry and candidate data geometries closer than an R-tree node closest to the query geometry.

8. In a database system, a computer-implemented method for comparing geometric elements and geographic objects, represented as data geometries stored in the database system, with a query geometry, the method comprising:

storing in the database data geometries representing geometric elements, geographic objects, or both;

determining a minimum bounding rectangle of the query geometry;

determining a minimum bounding rectangle of each data geometry;

identifying candidate data geometries by determining whether data geometries fulfill a first filter condition with respect to the query geometry by comparing the minimum bounding rectangles of each data geometry with the minimum bounding rectangle of the query geometry;

continuing the comparing of the minimum bounding rectangle of the query geometry with the minimum bounding rectangles until a number of data geometries that fulfill the first filter condition reaches a threshold value; and

comparing the query geometry with each data geometry that fulfills the first filter condition, upon the number of data geometries that fulfill the first filter condition reaching the threshold value.

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

ordering the candidate data geometries by increasing distance from the query geometry.

10. The method according to claim 8, wherein the first filter condition comprises a threshold distance based on a predetermined number of distances between the query geometry and data geometries.

11. The method according to claim 10, wherein a data geometry satisfies the first filter condition if the distance between the minimum bounding rectangle and the query geometry is less than or equal to the threshold distance.

12. The method according to claim 11, wherein the data geometries are included in a database organized with an R-tree index, the method further comprising:

determining a distance from each R-tree node processed to the query geometry;

comparing the distance of the query geometry from the R-tree node to the threshold distance; and

mathematically calculating a distance between the query geometry and candidate data, geometries closer than an R-tree node closest to the query geometry.

13. The method according to claim 10, further comprising:

mathematically calculating a distance between the query geometry and the candidate data geometries when a number of candidate data geometries equals a threshold number or when no more data geometries remain.

14. The method according to claim 13, wherein the distance between the query geometry and the candidate geometry is computed only for geometries having a distance between the minimum bounding rectangle of the candidate geometry and the minimum bounding rectangle of the query geometry less than or equal to the threshold distance.

15. The method according to claim 8, further comprising:

mathematically calculating a distance between the query geometry and the candidate data geometries when a number of candidate data geometries equals a threshold number or when no more data geometries remain.

16. The method according to claim 15, wherein the data geometries are included in a database organized with an R-tree index.

17. The method according to claim 8, wherein the threshold value of data geometries is 1000.

18. A computer program product for performing a process of determining relationships among geometric elements and geographic 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

storing in the database data geometries representing geometric elements, geographic objects, or both;

determining a minimum bounding rectangle of the query geometry;

determining a minimum bounding rectangle of each data geometry;

identifying candidate data geometries by determining whether data geometries fulfill a first filter condition with respect to the query geometry by comparing the minimum bounding rectangles of each data geometry with the minimum bounding rectangle of the query geometry;

continuing the comparing of the minimum bounding rectangles until a number of data geometries that fulfill the first filter condition reaches a threshold value; and

comparing the query geometry with each data geometry that fulfills the first filter condition, upon the number of data geometries that fulfill the first filter condition reaching the threshold value.

19. A system for performing a process of determining relationships among geometric elements and geographic 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;

storing in the database data geometries representing geometric elements, geographic objects, or both;

determining a minimum bounding rectangle of the query geometry;

determining a minimum bounding rectangle of each data geometry;

identifying candidate data geometries by determining whether data geometries fulfill a first filter condition with respect to the query geometry by comparing the minimum bounding rectangles of each data geometry with the minimum bounding rectangle of the query geometry;

continuing the comparing of the minimum bounding rectangles until a number of data geometries that fulfill the first filter condition reaches a threshold value; and

comparing the query geometry with each data geometry that fulfills the first filter condition, upon the number of data geometries that fulfill the first filter condition reaching the threshold value.