TY - GEN
T1 - Scalable Overlay Operations over DCEL Polygon Layers
AU - Calderon-Romero, Andres
AU - Tsotras, Vassilis J.
AU - Magdy, Amr
N1 - Publisher Copyright:
© 2023 Owner/Author.
PY - 2023/8/23
Y1 - 2023/8/23
N2 - The Doubly Connected Edge List (DCEL) is an edge-list structure that has been widely utilized in spatial applications for planar topological computations. An important operation is the overlay which combines the DCELs of two input layers and can easily support spatial queries like the intersection, union and difference between these layers. However, existing sequential implementations for computing the overlay do not scale and fail to complete for large datasets (for example the US census tracks). In this paper we propose a distributed and scalable way to compute the overlay operation and its related supported queries. We address the issues involved in efficiently distributing the overlay operator and offer various optimizations that improve performance. Our scalable solution can compute the overlay of very large real datasets (32M edges) in few minutes.
AB - The Doubly Connected Edge List (DCEL) is an edge-list structure that has been widely utilized in spatial applications for planar topological computations. An important operation is the overlay which combines the DCELs of two input layers and can easily support spatial queries like the intersection, union and difference between these layers. However, existing sequential implementations for computing the overlay do not scale and fail to complete for large datasets (for example the US census tracks). In this paper we propose a distributed and scalable way to compute the overlay operation and its related supported queries. We address the issues involved in efficiently distributing the overlay operator and offer various optimizations that improve performance. Our scalable solution can compute the overlay of very large real datasets (32M edges) in few minutes.
KW - DCEL
KW - Spatial data structures
KW - overlay operator
UR - https://www.scopus.com/pages/publications/85171271771
U2 - 10.1145/3609956.3609964
DO - 10.1145/3609956.3609964
M3 - Conference contribution
AN - SCOPUS:85171271771
T3 - ACM International Conference Proceeding Series
SP - 85
EP - 95
BT - Proceedings of 18th International Symposium on Spatial and Temporal Data, SSTD 2023
PB - Association for Computing Machinery
T2 - 18th International Symposium on Spatial and Temporal Data, SSTD 2023
Y2 - 23 August 2023 through 25 August 2023
ER -