[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

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},
  editor = {Mero\~no Pe\~nuela, Albert and Corcho, Oscar and Groth, Paul and Simperl, Elena and Tamma, Valentina and Nuzzolese, Andrea Giovanni and Poveda-Villal\'on, Maria and Sabou, Marta and Presutti, Valentina and Celino, Irene and Revenko, Artem and Raad, Joe and Sartini, Bruno and Lisena, Pasquale},
  year = 2024,
  month = may,
  pages = {228--233},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer},
  doi = {10.1007/978-3-031-78952-6_32},
  isbn = {978-3-031-78951-9},
}

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 (Lecture Notes in Computer Science), Springer, 228–233.
APA
Hanski, J., Taelman, R., & Verborgh, R. (2024). Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods. In A. Meroño Peñuela, O. Corcho, P. Groth, E. Simperl, V. Tamma, A. G. Nuzzolese, M. Poveda-Villalón, M. Sabou, V. Presutti, I. Celino, A. Revenko, J. Raad, B. Sartini, & P. Lisena (Eds.), Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos (pp. 228–233). Springer.
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, pp. 228–233.
LNCS
Hanski, J., Taelman, R., Verborgh, R.: Observations on Bloom Filters for Traversal-Based Query Execution over Solid Pods. In: Meroño Peñuela, A., Corcho, O., Groth, P., Simperl, E., Tamma, V., Nuzzolese, A.G., Poveda-Villalón, M., Sabou, M., Presutti, V., Celino, I., Revenko, A., Raad, J., Sartini, B., and Lisena, P. (eds.) Proceedings of the 21st Extended Semantic Web Conference: Posters and Demos. pp. 228–233. Springer (2024).
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, edited by Albert Meroño Peñuela et al., Springer, 2024, pp. 228–33.

Discuss this article