[Profile picture of Ruben Verborgh]

Ruben Verborgh

Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods

Jonni Hanski, Ruben Taelman, and Ruben Verborgh

Traversal-based query execution enables the resolving of queries over Linked Data documents, using a follow-your-nose approach to locating query-relevant data by following series of links through documents. This traversal, however, incurs an unavoidable overhead in the form of data access costs. Through only following links known to be relevant for answering a given query, this overhead could be minimized. Prior work exists in the form of reachability conditions to determine the links to dereference, however this does not take into consideration the contents behind a given link. Within this work, we have explored the possibility of using Bloom filters to prune query-irrelevant links based on the triple patterns contained within a given query, when performing traversal-based query execution over Solid pods containing simulated social network data as an example use case. Our discoveries show that, with relatively uniform data across an entire benchmark dataset, this approach fails to effectively filter links, especially when the queries contain triple patterns with low selectivity. Thus, future work should consider the query plan beyond individual patterns, or the structure of the data beyond individual triples, to allow for more effective pruning of links.

BibTeX other citation formats

To be published in 2024 in Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos.

Keywords:

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@inproceedings{hanski_eswc_2024,
  author = {Hanski, Jonni and Taelman, Ruben and Verborgh, Ruben},
  title = {Observations on {Bloom} Filters for Traversal-Based Query Execution over {Solid} Pods},
  booktitle = {Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos},
  year = 2024,
  month = jun,
}

Alternatively, pick a reference of your choice below:

ACM
Jonni Hanski, Ruben Taelman, and Ruben Verborgh. 2024. Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods. In Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos. Accepted for publication.
APA
Hanski, J., Taelman, R., & Verborgh, R. (2024, June). Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods. Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos. Accepted for publication.
IEEE
J. Hanski, R. Taelman, and R. Verborgh, “Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods,” in Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos, 2024. Accepted for publication.
LNCS
Hanski, J., Taelman, R., Verborgh, R.: Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods. In: Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos (2024). Accepted for publication.
MLA
Hanski, Jonni, et al. “Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods.” Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos, 2024. Accepted for publication.

Discuss this article