G-ToPSS: fast filtering of graph-based metadata

Milenko Petrovic, Haifeng Liu, Hans-Arno JacobsenWWW 2005 · DOI

TL;DR

This paper introduces G-ToPSS, a novel publish/subscribe system designed for efficient filtering of graph-based metadata like RSS feeds. It tackles the scalability issues of current RSS dissemination by using a graph-matching approach that leverages ontologies and RDFS taxonomies for richer semantic filtering, outperforming existing methods in performance and scalability.

What Problem Does This Paper Address?

The internet is awash with information, and tools for publishing this information have become increasingly accessible. This has led to a proliferation of online content, particularly in formats like RSS (RDF Site Summary), which are used to track changes in web content. Current methods for disseminating this information, primarily RSS feed aggregators, rely on a "pull-based" architecture where aggregators constantly poll numerous RSS feeds. This approach is inefficient, consumes significant resources, and struggles to scale as the volume of content and publishers grows. The paper aims to address this scalability challenge by proposing a more efficient publish/subscribe system for selective information dissemination, particularly for large-volume, graph-based metadata.

Methods

G-ToPSS employs a publish/subscribe, data-centric communication model with three main entities: publishers, subscribers, and brokers. The core innovation lies in its graph-based publication and subscription data model, which uses directed graphs to represent RDF data.

  • Publication Data Model: Publications are represented as directed labeled graphs, where nodes are subjects and objects, and edges represent properties, directly mapping to RDF triples.
  • Subscription Language Model: Subscriptions are also represented as directed graph patterns. Crucially, G-ToPSS allows for variables within subscriptions, which can be either unconstrained or constrained by specific values or RDFS class taxonomies. This enables semantic filtering beyond simple keyword matching.
  • Ontology Support: The system leverages RDFS class taxonomies to provide semantic information about subjects and objects. This allows subscriptions to specify interests in broader categories (e.g., "any publication that is a descendant of the 'Publication' class") rather than just specific instances.
  • Graph Matching Algorithm: G-ToPSS integrates all subscriptions into a single graph (GM). When a publication (GP) arrives, it efficiently identifies subgraphs within GM that match parts of GP. This is achieved through a two-stage matching process: first, identifying potential matches for publication edges within the subscription graph, and second, evaluating constraints and bindings for variables. The paper highlights that their matching problem is distinct from standard subgraph isomorphism, focusing on identifying subgraphs of GP that are isomorphic to some subgraph of Gs.
  • Data Structure: A two-level hash table structure is used to efficiently store and query the integrated subscription graph (GM), exploiting commonalities between subscriptions.

Datasets

Not discussed in the paper. The authors mention using a synthetic workload for their experiments, generated based on specific parameters like publication and subscription size, number of subscriptions, and overlap.

Key Insights and Ideas

  • Graph-based filtering is key for complex metadata: Representing and filtering metadata as graphs, rather than simple attribute-value pairs, unlocks more sophisticated and semantically rich queries.
  • Ontologies and RDFS taxonomies are powerful for semantic filtering: Integrating class hierarchies allows for flexible and expressive subscriptions that go beyond exact matches, enabling users to express interests in broader categories.
  • Optimized graph matching is crucial for scalability: The paper's core contribution is an efficient graph matching algorithm and data structure that avoids the quadratic complexity of naive subgraph isomorphism by exploiting subscription overlaps and a more realistic assumption about variable usage.
  • Decoupling publishers and subscribers: The publish/subscribe model inherently decouples entities, which is vital for large-scale, dynamic systems like the internet. G-ToPSS enhances this by allowing semantic matching.

Key Results

  • Scalability: G-TOPSS demonstrates significant scalability. Experimental results show that memory usage grows linearly with the number of subscriptions, and matching time increases predictably.
  • Performance: G-TOPSS consistently outperforms the OPS (Ontology-Based Publish/Subscribe) system in matching time, especially as the number of subscriptions increases. For instance, at 20,000 subscriptions, G-TOPSS is orders of magnitude faster than OPS.
  • Efficiency: The paper's approach to graph matching, which assumes a low number of variables per subscription, is more efficient than traditional subgraph isomorphism algorithms that treat all nodes as potential variables.
  • Memory Usage: The memory footprint of G-TOPSS is manageable and scales linearly with the number of subscriptions, with a notable decrease in space usage when subscriptions have higher overlap.

Limitations and Future Work

  • Full RDF Language Features: The current implementation does not fully support all RDF language features like bags and sequences. The authors note that these would primarily add syntactic sugar and not affect the core matching rate.
  • Variables on Predicates: Extending the system to support variables on predicates is a straightforward future work, as the techniques for handling variables on subjects and objects can be applied.
  • Optimizations for Constraint Processing: The authors plan to implement optimizations for parallel constraint evaluation, especially for subscriptions with many overlapping constraints.
  • Natural Join for Overlapping Subscriptions: Further research is needed to examine ways of performing natural joins for overlapping subscriptions that leverage the overlap for efficiency.
  • More Powerful Inference Techniques: While RDFS taxonomies are supported, the paper suggests that more powerful inference techniques from Description Logics (like those used in OWL) could further augment constraint filtering without major changes to the matching engine.

Summary updated

BibTeX
@inproceedings{petrovic2005g,
  author = {Milenko Petrovic and Haifeng Liu and Hans-Arno Jacobsen},
  title = {{G-ToPSS: fast filtering of graph-based metadata}},
  booktitle = {The Web Conference},
  year = {2005},
  doi = {10.1145/1060745.1060824},
}
Figure