Road network simplification for location-based services

Road-network data compression or simplification reduces the size of the network to occupy less storage with the aim to fit small form-factor routing devices, mobile devices, or embedded systems. Simplification (a) reduces the storage cost of memory and disks, and (b) reduces the I/O and communication overhead. There are several road network compression techniques proposed in the literature. These techniques are evaluated by their compression ratios. However, none of these techniques takes into consideration the possibility that the generated compressed data can be used directly in Map-matching operation which is an essential component for all location-aware services. Map-matching matches a measured latitude and longitude of an object to an edge in the road network graph. In this paper, we propose a novel simplification technique, named COMA, that (1) significantly reduces the size of a given road network graph, (2) achieves high map-matching quality on the simplified graph, and (3) enables the generated compressed road network graph to be used directly in map-matching and location-based applications without a need to decompress it beforehand. COMA smartly deletes those nodes and edges that will not affect the graph connectivity nor causing much of ambiguity in the map-matching of objects' location. COMA employs a controllable parameter; termed a conflict factor C, whereby location aware services can trade the compression gain with map-matching accuracy at varying granularity. We show that the time complexity of our COMA algorithm is O(|N|log|N|). Intensive experimental evaluation based on a real implementation and data demonstrates that COMA can achieve about a 75% compression-ratio while preserving high map-matching quality. Road Network, Simplification, Compression, Spatial, Location, Performance, Accuracy, Efficiency, Scalability.