Assessing Topological Similarity of Spatial Networks

John D. Nystuen, Andrea E. Frank, and Larry Frank
University of Michigan

Problem Statement

A common need in spatial operations and analyses is the ability to transfer data between digital databases. The requirements f or creating such capacity have received a great deal of attention, for example, through the efforts to develop Spatial Data Transfer St andards (SDTS) (USGS, 1990). However, more is involved than the need to agree on standard definitions for data from different sources to be effectively combined; although the standards issue remains of paramount importance. Many technical, semantic and organizational issues arise when attempting to transfer data between databases. Our concern is with how to compare or combine databases that characte rize spatial networks such as road and highways systems.


Digital maps of road networks play an important role in many transportation related applications including motor vehicle naviga tion, traffic advisories, route scheduling, and emergency vehicle routing. Many different agencies, both public and private, are creat ing databases of road networks and the need to coordinate outputs often arises. These needs are receiving attention but a great deal o f theoretical, technical, and institutional effort is required before transportation applications achieve widespread use (Goodwin, 1996 ).

In another allied public field, TIGER files have been shown to have reasonably accurate address ranges and effectively associat e street addresses with census polygons. However, at municipal street map scales, streets known to be straight lines appear noticeably crooked on printouts of TIGER files. It would be useful if the TIGER line file could be linked to the typically more positionally accu rate municipal street map. The municipal street maps are often tied to land parcel maps and merging them with the TIGER street map woul d create a link between the census polygon database and the land parcel polygon database.

A third general reason for developing means to compare networks is to be able to make comparisons of a network over different t ime periods. Overlaying a digital database of a network in one time period with the database in another time period would allow the di fferences to be highlighted. Change detection is often of interest. In general, being able to merge or match different databases char acterizing the same spatial network would be useful in many contexts.

Approach

The key to comparing two spatial networks is to associate nodes in one coverage to corresponding nodes in another coverage. Th is is not a simple task. In the first place, two maps of a network such as a highway system, are unlikely to have exactly the same num ber of nodes. Databases will especially not have the same number of pseudo-nodes because pseudo-nodes are generated for a variety of s pecial functions not likely to be universal1. However, the topology or connectiveness of different representations of the same real ne twork should be similar. Acting on this assumption the approach adopted is to identify for each node in a first coverage a nearest nod e in the second coverage which also has the identical topological properties. As the coverages may have many nodes, the matching proce dure is automated using standard GIS software. The automated processing results in some but not all nodes in a coverage being matched with corresponding nodes in the second coverage. Unmatched nodes are identified and an interactive process is initiated in which human judgment is used for finding additional matches. Initial proximity parameters are relaxed and additional information referenced to in crease the number of matched pairs identified. The interactive procedure ends with a summary statement of the degree to which the netw orks match. Once a clean subset of paired nodes is created it can be used to assess displacement discrepancies using standard error ellipses.

This work is derivative of research we have undertaken to evaluate the quality of digital map databases for Intelligent Transpo rtation Systems (ITS) applications (Aggarwala, et al, 1997). In that research we developed methods for identifying and separating diff erent types of errors in digital map databases intended for use in motor vehicle navigation. Error detection was accomplished by compa ring segments of a vendor map with the corresponding portion of a reference map of known greater positional accuracy. Errors of displa cement, omission and commission are identified by these procedures. The procedures we have developed are appropriate for addressing wi der issues involved in analysis of spatial networks.

Research Concerns

We have encountered a number of items that appear to be interesting research topics. A few a listed below.

References

Aggarwala, Raj, John D. Nystuen, Andrea Frank, Jyothi Palathinkara, "Digital Map Database Quality Evaluation Issues for ITS Applications," Paper Presented at UCGIS Annual Assembly and Summer Retreat, Bar Harbor, Maine, June 17, 1997

Goodwin, Cecil W. H., 1996, "Location Referencing for ITS," White Paper prepared for Oak Ridge National Laboratory and the National ITS Architecture Program, April, 1997, 18 pages.

U. S. Geological Survey, (1990) National Mapping Division: Spatial Data Transfer Standards, U. S. Department of the Interior, Washington DC. 


1 Nodes are topologically distinguished if they have degree other than two. A node with two incident arcs is termed a pseudo-node and is not topologically distinguishable. Shape points are not topologically distinguishable.