The amount of available geospatial data, particularly different data sets describing the same area, grows continuously. Finding entity correspondences between multiple such datasets is a vital prerequisite for data integration, fusion, and quality assessment. In this work, we focus on polygon datasets, more specifically, building footprints. We compute many-to-many matchings between two input datasets to find correspondences between polygons. Existing research explored heuristic solutions, exact optimization approaches, and machine learning strategies. So far, none of these methods scale well to large datasets while providing a precise problem formulation to measure the quality of a computed matching. We present a fast and versatile algorithm based on a constrained optimization model. Given a partitioning of the datasets into connected subsets, it can solve instances of over 5 million polygons per dataset in under 7 min. Our approach is based on the Jaccard index (intersection over union, IoU) as its central quality measure. However, it is flexible and easily adaptable to different metrics proposed in other works.

doi:10.1016/j.inffus.2025.103360

@article{naumann2025matching,
    abstract = {The amount of available geospatial data, particularly different data sets describing the same area, grows continuously. Finding entity correspondences between multiple such datasets is a vital prerequisite for data integration, fusion, and quality assessment. In this work, we focus on polygon datasets, more specifically, building footprints. We compute many-to-many matchings between two input datasets to find correspondences between polygons. Existing research explored heuristic solutions, exact optimization approaches, and machine learning strategies. So far, none of these methods scale well to large datasets while providing a precise problem formulation to measure the quality of a computed matching. We present a fast and versatile algorithm based on a constrained optimization model. Given a partitioning of the datasets into connected subsets, it can solve instances of over 5 million polygons per dataset in under 7 min. Our approach is based on the Jaccard index (intersection over union, IoU) as its central quality measure. However, it is flexible and easily adaptable to different metrics proposed in other works.},
    author = {Naumann, Alexander and Bonerath, Annika and Haunert, Jan-Henrik},
    doi = {10.1016/j.inffus.2025.103360},
    journal = {Information Fusion},
    note = {Accepted for publication. Already available online.},
    pages = {},
    publisher = {Elsevier},
    title = {Scalable many-to-many building footprint matching},
    url = {https://www.sciencedirect.com/science/article/pii/S1566253525004336},
    volume = {},
    year = {2025}
}

Recent developments in consumer-grade panoramic cameras led to new possibilities in creating virtual tours, e.g., through museums or real estate. Most current approaches for the creation of these tours are based on manual generation of navigable links between the images. We consider cases where large numbers of georeferenced images are taken by multiple users and introduce an approach for automatically generating a graph structure that links the images in a reasonable network while sorting out redundant data. Our approach does not expect a trajectory of temporally related points but merely an incoherent point cloud, e.g., from crowdsourcing of many different contributors. We expand our methodology by a visualization approach offering in-image navigation, realized through interactive links pointing towards neighbored images. Our method delivers a virtual tour with adjustable density on and apart from road networks. We compared the output of our algorithm to human-made virtual tour graphs and were able to verify a high similarity, which approves the hypothesis that automatically generated virtual tours can be intuitive for users.

doi:10.1007/s41651-025-00228-1

@article{baltzer2025graph,
    abstract = {Recent developments in consumer-grade panoramic cameras led to new possibilities in creating virtual tours, e.g., through museums or real estate. Most current approaches for the creation of these tours are based on manual generation of navigable links between the images. We consider cases where large numbers of georeferenced images are taken by multiple users and introduce an approach for automatically generating a graph structure that links the images in a reasonable network while sorting out redundant data. Our approach does not expect a trajectory of temporally related points but merely an incoherent point cloud, e.g., from crowdsourcing of many different contributors. We expand our methodology by a visualization approach offering in-image navigation, realized through interactive links pointing towards neighbored images. Our method delivers a virtual tour with adjustable density on and apart from road networks. We compared the output of our algorithm to human-made virtual tour graphs and were able to verify a high similarity, which approves the hypothesis that automatically generated virtual tours can be intuitive for users.},
    author = {Baltzer, Dorian and Naumann, Alexander and Rosenberg, Stephan and Haunert, Jan-Henrik},
    doi = {10.1007/s41651-025-00228-1},
    journal = {Journal of Geovisualization and Spatial Analysis},
    pages = {},
    publisher = {Springer Nature},
    title = {Graph Construction and Interactive Visualization for Virtual Tours Based on Redundant Panoramic Image Collections},
    url = {https://link.springer.com/article/10.1007/s41651-025-00228-1},
    volume = {9},
    year = {2025}
}

Integration of spatial data is a major field of research. An important task of data integration is finding correspondences between entities. Here, we focus on combining building footprint data from cadastre and from volunteered geographic information, in particular OpenStreetMap. Previous research on this topic has led to exact 1:1 matching approaches and heuristic m:n matching approaches, most of which are lacking a mathematical problem definition. We introduce a model for many-to-many polygon matching based on the well-established Jaccard index. This is a natural extension to the existing 1:1 matching approaches. We show that the problem is NP-complete and a naive approach via integer programming fails easily. By analyzing the structure of the problem in detail, we can reduce the number of variables significantly. This approach yields an optimal m:n matching even for large real-world instances with appropriate running time. In particular, for the set of all building footprints of the city of Bonn (119,300 / 97,284 polygons) it yielded an optimal solution in approximately 1 hour.

doi:10.4230/LIPIcs.ESA.2024.90

@inproceedings{NaumannEtAl2024,
    abstract = {Integration of spatial data is a major field of research. An important task of data integration is finding correspondences between entities. Here, we focus on combining building footprint data from cadastre and from volunteered geographic information, in particular OpenStreetMap. Previous research on this topic has led to exact 1:1 matching approaches and heuristic m:n matching approaches, most of which are lacking a mathematical problem definition. We introduce a model for many-to-many polygon matching based on the well-established Jaccard index. This is a natural extension to the existing 1:1 matching approaches. We show that the problem is NP-complete and a naive approach via integer programming fails easily. By analyzing the structure of the problem in detail, we can reduce the number of variables significantly. This approach yields an optimal m:n matching even for large real-world instances with appropriate running time. In particular, for the set of all building footprints of the city of Bonn (119,300 / 97,284 polygons) it yielded an optimal solution in approximately 1 hour.},
    author = {Naumann, Alexander and Bonerath, Annika and Haunert, Jan-Henrik},
    booktitle = {Proc. European Symposium on Algorithms (ESA'24)},
    doi = {10.4230/LIPIcs.ESA.2024.90},
    pages = {90:1--90:15},
    title = {Many-to-many polygon matching \`{a} la {Jaccard}},
    year = {2024}
}