[Profile picture of Ruben Verborgh]

Ruben Verborgh

Opportunistic Linked Data Querying through Approximate Membership Metadata

Miel Vander Sande, Ruben Verborgh, Joachim Van Herwegen, Erik Mannens, and Rik Van de Walle

Between URI dereferencing and the SPARQL protocol lies a largely unexplored axis of possible interfaces to Linked Data, each of which comes with its own combination of trade-offs. One of these interfaces is Triple Pattern Fragments, which allows clients to execute SPARQL queries against low-cost servers, at the cost of higher bandwidth. To increase a client’s efficiency, we need to lower the number of requests, and one of the means for this is the incorporation of additional metadata in responses. We analyzed typical SPARQL query evaluations against Triple Pattern Fragments, and noted that a significant portion of requests consists of membership subqueries, which check the presence of a specific triple rather than a variable pattern. In this paper, we therefore study the impact of adding approximate membership functions, i.e., Bloom filters and Golomb-coded sets, as extra metadata. In addition to reducing http requests, such functions allow to achieve full result recall earlier when temporarily allowing lower precision. Half of the tested queries a WatDiv benchmark test set could be executed with up to a third fewer http requests with only marginally higher server cost. Query times, however, did not improve, likely due to slower generation time and transfer time. This indicates that approximate membership functions can partly improve the client-side query process with minimal impact on the server and its interface.

full text BibTeX other citation formats

Published in 2015 in Proceedings of the 14th International Semantic Web Conference.

Keywords:

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@inproceedings{vandersande_iswc_2015,
  author = {Vander Sande, Miel and Verborgh, Ruben and Van Herwegen, Joachim and Mannens, Erik and Van de Walle, Rik},
  title = {Opportunistic {Linked Data} Querying through Approximate Membership Metadata},
  booktitle = {Proceedings of the 14th International Semantic Web Conference},
  editor = {Arenas, Marcelo and Corcho, Oscar and Simperl, Elena and Strohmaier, Markus and d'Aquin, Mathieu and Srinivas, Kavitha and Groth, Paul and Dumontier, Michel and Heflin, Jeff and Thirunarayan, Krishnaprasad and Staab, Steffen},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  volume = 9366,
  pages = {92--110},
  year = 2015,
  month = oct,
  url = {https://linkeddatafragments.org/publications/iswc2015-amf.pdf},
}

Alternatively, pick a reference of your choice below:

ACM
Miel Vander Sande, Ruben Verborgh, Joachim Van Herwegen, Erik Mannens, and Rik Van de Walle. 2015. Opportunistic Linked Data Querying through Approximate Membership Metadata. In Proceedings of the 14th International Semantic Web Conference (Lecture Notes in Computer Science), Springer, 92–110.
APA
Vander Sande, M., Verborgh, R., Van Herwegen, J., Mannens, E., & Van de Walle, R. (2015). Opportunistic Linked Data Querying through Approximate Membership Metadata. In M. Arenas, O. Corcho, E. Simperl, M. Strohmaier, M. d’Aquin, K. Srinivas, P. Groth, M. Dumontier, J. Heflin, K. Thirunarayan, & S. Staab (Eds.), Proceedings of the 14th International Semantic Web Conference (Vol. 9366, pp. 92–110). Springer.
IEEE
M. Vander Sande, R. Verborgh, J. Van Herwegen, E. Mannens, and R. Van de Walle, “Opportunistic Linked Data Querying through Approximate Membership Metadata,” in Proceedings of the 14th International Semantic Web Conference, 2015, vol. 9366, pp. 92–110.
LNCS
Vander Sande, M., Verborgh, R., Van Herwegen, J., Mannens, E., Van de Walle, R.: Opportunistic Linked Data Querying through Approximate Membership Metadata. In: Arenas, M., Corcho, O., Simperl, E., Strohmaier, M., d’Aquin, M., Srinivas, K., Groth, P., Dumontier, M., Heflin, J., Thirunarayan, K., and Staab, S. (eds.) Proceedings of the 14th International Semantic Web Conference. pp. 92–110. Springer (2015).
MLA
Vander Sande, Miel, et al. “Opportunistic Linked Data Querying through Approximate Membership Metadata.” Proceedings of the 14th International Semantic Web Conference, edited by Marcelo Arenas et al., vol. 9366, Springer, 2015, pp. 92–110.

Discuss this article