Inverse Space Filling Curve Partitioning Applied to Wide Area Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Inverse Space Filling Curve Partitioning Applied to Wide Area Graphs

Résumé

The most recent developments in graph partitioning research often consider scale-free graphs. Instead we focus on partitioning geometric graphs using a less usual strategy: Inverse Spacefilling Partitioning (ISP). ISP relies on a space filling curve to partition a graph and was previously applied to graphs essentially generated from Meshes. We extend ISP to apply it to a new context where the targets are now Wide Area Graphs. We provide an extended comparison with two state-of-the-art graph partitioning streaming strategies, namely LDG and FENNEL. We also propose customized metrics to better understand and identify the use cases for which the ISP partitioning solution is best suited. Experimentations show that in favourable contexts, edge-cuts can be drastically reduced, going from more 34% using FENNEL to less than 1% using ISP.
Fichier principal
Vignette du fichier
csit101417.pdf (810.98 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03137952 , version 1 (10-02-2021)

Identifiants

Citer

Cyprien Gottstein, Philippe Raipin Parvedy, Michel Hurfin, Thomas Hassan, Thierry Coupaye. Inverse Space Filling Curve Partitioning Applied to Wide Area Graphs. DMS 2020 - 11th International conference on Database Management Systems, Nov 2020, Zurich, Switzerland. pp.223-241, ⟨10.5121/csit.2020.101417⟩. ⟨hal-03137952⟩
129 Consultations
79 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More