Centre de documentation
scientifique

Finding the most navigable path in road networks / Ramneek Kaur in Geoinformatica, vol 25 n° 1 (January 2021)  

Public [article]  inGeoinformatica > vol 25 n° 1 (January 2021) . - pp 207 - 240 Titre : Finding the most navigable path in road networks Type de document : Article/Communication Auteurs : Ramneek Kaur, Auteur ; Vikram Goyal, Auteur ; Venkata M. V. Gunturi, Auteur Année de publication : 2021 Article en page(s) : pp 207 - 240 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse spatiale [Termes IGN] arc [Termes IGN] calcul d'itinéraire [Termes IGN] durée de trajet [Termes IGN] programmation dynamique [Termes IGN] réseau routier Résumé : (Auteur) Input to the Most Navigable Path (MNP) problem consists of the following: (a) a road network represented as a directed graph, where each edge is associated with numeric attributes of cost and “navigability score” values; (b) a source and a destination and; (c) a budget value which denotes the maximum permissible cost of the solution. Given the input, MNP aims to determine a path between the source and the destination which maximizes the navigability score while constraining its cost to be within the given budget value. The problem can be modeled as the arc orienteering problem which is known to be NP-hard. The current state-of-the-art for this problem may generate paths having loops, and its adaptation for MNP that yields simple paths, was found to be inefficient. In this paper, we propose five novel algorithms for the MNP problem. Our algorithms first compute a seed path from the source to the destination, and then modify the seed path to improve its navigability. We explore two approaches to compute the seed path. For modification of the seed path, we explore different Dynamic Programming based approaches. We also propose an indexing structure for the MNP problem which helps in reducing the running time of some of our algorithms. Our experimental results indicate that the proposed solutions yield comparable or better solutions while being orders of magnitude faster than the current state-of-the-art for large real road networks. Numéro de notice : A2021-095 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1007/s10707-020-00428-5 Date de publication en ligne : 03/01/2021 En ligne : https://doi.org/10.1007/s10707-020-00428-5 Format de la ressource électronique : URL Article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=96935 [article]

Discovering non-compliant window co-occurrence patterns / Reem Y. Ali in Geoinformatica, vol 21 n° 4 (October - December 2017)  

Public [article]  inGeoinformatica > vol 21 n° 4 (October - December 2017) . - pp 829 - 866 Titre : Discovering non-compliant window co-occurrence patterns Type de document : Article/Communication Auteurs : Reem Y. Ali, Auteur ; Venkata M. V. Gunturi, Auteur ; Andrew J. Kotz, Auteur ; et al., Auteur Année de publication : 2017 Article en page(s) : pp 829 - 866 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique [Termes IGN] exploration de données géographiques [Termes IGN] géostatistique [Termes IGN] matrice de co-occurrence [Termes IGN] reconstruction d'itinéraire ou de trajectoire [Termes IGN] transport Résumé : (Auteur) Given a set of trajectories annotated with measurements of physical variables, the problem of Non-compliant Window Co-occurrence (NWC) pattern discovery aims to determine temporal signatures in the explanatory variables which are highly associated with windows of undesirable behavior in a target variable. NWC discovery is important for societal applications such as eco-friendly transportation (e.g. identifying engine signatures leading to high greenhouse gas emissions). Challenges of designing a scalable algorithm for NWC discovery include the non-monotonicity of popular spatio-temporal statistical interest measures of association such as the cross-K function which renders the anti-monotone pruning based algorithms (e.g. Apriori) inapplicable for such interest measures. In our preliminary work, we proposed two upper bounds for the cross-K function and a top-down multi-parent tracking approach that uses these bounds for filtering out uninteresting candidate patterns and then applies a minimum support (i.e. frequency) threshold as a post-processing step to filter out chance patterns. In this paper, we propose a novel bi-directional pruning approach (BDNMiner) that combines top-down pruning based on the cross-K function threshold with bottom-up pruning based on the minimum support threshold to efficiently mine NWC patterns. Case studies with real world engine data demonstrates the ability of the proposed approach to discover patterns which are interesting to engine scientists. Experimental evaluation on real-world data show that the proposed approach yields substantial computational savings compared to prior work. Numéro de notice : A2017-605 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-016-0289-3 En ligne : https://doi.org/10.1007/s10707-016-0289-3 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=86915 [article]