DDCEL: Efficient Distributed Doubly Connected Edge List for Large Spatial Networks
DDCEL: Efficient Distributed Doubly Connected Edge List for Large Spatial Networks
复制标题
DOI：
10.1109/mdm58254.2023.00029
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
Laila Abdelhafeez;A. Magdy;V. Tsotras
中科院分区：
文献类型：
--
作者：
Laila Abdelhafeez;A. Magdy;V. Tsotras
双连通边列表 (DCEL) 是一种流行的表示平面细分的数据结构，用于加速地图叠加、图形简化和细分遍历等空间应用。当前的 DCEL 实现假设一个独立的机器环境，在处理当今空间应用程序中大量存在的大型数据集时，该环境无法扩展。本文提出了一种分布式双连接边列表（DDCEL）数据结构，将 DCEL 扩展到分布式环境。 DDCEL 构造函数采用两阶段范例来生成细分的顶点、半边和面。对输入数据进行空间分区后，第一阶段在每个数据分区上并行运行顺序 DCEL 构造算法。然后，第二阶段迭代地合并来自多个数据分区的信息以生成共享数据结构。我们对多达 5.63 亿条线段的道路网络真实数据进行的实验评估表明，所提出的方法相对于现有技术具有显着的性能优势。
The Doubly Connected Edge List (DCEL) is a popular data structure for representing planar subdivisions and is used to accelerate spatial applications like map overlay, graph simplification, and subdivision traversal. Current DCEL implementations assume a standalone machine environment, which does not scale when processing the large dataset sizes that abound in today’s spatial applications. This paper proposes a Distributed Doubly Connected Edge List (DDCEL) data structure extending the DCEL to a distributed environment. The DDCEL constructor undergoes a two-phase paradigm to generate the subdivision’s vertices, half-edges, and faces. After spatially partitioning the input data, the first phase runs the sequential DCEL construction algorithm on each data partition in parallel. The second phase then iteratively merges information from multiple data partitions to generate the shared data structure. Our experimental evaluation with real data of road networks of up to 563 million line segments shows significant performance advantages of the proposed approach over the existing techniques.