Mind the data skew: distributed inferencing by speeddating in elastic regions

Spyros Kotoulas, Eyal Oren, Frank van HarmelenWWW 2010 · DOI

TL;DR

This paper tackles the challenge of efficiently performing semantic web reasoning on massive, skewed RDF datasets. They introduce "speeddating in elastic regions," a novel peer-to-peer approach that dynamically clusters data, overcoming the scalability limitations of traditional term-based partitioning methods and achieving impressive performance on large-scale RDFS closure computations.

What Problem Does This Paper Address?

The Semantic Web is built on RDF (Resource Description Framework) data, which often exhibits a severe "data skew." This means a few terms (URIs, literals) appear in a vast majority of triples, while most terms are rare. Traditional distributed reasoning systems, which partition data based on these terms (term-based partitioning), struggle with this skew. When a popular term is assigned to a specific peer, that peer becomes a "hotspot," overwhelmed with data and requests, leading to significant load-balancing issues and hindering scalability. This paper aims to develop a distributed reasoning approach that can handle this data skew efficiently and scale to web-scale datasets.

Methods

The core contribution is the "speeddating in elastic regions" approach. Instead of deterministically assigning triples to fixed peers based on terms, this method uses a dynamic, self-organizing peer-to-peer strategy:

  • Elastic Regions: Data is attracted to "regions" of peers rather than fixed locations. These regions dynamically stretch or shrink based on the density of triples associated with a particular term. More popular terms lead to larger regions, recruiting more peers to handle the load.
  • Speeddating: Within these elastic regions, triples are temporarily colocated ("speeddate") to perform inference. This temporal collocation, rather than permanent assignment, is key.
  • Distributed Clustering: A novel algorithm ensures that triples with shared terms are likely to end up in the same or adjacent peers. This is achieved by assigning numeric identifiers to peers and terms, and routing triples based on proximity in this identifier space.
  • Local Clustering: To further enhance inference efficiency, peers locally cluster in-memory triples, prioritizing those that share terms when loading data into the reasoner.

This approach avoids upfront data analysis, central coordination, and is robust to dynamic changes in the network (peers joining/leaving).

Datasets

The paper evaluates its approach using several large-scale RDF datasets:

  • DBpedia: A well-known dataset derived from Wikipedia.
  • Geonames: A dataset of geographical data.
  • SwetoDBLP: A dataset related to computer science publications.
  • Combined Datasets: Aggregations of the above, including a large dataset of 865M triples.

These datasets were chosen to demonstrate the impact of real-world data skew. The authors also reference the Billion Triple Challenge datasets.

Key Insights and Ideas

  • Data Skew is the Enemy of Deterministic Partitioning: The paper strongly demonstrates that the inherent skew in Semantic Web data fundamentally breaks traditional term-based partitioning for distributed reasoning. A single popular term can cripple a peer, regardless of how many other peers are available.
  • Temporal Collocation is Sufficient: For reasoning, triples don't need to be permanently stored together. Temporary "speeddating" within a region is enough to facilitate inference, offering flexibility.
  • Emergent Elasticity: The "elastic regions" are not pre-configured but emerge dynamically from the routing and clustering algorithms. This self-organization is crucial for robustness and scalability.
  • Clustering Improves Inference Efficiency: Both distributed and local clustering significantly boost the rate at which triples can "meet" and participate in inference, leading to faster RDFS closure computation.

Key Results

  • Scalability: The "speeddating" approach scales well with an increasing number of nodes.
  • Performance: The system achieved a throughput of 450,000 triples/sec when computing the RDFS closure of 195M triples on a 64-node cluster.
  • Load Balancing: The approach maintains near-perfect load balancing, comparable to perfectly uniform random partitioning, even with highly skewed data.
  • Efficiency: Combining local and distributed clustering improved join throughput by up to 159% for binary joins compared to random exchanges.
  • RDFS Closure: The paper reports calculating the RDFS closure of 200 million triples in just 7.2 minutes on a 64-node cluster.

Limitations and Future Work

  • Experimental Environment: Experiments were conducted on a distributed compute cluster, not a wide-area network. Issues like bandwidth, peer failures, and network latency were not explicitly evaluated.
  • Reasoner Independence: While the routing is independent of the reasoner, the reported performance metrics (like triple production) are dependent on the specific RDFS reasoner used.
  • Future Work: The authors suggest investigating the applicability of their method to querying, noting that while reasoning prioritizes matching many rules, querying also requires low response times.

Summary updated

BibTeX
@inproceedings{kotoulas2010mind,
  author = {Spyros Kotoulas and Eyal Oren and Frank van Harmelen},
  title = {{Mind the data skew: distributed inferencing by speeddating in elastic regions}},
  booktitle = {The Web Conference},
  year = {2010},
  doi = {10.1145/1772690.1772745},
}
Figure