Geographic information data base engine

• US 20050288836A1
• Filed: 03/16/2005
• Published: 12/29/2005
• Est. Priority Date: 03/16/2004
• Status: Active Grant

• Current Assignee: Advanced Tracking Technologies, Inc.
• Original Assignee: Advanced Tracking Technologies, Inc.
• Inventors: Buske, Jeffrey M., Glass, Paul M., Kight, Susan M., Dotson, Vernon C., Chen, Du
• Granted Patent: US 7,430,340 B2
• Time in Patent Office: Days
• US Class Current: 701/29
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method to compress a very large original geographic database down to a manageable and economical size while preserving accuracy is herein described. Similarly, a method to quickly retrieve, decompress, and display data is herein described. An original geographic database is prepared for compression by dividing it into discrete regions called bounding boxes. The bounding boxes may be variable sized to improve accuracy and compression. Absolute map coordinate data is compressed by converting it to relative map coordinate data. Map files are named in a descriptive manner to allow determination of map file characteristics merely by inspecting the file name. Relative map coordinate data can be displayed without being converted to absolute map coordinate data. Alternately, relative map coordinate data may be quickly decompressed into absolute coordinate data. Retrieving compressed data is facilitated by forming view windows having adjacent load regions pre-decompressed and ready for user display.

Claims

1. A method to compress a geographic database and retrieve the compressed geographic data, the method comprising the steps of:

selecting at least one layer of detailed descriptive data to be compressed from an original geographic database;

partitioning the layer into a chosen number of discrete geographic bounding boxes;

selecting a reference coordinate in at least one geographic bounding box to be used as a reference coordinate for all other coordinates in the respective bounding box;

converting a selected number of absolute coordinates in the bounding box to a new relative coordinate with respect to the reference coordinate;

wherein at least one new relative coordinate in the bounding box comprises fewer digits than its absolute coordinate; and

thereby forming a new compressed geographic database having fewer stored digits than the original geographic database.

2. The method of claim 1 further comprising the step of selecting a reference coordinate in each discrete geographic bounding box, wherein each bounding box is of a predetermined identical size.

3. The method of claim 1 further comprising the step of selecting a reference coordinate in each discrete geographic bounding box, and varying the size of each bounding box such that each bounding box contains the same predetermined number of map entities.

4. The method of claim 3, wherein the number of entities per bounding box is determined in a manner such that an error rate associated with a data compression method remains within an acceptable error rate.

5. The method of claim 3, wherein the bounding box size determinations are performed by density calculations comprising count and comparison operations.

6. The method of claim 1, wherein a horizontal absolute coordinate is converted to a horizontal relative coordinate by a method comprising the steps of:

determining the bounding box width by subtracting the horizontal coordinate of the bounding box left side from the horizontal coordinate of the bounding box right side;

subtracting the horizontal coordinate of the bounding box left side from the horizontal relative map coordinate;

dividing the difference by the bounding box width; and

multiplying the quotient by a scaling factor.

7. The method of claim 6, wherein the scaling factor is a power of two whereby rapid compression and decompression are facilitated.

8. The method of claim 1, wherein a vertical absolute coordinate is converted to a vertical relative coordinate by a method comprising the steps of:

determining the bounding box height by subtracting the vertical coordinate of the bounding box bottom side from the vertical coordinate of the bounding box top side;

subtracting the vertical component of the bounding box bottom side from the vertical absolute map coordinate;

dividing the difference by the bounding box height; and

multiplying the quotient by a scaling factor.

9. The method of claim 8, wherein the scaling factor is a power of two whereby rapid compression and decompression are facilitated.

10. The method of claim 1 further including compressing absolute coordinate data by use of a line simplification process before converting the absolute coordinate data to relative coordinate data.

11. The method of claim 1 further including constructing a data structure comprising the steps of:

saving one or more relative coordinate points to a data structure;

including a data structure length code within the data structure; and

including the bounding box size characteristics within the data structure.

12. The method of claim 1 further including a method to compress map label data comprising the steps of:

reading a word contained in the map label data string;

replacing the word in the map label data string with a token from a dictionary file;

repeating the above steps for each word in the map label data string; and

whereby the aggregate map label data string length is reduced.

13. The method of claim 12 further including the creation of a dictionary file comprising the steps of:

reading a map label data string from the original geographic database;

finding a word within the map label data string;

searching the dictionary file to see if the word already exists in the dictionary file;

adding the word to the dictionary file if it does not already exist in the dictionary file;

repeating the above steps until each word in each in each map label data string in the original geographic database has been read; and

associating a token with each word in the dictionary file.

