System and method of optimizing database queries in two or more dimensions

• US 20030187867A1
• Filed: 10/22/2002
• Published: 10/02/2003
• Est. Priority Date: 02/27/1997
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Smartt, Brian E.
• Granted Patent: US 7,035,869 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• 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 and system for storing and retrieving spatial data objects from a spatial database is discussed. The system stores multi-dimensional objects within the database by determining their position in a multi-tiered coordinate system. One each object has been assigned to a particular coordinate, the object is further assigned to one of many overlapping sections within the coordinate system. Each object is assigned to a particular section of the coordinate system depending on its overall size and position.

Claims

1. A method of partitioning a database, the method comprising:

creating a top level region comprising substantially all of the objects in the database;

creating a first sub-region comprising a first subset of objects contained in the top level region; and

creating a second sub-region comprising a second subset of objects contained in the top level region and a subset of objects contained in the first sub-region.

2. The method of claim 1, wherein the database is a map database and creating the top level region comprises creating a top level region defining a geographic area enclosing substantially all objects within the map database.

3. The method of claim 2, wherein creating the first sub-region comprises creating a first geographic sub-region of the top level region.

4. The method of claim 2, wherein creating the second sub-region comprises creating a second geographic sub-region having an overlapping region common to both the first and second sub-regions.

5. The method of claim 4, wherein the overlapping region comprises about 25% of an area of the first sub region.

6. A method of searching a database, the method comprising:

receiving a query defining a search space having a perimeter;

determining a set of overlapping regions in a first hierarchical level that contain at least a portion of the perimeter, the set of overlapping regions defining a boundary; and

determining additional overlapping regions in the first hierarchical level that are contained within the boundary.

7. The method of claim 6, further comprising eliminating a first region from the set of overlapping regions for which the portion of the perimeter contained within the first region is wholly contained within a section of the first region overlapping a second region.

8. The method of claim 6, wherein determining the set of overlapping regions in the first hierarchical level comprises:

tracing a path along the perimeter;

determining each region through which the path intersects; and

eliminating redundant occurrences of regions.

9. The method of claim 6, wherein determining additional overlapping regions in the first hierarchical level comprises:

determining a region at a boundary minimum along a first row of the set of overlapping regions defining the boundary;

determining a region at a boundary maximum along the first row of the set of overlapping regions defining the boundary; and

determining overlapping regions between the region at the boundary minimum and the region at the boundary maximum.

10. The method of claim 6, wherein determining additional overlapping regions in the first hierarchical level comprises determining the additional overlapping regions using a Peano-Hilbert curve.

11. The method of claim 6, further comprising determining a set of overlapping regions in a second hierarchical level that contain at least a portion of the perimeter.

12. The method of claim 6, wherein the perimeter defines a rectangular window.

13. The method of claim 6, wherein the perimeter defines a polygonal window.

14. A method of searching a database, the method comprising:

receiving a query;

determining a first set of overlapping regions in a lowest level of a tiered structure based at least in part on the query; and

determining a second set of overlapping regions in an upper level of the tiered structure based at least in part on the query, each region in the upper level of the tiered structure comprising a plurality of regions from the lowest level of the tiered structure.

15. The method of claim 14, wherein the tiered structure comprises a map database and each region in the tiered structure defines a geographic area.

16. The method of claim 14, wherein at least one region within the tiered structure contains an object from a map database having an area wholly contained within an area defined by the region.

17. The method of claim 14, wherein at least one upper level region within the tiered structure contains an object from a map database having a dimension larger than a dimension of the region from the lowest level.

18. A method of searching a database, the method comprising:

generating a query;

receiving a first set of regions from a lowest level of a tiered database, the tiered database comprising overlapping regions and the first set of regions based at least in part on the query; and

receiving a second set of regions from an upper level of the tiered database based at least in part on the query, each region in the upper level of the tiered database comprising a plurality of regions from the lowest level of the tiered database.

19. The method of claim 18, wherein the first set of regions from the lowest level of the tiered database define at least one object from the database, each of the at least one object having an area smaller than an area of the lowest level region.

20. The method of claim 18, wherein generating the query comprises generating a query for an area within a map database.

21. The method of claim 18, wherein generating the query comprises generating a query for an object within a map database.

22. The method of claim 18, wherein each region in a level of the tiered database overlaps an adjacent region.

23. The method of claim 18, wherein each region in a level of the tiered database overlaps an adjacent region by about 25% of an area defined by the adjacent region.

24. The method of claim 18, wherein at least one region in the first set of regions from the lowest level of the tiered database comprises street segment objects from a street map database.

25. An electronic map, comprising:

a memory configured to store a map database configured as multiple tiers, each tier lower than a top level tier comprising overlapping regions;

a processor configured to receive a query and, based in part on the query, further configured to determine a first set of overlapping regions in a lowest tier of the map database; and

a monitor configured to display a map segment comprising objects from the first set of overlapping regions.

26. The electronic map of claim 25, wherein the processor is further configured to determine at least one overlapping region in a tier higher than the lowest tier of the map database, the map segment further comprising at least one object from the tier higher than the lowest tier.

27. The electronic map of claim 25, wherein the memory comprises a disk.

28. The electronic map of claim 25, wherein the query comprises a query for a region within the map database.

29. The electronic map of claim 25, wherein the query comprises a query for an object stored within a region in one tier of the map database.

30. The electronic map of claim 25, wherein the query comprises a query for a window from the map database.

31. One or more processor readable storage devices having processor readable code embodied thereon, the processor readable code for programming one or more processors to perform a method of searching a database, the method comprising:

receiving a query;

determining a first set of overlapping regions in a lowest level of a tiered structure based at least in part on the query; and

determining a second set of overlapping regions in an upper level of the tiered structure based at least in part on the query, each region in the upper level of the tiered structure comprising a plurality of regions from the lowest level of the tiered structure.