Scalable many-to-many building footprint matching
Alexander Naumann, Annika Bonerath, Jan‐Henrik Haunert · Information Fusion · 2025
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.