Map database management
Encyclopedia
Map database management stems from navigation units becoming more common in automotive vehicles (see Automotive navigation system
Automotive navigation system
An automotive navigation system is a satellite navigation system designed for use in automobiles. It typically uses a GPS navigation device to acquire position data to locate the user on a road in the unit's map database. Using the road database, the unit can give directions to other locations...

). They serve to perform usual navigation functions, such as finding a route to a desired destination and guiding the driver to it or determining the vehicle’s location and providing information about nearby points of interest. Moreover, they are playing an increasingly important role in the emerging areas of Location-based service
Location-based service
A Location-Based Service is an information or entertainment service, accessible with mobile devices through the mobile network and utilizing the ability to make use of the geographical position of the mobile device....

s, Active safety
Active safety
In engineering, active safety systems are systems activated in response to a safety problem or abnormal event. Such systems may be activated by a human operator, automatically by a computer driven system, or even mechanically...

 functions and Advanced Driver Assistance Systems
Advanced Driver Assistance Systems
Advanced Driver Assistance Systems, or ADAS, are systems to help the driver in its driving process. When designed with a safe Human-Machine Interface it should increase car safety and more generally road safety.Examples of such a system are:...

. Common to these functions is the requirement for an on-board map database that contains information describing the road network. Maintaining such a map database, including keeping it up to date and incorporating related information, is the subject of this article.

Content of a map database

A map database represents a road network along with associated features. Map providers choose various models of a road network as a basis to formulate a database. Commonly, such a model comprises basic elements (nodes, links and areas) of the road network and properties of those elements (location coordinates, shape, addresses, road class, speed range, etc). The basic elements are referred to as features and the properties as attributes. Other information associated with the road network is also included, including points of interest, building shapes, and political boundaries. This is shown schematically in the image to the right. Geographic Data Files (GDF
Geographic Data Files
Geographic Data Files or GDF is an interchange file format for geographic data.In contrast with generic GIS formats, GDF provides detailed rules for data capture and representation, and an extensive catalog of standard features, attributes and relationships...

) is a standardized description of such a model.

Each node represents a point location of the surface of the Earth and is represented by a pair of longitude
Longitude
Longitude is a geographic coordinate that specifies the east-west position of a point on the Earth's surface. It is an angular measurement, usually expressed in degrees, minutes and seconds, and denoted by the Greek letter lambda ....

 (lon) and latitude
Latitude
In geography, the latitude of a location on the Earth is the angular distance of that location south or north of the Equator. The latitude is an angle, and is usually measured in degrees . The equator has a latitude of 0°, the North pole has a latitude of 90° north , and the South pole has a...

 (lat) coordinates. Each link represents a stretch of road between two nodes, and is represented by a line segment (corresponding to a straight section of road) or a curve having a shape that is generally described by intermediate points (called shape points) along the link. However, curves may also be represented by a combination of centroid (point or node), with a radius, and polar coordinates to define the boundaries of the curve. Shape points are represented by lon, lat coordinates as are nodes, but shape points do not serve the purpose of connecting links, as do nodes. Areas are two-dimensional shapes that represent things like parks, cities, blocks and are defined by their boundaries (usually formed by a closed polygon).

Interchange format

Map providers generally collect, aggregate and supply data in a well-defined and documented file format that is specifically intended for information interchange, e.g. Navteq
NAVTEQ
Navteq is a Chicago, Illinois-based provider of Geographic Information Systems data and is a dominant company in providing the base electronic navigable maps...

 uses Standard Interchange Format
Standard Interchange Format
Standard Interchange Format, called SIF, is a geospatial data exchange format. A standard or neutral format used to move graphics files between computer systems....

 (SIF) and GDF
Geographic Data Files
Geographic Data Files or GDF is an interchange file format for geographic data.In contrast with generic GIS formats, GDF provides detailed rules for data capture and representation, and an extensive catalog of standard features, attributes and relationships...

, while Tele Atlas
Tele Atlas
Tele Atlas is a Netherlands-based company founded in 1984 which delivers digital maps and other dynamic content for navigation and location-based services, including personal and in-car navigation systems, and provides data used in a wide range of mobile and Internet map applications...

 uses a proprietary form of GDF. It is usually in a plain-text form (ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...

) consisting of fields that are easily parsed and interpreted by the various parties who will handle it. The portable format allows additions, deletions and modifications to be readily performed by simple text-editing programs.

