Map Database Management - Run-time Format

Run-time Format

Runtime formats are typically proprietary, preventing interoperation of maps between different navigation systems. However a new initiative called Physical Storage Format (PSF) is an industry grouping of car manufacturers, navigation system suppliers and map data suppliers whose objective is the standardization of the data format used in car navigation systems. Companies involved include BMW, Volkswagen, Daimler, Renault, ADIT, Alpine Electronics, Navigon, Bosch, DENSO, Mitsubishi, Harman Becker, Panasonic, PTV, Continental AG, Navteq, Tele Atlas and Zenrin.

The database is reorganized by a navigation provider through a compilation process that includes at least the following five steps:

1. Check for network consistency. For example, ensure that all node pairs that should be connected by a link do have such a link and inversely all node pairs that should not be connected do not have a connecting link.
2. Assign identifiers (IDs) to all entities in a systematic manner.
3. Apply multiple sets of indices to entities to facilitate searching the database in expected ways.
4. Replace multiple occurrences of data items (street names, coordinates, etc.) by indices into tables containing a single copy of each such item.
5. Apply other compression techniques to reduce the overall size of the database.

The consistency check of step 1 is usually a very interactive and iterative process that might take weeks to complete. During this time discrepancies need to be detected, investigated and resolved.

In step 2, IDs are generally assigned sequentially as entities of each type are encountered. Any changes made to the input database from one version to another will affect the assignment of IDs to all entities. Consequently, there is little expectation of continuity in the assignment between versions.

In step 3 each applied index allows the database to be quickly searched in a specific manner. One index set applied to links can be sorted by the alphabetic order of the street names of the links. Another index set applied to links can be sorted according to the nodes to which they are connected to facilitate route planning. Yet another index set applied to nodes can be sorted according to their order of appearance along a road. In some of these cases a binary search can be performed instead of an exhaustive search and in some cases, a search process can be replaced with a simple table lookup.