14. The method of claim 1 further including forming a customized lookup table comprising selected common elements from the new compressed database.

15. The method of claim 1 further including converting a horizontal relative coordinate to a horizontal absolute coordinate comprising the steps of:

determining the bounding box width by subtracting the horizontal coordinate of the bounding box left side from the horizontal coordinate of the bounding box right side;

multiplying the horizontal relative coordinate by the bounding box width;

dividing the product by a scaling factor; and

adding to the quotient the horizontal coordinate of the bounding box left side.

16. The method of claim 1 further including converting a vertical relative coordinate to a vertical absolute coordinate comprising the steps of:

determining the bounding box height by subtracting the vertical coordinate of the bounding box bottom side from the vertical coordinate of the bounding box top side;

multiplying the vertical relative coordinate by the bounding box height;

dividing the product by a scaling factor; and

adding to the quotient the vertical coordinate of bounding box bottom side.

17. The method of claim 1 further including a method of naming a compressed geographic database file, the method comprising the steps of:

determining the geographic area represented by the geographic database file;

determining the type of data contained within the geographic database file;

determining the accuracy of the data contained within the geographic database file; and

naming the geographic database file such that the geographic area represented by the geographic database file, the type of data contained within the geographic database file, and the accuracy of the data contained within the geographic database can be determined merely by inspecting the geographic database file name.

18. The method of claim 1 further comprising the step of retrieving selected segments of the new compressed geographic database by forming view windows each having an adjacent projected area to be viewed which is pre-decompressed before an actual retrieval thereof.

19. The method of claim 18, wherein one or more relative coordinate points are displayed without being converted to absolute coordinate points.

20. The method of claim 18, wherein one or more relative coordinate points are displayed after being converted to absolute coordinate points.

21. The method of claim 18 further including a method of map data memory management comprising the steps of:

creating a load region around the view window;

preloading into map data memory map entities located within the load region; and

whereby the map entities adjacent to the view window are already resident in map data memory and are available for immediate display when panning or zooming.

22. The method of claim 21 further including entity preloading at a lower priority level than other system tasks.

23. The method of claim 18 further including a method of map data memory management comprising the steps of:

identifying view window movement, panning, or zooming;

preloading into map data memory map entities located in the direction of the view window movement, panning, or zooming; and

whereby the map entities in the direction of view window movement, panning, or zooming are already resident in map data memory and are available for immediate display.

24. The method of claim 23 further including entity preloading at a lower priority level than other system tasks.

25. The method of claim 18 further including a method of map data memory management comprising the steps of:

identifying view window movement, panning, or zooming;

unloading from map data memory map entities located in the opposite direction of the view window movement, panning, or zooming; and

whereby the map data memory is freed of the map entities.

26. The method of claim 25 further including entity preloading at a lower priority level than other system tasks.

27. The method of claim 18 further including a method of map data memory management comprising the steps of:

identifying a next lower zoom level;

preloading into map data memory map entities located within the next lower zoom level; and

whereby the map entities located within the next lower zoom level are already resident in map data memory and are available for immediate display when zooming out.

28. The method of claim 27 further including entity preloading at a lower priority level than other system tasks.

29. The method of claim 18 further including a method of map data memory management comprising the steps of:

creating an unload region around a view window;

unloading from map data memory map entities located outside the unload region; and

whereby the map data memory is freed of the map entities.

30. The method of claim 29 further including entity preloading at a lower priority level than other system tasks.

31. A method of naming a compressed geographic database file, the method comprising the steps of:

determining the geographic area represented by the geographic database file;

determining the type of data contained within the geographic database file;

determining the accuracy of the data contained within the geographic database file; and

naming the geographic database file such that the geographic area represented by the geographic database file, the type of data contained within the geographic database file, and the accuracy of the data contained within the geographic database can be determined merely by inspecting the geographic database file name.

32. A system for compressing a geographic database and retrieving the compressed geographic data, the system comprising:

a means for selecting at least one layer of detailed descriptive data to be compressed from an original geographic database functioning to allow an user to choose one or more entity types of interest;

a means for partitioning the selected layer into a chosen number of discrete geographic bounding boxes functioning to provide a reference grid for data compression;

a means for selecting a reference coordinate in at least one geographic bounding box functioning to provide a reference coordinate for all other coordinates in the respective bounding box;

a means for converting a selected number of absolute coordinates in the bounding box to a new relative coordinate with respect to the reference coordinate functioning to reduce the number of digits of the coordinates; and

a means for forming a new compressed geographic database functioning to provide a compact map data source for mapping applications.