A small number of record types are used to represent the various types of data. Each record type consists of a sequence of fields, which are either fixed length or delimited by a punctuation character such as a comma. For example, a link entity could be represented by a record of the form:

type1,label,node1,z1,node2,z2,class,number of shape points,number of lanes,speed


where type1 defines this as a link record type and label serves as an identifier to distinguish this link from all others. The z1 and z2 fields determine the vertical separation of this link from others sharing the corresponding nodes node1 and node2. Thus an overpass to a link, for example, can be represented as not connected to that link. Other record types are used to represent address information, shape-points for a link, cities and states, points of interest (POI’s), etc.

The interchange format for a map database is not organized well for use by a navigation unit during runtime. Records are in an arbitrary order and therefore difficult to search and data, such as street names and coordinate values, are repeated from record to record. Consequently the database content is reorganized into a binary form more suitable for run-time operation.

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
BMW
Bayerische Motoren Werke AG is a German automobile, motorcycle and engine manufacturing company founded in 1916. It also owns and produces the Mini marque, and is the parent company of Rolls-Royce Motor Cars. BMW produces motorcycles under BMW Motorrad and Husqvarna brands...

, Volkswagen
Volkswagen
Volkswagen is a German automobile manufacturer and is the original and biggest-selling marque of the Volkswagen Group, which now also owns the Audi, Bentley, Bugatti, Lamborghini, SEAT, and Škoda marques and the truck manufacturer Scania.Volkswagen means "people's car" in German, where it is...

, Daimler, Renault
Renault
Renault S.A. is a French automaker producing cars, vans, and in the past, autorail vehicles, trucks, tractors, vans and also buses/coaches. Its alliance with Nissan makes it the world's third largest automaker...

, ADIT, Alpine Electronics
Alpine Electronics
is traditionally known as an aftermarket car audio and navigation systems manufacturer, famed for their high quality, premium in-car audio units commonly known as headunits. It is a subsidiary of Alps Electric Co. and its registered head office is in Tokyo, Japan. However its main offices, or the...

, Navigon
Navigon
Navigon GmbH is a Hamburg, Germany-based manufacturer of GPS devices and GPS navigation software. It is privately owned, however in June 2011 it was announced that Navigon is to be acquired by a subsidiary of Garmin...

, Bosch
Robert Bosch GmbH
Robert Bosch GmbH is a multinational engineering and electronics company headquartered in Gerlingen, near Stuttgart, Germany. It is the world's largest supplier of automotive components...

, DENSO
DENSO
is a global automotive components manufacturer headquartered in the city of Kariya, Aichi Prefecture, Japan. Established December 16, 1949 as , in 1996 the company became DENSO Corporation worldwide...

, Mitsubishi
Mitsubishi
The Mitsubishi Group , Mitsubishi Group of Companies, or Mitsubishi Companies is a Japanese multinational conglomerate company that consists of a range of autonomous businesses which share the Mitsubishi brand, trademark and legacy...

, Harman Becker, Panasonic
Panasonic
Panasonic is an international brand name for Japanese electric products manufacturer Panasonic Corporation, which was formerly known as Matsushita Electric Industrial Co., Ltd...

, PTV, Continental AG
Continental AG
Continental AG, internally often called Conti for short, is a worldwide leading German manufacturer of tires, brake systems, vehicle stability control systems, engine injection systems, tachographs and other parts for the automotive and transport industries. The company is based in Hanover, Germany...

, Navteq
NAVTEQ
Navteq is a Chicago, Illinois-based provider of Geographic Information Systems data and is a dominant company in providing the base electronic navigable maps...

, Tele Atlas
Tele Atlas
Tele Atlas is a Netherlands-based company founded in 1984 which delivers digital maps and other dynamic content for navigation and location-based services, including personal and in-car navigation systems, and provides data used in a wide range of mobile and Internet map applications...

 and Zenrin
Zenrin
Zenrin Co. Ltd. is a Japanese map publisher. Founded in 1948, the company is known as a maker of residential maps and software used in personal computers and Automotive navigation systems...

