Abstract
As the Semantic Web expands, linking massive geospatial datasets has become a significant computational challenge. Determining topological relations—such as whether one complex polygon contains or touches another—traditionally suffers from quadratic complexity and heavy geometric calculations. This paper presents Radon (Rapid Discovery of Topological Relations), a high-performance framework that utilizes a novel sparse indexing method, intelligent filtering, and a volume-based swapping strategy. Radon outperforms existing state-of-the-art tools by up to three orders of magnitude, processing millions of resources in minutes rather than days.
The Challenge of Geospatial Scale
Geospatial Link Discovery (LD) involves identifying topological relations between entities based on the DE-9IM standard. This process faces two primary hurdles:
- Computational Scale: Comparing millions of resources in a naive "all-to-all" fashion leads to $O(n^2)$ complexity, making large-scale discovery infeasible.
- Geometric Complexity: Real-world entities, such as land-cover areas or administrative regions, are often represented by polygons containing thousands of vertices. Calculating precise intersections for these shapes is mathematically intensive.
Existing frameworks often lack the specialized optimizations required to handle "big" geospatial data efficiently.
Methodology: The Radon Framework
Radon introduces a three-pronged optimization strategy to accelerate discovery without sacrificing precision:
- Swapping Strategy: Radon calculates the "Estimated Total Hypervolume" (ETH) of both the source and target datasets. By indexing the dataset with the smaller hypervolume first, the framework minimizes the number of grid cells (hypercubes) generated, reducing memory overhead.
- Optimized Sparse Space Tiling: Unlike traditional dense grids that allocate memory for every cell, Radon employs a sparse index. It only creates "buckets" for hypercubes that actually contain geometric data, effectively ignoring the "empty space" between entities.
- MBB-based Filtering: Radon uses Minimum Bounding Boxes (MBBs) as a lightweight first-pass filter. If the MBBs of two polygons do not interact, the complex geometries themselves cannot have a topological relation (except for "disjoint"). This allows the system to discard the vast majority of candidate pairs before performing expensive geometric intersections.
Experimental Evaluation
The researchers evaluated Radon using real-world datasets, including NUTS (European statistical regions) and CORINE Land Cover (CLC). To test extreme scalability, they used CLCm, a merged dataset containing over 2.2 million resources.
Key Results
Radon demonstrated dramatic performance improvements over existing solutions:
- Versus Silk: Radon was approximately 65x faster on average for smaller datasets. On large-scale tasks where Silk timed out, Radon was estimated to be over 700x faster.
- Versus Strabon: Radon was 12x faster on average. While Strabon’s R-tree index performed well for simple "intersects" queries, Radon dominated in complex relations like "within," "equals," and "crosses."
- Scalability: In parallelized tests (8 threads), Radon processed the 2.2-million-resource CLCm dataset in roughly 20 minutes. Competitive frameworks were estimated to require over 4 days for the same task.
Conclusion and Future Work
Radon proves that physical space (Hypervolume) is a more effective predictor of indexing performance than raw triple counts. By leveraging sparsity and efficient filtering, it transforms geospatial link discovery from a multi-day bottleneck into a near-real-time process. Future work will focus on more sophisticated load balancing, such as particle-swarm optimization, and exploring tighter topology approximations to further refine the filtering stage.
Summary updated