Map database management systems are software programs designed to store and recall spatial information for navigation applications, and are thus a form of Geographic information system. They are widely used in localization and navigation, especially in automotive applications. Moreover, they are playing an increasingly important role in the emerging areas of location-based services, active safety functions and advanced driver-assistance systems. Common to these functions is the requirement for an on-board map database that contains information describing the road network.
Figure 1: Features and their respective attributes in a map database
Maps are stored as graphs, or two dimensional arrays of objects with attributes of location and category, where some common categories include parks, roads, cities, and the like.
A map database represents a road network along with associated features. Map providers can 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 adjacent image. Geographic Data Files (GDF)[1] is a standardized description of such a model.
Each node within a map graph represents a point location of the surface of the Earth and is represented by a pair of longitude (lon) and latitude (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. These are usually formed by a closed polygon, which are shapes that indicated an object over a map has to have a close boundary, meaning the first vertex should be same as the last vertex. (For example, to plot a square object on a map, the vertices of the polygon are numbered 1,2,3,4,1, in this order)
Another point for validation on data is the point in polygon, which helps in finding points lying outside a polygon. E.g., for a particular lon-lat coordinates in a city, if the point is intersecting the polygon in an odd number, then it is inside the polygon and a valid point; otherwise it is outside the polygon and invalid.
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 uses Standard Interchange Format (SIF)[2] and GDF, while Tele Atlas uses a proprietary form of GDF.[3] It is usually in a plain-text form (ASCII) 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 Navigation Data Standard (NDS) 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.[4] Companies involved include TomTom, BMW, Volkswagen, Daimler, Renault, ADIT, Alpine Electronics, Navigon, Bosch, DENSO, Mitsubishi, Harman Becker, Panasonic, PTV, Continental AG, Navteq and Zenrin.
The database is reorganized by a navigation provider[5][6][7] through a compilation process that includes at least the following five steps:
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.
Assign identifiers (IDs) to all entities in a systematic manner.
Apply multiple sets of indices to entities to facilitate searching the database in expected ways.
Replace multiple occurrences of data items (street names, coordinates, etc.) by indices into tables containing a single copy of each such item.
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 be bi-directional, such as Wi-Fi and cellular phone, broadcast, such as satellite radio, FM sub-carrier or ATSCdatacasting, 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 1km 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 addressed 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.
Figure 2: TMC locations in Metro Detroit
A widely used example is the TMC standard for location-code tables for referencing traffic data. TMC, which stands for Traffic Message Channel,[8] is part of the Radio Data System (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)[9] 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 (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 and based on the concepts of the ISO standard GDF 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.
AutoCAD DXF is a CAD data file format developed by Autodesk for enabling data interoperability between AutoCAD on different platforms.
The Geography Markup Language (GML) is the XML grammar defined by the Open Geospatial Consortium (OGC) to express geographical features. GML serves as a modeling language for geographic systems as well as an open interchange format for geographic transactions on the Internet. Key to GML's utility is its ability to integrate all forms of geographic information, including not only conventional "vector" or discrete objects, but coverages and sensor data.
A controller area network (CAN) is a vehicle bus standard designed to enable efficient communication primarily between electronic control units (ECUs). Originally developed to reduce the complexity and cost of electrical wiring in automobiles through multiplexing, the CAN bus protocol has since been adopted in various other contexts. This broadcast-based, message-oriented protocol ensures data integrity and prioritization through a process called arbitration, allowing the highest priority device to continue transmitting if multiple devices attempt to send data simultaneously, while others back off. Its reliability is enhanced by differential signaling, which mitigates electrical noise. Common versions of the CAN protocol include CAN 2.0, CAN FD, and CAN XL which vary in their data rate capabilities and maximum data payload sizes.
In computing, extract, transform, load (ETL) is a three-phase process where data is extracted from an input source, transformed, and loaded into an output data container. The data can be collated from one or more sources and it can also be output to one or more destinations. ETL processing is typically executed using software applications but it can also be done manually by system operators. ETL software typically automates the entire process and can be run manually or on recurring schedules either as single jobs or aggregated into a batch of jobs.
A GIS file format is a standard for encoding geographical information into a computer file, as a specialized type of file format for use in geographic information systems (GIS) and other geospatial applications. Since the 1970s, dozens of formats have been created based on various data models for various purposes. They have been created by government mapping agencies, GIS software vendors, standards bodies such as the Open Geospatial Consortium, informal user communities, and even individual developers.
A geocode is a code that represents a geographic entity. It is a unique identifier of the entity, to distinguish it from others in a finite set of geographic entities. In general the geocode is a human-readable and short identifier.
Geographic Data Files (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. The most recent extension expanded applicability further towards pedestrian navigation, 3-D map rendering, and advanced driver-assistance systems (ADAS).
In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object's surface. It simplifies rendering, as in a wire-frame model. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons). A polygonal mesh may also be more generally composed of concave polygons, or even polygons with holes.
An automotive navigation system is part of the automobile controls or a third party add-on used to find direction in an automobile. It typically uses a satellite navigation device to get its position data which is then correlated to a position on a road. When directions are needed routing can be calculated. On the fly traffic information can be used to adjust the route.
The shapefile format is a geospatial vector data format for geographic information system (GIS) software. It is developed and regulated by Esri as a mostly open specification for data interoperability among Esri and other GIS software products. The shapefile format can spatially describe vector features: points, lines, and polygons, representing, for example, water wells, rivers, and lakes. Each item usually has attributes that describe it, such as name or temperature.
Navteq Corporation was an American Chicago-based provider of geographic information system (GIS) data and a major provider of base electronic navigable maps. The company was acquired by Nokia in 2007–2008, and fully merged into Nokia in 2011 to form part of the Here business unit. The unit was subsequently sold to a consortium of German auto makers in 2016.
A spatial database is a general-purpose database that has been enhanced to include spatial data that represents objects defined in a geometric space, along with tools for querying and analyzing such data.
Well-known text (WKT) is a text markup language for representing vector geometry objects. A binary equivalent, known as well-known binary (WKB), is used to transfer and store the same information in a more compact form convenient for computer processing but that is not human-readable. The formats were originally defined by the Open Geospatial Consortium (OGC) and described in their Simple Feature Access. The current standard definition is in the ISO/IEC 13249-3:2016 standard.
MapInfo Pro is a desktop geographic information system (GIS) software developed by Precisely, used for mapping and location analysis. It was formerly developed by Pitney Bowes Software and the MapInfo Corporation.
PLY is a computer file format known as the Polygon File Format or the Stanford Triangle Format. It was principally designed to store three-dimensional data from 3D scanners. The data storage format supports a relatively simple description of a single object as a list of nominally flat polygons. A variety of properties can be stored, including color and transparency, surface normals, texture coordinates and data confidence values. The format permits one to have different properties for the front and back of a polygon.
A geographic data model, geospatial data model, or simply data model in the context of geographic information systems, is a mathematical and digital structure for representing phenomena over the Earth. Generally, such data models represent various aspects of these phenomena by means of geographic data, including spatial locations, attributes, change over time, and identity. For example, the vector data model represents geography as collections of points, lines, and polygons, and the raster data model represent geography as cell matrices that store numeric values. Data models are implemented throughout the GIS ecosystem, including the software tools for data management and spatial analysis, data stored in a variety of GIS file formats, specifications and standards, and specific designs for GIS installations.
In computing, Open Data Protocol (OData) is an open protocol that allows the creation and consumption of queryable and interoperable Web service APIs in a standard way. Microsoft initiated OData in 2007. Versions 1.0, 2.0, and 3.0 are released under the Microsoft Open Specification Promise. Version 4.0 was standardized at OASIS, with a release in March 2014. In April 2015 OASIS submitted OData v4 and OData JSON Format v4 to ISO/IEC JTC 1 for approval as an international standard. In December 2016, ISO/IEC published OData 4.0 Core as ISO/IEC 20802-1:2016 and the OData JSON Format as ISO/IEC 20802-2:2016.
Additive manufacturing file format (AMF) is an open standard for describing objects for additive manufacturing processes such as 3D printing. The official ISO/ASTM 52915:2016 standard is an XML-based format designed to allow any computer-aided design software to describe the shape and composition of any 3D object to be fabricated on any 3D printer via a computer-aided manufacturing software. Unlike its predecessor STL format, AMF has native support for color, materials, lattices, and constellations.
Cypher is a declarative graph query language that allows for expressive and efficient data querying in a property graph.
A discrete global grid (DGG) is a mosaic that covers the entire Earth's surface. Mathematically it is a space partitioning: it consists of a set of non-empty regions that form a partition of the Earth's surface. In a usual grid-modeling strategy, to simplify position calculations, each region is represented by a point, abstracting the grid as a set of region-points. Each region or region-point in the grid is called a cell.
References
↑ ISO 14825, Intelligent transport systems - Geographic Data Files (GDF) - Overall data specification, first edition 2004, Switzerland, http://www.iso.org
↑ GDF ASCII Sequential, Tele Atlas, "Archived copy". Archived from the original on 2008-08-27. Retrieved 2007-10-01.{{cite web}}: CS1 maint: archived copy as title (link)
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
