{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:09:30Z","timestamp":1757617770171,"version":"3.44.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T00:00:00Z","timestamp":1745366400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T00:00:00Z","timestamp":1745366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["IIS-1901379, IIS-2237348, CNS-2031418, SES-1831615"],"award-info":[{"award-number":["IIS-1901379, IIS-2237348, CNS-2031418, SES-1831615"]}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["CAHSI research grant"],"award-info":[{"award-number":["CAHSI research grant"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The Doubly Connected Edge List (DCEL) is an edge-list structure widely used in spatial applications, primarily for planar topological and geometric computations. However, it is also applicable to various types of data, including 3D models and geographic data. An essential operation is the <jats:italic>overlay operation<\/jats:italic>, which combines the DCELs of two input polygon layers and can easily support spatial queries on polygons like the intersection, union, and difference between these layers. However, existing techniques for spatial overlay operations suffer from two main limitations. First, they fail to handle many large datasets practically used in real applications. Second, they cannot handle arbitrary spatial lines that practically form polygons, e.g., city blocks, but they are given as a set of scattered lines. This work proposes a distributed and scalable way to compute the overlay operation and its related supported queries. Our operations also support arbitrary spatial lines through a scalable polygonization process. We address the issues of efficiently distributing the lines and overlay operators and offer various optimizations that improve performance. Our experiments demonstrate that the proposed scalable solution can efficiently compute the overlay of large real datasets.<\/jats:p>","DOI":"10.1007\/s10707-025-00539-x","type":"journal-article","created":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T02:48:20Z","timestamp":1745376500000},"page":"751-788","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On scalable DCEL overlay operations"],"prefix":"10.1007","volume":"29","author":[{"given":"Andres","family":"Calderon-Romero","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laila","family":"Abdelhafeez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Goce","family":"Trajcevski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amr","family":"Magdy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vassilis J.","family":"Tsotras","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,23]]},"reference":[{"key":"539_CR1","volume-title":"The design and analysis of spatial data structures","author":"H Samet","year":"1990","unstructured":"Samet H (1990) The design and analysis of spatial data structures. Wesley, Boston"},{"issue":"1","key":"539_CR2","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J Nievergelt","year":"1984","unstructured":"Nievergelt J, Hinterberger H, Sevcik K (1984) The grid file: An adaptable, symmetric multikey file structure. ACM Trans Database Syst 9(1):38\u201371","journal-title":"ACM Trans Database Syst"},{"key":"539_CR3","doi-asserted-by":"crossref","unstructured":"Guttman A (1984) R-Trees: a dynamic index structure for spatial searching. In: ACM SIGMOD ICMD, pp. 47\u201357. Association for Computing Machinery, New York","DOI":"10.1145\/971697.602266"},{"key":"539_CR4","doi-asserted-by":"crossref","unstructured":"Beckmann N, Kriegel H, Schneider R, Seeger B (1990) The R*-Tree: an efficient and robust access method for points and rectangles. In: ACM SIGMOD PODS, pp. 322\u2013331. Association for Computing Machinery, New York","DOI":"10.1145\/93597.98741"},{"key":"539_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R Finkel","year":"1974","unstructured":"Finkel R, Bentley J (1974) Quadtrees: a data structure for retrieval on composite keys. Acta Inf 4:1\u20139","journal-title":"Acta Inf"},{"key":"539_CR6","unstructured":"Berg M, Cheong O, Kreveld M, Overmars M (2008) Computational geometry: algorithms and applications. Springer, TU Eindhoven"},{"issue":"2","key":"539_CR7","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0304-3975(78)90051-8","volume":"7","author":"D Muller","year":"1978","unstructured":"Muller D, Preparata F (1978) Finding the intersection of two convex polyhedra. Theoret Comput Sci 7(2):217\u2013236","journal-title":"Theoret Comput Sci"},{"key":"539_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: an introduction","author":"F Preparata","year":"1985","unstructured":"Preparata F, Shamos M (1985) Computational Geometry: an introduction. Springer, New York, NY"},{"issue":"1","key":"539_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal V (1975) A combinatorial theorem in plane geometry. Comb Theory 18(1):39\u201341","journal-title":"Comb Theory"},{"key":"539_CR10","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke J (1987) Art gallery theorems and algorithms. Oxford University Press, United States"},{"issue":"2","key":"539_CR11","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0925-7721(93)90001-M","volume":"3","author":"L Chew","year":"1993","unstructured":"Chew L, Kedem K (1993) A convex polygon among polygonal obstacles. Comput Geom 3(2):59\u201389","journal-title":"Comput Geom"},{"key":"539_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17283-0","volume-title":"CGAL arrangements and their applications","author":"E Fogel","year":"2012","unstructured":"Fogel E, Halperin D, Wein R (2012) CGAL arrangements and their applications. Springer, Heidelberg"},{"issue":"1","key":"539_CR13","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s11786-010-0043-4","volume":"4","author":"E Berberich","year":"2010","unstructured":"Berberich E, Fogel E, Halperin D, Kerber M, Setter O (2010) Arrangements on parametric surfaces. Math Comput Sci 4(1):67\u201391","journal-title":"Math Comput Sci"},{"issue":"2","key":"539_CR14","first-page":"188","volume":"66","author":"P Boguslawski","year":"2011","unstructured":"Boguslawski P, Gold C, Ledoux H (2011) Modelling and analysing 3D buildings with a primal\/dual data structure. ISPRS. 66(2):188\u2013197","journal-title":"ISPRS."},{"key":"539_CR15","doi-asserted-by":"crossref","unstructured":"Calderon A, Tsotras V, Magdy A (2023) Scalable overlay operations over DCEL polygon layers. In: Proceedings of the 18th international Symposium on Spatial and Temporal Data. SSTD \u201923, pp. 85\u201395. Association for Computing Machinery, New York, NY, USA","DOI":"10.1145\/3609956.3609964"},{"key":"539_CR16","doi-asserted-by":"crossref","unstructured":"Abdelhafeez L, Magdy A, Tsotras V (2023) DDCEL: efficient distributed doubly connected edge list for large spatial networks. In: 2023 24th IEEE international conference on Mobile Data Management (MDM). pp 122\u2013131","DOI":"10.1109\/MDM58254.2023.00029"},{"issue":"05n06","key":"539_CR17","first-page":"619","volume":"08","author":"G Barequet","year":"1998","unstructured":"Barequet G (1998) DCEL - a polyhedral database and programming environment. IJCGA. 08(05n06):619\u2013636","journal-title":"IJCGA."},{"key":"539_CR18","doi-asserted-by":"crossref","unstructured":"Boltcheva D, Basselin J, Poull C, Barth\u00e9lemy H, Sokolov D (2020) Topological-based roof modeling from 3D point clouds. In: WSCG, vol. 28, pp. 137\u2013146. Union Agency, Science Press, Plzen","DOI":"10.24132\/JWSCG.2020.28.17"},{"key":"539_CR19","unstructured":"Freiseisen W (1998) Colored DCEL for boolean operations in 2D"},{"issue":"1","key":"539_CR20","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K Mehlhorn","year":"1995","unstructured":"Mehlhorn K, N\u00e4her S (1995) LEDA: a platform for combinatorial and geometric computing. Commun ACM 38(1):96\u2013102","journal-title":"Commun ACM"},{"key":"539_CR21","unstructured":"Holmes R (2021) The DCEL data structure for 3D graphics. University of Bremen"},{"key":"539_CR22","first-page":"27","volume-title":"IEEE big data","author":"J Challa","year":"2016","unstructured":"Challa J, Goyal P, Nikhil S, Mangla A, Balasubramaniam S, Goyal N (2016) DD-Rtree: a dynamic distributed data structure for efficient data distribution among cluster nodes for spatial data mining algorithms. IEEE big data. IEEE, Danvers, pp 27\u201336"},{"key":"539_CR23","first-page":"1","volume-title":"ACM SIGSPATIAL","author":"I Sabek","year":"2017","unstructured":"Sabek I, Mokbel M (2017) On spatial joins in Map-Reduce. ACM SIGSPATIAL. Association for Computing Machinery, New York, pp 1\u201310"},{"issue":"1","key":"539_CR24","first-page":"523","volume":"28","author":"Y Li","year":"2019","unstructured":"Li Y, Eldawy A, Xue J, Knorozova N, Mokbel M, Janardan R (2019) Scalable computational geometry in Map-Reduce. VLDB. 28(1):523\u2013548","journal-title":"Scalable computational geometry in Map-Reduce. VLDB."},{"key":"539_CR25","first-page":"16","volume-title":"ACM BigSpatial","author":"W Franklin","year":"2018","unstructured":"Franklin W, Magalh\u00e3es S, Andrade M (2018) Data structures for parallel spatial algorithms on large datasets. ACM BigSpatial. ACM, Seattle, pp 16\u201319"},{"key":"539_CR26","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/2835185.2835188","volume-title":"ACM BigSpatial","author":"S Magalh\u00e3es","year":"2015","unstructured":"Magalh\u00e3es S, Andrade M, Franklin W, Li W (2015) Fast exact parallel map overlay using a two-level uniform grid. ACM BigSpatial. Association for Computing Machinery, New York, pp 45\u201354"},{"key":"539_CR27","first-page":"2238","volume-title":"IEEE IPDPS","author":"S Puri","year":"2013","unstructured":"Puri S, Prasad S (2013) Efficient parallel and distributed algorithms for GIS polygonal overlay processing. IEEE IPDPS. IEEE Computer Society, USA, pp 2238\u20132241"},{"key":"539_CR28","first-page":"1009","volume-title":"IEEE IPDPS","author":"S Puri","year":"2013","unstructured":"Puri S, Agarwal D, He X, Prasad S (2013) Map-Reduce algorithms for GIS polygonal overlay processing. IEEE IPDPS. IEEE, Cambridge, pp 1009\u20131016"},{"key":"539_CR29","unstructured":"JTS Polygonizer Implementation. https:\/\/github.com\/locationtech\/jts"},{"key":"539_CR30","unstructured":"GEOS Polygonizer Implementation. https:\/\/github.com\/libgeos\/geos"},{"key":"539_CR31","doi-asserted-by":"crossref","unstructured":"Pandey V, Renen A, Kipf A, Kemper A (2021) How good are modern spatial libraries? Data science and engineering","DOI":"10.1007\/978-3-030-59416-9_46"},{"key":"539_CR32","doi-asserted-by":"crossref","unstructured":"Aji A, Wang F, Vo H, Lee R, Liu Q, Zhang X, Saltz J (2013) Hadoop-GIS: a high performance spatial data warehousing system over Map-Reduce. In: VLDB Journal","DOI":"10.14778\/2536222.2536227"},{"key":"539_CR33","doi-asserted-by":"crossref","unstructured":"Eldawy A, Mokbel MF (2015) Spatialhadoop: a map-reduce framework for spatial data. In: Proceedings of the IEEE International Conference on Data Engineering, ICDE","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"539_CR34","doi-asserted-by":"crossref","unstructured":"Yu J, Zhang Z, Sarwat M (2018) Spatial data management in Apache Spark: the GeoSpark perspective and beyond. GeoInformatica","DOI":"10.1007\/s10707-018-0330-9"},{"key":"539_CR35","doi-asserted-by":"crossref","unstructured":"You S, Zhang J, Gruenwald L (2015) Large-scale spatial join query processing in cloud. In: Proceedings of the IEEE International Conference on Data Engineering, ICDE","DOI":"10.1109\/ICDEW.2015.7129541"},{"key":"539_CR36","doi-asserted-by":"crossref","unstructured":"Hoel EG, Samet H (2003) Data-parallel polygonization. Parallel Computing","DOI":"10.1016\/j.parco.2003.05.001"},{"key":"539_CR37","unstructured":"OpenStreetMap Data Extracts. http:\/\/download.geofabrik.de\/"},{"key":"539_CR38","doi-asserted-by":"publisher","unstructured":"U.S. Street Network Shapefiles, Node\/Edge Lists, and GraphML Files. https:\/\/doi.org\/10.7910\/DVN\/CUWWYJ","DOI":"10.7910\/DVN\/CUWWYJ"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-025-00539-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10707-025-00539-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-025-00539-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T11:47:30Z","timestamp":1757159250000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10707-025-00539-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,23]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["539"],"URL":"https:\/\/doi.org\/10.1007\/s10707-025-00539-x","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"type":"print","value":"1384-6175"},{"type":"electronic","value":"1573-7624"}],"subject":[],"published":{"date-parts":[[2025,4,23]]},"assertion":[{"value":"31 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This work was partially supported by the National Science Foundation under grants IIS-1901379, IIS-2237348, CNS-2031418, SES-1831615, and the Google-CAHSI research grant.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}