For most navigational functions it is important to have in the vehicle an up-to-date map database, and for some functions it is critical, especially those related to active safety. A common strategy is to transfer update information to the vehicle whenever it becomes available over a wireless channel. The wireless channel might bi-directional, such as wifi and cellular phone, broadcast, such as satellite radio, FM sub-carrier or ATSC datacasting, or a combination of both. In any case it would be impractical or extremely inefficient to transmit the entire new database to replace an existing version, since it is likely to be several gigabytes in size.
Instead it is desirable to transfer just that information related to changes made to the existing database. A major difficulty is that any change made to the content of a map database generally causes changes to all assigned entity IDs and all assigned indices during the compilation process. These new IDs and indices permeate the entire compiled database so that any collection of increments will likely constitute most of the database. To overcome this difficulty, three approaches have been taken, which are briefly 1) onboard compiler 2) look-aside store 3) geographical tiles.
On-board compiler
In this case, basic changes made to the interchange format of the database are transmitted to the vehicle. Such changes are represented in transactional form consisting of additions, deletions and replacements. These changes are applied to the existing onboard database in interchange format. The interchange format for the onboard database could either be stored separately or generated as needed by “decompiling” the run-time format. The combined database is then compiled, which involves assigning IDs and applying indices.
This onboard compilation will likely be computationally intensive and require considerable memory. However, it does not need to be interactive and iterative as does the off-board compilation since consistency checks and resolution will have already been done. Furthermore, the onboard compilation can be done in the background so computation time is not critical.
Look-aside store
In this case, basic changes are also transmitted to the vehicle, but are placed into a separate memory location called a look-aside store. The changes are also represented in transactional form but may appear in any convenient format, which is not necessarily either interchange or run-time. During operation of the navigation unit, the look-aside store is searched each time the main database is accessed. Any transactions (changes) that pertain to the accessed data are then applied.
The necessity of examining the look-aside store and applying changes for each database access of course complicates the navigational algorithms and lengthens their computation time. However, this avoids the need for an onboard compiler.
Geographical tiles
In this approach, the map database is broken down into relatively small rectangular regions (tiles) that tessellate the map. The tile size is on the order of 1 km on a side. These tiles are compiled separately, so that all IDs and indices are conditioned by the particular tile to which they apply. The tiles that have changed due to basic entity or attribute changes to the database are transmitted to the vehicle, where they replace the corresponding existing tile.
Replacing tiles is considerably simpler than onboard compilation or employing a look-aside store. However, it may not be efficient for transmission. A local change to entities and attributes, regardless of the extent, requires the transmission of the entire containing tile. Furthermore, there are edge effects in which a change in an entity within one tile affects the entities in neighboring tiles. It is quite possible that a small number of entity changes will require the transmission of almost all tiles, thereby defeating the purpose of incremental updates. These problems can be address by selecting the tile size and the frequency of updating.
Instead it is desirable to transfer just that information related to changes made to the existing database. A major difficulty is that any change made to the content of a map database generally causes changes to all assigned entity IDs and all assigned indices during the compilation process. These new IDs and indices permeate the entire compiled database so that any collection of increments will likely constitute most of the database. To overcome this difficulty, three approaches have been taken, which are briefly 1) onboard compiler 2) look-aside store 3) geographical tiles.
On-board compiler
In this case, basic changes made to the interchange format of the database are transmitted to the vehicle. Such changes are represented in transactional form consisting of additions, deletions and replacements. These changes are applied to the existing onboard database in interchange format. The interchange format for the onboard database could either be stored separately or generated as needed by “decompiling” the run-time format. The combined database is then compiled, which involves assigning IDs and applying indices.
This onboard compilation will likely be computationally intensive and require considerable memory. However, it does not need to be interactive and iterative as does the off-board compilation since consistency checks and resolution will have already been done. Furthermore, the onboard compilation can be done in the background so computation time is not critical.
Look-aside store
In this case, basic changes are also transmitted to the vehicle, but are placed into a separate memory location called a look-aside store. The changes are also represented in transactional form but may appear in any convenient format, which is not necessarily either interchange or run-time. During operation of the navigation unit, the look-aside store is searched each time the main database is accessed. Any transactions (changes) that pertain to the accessed data are then applied.
The necessity of examining the look-aside store and applying changes for each database access of course complicates the navigational algorithms and lengthens their computation time. However, this avoids the need for an onboard compiler.
Geographical tiles
In this approach, the map database is broken down into relatively small rectangular regions (tiles) that tessellate the map. The tile size is on the order of 1 km on a side. These tiles are compiled separately, so that all IDs and indices are conditioned by the particular tile to which they apply. The tiles that have changed due to basic entity or attribute changes to the database are transmitted to the vehicle, where they replace the corresponding existing tile.
Replacing tiles is considerably simpler than onboard compilation or employing a look-aside store. However, it may not be efficient for transmission. A local change to entities and attributes, regardless of the extent, requires the transmission of the entire containing tile. Furthermore, there are edge effects in which a change in an entity within one tile affects the entities in neighboring tiles. It is quite possible that a small number of entity changes will require the transmission of almost all tiles, thereby defeating the purpose of incremental updates. These problems can be address by selecting the tile size and the frequency of updating.
No comments:
Post a Comment