Road network simplification for location-based services
- PDF / 1,547,644 Bytes
- 26 Pages / 439.642 x 666.49 pts Page_size
- 76 Downloads / 216 Views
Road network simplification for location-based services Abdeltawab Hendawi1,2 · John A. Stankovic3 · Ayman Taha2,4 · Shaker El-Sappagh5 · Amr A. Ahmadain6 · Mohamed Ali7 Received: 15 February 2018 / Revised: 16 April 2019 / Accepted: 2 April 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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. Keywords Spatial road network · Compression · Performance · Efficiency · Accuracy · Scalability
Abdeltawab Hendawi
[email protected]; [email protected]
Extended author information available on the last page of the article.
Geoinformatica
1 Introduction Extensive availability of GPS-enabled devices has increased the need for routing and navigation services. The storage, processing, and transmission of road-network data are the biggest performance issues facing such services and is an important data management challenge. A road-network map, road map for short, is represented as a graph structure with a set of nodes, edges and edges weights, i.e., travel distance or time. To provide a navigation service, the user’s location, as measured by a GPS device, is continuously map-matched to an edge in the graph. This edge represents the current road segment th
Data Loading...
