Back to Search
Start Over
Inverse Space Filling Curve Partitioning Applied to Wide Area Graphs
- Source :
- DMS 2020-11th International conference on Database Management Systems, DMS 2020-11th International conference on Database Management Systems, Nov 2020, Zurich, Switzerland. pp.223-241, ⟨10.5121/csit.2020.101417⟩
- Publication Year :
- 2020
- Publisher :
- HAL CCSD, 2020.
-
Abstract
- International audience; 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.
- Subjects :
- Theoretical computer science
SFC
Inverse
Context (language use)
010103 numerical & computational mathematics
02 engineering and technology
Space-filling curve
01 natural sciences
Graph
0202 electrical engineering, electronic engineering, information engineering
Spatial
Polygon mesh
Use case
ISP
0101 mathematics
[INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB]
Geography
Graph partitioning
Geometric
Graph partition
020206 networking & telecommunications
Partition (database)
Space Filling Curve
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Focus (optics)
Partitioning
Geometric partitioning
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- DMS 2020-11th International conference on Database Management Systems, DMS 2020-11th International conference on Database Management Systems, Nov 2020, Zurich, Switzerland. pp.223-241, ⟨10.5121/csit.2020.101417⟩
- Accession number :
- edsair.doi.dedup.....8f1221c120e736521f6bb64a45d864c6