.

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.

Incremental update

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
WIFI
WIFI is a radio station broadcasting a brokered format. Licensed to Florence, New Jersey, USA, the station is currently operated by Florence Broadcasting Partners, LLC.This station was previously owned by Real Life Broadcasting...

 and cellular phone, broadcast
Broadcast
Broadcast or Broadcasting may refer to:* Broadcasting, the transmission of audio and video signals* Broadcast, an individual television program or radio program* Broadcast , an English electronic music band...

, 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.

Attaching auxiliary data

Various navigational functions, involving active safety, driver assistance and location-based services require data that is not considered to be part of a map database and is likely supplied by a vendor other than that of the map provider. Such data needs to be cross-referenced with the entities and attributes of the main database. However, since the auxiliary data is not necessarily compiled with the main database some other means is needed to establish cross-referencing, which is referred to as attaching the auxiliary data. Two common approaches are function-specific referencing tables and generic referencing.

Function-specific referencing tables

Function-specific referencing tables provide a means for attaching function-specific data to a map-data base produced by any participating supplier. Such a table is collaboratively produced to support a specific function or class of functions involving location-based service, active-safety or advanced driver assistance. It will generally consist of a list of map elements of a specific type (e.g., links, intersections, point-of-interest locations, etc.) along with identifying attributes (e.g., street names, longitude/latitude coordinates, etc.). Additionally, each entry in the table is assigned a unique identifier. The set of entries in a table are generally selected, through consensus of all interested parties. As a practical matter the result will represent a small subset of the elements of the given type that are available in the map databases and will consist of those that are more important to the application area. After a table is formulated, it is the task of each participating supplier to determine and cross-reference the elements in their map-database that correspond to the table entries.

A widely used example is the TMC standard for location-code tables for referencing traffic data. TMC, which stands for Traffic Message Channel
Traffic Message Channel
Traffic Message Channel is a technology for delivering traffic and travel information to drivers. It is typically digitally coded using the FM-RDS system on conventional FM radio broadcasts...

, is part of the Radio Data System
Radio Data System
Radio Data System, or RDS, is a communications protocol standard for embedding small amounts of digital information in conventional FM radio broadcasts. RDS standardises several types of information transmitted, including time, station identification and programme information.Radio Broadcast Data...

 (RDS), which is implemented as a sub-carrier modulation of a commercial FM broadcast signal. The TMC tables primarily provide references to point locations along major roads corresponding to intersections with other roads. A table entry identifies a point location using both contextual information (such as, region, road and section of road, name of intersection) and approximate longitude/latitude coordinates.

Identifiers assigned to entries in a table are 16-bit integers and therefore have a range of 65536 values. This is too few to cover the world, so separate tables are formulated for each country or region of a country. For a given metropolitan region, only intersections along freeways, arterials and some major roads are included. This is illustrated in the following figure for the Detroit metro area. The coverage is intended for providing traffic advisory information on high-use roads. Traffic-based route planning, on the other hand, requires coverage of all or almost all major roads and, therefore, is not adequately supported by TMC location code tables as they are currently formulated.

Generic referencing

Generic referencing is an attempt to attach data to any map database by discovering reference information through a form of map matching. The function-specific data items are assigned to elements, such as points, links or areas, that likely only approximate the corresponding map elements in a specific map database. A search of the map database is made for the best fit. To enhance the search process neighboring elements are strategically appended to each given element to help ensure that the correct solution is found in each case. For example, if the map element is a link connecting two intersections, then one or both cross streets could be appended for the sake of the search. Hopefully, this makes an incorrect match unlikely. Although the procedure is quite heuristic, a proposed standard called Agora outlines the strategy for choosing neighboring elements to append.

European consortium ActMAP

