Abstract
Entity Resolution (ER) is a critical task for linking data on the Semantic Web, yet its quadratic complexity poses significant scalability challenges. This paper adapts the "Sorted Neighborhood" (SN) blocking method, traditionally used in relational databases, for the flexible and schema-free environment of RDF data. We propose a modular workflow that leverages property-specific blocking keys and sliding window techniques to efficiently identify candidate entity pairs. Evaluation on real-world benchmarks demonstrates that our approach maintains high pairs completeness while significantly reducing the number of required comparisons, outperforming established clustering-based baselines.
Introduction
In the Semantic Web, data is represented as a graph (RDF), where nodes represent entities and edges represent properties. A fundamental challenge in this domain is Entity Resolution (ER): determining whether two distinct nodes refer to the same real-world object. For example, a system must decide if "Cathy Ridley" in one dataset is the same individual as "Catherine Ridley" in another.
Performing exhaustive comparisons across large datasets is computationally prohibitive. With $n$ entities, a naive approach requires $n^2$ comparisons. Given the billions of resources in the Linked Open Data (LOD) cloud, this quadratic growth makes exhaustive ER impossible. To mitigate this, researchers employ blocking techniques, which group similar entities into blocks to restrict comparisons to likely matches. While the "Sorted Neighborhood" (SN) method is a standard in relational database blocking, its application to RDF has been limited by the schema-free and distributed nature of graph data.
Methodology
The authors propose a modular workflow designed to operationalize Sorted Neighborhood for RDF data, bridging the gap between structured relational tables and flexible graphs.
The workflow consists of several key stages:
- Property-Specific Blocking Keys: Instead of a fixed schema, the system uses specific RDF properties to generate Blocking Key Values (BKVs). For instance, a BKV might combine a name's initials with a zip code.
- Loosely Structured Tuples: The system can ingest data from local files or remote SPARQL endpoints. It extracts relevant properties to form "loosely structured tuples," effectively flattening the graph into a sortable format.
- Sorting and Windowing: Entities are sorted based on their BKVs. A sliding window of size $w$ (typically 2 to 10) moves across the sorted list. Only entities appearing within the same window are considered candidate pairs for subsequent, more intensive similarity checks.
- Result Publication: The workflow supports publishing blocking results back to the web as "third-party triples," enabling work reuse and caching across the LOD cloud.
Experimental Evaluation
The proposed SN workflow was evaluated using the Video Game benchmark, a dataset comprising over 230,000 triples. The primary metrics for evaluation were the Reduction Ratio (the percentage of comparisons avoided) and Pairs Completeness (the percentage of true matches successfully identified).
The results indicate that the SN approach consistently outperforms Canopies, a popular clustering-based baseline. Notably, SN exhibits "graceful degradation": it maintains higher pairs completeness even as the reduction ratio increases. By utilizing a sliding window where $w \ll n$, the computational complexity is dominated by the $O(n \log n)$ sorting step rather than the comparison step, providing significant efficiency gains.
Conclusion and Future Work
This research demonstrates that Sorted Neighborhood can be effectively adapted for the Semantic Web without requiring rigid schemas. By focusing on property-specific keys, the method remains robust even with messy or incomplete Linked Open Data.
Future work will address scaling the workflow to billions of triples using MapReduce frameworks. Additionally, the authors aim to automate the selection of optimal blocking keys and explore dynamic window sizes to better handle varying data densities.
Summary updated