Scaling Large RDF Archives To Very Long Histories

Olivier Pelgrin, Ruben Taelman, Luis Galárraga, Katja HoseICSC 2023 · DOI

Abstract

Managing the evolution of Resource Description Framework (RDF) data is critical for version control, trend analysis, and historical querying. However, existing archiving systems like OSTRICH struggle to scale as histories grow into the thousands of revisions, primarily due to the overhead of maintaining a single, massive delta chain. This paper introduces a multi-snapshot hybrid approach that periodically creates fresh snapshots to start new delta chains. Evaluation using the BEAR benchmark demonstrates ingestion speedups of up to 100x, enabling the management of datasets with over 20,000 revisions—a scale previously considered unreachable.

The Challenge of RDF Archiving

RDF data serves as the backbone of the Semantic Web, powering massive knowledge bases like DBpedia and Wikidata. As these datasets evolve, researchers require access to their entire history rather than just the current state. Current state-of-the-art systems utilize "aggregated changesets," where a base version is stored alongside a list of every addition and deletion since that point.

While efficient for small histories, this approach faces a scaling nightmare as the number of revisions grows. The "delta" (the change log) becomes bloated, and ingesting a new version becomes exponentially slower because the system must reconcile it against an ever-growing mountain of previous changes. For datasets like "DBpedia Live," which receive continuous updates, existing tools eventually hit an "ingestion wall," where processing new data takes months instead of hours.

The Multi-Snapshot Hybrid Approach

To overcome the ingestion wall, this research proposes moving from a single, massive delta chain to a multi-snapshot hybrid architecture. Instead of maintaining one snapshot at version 0 followed by tens of thousands of changes, the system periodically creates a fresh snapshot—a full copy of the graph at that moment—and starts a new delta chain from there.

Comparison of (a) a single delta chain versus (b) the proposed multiple delta chains architecture.

Implementing this required two major innovations:

  1. Cross-Chain Query Algorithms: New methods were developed to handle queries spanning different delta chains. For example, calculating the difference between version 500 (in Chain A) and version 1500 (in Chain B) requires reconciling intermediate deltas with the differences between the snapshots themselves.
  2. Snapshot Creation Strategies: Since snapshots improve speed but consume disk space, the authors tested several strategies to determine the optimal trigger for a new snapshot:
  3. Periodic: Create a snapshot every X versions.
  4. Change-ratio: Trigger a snapshot when the cumulative amount of change exceeds a specific threshold.
  5. Time-based: Trigger a snapshot when ingestion time slows significantly compared to the initial version.

Evaluation and Key Results

The approach was evaluated using the BEAR benchmark, focusing on the BEAR-B Instant dataset. This dataset features 21,046 revisions, representing a "final boss" scenario for RDF archiving engines.

Ingestion duration (ms) vs. Version for BEAR-B Daily, Hourly, and Instant datasets, comparing various snapshot strategies against the baseline.

Ingestion Performance

The study confirmed that without multiple snapshots, ingesting BEAR-B Instant would take over a month. With the hybrid approach, the process was completed in less than two hours. Ingestion speedups of up to 100x (two orders of magnitude) were observed for the BEAR-B Hourly dataset.

Query Performance and Trade-offs

While the hybrid approach significantly improves ingestion and Version Materialization (VM) queries (viewing a specific point in time), it introduces a penalty for Version Queries (VQ). Because V-Queries must check every delta chain individually to see when a specific fact existed, having too many snapshots can lead to a linear slowdown. However, Diff Queries (DM) remained competitive, often outperforming the baseline on long histories where single-chain operations become sluggish.

Storage Efficiency

Interestingly, the authors found that for very long histories, a single delta chain can actually become less space-efficient than a few well-placed snapshots. This is due to the massive overhead required to manage aggregated changesets in a single, bloated chain.

Conclusion and Future Work

The multi-snapshot approach makes archiving massive, frequently-updated RDF knowledge graphs feasible for the first time. The "Change-ratio" strategy proved particularly effective by monitoring data redundancy to trigger snapshots only when necessary.

Future research will focus on mitigating the V-Query penalty, potentially using machine learning to predict optimal snapshot moments based on expected query loads. Additionally, the authors aim to study how multi-chain structures affect complex SPARQL join queries and explore more efficient serialization for the deltas themselves.

Summary updated

BibTeX
@inproceedings{pelgrin2023scaling,
  author = {Olivier Pelgrin and Ruben Taelman and Luis Galárraga and Katja Hose},
  title = {{Scaling Large RDF Archives To Very Long Histories}},
  booktitle = {ICSC},
  year = {2023},
  doi = {10.1109/icsc56153.2023.00013},
}
Figure