A European consortium called ActMAP (Actualize Map) is (in their words) "developing standardised mechanisms to update existing map database content and enable dynamic attachment of information to the digital in-vehicle map". The ActMAP consortium comprises ERTICO
ERTICO
ERTICO - ITS Europe is Europe's Intelligent Transportation System organization that funds research and defines ITS industry standards. It is a network of ITS and Services stakeholders in Europe. It connects together public authorities, industry players, infrastructure operators, users, national...

 (coordinator), BMW, CRF Fiat Research Centre, DaimlerChrysler, Navigon, Navteq, Tele Atlas, and Siemens VDO Automotive. They have finished most of their work and published a number of reports, which were submitted to the ISO committee TC204 WG3 for standardization. Their reports serve as a good starting point and reference for the work of this project. An important issue their reports address is dealing with the complexity of multiple map suppliers, using proprietary formats, coupled with multiple data suppliers and multiple versions of in-vehicles maps. They resolve this by using an open intermediate map format expressed with XML
XML
Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....

 and based on the concepts of the ISO standard GDF
Geographic Data Files
Geographic Data Files or GDF is an interchange file format for geographic data.In contrast with generic GIS formats, GDF provides detailed rules for data capture and representation, and an extensive catalog of standard features, attributes and relationships...

 4.0. All modifications to a supplier's database are first converted to this intermediate format, stored on a server and then converted to each format used within individual vehicles. They assume that each car has a "baseline" map from a map supplier and that this baseline defines reference identifiers (e.g. map segment ID) for most features to be updated. For features with no reference identifier in the baseline, they propose using a "generic" reference that is discovered heuristically using map matching as described by a proposed standard called AGORA

A major issue not directly addressed by ActMAP is that for each new version of a supplier's map database all reference IDs are usually reassigned by a compiling process, which destroys any correspondence with IDs of previous versions. This seriously interferes with the ability to use incremental updates to generate a new version of a map database from a previous version. Another issue not resolved by ActMAP is the inability to reference and characterize subsections of road segments (for example, curves, hills, maneuver lanes, etc.) in order to update them.

See also

  • Automotive navigation system
    Automotive navigation system
    An automotive navigation system is a satellite navigation system designed for use in automobiles. It typically uses a GPS navigation device to acquire position data to locate the user on a road in the unit's map database. Using the road database, the unit can give directions to other locations...

  • Geographic Information System
    Geographic Information System
    A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present all types of geographically referenced data...

  • Global Navigation Satellite System
    Global Navigation Satellite System
    A satellite navigation or SAT NAV system is a system of satellites that provide autonomous geo-spatial positioning with global coverage. It allows small electronic receivers to determine their location to within a few metres using time signals transmitted along a line-of-sight by radio from...

  • Intelligent transportation system
    Intelligent transportation system
    The term intelligent transportation systems refers to information and communication technology that improve transport outcomes such as transport safety, transport productivity, travel reliability, informed travel choices, social equity, environmental performance and network operation...

  • Map
    Map
    A map is a visual representation of an area—a symbolic depiction highlighting relationships between elements of that space such as objects, regions, and themes....

  • Navteq
    NAVTEQ
    Navteq is a Chicago, Illinois-based provider of Geographic Information Systems data and is a dominant company in providing the base electronic navigable maps...

  • Point of interest
    Point of interest
    A point of interest, or POI, is a specific point location that someone may find useful or interesting. An example is a point on the Earth representing the location of the Space Needle, or a point on Mars representing the location of the mountain, Olympus Mons.The term is widely used in...

  • Object-relational database
    Object-relational database
    An object-relational database , or object-relational database management system , is a database management system similar to a relational database, but with an object-oriented database model: objects, classes and inheritance are directly supported in database schemas and in the query language...

  • Open Geospatial Consortium
    Open Geospatial Consortium
    The Open Geospatial Consortium , an international voluntary consensus standards organization, originated in 1994. In the OGC, more than 400 commercial, governmental, nonprofit and research organizations worldwide collaborate in a consensus process encouraging development and implementation of open...

  • Robotic mapping
    Robotic mapping
    Robotic mapping is related to cartography. The goal for an autonomous robot to be able to construct a map or floor plan and to localize itself in it...

  • Tele Atlas
    Tele Atlas
    Tele Atlas is a Netherlands-based company founded in 1984 which delivers digital maps and other dynamic content for navigation and location-based services, including personal and in-car navigation systems, and provides data used in a wide range of mobile and Internet map applications...

  • Telematics
    Telematics
    Telematics typically is any integrated use of telecommunications and informatics, also known as ICT...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK