Querying RDF Data in Networks of Web Browsers

Arnaud Grall, Pascal Molli, Hala Skaf-MolliInternational Semantic Web Conference (P&D/Industry/BlueSky) 2018 · OpenReview

TL;DR

This paper introduces Snob, a novel decentralized engine for executing SPARQL queries over RDF data stored directly within web browsers. By leveraging a peer-to-peer network of browsers and a semantic overlay network, Snob aims to unlock the vast, underutilized data residing in everyday web browsing sessions for complex data querying.

What Problem Does This Paper Address?

Web browsers are ubiquitous and collect a wealth of user-generated data, including browsing history, location, and perceptions of the real world. This data, often in RDF format, represents a massive, yet largely untapped, data deposit. However, querying this data across a large-scale network of browsers presents significant challenges:

  • Source Selection: The sheer number of browsers makes it difficult to efficiently identify relevant data sources for a query.
  • Resource Constraints: Many browsers run on mobile devices, necessitating query execution that is mindful of bandwidth and battery consumption.
  • Network Limitations: The underlying WebRTC standard lacks robust routing, making communication with distant neighbors expensive. This highlights the importance of prioritizing direct neighbors as data sources.

Methods

Snob tackles these challenges with a four-pronged approach:

  1. Unstructured Network (RPS): Browsers are connected via a Random Peer Sampling (RPS) network. This means browsers periodically exchange their network views with neighbors, ensuring the network remains connected and resilient to churn. This approach is well-suited for dynamic environments like browser networks.
  2. Federated Query Execution: Each browser acts as a federated query processor, evaluating queries using only its direct neighbors as data sources. This approach inherently limits the number of messages exchanged per browser, conserving resources.
  3. Intermediate Result Sharing: To accelerate query execution, Snob promotes the sharing of intermediate results. This allows browsers to build upon partial results from others, increasing the probability of finding relevant data over time.
  4. Semantic Overlay Network (SON): A Semantic Overlay Network is built on top of the RPS network. This SON selects neighbors based on query similarity. A browser's "profile" (the set of triple patterns in its active queries) is used to rank potential neighbors. This clustering of similar queries aims to improve the efficiency of finding relevant data and intermediate results.

Datasets

The experiments were conducted using two real-world datasets:

  • Diseasome: A dataset related to diseases.
  • Linked Movies Database (LinkedMDB): A dataset containing information about movies.

The authors generated 100 queries per dataset using PATH and STAR shaped templates, instantiated with random values. They filtered out queries that caused the query engine to abort execution.

Key Insights and Ideas

  • Browsers as Data Sources: The paper highlights the significant potential of leveraging web browsers as a distributed data source for complex queries, moving beyond their traditional role as mere clients.
  • Balancing Decentralization and Efficiency: Snob demonstrates a clever balance between a fully decentralized, dynamic network (RPS) and a more targeted, semantic network (SON) to optimize query execution.
  • The Power of Semantic Proximity: The Semantic Overlay Network proves effective in grouping browsers with similar query interests, leading to faster and more complete query results, especially when the network is not saturated with queries.
  • Progressive Query Completion: The periodic shuffling in the RPS network ensures that queries can make progress over time, even if the federation of data sources changes.

Key Results

The experimental study compared three configurations: RPS only, RPS+SON, and a baseline. The key findings, visualized in Figure 2, indicate:

  • RPS+SON Outperforms RPS: The Semantic Overlay Network consistently provides better query completeness, especially when fewer queries are running simultaneously in the network.
  • Scalability with Network Size: The experiments were conducted with varying numbers of clients (49, 98, and 196), demonstrating the approach's scalability.
  • Proportional Replication Suffices: When every browser is actively running a query, the benefits of SON diminish, suggesting that proportional replication of intermediate results is sufficient in such saturated scenarios.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Optimizing Data Exchange: Further optimization is needed for data exchange when a data source is revisited, to reduce traffic.
  • Streaming Intermediate Results: Intermediate results could potentially be streamed over the semantic overlay network for even greater efficiency.
  • DHT for Query Discovery: Implementing a Distributed Hash Table (DHT) in browsers could accelerate the discovery of similar queries within the network.

Summary updated

BibTeX
@inproceedings{grall2018querying,
  author = {Arnaud Grall and Pascal Molli and Hala Skaf-Molli},
  title = {{Querying RDF Data in Networks of Web Browsers}},
  booktitle = {International Semantic Web Conference (P\&D/Industry/BlueSky)},
  year = {2018},
  url = {https://openreview.net/forum?id=Gmnd-R0LRrb},
}
Figure