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

• US 5,963,956 A
• Filed: 02/27/1997
• Issued: 10/05/1999
• 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): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/807,471
• Time in Patent Office: 950 Days
• Field of Search: 707/1-206, 707/501-529, 707/531-540, 348/466-845.1, 340/905-933
• 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 method of organizing spatial data objects in a map database, comprising:

referencing data objects as location points in a region to a coordinate system;

separating said region into multiple sub-regions; and

assigning said data objects whose location point falls within a sub-region to said sub-region so long as no part of said object extends outside said sub-region by a predetermined amount.

2. The method of claim 1 wherein said data objects are spatial data objects.

3. The method of claim 1 wherein said location point of said data object is calculated by determining the minimum bounding rectangle for said data object.

4. The method of claim 1 wherein multiple sub-regions further comprise multiple tiers of sub-regions.

5. The method of claim 1 wherein each of said sub-regions is assigned a unique code.

6. The method of claim 1 wherein said predetermined amount is equal to one-half the size of said quadrant.

8. The method of claim 1 wherein said predetermined amount is equal to the size of said quadrant.

9. The method of claim 1 wherein said data objects are selected from the group comprising:

lines, circles, squares and polygons.

10. The method of claim 1 wherein said region is separated into multiple square sub-regions.

11. The method of claim 1 wherein said region is separated into multiple rectangular sub-regions.

12. The method of claim 1 wherein said region is separated into multiple round sub-regions.

13. The method of claim 1 wherein said region is separated into multiple hexagonal sub-regions.

7. The method of claim I wherein said predetermined amount is equal to one-fourth the size of said quadrant.

14. A method of storing spatial data objects to a computer memory, comprising the steps of:

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

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

calculating the boundaries of a first 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;

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; and

storing said spatial data objects along with its reference to a specific sub-region to said computer memory.

15. The method of claim 14 wherein said spatial data objects are part of a map database.

16. The method of claim 14 wherein said spatial data objects are selected from the group comprising:

lines, circles, squares and polygons.

17. The method of claim 14 wherein said computer memory is a computer hard disk.

18. The method of claim 14 wherein said referencing step comprises the Peano-Hilbert method of ordering spatial data quadrants.

19. The method of claim 14 wherein said sub-regions are shingles and said reference is a shingle code.

20. The method of claim 14 wherein the size of said overlap between sub-regions is equal to the size of said sub-region.

21. The method of claim 14 wherein the size of said overlap between sub-regions is equal to one-half the size of said sub-region.

22. The method of claim 14 wherein the size of said overlap between sub-regions is equal to one-fourth the size of said sub-region.

23. The method of claim 14 wherein said determining step further comprises calculating a minimum bounding rectangle for said spatial data object.

24. The method of claim 23, wherein said assigning step 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 position.

25. The method of claim 14 wherein said spatial data objects are selected from the group comprising:

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

26. The method of claim 14 further comprising the steps of:

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

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. The method of claim 14 wherein said data objects are selected from the group comprising:

lines, circles, squares and polygons.

28. The method of claim 14 wherein said region is separated into multiple square sub-regions.

29. The method of claim 14 wherein said region is separated into multiple rectangular sub-regions.

30. The method of claim 14 wherein said region is separated into multiple round sub-regions.

31. The method of claim 14 wherein said region is separated into multiple hexagonal sub-regions.