Centre dedocumentation
scientifique

Road network simplification for location-based services / Abdeltawab M. Hendawi in Geoinformatica, vol 24 n° 4 (October 2020)  

Public [article]  inGeoinformatica > vol 24 n° 4 (October 2020) . - pp 801 - 826 Titre : Road network simplification for location-based services Type de document : Article/Communication Auteurs : Abdeltawab M. Hendawi, Auteur ; John A. Stankovic, Auteur ; Ayman Taha, Auteur ; et al., Auteur Année de publication : 2020 Article en page(s) : pp 801 - 826 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Termes IGN] algorithme de Douglas-Peucker [Termes IGN] appariement de cartes [Termes IGN] appariement de données localisées [Termes IGN] appariement de graphes [Termes IGN] carte routière [Termes IGN] compression de données [Termes IGN] modèle de Markov caché [Termes IGN] réseau routier [Termes IGN] service fondé sur la position [Termes IGN] simplification de contour [Termes IGN] stockage de données [Vedettes matières IGN] Généralisation Résumé : (Auteur) 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. Numéro de notice : A2020-495 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1007/s10707-020-00406-x Date de publication en ligne : 01/05/2020 En ligne : https://doi.org/10.1007/s10707-020-00406-x Format de la ressource électronique : URL Article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=96115 [article]