Map database management

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.

When designed well, a map database enables the rapid indexing and lookup of a large amount of geographic data.

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 Geographic Data Files (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:

donde type1 define este como un tipo de registro de enlace y label sirve como identificador para distinguir este enlace de todos los demás. Los campos z1 y z2 determinan la separación vertical de este enlace con respecto a otros que comparten los nodos correspondientes node1 y node2 . Por lo tanto, un paso elevado a un enlace, por ejemplo, puede representarse como no conectado a ese enlace. Otros tipos de registro se utilizan para representar información de direcciones, puntos de forma para un enlace, ciudades y estados, puntos de interés (POI), etc.

El formato de intercambio de la base de datos cartográfica no está bien organizado para su uso por una unidad de navegación durante la ejecución. Los registros se encuentran en un orden arbitrario, lo que dificulta la búsqueda, y datos como nombres de calles y coordenadas se repiten de un registro a otro. Por consiguiente, el contenido de la base de datos se reorganiza en un formato binario más adecuado para su funcionamiento.

Los formatos de tiempo de ejecución suelen ser propietarios, lo que impide la interoperabilidad de mapas entre diferentes sistemas de navegación. Sin embargo, una nueva iniciativa llamada Navigation Data Standard (NDS) es una agrupación industrial de fabricantes de automóviles, proveedores de sistemas de navegación y proveedores de datos cartográficos cuyo objetivo es la estandarización del formato de datos utilizado en los sistemas de navegación de automóviles. ^{[ 4 ]} Las empresas involucradas incluyen TomTom , BMW , Volkswagen , Daimler , Renault , ADIT, Alpine Electronics , Navigon , Bosch , DENSO , Mitsubishi , Harman Becker , Panasonic , PTV , Continental AG , Navteq y Zenrin .

La base de datos es reorganizada por un proveedor de navegación ^{[ 5 ] [ 6 ] [ 7 ]} a través de un proceso de compilación que incluye al menos los siguientes cinco pasos:

1. Verifique la coherencia de la red. Por ejemplo, asegúrese de que todos los pares de nodos que deban estar conectados por un enlace tengan dicho enlace y, a la inversa, que todos los pares de nodos que no deban estar conectados no tengan un enlace de conexión.
2. Asigne identificadores (ID) a todas las entidades de manera sistemática.
3. Aplique varios conjuntos de índices a las entidades para facilitar la búsqueda en la base de datos de la forma esperada.
4. Reemplazar las múltiples ocurrencias de elementos de datos (nombres de calles, coordenadas, etc.) por índices en tablas que contengan una sola copia de cada uno de dichos elementos.
5. Aplique otras técnicas de compresión para reducir el tamaño total de la base de datos.

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.

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.

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

Los identificadores asignados a las entradas de una tabla son enteros de 16 bits y, por lo tanto, abarcan un rango de 65 536 valores. Esta cantidad es insuficiente para cubrir todo el mundo, por lo que se elaboran tablas independientes para cada país o región. Para una región metropolitana determinada, solo se incluyen las intersecciones a lo largo de autopistas, vías arteriales y algunas carreteras principales. Esto se ilustra en la siguiente figura para el área metropolitana de Detroit. La cobertura tiene como objetivo proporcionar información de asesoramiento de tráfico en las carreteras de mayor uso. La planificación de rutas basada en el tráfico, por otro lado, requiere la cobertura de todas o casi todas las carreteras principales y, por lo tanto, no está adecuadamente respaldada por las tablas de códigos de ubicación de TMC tal como están formuladas actualmente.

Un consorcio europeo llamado ActMAP (Actualize Map) ^{[ 9 ]} está (en sus propias palabras) "desarrollando mecanismos estandarizados para actualizar el contenido de las bases de datos de mapas existentes y permitir la incorporación dinámica de información al mapa digital del vehículo". El consorcio ActMAP está compuesto por ERTICO (coordinador), BMW, CRF Fiat Research Centre, DaimlerChrysler, Navigon, Navteq, Tele Atlas y Siemens VDO Automotive. Han finalizado la mayor parte de su trabajo y publicado varios informes, que fueron presentados al comité ISO TC204 WG3 para su estandarización. Estos informes sirven como un buen punto de partida y referencia para el trabajo de este proyecto. Un aspecto importante que abordan sus informes es la complejidad de gestionar múltiples proveedores de mapas, que utilizan formatos propietarios, junto con múltiples proveedores de datos y múltiples versiones de mapas para vehículos. Resuelven este problema utilizando un formato de mapa intermedio abierto expresado en XML y basado en los conceptos del estándar ISO GDF 4.0. Todas las modificaciones a la base de datos de un proveedor se convierten primero a este formato intermedio, se almacenan en un servidor y luego se convierten a cada formato utilizado en cada vehículo. Se parte de la base de que cada automóvil tiene un mapa "base" de un proveedor de mapas y que esta base define identificadores de referencia (por ejemplo, ID de segmento de mapa) para la mayoría de las características que se actualizarán. Para las características sin identificador de referencia en la base, se propone utilizar una referencia "genérica" ​​que se descubre heurísticamente mediante la comparación de mapas, tal como se describe en un estándar propuesto llamado AGORA.

Un problema importante que ActMAP no aborda directamente es que, para cada nueva versión de la base de datos cartográfica de un proveedor, todos los identificadores de referencia suelen reasignarse mediante un proceso de compilación, lo que elimina cualquier correspondencia con los identificadores de versiones anteriores. Esto dificulta considerablemente la posibilidad de utilizar actualizaciones incrementales para generar una nueva versión de la base de datos cartográfica a partir de una versión anterior. Otro problema que ActMAP no resuelve es la imposibilidad de referenciar y caracterizar subsecciones de segmentos de carretera (por ejemplo, curvas, pendientes, carriles de maniobra, etc.) para actualizarlas.

• Sistema de navegación automotriz
• Problema de la ruta más corta , clase de problemas y algoritmos empleados para obtener una ruta de navegación a partir de una base de datos de mapas.
• Base de datos geográfica
• Sistema de Información Geográfica
• Sistema Global de Navegación por Satélite
• Sistema de transporte inteligente
• Mapa
• Navteq
• Punto de interés
• Base de datos objeto-relacional
• Consorcio Geoespacial Abierto
• Mapeo robótico
• Tele Atlas
• Telemática