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

• US 20040193615A1
• Filed: 03/27/2003
• Published: 09/30/2004
• 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.
• Granted Patent: US 7,181,467 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/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. A method for locating neighboring data geometries of a query geometry, the method comprising:

determining a minimum bounding rectangle of the query geometry;

determining a minimum bounding rectangle of each data geometry;

identifying candidate data geometries by determining if a distance between the minimum bounding rectangle of the query geometry and the data geometry is less than a threshold distance; and

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

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

continuously updating the threshold distance to a value equal to one of the mathematically calculated distances.

3. The method according to claim 2, wherein the threshold distance is updated to a smallest mathematically calculated distance.

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. A method for comparing data geometries with a query geometry, the method comprising:

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

continuing the comparing 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 or no more data geometries remain.

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 that reflects a predetermined number of computed exact geometry-to-query distances.

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 query is less than or equal to the threshold distance.

12. 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.

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

14. 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.

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, wherein the data geometries are mathematically compared with the query geometry when all relevant nodes in the R-tree index have been searched.

17. The method according to claim 15, 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.

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

19. A computer program product for performing a process of determining relationships among 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;

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

continuing the comparing of the minimum bounding rectangles until a number of data geometries that fulfill the first filter condition reaches a threshold value or no more data geometries remain.

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

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

continuing the comparing of the minimum bounding rectangles until a number of data geometries that fulfill the first filter condition reaches a threshold value or no more data geometries remain.