Quadtree center tile/boundary tile optimization

• US 7,580,927 B1
• Filed: 05/29/2001
• Issued: 08/25/2009
• Est. Priority Date: 05/29/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Geringer, Daniel, Abugov, Daniel, Ravada, Siva
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US09/865,597
• Time in Patent Office: 3,010 Days
• Field of Search: 707/104.1, 707/2, 707/100, 707/6, 707/3, 707/4, 345/423
• US Class Current: 1/1
• CPC Class Codes: G06F 16/56 having vectorial format
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method for determining positional relationships among objects represented in a database. A plurality of tiles are defined. A distribution of objects with respect to the tiles is determined. The distribution of objects is compared with respect to the tiles to identify objects fulfilling a primary filter condition related to an interaction of the objects with respect to the tiles. Objects are identified that fulfill a secondary filter condition related to an interaction of the geometries of the objects by analyzing the distribution of objects that fulfill the primary filter condition with respect to the tiles. Objects are identified that fulfill the secondary filter condition by comparing geometries of objects that fulfill the primary filter condition that the analysis does not identify as fulfilling the secondary filter condition.

Claims

1. A computer implemented method for determining positional relationships among objects represented in a database, the method comprising:

receiving a query including at least a first object in the database and a desired positional relationship between the first object and a second object in the database;

in response to receiving the query performing the steps of;

identifying, for the first object, one or more tiles in a plurality of tiles defined in a spatial index in the database that are interior tiles of the first object and one or more tiles in the plurality of tiles that are boundary tiles of the first object;

identifying, for the second object, one or more tiles in the plurality of tiles that are interior tiles of the second object and tiles in the plurality of tiles that are boundary tiles of the second object; and

providing the query to a primary filter operable to;

compare tiles of the first object with tiles of the second object to determine whether at least one tile of the first object intersects with at least one tile of the second object; and

determine whether the at least one tile of the second object with which the at least one tile of the first object intersects is an interior tile of the second object;

if so, providing the first object to a result set of objects that satisfy the desired positional relationship,

otherwise, providing the first object and second object to a secondary filter operable to;

compare the second object with the first object; and

if the first object fulfills the desired positional relationship, include the first object in the result set of objects that satisfy the desired positional relationship;

otherwise, exclude the first object from the result set of objects that satisfy the desired positional relationship.

2. The method according to claim 1, wherein the desired positional relationship among objects includes at least one member selected from the group comprising:

the first object in the second object,

the second object contained by the first object,

the first object in the second object where a boundary of the first object intersects a boundary of the second object,

the first object covering the second object where a boundary of the first object intersects a boundary of the second object,

the first object outside the second object where a boundary of the first object intersects a boundary of the second object,

the first object does not cover the second object where a boundary of the first object intersects a boundary of the second object,

the first object overlaps the second object but the boundaries of the first object and the second object do not touch,

the first object overlaps the second object and the boundaries of the first object and the second object touch,

the first object is equivalent to the second object, and

the first object is disjoint from the second object.

3. The method according to claim 1, wherein the tiles all have at least one of the same size and the same shape.

4. The method according to claim 3, wherein the tiles are rectangular.

5. The method according to claim 1, wherein the tiles have different sizes.

6. The method according to claim 1, wherein the database comprises objects on a surface or in a three-dimensional space.

7. The method according to claim 6, wherein the database stores exact representations of the objects and approximate representations of the objects.

8. The method according to claim 7, wherein the objects comprise linestrings and polygons and the method determines positional relationships among the polygons.

9. The method according to claim 8, wherein the linestrings represent streets and the polygons represent a geographic region, and the method determines streets that at least partially fall within the geographic region.

10. The method according to claim 9, wherein the geographic region includes a member selected from the group comprising counties, cities, and zip code regions.

11. The method according to claim 1, wherein the objects comprise polygons and the method determines positional relationships among polygons.

12. The method according to claim 1, wherein the objects are organized with a linear quadtree index.

13. The method according to claim 1, wherein the step of determining whether the at least one tile of the second object with which the at least one tile of the first object intersects is an interior tile of the second object is applied only to objects wherein at least one tile of the first object intersects with at least one tile of the a second object.

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

assigning each tile, a tile code and an associated object as the tiles are defined.

15. The method of claim 1, further comprising the steps of:

exactly comparing the first object the second object if none of the tiles of the second object that intersect with the at least one tile of the first object is a tile that intersects the second object while all of the boundary of the second object lies outside the tile.

16. A computer program product for performing a process for determining positional relationships among objects represented in a database in a computer system, comprising:

a computer readable medium; and

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

receiving a query including at least a first object in the database and a desired relationship between the first object and a second object in the database;

in response to receiving the query performing the steps of;

identifying, for the first object, one or more tiles in a plurality of tiles defined in a spatial index in the database that are interior tiles of the first object and one or more tiles in the plurality of tiles that are boundary tiles of the first object

identifying, for the second object, one or more tiles in the plurality of tiles that are interior tiles of the second object and tiles in the plurality of tiles that are boundary tiles of the second object; and

providing the query to a primary filter operable to;

compare tiles of the first object with tiles of the second object to determine whether at least one tile of the first object intersects with at least one tile of the second object; and

determine whether the at least one tile of the second object with which the at least one tile of the first object intersects is an interior tile of the second object;

if so, providing the first object to a result set of objects that satisfy the desired positional relationship,

otherwise, providing the first object and second object to a secondary filter operable to;

compare the second object with the first object; and

if the first object fulfills the desired positional relationship, include the first object in the result set of objects that satisfy the desired positional relationship;

otherwise, exclude the first object from the result set of objects that satisfy the desired positional relationship.

17. The computer program product of claim 16, further comprising the steps of:

exactly comparing a geometry of the first object with the second object if none of the tiles of the second object that intersect with the at least one tile of the first object is a tile that intersects the second object while all of the boundary of the second object lies outside the tile.

18. A system for performing a process method for determining positional 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;

receiving a query including at least a first object in the database and a desired positional relationship between the first object and a second object in the database;

in response to receiving the query performing the steps of;

identifying, for the first object, one or more tiles in a plurality of tiles defined in a spatial index in the database that are interior tiles of the first object and one or more tiles in the plurality of tiles that are boundary tiles of the first object;

identifying, for the second object, one or more tiles in the plurality of tiles that are interior tiles of the second object and tiles in the plurality of tiles that are boundary tiles of the second object; and

providing the query to a primary filter operable to;

compare tiles of the first object with tiles of the second object to determine whether at least one tile of the first object intersects with at least one tile of the second object; and

determine whether the at least one tile of the second object with which the at least one tile of the first object intersects is an interior tile of the second object;

if so, providing the first object to a result set of objects that satisfy the desired positional relationship,

otherwise, providing the first object and second object to a secondary filter operable to;

compare the second object with the first object; and

if the first object fulfills the desired positional relationship, include the first object in the result set of objects that satisfy the desired positional relationship;

otherwise, exclude the first object from the result set of objects that satisfy the desired positional relationship.

19. The system of claim 18, further comprising the steps of:

exactly comparing the first object with the second object if none of the tiles of the second object that intersect with the at least one tile of the first object is a tile that intersects the second object while all of the boundary of the second object lies outside the tile.