Centre de documentation
scientifique

A dilution-matching-encoding compaction of trajectories over road networks / Ranit Gotsman in Geoinformatica, vol 19 n° 2 (April - June 2015)  

Public [article]  inGeoinformatica > vol 19 n° 2 (April - June 2015) . - pp 331-364 Titre : A dilution-matching-encoding compaction of trajectories over road networks Type de document : Article/Communication Auteurs : Ranit Gotsman, Auteur ; Yaron Kanza, Auteur Année de publication : 2015 Article en page(s) : pp 331-364 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique web [Termes IGN] calcul d'itinéraire [Termes IGN] chemin le plus court, algorithme du [Termes IGN] géocodage [Termes IGN] noeud [Termes IGN] positionnement par GPS [Termes IGN] réseau routier [Termes IGN] stockage de données [Termes IGN] vectorisation Résumé : (auteur) Many devices nowadays record traveled routes as sequences of GPS locations. With the growing popularity of smartphones, millions of such routes are generated each day, and many routes have to be stored locally on the device or transmitted to a remote database. It is, thus, essential to encode the sequences, in order to decrease the volume of the stored or transmitted data. In this paper we study the problem of encoding routes over a vectorial road network (map), where GPS locations can be associated with vertices or with road segments. We consider a three-step process of dilution, map-matching and coding, which helps reducing the amount of transmitted data between the cellular device and remote servers. We present two methods to code routes. The first method represents the given route as a sequence of greedy paths. We provide two algorithms to generate a greedy-path code for a sequence of n vertices on the map. The first algorithm has O(n) time complexity, and the second one has O(n 2) time complexity, but it is optimal, meaning that it generates the shortest possible greedy-path code. Decoding a greedy-path code can be done in O(n) time. The second method encodes a route as a sequence of shortest paths. We provide algorithms to generate unidirectional and bidirectional optimal shortest-path codes. Encoding and decoding a shortest-path code can be done in O(k n 2 logn) time, where k is the length of the produced code, assuming the graph valency is bounded. Our experimental evaluation shows that shortest-path codes are more compact than greedy-path codes, justifying the larger time complexity. Numéro de notice : A2015-491 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-014-0216-4 Date de publication en ligne : 11/08/2014 En ligne : https://doi.org/10.1007/s10707-014-0216-4 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=77284 [article]