Efficient Identification of High Similarity Clusters in Polygon Datasets

John N. Daras · 2025

Read Efficient Identification of High Similarity Clusters in Polygon Datasets by John N. Daras (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-23942.txt.

Introduction

Finding clusters of near-duplicate polygons in a giant spatial data set can drown even fast geometry tools in comparisons. John N. Daras, the sole author, proposes a framework that cuts how many clusters need full verification. Dynamic thresholding, guided by kernel density estimation, sets similarity cutoffs as the data demand. A supervised scheduling step, driven by machine learning models, prioritizes which clusters to check first.

A recall-constrained optimization keeps the savings honest, holding user-set precision and recall targets. Experiments show substantial cost reductions without losing accuracy. Daras offers the framework as a practical route to large-scale geospatial similarity analysis with modern tools like Shapely and Triton.

Catalog record

CREATORJohn N. Daras
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-23942

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Identification of High Similarity Clusters in Polygon Datasets John N. Daras Abstract Advancements in tools like Shapely 2.0 and Triton can significantly improve the efficiency of spatial similarity computations by enabling faster and more scalable geometric operations [ 1 , 2 ] . However, for extremely large datasets, these optimizations may face challenges due to the sheer volume of computations required. To address this, we propose a framework that reduces the number of clusters requiring verification, thereby decreasing the computational load on these systems. The framework integrates dynamic similarity index thresholding, supervised scheduling [ 3 ] , and recall-constrained optimization to efficiently identify clusters with the highest spatial similarity while meeting user-defined precision and recall requirements [ 4 ] . By leveraging Kernel Density Estimation (KDE) to dynamically determine similarity thresholds [ 5 ] and machine learning models to prioritize clusters, our approach achieves substantial reductions in computational cost without sacrificing accuracy. Experimental results demonstrate the scalability and effectiveness of the method, offering a practical solution for large-scale geospatial analysis. I Introduction Geospatial data constitutes the cornerstone of numerous applications across various domains, including urban planning, environmental monitoring, infrastructure development, and medicine. For example, OpenStreetMap contains global data amounting to over 1.5 terabytes [ 6 ] , while GeoNames describes more than 12 million locations, providing extensive point geometries such as latitude and longitude [ 7 ] . Expanding these datasets, geospatial knowledge graphs like YAGO2geo integrate millions of lines, polygons, and multipolygons from OpenStreetMap and administrative divisions [ 8 ] , while WorldKG represents around 113.4 million geographic entities [ 9 ] . KnowWhereGraph, a more recent initiative, comprises over 12 billion RDF triples, including data on polygons and multipolygons, and supports applications in disaster relief, agricultural land use, and food-related supply chains [ 10 ] . Even cross-domain knowledge graphs such as DBpedia and Wikidata incorporate a substantial amount of geospatial information, underscoring the critical role of spatial data on the Web. Beyond these well-known repositories, spatial datasets also play a transformative role in medicine, particularly in the analysis and modeling of organ structures. For instance, the Visible Human Project provides high-resolution spatial data for anatomical structures [ 11 ] , while the Human Connectome Project captures detailed spatial relationships within the brain [ 12 ] . Other datasets, such as the ACDC dataset, focus on cardiac MRI images to segment the heart [ 13 ] , while the 3D Liver Tumor Dataset provides high-resolution spatial data for liver segmentation and tumor localization [ 14 ] . These datasets are essential for advancing medical imaging, surgical planning, and personalized medicine. Despite the prominence and growing volume of spatial data, processing and analyzing these datasets efficiently remains a significant challenge. For instance, while OpenStreetMap geometries are widely used, only a fraction of them—0.52% as of April 2021—are linked to other sources such as Wikidata, highlighting the lack of comprehensive integration across datasets. Similarly, in medical datasets, the complexity and volume of spatial data often lead to computational bottlenecks, particularly when identifying spatial similarities or patterns across large datasets. Identifying clusters of geometric objects with strong spatial similarities is a fundamental task in geospatial analysis, with applications spanning urban planning, environmental monitoring, infrastructure analysis, medicine, and global datasets. In urban planning, such clusters reveal patterns in land use, infrastructure, or building layouts, aiding targeted development and disaster management. In environmental monitoring, they highlight regions with similar vegetation, soil, or climate characteristics, supporting conservation and agricultural optimization. Medical applications benefit from clustering spatially similar organ shapes or tissue structures to identify abnormalities, plan surgeries, and personalize treatments. Similarly, in datasets like OpenStreetMap, clustering geometrically similar objects improves data integration and interlinking for navigation, disaster response, and supply chain optimization. Across these domains, clustering high-similarity geometries enables meaningful insights, resource optimization, and predictive modeling. To quantify this, each cluster is assigned a similarity index, calculated as the average pairwise similarity score of its objects. This index serves as a benchmark for determining which clusters exhibit the highest spatial resemblance, providing the foundation for downstream analysis and decision-making. In this work the similarity index is derived from robust spatial similarity metrics, which are designed to capture various geometric and spatial properties of the objects in a cluster. These metrics are grouped into four categories: (1) Overlap Metrics (e.g., Jaccard similarity [ 15 ] , area similarity); (2) Shape Complexity Metrics (e.g., curvature, Fourier descriptors) [ 16 , 17 ] ; (3) Proportional and Spatial Metrics (e.g., aspect ratio similarity, bounding box distance) [ 18 ] ; and (4) Boundary Metrics (e.g., perimeter, circularity [ 18 ] ). Together, these metrics provide a comprehensive and nuanced measure of spatial similarity, enabling the accurate calculation of similarity indexes for clusters. However, calculating these similarity metrics for every cluster in a large dataset can be computationally expensive, particularly when the goal is to identify only the top percentage of high-similarity clusters. Recent advancements in tools like Triton and Shapely 2.0 offer opportunities to improve the efficiency of these calculations. Shapely 2.0 introduces vectorized operations, enabling geometric computations to be performed across multiple shapes simultaneously. By leveraging these capabilities, tasks such as calculating bounding boxes, intersections, and unions for large numbers of clusters can be completed more efficiently, reducing reliance on iterative loops in Python and improving throughput. In addition, Triton provides a way to harness GPU acceleration directly within Python, which can significantly reduce the computational overhead of tasks such as similarity metric calculations once geometric operations have been completed. Despite these optimizations, evaluating similarity metrics across large datasets remains demanding, underscoring the importance of reducing the number of required verifications. Traditionally, identifying clusters in the top percentage of similarity indexes (e.g., top 10%, 30%, or 50%) would require calculating the similarity indexes for all clusters, sorting them, and selecting the desired proportion—an approach that is computationally prohibitive for large datasets. To overcome this limitation, the proposed framework introduces Kernel Density Estimation (KDE) to dynamically determine the similarity index threshold corresponding to the desired top percentage. By estimating the distribution of similarity indexes from a representative sample of clusters, this method identifies the threshold directly, eliminating the need for exhaustive similarity calculations across the entire dataset. After determining the threshold, the framework employs a supervised scheduling approach to prioritize clusters for verification. During training, a sample of clusters is selected and their similarity indexes are computed. Clusters with similarity indexes above the threshold are labeled as “high similarity indexed” (class 1), while those below are labeled as “low similarity indexed” (class 0). A machine learning model is then trained using computationally lightweight features paired with these labels, enabling the model to predict which clusters are most likely to exceed the threshold. During verification, the model’s predictions focus computational resources on the most promising candidates, reducing overall cost while maintaining high recall. To further enhance reliability, a recall-constrained optimization technique is applied to ensure the system achieves a high recall rate. This ensures that the framework reliably identifies all important clusters with high similarity, even if it allows for some false positives. By dynamically adjusting the classification threshold, this technique prioritizes recall over precision so that no high-similarity clusters are overlooked—particularly critical in applications such as

Read the complete text