Database Requirements for Vehicle Navigation Systems

Final Report

1. Major Results

1.1 Typical Queries

In order to understand the database requirements it is necessary to know the kinds of operations performed in a vehicle navigation system. While the operations may appear to be mainly geometric manipulations, there is an equally strong need for operations involving non-geometric manipulations. We found the following types of queries of particular interest to a driver using a vehicle navigation system:

• Display a map with the vehicle's current location and in the context of an appropriate geographic environment. The map--showing the position and displaying some crucial travel information such as landmarks, nearby cities, and roads--must be constantly updated as the vehicle moves along the road. These updates include (1) panning, i.e., moving ahead as the car moves along the road, (2) changing the orientation of the map when the vehicle follows the curved road in order to match the driver's view with the map ("ahead is up"), and (3) zooming in or out, i.e., changing the scale and the level of detail. Such a map may also serve as the background and display medium for further types of queries such as
  - Display the vehicle's route while driving along a road.
  - Find a particular location based on a postal address.
  - Find the shortest path among two or more locations (known as the traveling salesperson problem). The operation of routing cars may require elaborate spatial analyses such as finding the shortest path where "shortest" may have multiple interpretations, e.g., in terms of distance, time, gas consumption, or toll.
• Generate driving instructions (either textual, verbal, or graphical) to guide the driver along a certain route. It is crucial that these instructions come at the right time--too late is obviously unacceptable, and may even be dangerous, while too early might be confusing for the driver.
• Get information with respect to the current location such as next exit, closest gas station, expected travel time to an Italian restaurant, or the distance to some city. This may require the link with a "Yellow Page" or customer database.

1.2 Properties of Geographic Data

Although geographic data are frequently associated with maps, geographic databases are more than just repositories of maps or map maintenance systems. Geographic databases manage geographic data, while maps are one of many possible graphical forms in which geographic data may be presented. These issues are relevant for the storage and retrieval of geographic data, as well as for the interaction with geographic databases (i.e., query languages) and for reasoning processes to derive information (e.g., query processors).

1.2.1 Geometry

We found that among the spatial objects represented in a geographic database for vehicle navigation, there are a number of complex geometric relationships that must be preserved and are used extensively when querying the system:

• Connectivity, e.g., from one intersection to another.
• Adjacency, e.g., counties to the left and to the right of the roads.
• Order, e.g., the linear sequence of landmarks along the road, and also cyclic orderings such as the sequence of incoming and outgoing roads in a roundabout.
• Metric relations and evaluates such as the lengths of segments, cardinal directions such as north and east, or approximate distances as such near and far.

Multiple geometric representations exist for the same geographic object in a vehicle navigation database, sometimes at different levels of detail. This has implications for query languages and query processing--which representation to select--as well as for database maintenance with complex consistency constraints among redundantly stored data. For example, approximate query results may be sufficient in some situations. For a driver in Maine who asks, "How far is it to Portland, Maine?" it is more important to get an answer quickly than to receive a very precise one. "About 30 miles" may be sufficient. On demand, refinements should be possible, if higher precision is required.

1.2.2 Distribution of Geographic Objects in Space

Geographic space is irregular and does not follow any preconceived patterns. With respect to storing and retrieving spatial objects in geographic databases, two aspects are relevant:

• The density of objects varies across geographic space. For example, in urban areas highway exits and entrances are every 1-2 miles, whereas in rural, less populated areas there may be 20-30 miles between two exits.
• The spatial extent of geographic objects may vary dramatically. Compare the sizes of I95--which extends from Maine to Florida--with the size of the town of Orono, both being stored in the same geographic database.

Databases for car navigation should be dynamic. Updates may involve the change of attribute values (a new name for a road) as well as geometry (construction of a new road). Some of these changes may be temporary (a tunnel may be flooded; a road may be blocked due to some accident; a bridge under repair such that one lane is closed) and will have to be reset to their previous value after some time. Others are permanent, e.g., after construction has been completed, there will be a third lane. Very rarely does it occur that the geographic objects in a vehicle navigation system "move" or "rotate." On the other hand, there are objects such as cars moving through geographic space.

1.2.4 Data Volume

By most standards, car navigation databases are very large, although certainly not as large as the terabyte databases generated from remote sensing. Their data volume is primarily governed by the tremendous number of individual (geometric) parts stored. In object-centered geographic databases, individual records are usually quite small--a point may have an integer pair to describe its x- and y-coordinates and some number (or string) to identify it. Besides this attribute information, geometric objects usually have many references (pointers) to other objects. A typical data source for vehicle navigation in the U.S. are the Census' TIGER files, which provide sufficient detail for the driver level. The entire set comprises some 600 MB of topologically structured vector data about the geometry of roads, geographic attribute data, and additional features such as county boundaries. The street network for a vehicle navigation system with its three different levels is generally too complex to be derived "on the fly" from a single representation; therefore, additional data volumes are created.

1.3 Consistency in Multiple Geometric Representations

Multiple representations are a particularly challenging problem for building the database for a vehicle navigation system. Since multiple versions of the same objects have to be maintained at different scales, it is necessary to have efficient methods to assess whether two or more representations are consistent or not. Topological information is generally considered first-class geographic information and as such the preservation of topological relations among objects in different representations manifests a critical criterion for the comparison of multiple representations and their consistency evaluation.

We developed a framework within which the topological consistency of multiple representations can be assessed. The rational for assessing topological similarity is the monotonicity assumption of a generalization, under which the topology of any object and any topological relation between objects must remain the same through consecutive representation levels; or continuously decrease in complexity and detail. Such changes are assessed through object similarity and relation similarity, respectively. Within this framework, only those topological invariants can be changed that are at least on an ordinal scale.

This model applies not only to databases for vehicle navigation systems, but also for other types of geographic databases that have to maintain multiple-representation data, such as cartographic databases for cartographic map series at different scales.

Last updated on August 18, 1995.