COMA: Road Network Compression for Map-Matching

Road-network data compression reduces the size of the network to occupy lesser storage with the aim to fit small form-factor routing devices, mobile devices, or embedded systems. Compression (1) reduces the storage cost of memory and disks, and (2) reduces the I/O and communication overhead. There are several road network compression techniques proposed in 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. Map-matching is an essential component of routing services that matches a measured latitude and longitude of an object to an edge in the road network graph. In this paper, we propose a novel compression technique, named COMA, that significantly reduces the size of a given road network data. Another advantage of the proposed technique is that it enables the generated compressed road network graph to be used directly in map-matching without a need to decompress it beforehand. COMA smartly deletes those nodes and edges that will not affect neither the graph connectivity nor the accuracy of map-matching objects' location. COMA is equipped with an adjustable parameter, termed conflict factor C, by which location-based services can achieve a trade-off between the compression gain and map-matching accuracy. Extensive experimental evaluation on real road network data demonstrates competitive performance on compression-ratio and the high mapmatching accuracy achieved by the proposed technique.