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

• US 6,470,287 B1
• Filed: 01/14/1999
• Issued: 10/22/2002
• Est. Priority Date: 02/27/1997
• Status: Expired due to Term

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Telcontar
• Inventors: Smartt, Brian E.
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/231,515
• Time in Patent Office: 1,377 Days
• Field of Search: 707/1-206, 707/501-540, 345/418-427
• US Class Current: 702/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 database of multi-dimensional objects, comprising:

a first function configured to determine the size of each multi-dimensional object within a coordinate system;

a second function configured to assign each multi-dimensional object to a location point in said coordinate system;

a third function configured to calculate the boundaries of a first tier of overlapping subregions of said coordinate system so that each location point in said coordinate system is assigned to at least one sub-region, wherein said overlapping sub-regions have a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent subregions; and

a key assigning each multi-dimensional object to one of said overlapping subregions of said coordinate system.

2. The database of claim 1 wherein said multi-dimensional objects are selected from the group comprising:

lines, polygons, circles and squares.

3. The database of claim 1 wherein said location point is calculated by determining the minimum bounding rectangle of said multi-dimensional object.

4. The database of claim 1 wherein subregions comprise multiple tiers of subregions.

5. The database of claim 1, wherein the sub-region has four sides.

6. The database of claim 1, wherein the overlap portion is one-half the length of one of said sides of the sub-region.

7. The database of claim 1, wherein the overlap portion is one-fourth the length of one of said sides of the sub-region.

8. The database of claim 1, wherein the overlap portion is equal to the length of one of said sides of the sub-region.

9. The database of claim 1, wherein the multi-dimensional objects comprise multi-dimensional map objects.

10. A map database comprising a set of multi-dimensional map objects, wherein each multi-dimensional map object comprises:

a key assigning each multi-dimensional map object to one of a plurality of sub-regions of said coordinate system, wherein the sub-regions comprise a central portion and a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions.

11. The map database of claim 10, comprising a location component that defines the minimum bounding rectangle for the multi-dimensional map object.

12. The map database of claim 10, 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 map database of claim 10, wherein the sub-regions have four sides.

14. The map database of claim 10, wherein the predetermined overlap portion is one-half the length of one of said sides of the sub-region.

15. The map database of claim 10, wherein the predetermined overlap portion is one-fourth the length of one of said sides of the sub-region.

16. The map database of claim 10, wherein the predetermined overlap portion is equal to the length of one of said sides of the sub-region.

17. A computer controlled mapping system for storing and retrieving spatial data objects to and from a computer memory, comprising:

means for determining the size of each data object within a coordinate system;

means for assigning each spatial data object to a location point in said coordinate system;

means for calculating the boundaries of a first tier of overlapping sub-regions of said coordinate system so that each location point in said coordinate system is assigned to at least one sub-region, wherein said sub-regions have a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions; and

means for storing said spatial data objects and its reference to a specific sub-region to said computer memory.

18. The mapping system of claim 17, further including means for referencing each spatial data object that is smaller than the size of said sub-regions in said first tier to a specific sub-region of said coordinate system based on the location point of each spatial data object.

19. The mapping system of claim 17 wherein said spatial data objects are selected from the group consisting of:

lines, circles, squares and polygons.

20. The mapping system of claim 17 wherein the size of said overlap portion shared between sub-regions is equal to the size of said sub-region.

21. The mapping system of claim 17 wherein the size of said overlap portion shared between sub-regions is equal to one-half the size of said sub-region.

22. The mapping system of claim 17 wherein the size of said overlap portion shared between sub-regions is equal to one-fourth the size of said sub-region.

23. The mapping system of claim 17 wherein said means for determining comprises determining a minimum bounding rectangle for said spatial data object.

24. The mapping system of claim 23, wherein said means for assigning comprises determining the coordinate position of the lower left corner of the minimum bounding rectangle of said spatial data object and storing said location point to said coordinate position.

25. The mapping system of claim 17 wherein said spatial data objects are selected from the group consisting of:

lines, circles, squares and polygons.

26. The mapping system of claim 17 further comprising:

means for calculating the boundaries of a second tier of overlapping sub-regions of said coordinate system so that each point in said coordinate system is assigned to at least one sub-region; and

means for referencing each spatial data object that is larger than the size of said sub-regions in said first tier to a specific sub-region in said second tier based on the location point of each spatial data object.

27. A computer system for storing map data, comprising:

a first function configured to determine the size of each multi-dimensional object within a coordinate system;

a second function configured to assign each multi-dimensional object to a location point in said coordinate system;

a third function configured to calculate the boundaries of a first tier of overlapping subregions of said coordinate system so that each location point in said coordinate system is assigned to at least one subregion, wherein said subregions have a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent subregions; and

a key assigning each multi-dimensional object to one of said overlapping subregions of said coordinate system.

28. The computer system of claim 27 wherein said multi-dimensional objects are selected from the group comprising:

lines, polygons, circles and squares.

29. The computer system of claim 27 wherein said location point is calculated by determining the minimum bounding rectangle of said multi-dimensional object.

30. The computer system of claim 27 wherein subregions comprise multiple tiers of subregions.

31. The computer system of claim 27, wherein the subregion has four sides.

32. The computer system of claim 27, wherein the overlap portion is one-half the length of one of said sides of the subregion.

33. The computer system of claim 27, wherein the overlap portion is one-fourth the length of one of said sides of the subregion.

34. The computer system of claim 27, wherein the overlap portion is equal to the length of one of said sides of the subregion.

35. The computer system of claim 27, wherein the multi-dimensional objects comprise multi-dimensional map objects.