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

• US 7,725,425 B2
• Filed: 03/20/2006
• Issued: 05/25/2010
• Est. Priority Date: 02/27/1997
• Status: Expired due to Term

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Smartt, Brian E.
• Primary Examiner(s): Jung; David Y
• Application Number:
  US11/385,625
• Publication Number:
  US 20060184519A1
• Time in Patent Office: 1,527 Days
• Field of Search: None
• US Class Current: 707/770
• 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 computer memory storing 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 index keys, and wherein the spatial map objects comprise spatial coordinates and are associated with one or more of the index keys; and

a computer system configured to;

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

identify in the computer memory at least one index key associated with the region; and

select from the computer memory at least one map object associated with the at least one index 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 computer system 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 the 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 executed by a computer system and comprising:

storing in a computer memory 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 index keys, and wherein each of the map objects comprises spatial coordinates and is associated with one or more of the index keys;

receiving by the computer system a query for one or more map objects within a region of spatial coordinates;

identifying by the computer system one or more index keys index the computer memory associated with the region, wherein each of the index keys identifies a sub-regions in the map database;

selecting from the computer memory at least one map object associated with one of the set of index 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 index keys associated with the region comprises using a Peano-Hilbert curve to identify each of the at least one set of index 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 nonspatial data associated with at least one of the map objects.

16. The method of claim 15, wherein the query comprises a request for nonspatial 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 the index keys comprise numeric keys and the one or more keys associated with the region comprises a range of keys.

20. A system for storing spatial data objects, the system comprising:

a computer memory storing a spatial database comprising a plurality of shingles, each shingle adjacent to at least one other shingle, each shingle overlapping each of its adjacent shingles by a predetermined portion of the shingle, the shingles arranged in a plurality of levels, from a lowest level to a highest, top level, the shingles within each level having a same size;

a computer system configured to perform the steps of;

determining from the computer memory a location of a data object within a coordinate system;

assigning the data object that is not larger than the size of the shingles in a level to the shingle in that level that completely contains the data object, including any portion of the data object that is within the portion of the shingle overlapping an adjacent shingle, and storing the assignment in the computer memory; and

storing the data object along with a reference to the shingle to which it is assigned in the computer memory.

21. The system of claim 20, wherein the spatial data objects are part of a map database stored in the computer memory.

22. The system of claim 20, wherein the spatial data objects are selected from the group consisting of:

lines, circles, squares and polygons.

23. The system of claim 20, wherein the computer system is further configured to assign each shingle a unique index key.

24. The system of claim 20, wherein the size of the overlapping portion is equal to one-half the size of a shingle.

25. The system of claim 20, wherein the size of the overlapping portion is equal to one-fourth the size of a shingle.

26. The system of claim 20, wherein determining a location of a data object comprising determining a minimum bounding rectangle for the spatial data object.

27. The system of claim 26, wherein assigning the data object comprises determining a coordinate position of a lower left corner of the minimum bounding rectangle of the data object.

28. The system of claim 20, wherein the data objects are selected from the group consisting of:

engineering and architectural drawings, animation and virtual reality databases and raster bit maps.

29. The system of claim 20, wherein the computer system is further configured to perform the steps of:

calculating the boundaries of a second level of overlapping shingles of the coordinate system so that each point in the coordinate system is assigned to at least one shingle; and

assigning each data object that is larger than the size of the shingles in the first level to a specific shingle in the second level based on the location of each data object.

30. The system of claim 20, wherein the data objects are selected from the group consisting of:

lines, circles, squares and polygons.

31. The system of claim 20, wherein the region is separated into multiple square, rectangular, round, or hexagonal shingles.

32. The system of claim 20, wherein storing the data object comprises storing the data object in the spatial database of multi-dimensional objects, wherein the spatial database, comprises:

a set of multidimensional objects, wherein each object includes a location within a coordinate system; and

a code referencing each multi-dimensional object to a shingle of the coordinate system.

33. The system of claim 32, wherein the multi-dimensional objects are selected from the group comprising:

lines, polygons, circles, and squares.

34. The system of claim 32, wherein the location point is calculated by determining the minimum bounding rectangle of the multi-dimensional object.

38. The method of claim 28, wherein the minimum bounding rectangle for the data object is over-estimated.

35. A method of organizing spatial data objects in a spatial database, the spatial database stored in a computer memory, the method executed by a computer system and comprising:

storing in the spatial database a plurality of shingles, each shingle adjacent to at least one other shingle, each shingle overlapping each of its adjacent shingles by a predetermined portion of the shingle, the shingles logically arranged in a plurality of levels, from a lowest level to a highest, top level, the shingles within each level having a same size;

determining by the computer system for the data objects respective locations in a coordinate system;

assigning by the computer system each data object that is not larger than the size of the shingles in a level to the shingle in that level that completely contains the data object, including any portion of the data object that is within the portion of the shingle overlapping an adjacent shingle.

36. The method of claim 35, wherein the data objects are spatial data objects.

37. The method of claim 35, wherein determining for the data object respective locations comprises determining for each data object a minimum bounding rectangle for the data object.

39. The method of claim 35, wherein each shingle is assigned a unique key.

40. The method of claim 35, wherein the size of the overlapping portion is equal to one-half of the size of shingle.

41. The method of claim 35, wherein the size of the overlapping portion is equal to one-fourth of the size shingle.

42. The method of claim 35, wherein the data objects are selected from the group comprising:

lines, circles, squares and polygons.

43. The method of claim 35, wherein each level is separated into multiple square, rectangular, round, or hexagonal shingles.

44. The method of claim 35, further comprising:

calculating by the computer system the boundaries of a second level of overlapping shingles of the coordinate system so that each point in the coordinate system is assigned to at least one shingle; and

assigning by the computer system each data object that is larger than the size of the shingles in the first level to a specific shingle in the second level based on the location of each data.