Centre de documentation
scientifique

Provably consistent distributed Delaunay triangulation / Mathieu Brédif in ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol V-2-2020 (August 2020)  

Public [article]  inISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences > vol V-2-2020 (August 2020) . - pp 195 - 202 Titre : Provably consistent distributed Delaunay triangulation Type de document : Article/Communication Auteurs : Mathieu Brédif , Auteur ; Laurent Caraffa , Auteur ; Murat Yirci, Auteur ; Pooran Memari, Auteur Année de publication : 2020 Projets : IQmulus / Métral, Claudine Conférence : ISPRS 2020, Commission 2, virtual Congress, Imaging today foreseeing tomorrow 31/08/2020 02/09/2020 Nice (en ligne) France Annals Commission 2 Article en page(s) : pp 195 - 202 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Lasergrammétrie [Termes IGN] données lidar [Termes IGN] données localisées 3D [Termes IGN] géomètrie algorithmique [Termes IGN] informatique en nuage [Termes IGN] semis de points [Termes IGN] Spark [Termes IGN] traitement de semis de points [Termes IGN] triangulation de Delaunay Résumé : (Auteur) This paper deals with the distributed computation of Delaunay triangulations of massive point sets, mainly motivated by the needs of a scalable out-of-core surface reconstruction workflow from massive urban LIDAR datasets. Such a data often corresponds to a huge point cloud represented through a set of tiles of relatively homogeneous point sizes. This will be the input of our algorithm which will naturally partition this data across multiple processing elements. The distributed computation and communication between processing elements is orchestrated efficiently through an uncentralized model to represent, manage and locally construct the triangulation corresponding to each tile. Initially inspired by the star splaying approach, we review the Tile\& Merge algorithm for computing Distributed Delaunay Triangulations on the cloud, provide a theoretical proof of correctness of this algorithm, and analyse the performance of our Spark implementation in terms of speedup and strong scaling in both synthetic and real use case datasets. A HPC implementation (e.g. using MPI), left for future work, would benefit from its more efficient message passing paradigm but lose the robustness and failure resilience of our Spark approach. Numéro de notice : A2020-410 Affiliation des auteurs : UGE-LASTIG+Ext (2020- ) Autre URL associée : vers HAL Thématique : IMAGERIE/INFORMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.5194/isprs-annals-V-2-2020-195-2020 Date de publication en ligne : 03/08/2020 En ligne : https://doi.org/10.5194/isprs-annals-V-2-2020-195-2020 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=94979 [article]

Tile & merge: Distributed Delaunay triangulations for cloud computing / Laurent Caraffa (2019)  

Public Titre : Tile & merge: Distributed Delaunay triangulations for cloud computing Type de document : Article/Communication Auteurs : Laurent Caraffa , Auteur ; Pooran Memari, Auteur ; Murat Yirci, Auteur ; Mathieu Brédif , Auteur Editeur : New-York : IEEE Computer society Année de publication : 2019 Projets : 1-Pas de projet / Métral, Claudine Conférence : Big Data 2019, IEEE International Conference on Big Data 09/12/2019 12/12/2019 Los Angeles Californie - Etats-Unis Proceedings IEEE Importance : 7 p. Format : 21 x 30 cm Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Traitement d'image [Termes IGN] géomètrie algorithmique [Termes IGN] informatique en nuage [Termes IGN] jeu de données [Termes IGN] mémoire d'ordinateur [Termes IGN] reconstruction d'objet [Termes IGN] semis de points [Termes IGN] Spark [Termes IGN] triangulation de Delaunay Résumé : (auteur) Motivated by the needs of a scalable out-of-core surface reconstruction algorithm available on the cloud, this paper addresses the computation of distributed Delaunay triangulations of massive point sets. The proposed algorithm takes as input a point cloud and first partitions it across multiple processing elements into tiles of relatively homogeneous point sizes. The distributed computation and communication between processing elements is orchestrated so that each one discovers the Delaunay neighbors of its input points within the theoretical overall Delaunay triangulation of all points and computes locally a partial view of this triangulation. This approach prevents memory limitations by never materializing the global triangulation. This efficiency is due to our proposed uncentralized model to represent, manage and locally construct the triangulation corresponding to each tile. The point set is first partitioned into non-overlapping tiles, then we construct within each tile the Delaunay triangulation of the local points and a minimal set of replicated foreign points in order to capture the simplices spanning multiple tiles. Inspired by the star splaying approach for Delaunay triangulation computation/repair, communication is limited to exchanging points of potential Delaunay neighbors across tiles. Therefore, our method is guaranteed to reconstruct, within each tile, a triangulation that contains the star of its local points, as though it were computed within the Delaunay triangulation of all points. The proposed algorithm is implemented with Spark for the scheduling and C++ for the geometric computations. This allows both an optimal scheduling on multiple machines and efficient low-level computation. The results show the efficiency of our algorithm in terms of speedup and strong scaling on a classical Spark configuration with both synthetic and real use case datasets. Numéro de notice : C2019-033 Affiliation des auteurs : LASTIG MATIS+Ext (2012-2019) Autre URL associée : vers HAL Thématique : IMAGERIE/INFORMATIQUE/MATHEMATIQUE Nature : Communication nature-HAL : ComAvecCL&ActesPubliésIntl DOI : 10.1109/BigData47090.2019.9006534 Date de publication en ligne : 24/02/2020 En ligne : https://doi.org/10.1109/BigData47090.2019.9006534 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=95318