The Quest for Parallel Reasoning on the Semantic Web

Peiqiang Li, Yi Zeng, Spyros Kotoulas, Jacopo Urbani, Ning ZhongAMT 2009 · DOI

TL;DR

The Semantic Web's vast and dynamic data presents a scalability challenge for traditional reasoning systems. This paper explores parallel reasoning approaches for the Semantic Web, introducing and analyzing existing systems like LarKC, MaRVIN, and Reasoning-Hadoop, and proposing a preliminary architecture for parallelizing "ReaSearch" (unifying search and reasoning).

What Problem Does This Paper Address?

The Semantic Web aims to create a web of data with machine-understandable semantics, enabling intelligent applications. A key component of this is reasoning engines, which infer new knowledge from existing data based on rules. However, current reasoning engines are typically designed for single machines and struggle with the sheer scale and dynamic nature of Semantic Web data (RDF and OWL datasets). This limitation hinders the Semantic Web's potential. The paper addresses this by investigating how to parallelize reasoning processes to handle Web-scale data efficiently.

Methods

The paper categorizes parallel reasoning approaches from two perspectives:

  • Platform Architecture:
    • Instruction/Data Streams: SIMD, MISD, MIMD.
  • Memory: SMP (Symmetric Multiprocessing), DMP (Distributed Memory Parallel), and HMS (Hierarchical Memory systems).
  • Algorithm Perspective: Focuses on minimizing communication overhead and achieving load balancing among processing nodes. Two algorithms are discussed:
  • Load Balancing Algorithm [11]: Uses matrices to represent distances and task transfers between reasoning engines, employing a shortest-path approach. It's noted as potentially centralized.
  • Load Sharing by State (LDSHBS) Algorithm [12]: Restricts communication to nearest engines and uses a tree-structured allocator for load balancing.

The paper then delves into specific implementations for Semantic Web reasoning:

  • LarKC (Large Knowledge Collider): An open architecture and generic platform for massive distributed reasoning. It uses a workflow engine with plug-ins that can be distributed and executed in parallel. LarKC supports parallelization through parallel plug-in implementations, distinct plug-in invocation, and parallel execution of multiple workflows.
  • MaRVIN (Massive RDF Versatile Inference Network): A parallel and distributed platform specifically for processing large RDF datasets. It introduces the "divide-conquer-swap" method, which iteratively divides data, computes closures on partitions, and merges results. It also features the "SPEEDDATE" routing strategy to optimize partitioning.
  • Reasoning-Hadoop: A parallel rule-based RDFS/OWL reasoning system built on the Hadoop framework and its MapReduce programming model. It implements data and rule partitioning on a DMP architecture. The paper highlights optimizations for RDFS reasoning, such as in-memory schema triple loading and optimized rule application order.

Finally, the paper proposes a preliminary architecture for ReaSearch (unifying search and reasoning), suggesting parallelization strategies for both search plugins (e.g., meta-search plugin for selecting important subsets) and reasoning plugins (e.g., data partitioning for speed, ensemble reasoning for diverse results).

Datasets

The paper mentions the "2008 Billion Triples challenge" dataset for evaluating Reasoning-Hadoop. It also refers to the "SwetoDBLP dataset" in the context of ReaSearch experiments for calculating co-author numbers. No new benchmarks are introduced.

Key Insights and Ideas

  • The fundamental challenge: Traditional single-machine reasoning is insufficient for the Web's scale and dynamism. Parallelism is essential.
  • Two-pronged approach to parallelism: Effective parallel reasoning requires considering both the underlying hardware architecture (how processors and memory are organized) and the algorithms used to distribute work and manage communication.
  • Semantic Web data is tricky to partition: Unlike traditional data, Semantic Web data (RDF/OWL) has complex dependencies, making straightforward partitioning difficult. This is a recurring theme for systems like MaRVIN.
  • Trade-offs in reasoning: Achieving speed can sometimes come at the cost of completeness or correctness. Systems like MaRVIN demonstrate "anytime behavior," providing incremental results.
  • ReaSearch is the next frontier: Simply parallelizing reasoning isn't enough; unifying search and reasoning (ReaSearch) on a Web scale is crucial, and this unification itself needs parallelization.
  • Ensemble reasoning offers more than just speed: Beyond accelerating computation, ensemble reasoning (using diverse reasoners) can yield richer, more meaningful results by identifying commonalities across different inference paths.

Key Results

  • MaRVIN: Demonstrated the ability to calculate the closure of 200 million triples on 64 compute nodes in 7.2 minutes, achieving a throughput of 450K triples per second.
  • Reasoning-Hadoop: Achieved very high performance for RDFS reasoning, computing the closure of 1 billion triples in under 1 hour using 33 machines. This approach is presented as outperforming others for RDFS.
  • OWL reasoning with Reasoning-Hadoop: The performance for OWL reasoning is noted as not yet competitive, with ongoing research focused on optimizations.

Limitations and Future Work

  • OWL Horst complexity: Reasoning-Hadoop faces challenges with the complexity of OWL Horst rules, which are more difficult to encode and optimize compared to RDFS.
  • Centralized aspects: Some proposed algorithms (like the load balancing algorithm in [11]) are noted as potentially centralized, which can be a bottleneck.
  • ReaSearch parallelization is nascent: The paper presents a "preliminary design" for parallel ReaSearch architecture, indicating this is an area requiring significant further investigation and concrete implementation.
  • Further investigation needed: The authors emphasize the need for more research into parallelizing ReaSearch, particularly the USER-G methods, and exploring how parallel architectures can improve reasoning speed and produce more fruitful results. They plan to delve deeper into concrete implementations in future work.

Summary updated

BibTeX
@inproceedings{li2009quest,
  author = {Peiqiang Li and Yi Zeng and Spyros Kotoulas and Jacopo Urbani and Ning Zhong},
  title = {{The Quest for Parallel Reasoning on the Semantic Web}},
  booktitle = {AMT},
  year = {2009},
  doi = {10.1007/978-3-642-04875-3\_45},
}
Figure