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

• US 20060184519A1
• Filed: 03/20/2006
• Published: 08/17/2006
• 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,725,425 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 system for searching a map database, the system comprising:

a map database comprising a plurality of sub-regions and a plurality of map objects, wherein the sub-regions comprise a central portion and a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions, wherein each of the sub-regions is identified with one of a plurality of keys, and wherein the spatial map objects comprise spatial coordinates and are associated with one or more of said keys; and

a processor configured to;

receive a query for map objects within a region of spatial coordinates;

identify at least one key associated with the region; and

select at least one map object associated with said at least one key.

2. The system of claim 1, wherein the plurality of sub-regions comprise multiple tiers of sub-regions, such that first sub-regions are located within second sub-regions.

3. The system of claim 1, wherein the processor is configured to identify the at least one key associated with the region using a Peano-Hilbert curve.

4. The system of claim 1, wherein the map database is stored within a storage that comprises a hard disk or a main memory.

5. The system of claim 1, wherein the region comprises a polygon enclosing a location within the coordinate system.

6. The system of claim 1, wherein the database further comprises non-spatial data associated with at least one of the map objects.

7. The system of claim 6, wherein the query comprises a request for non-spatial data associated with map objects within a specified distance of a specified location.

8. The system of claim 7, wherein the non-spatial data comprises business names.

9. The system of claim 7, wherein the non-spatial data comprises business types.

10. The system of claim 1, wherein said keys comprise numeric keys and the one or more keys associated with the region comprises a range of keys.

11. A method of searching a map database for objects within a specified spatial region, the method comprising:

providing a map database comprising a plurality of sub-regions and a plurality of map objects, wherein the sub-regions comprise a central portion and a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions, wherein each of the sub-regions is identified with one of a plurality of keys, and wherein each of the map objects comprises spatial coordinates and is associated with one or more of said keys;

receiving a query for one or more map objects within a region of spatial coordinates;

identifying one or more keys associated with the region, wherein each of said keys identifies a sub-regions in said map database; and

selecting at least one map object associated with one of the set of keys.

12. The method of claim 11, wherein the plurality of sub-regions comprise multiple tiers of sub-regions, such that first sub-regions are located within second sub-regions.

13. The method of claim 11, wherein identifying the one or more keys associated with the region comprises using a Peano-Hilbert curve to identify each of the at least one set of keys.

14. The method of claim 11, wherein the region comprises a polygon enclosing a location within the coordinate system.

15. The method of claim 11, wherein the map database further comprises non-spatial data associated with at least one of the map objects.

16. The method of claim 15, wherein the query comprises a request for non-spatial data associated with map objects within a specified distance of a specified location.

17. The method of claim 16, wherein the non-spatial data comprises business names.

18. The method of claim 16, wherein the non-spatial data comprises business types.

19. The method of claim 11, wherein said keys comprise numeric keys and the one or more keys associated with the region comprises a range of keys.