[Profile picture of Ruben Verborgh]

Ruben Verborgh

Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes

Bryan Elliott Tam, Joachim Van Herwegen, Pieter Colpaert, Ruben Verborgh, and Ruben Taelman

The centralization of web information raises legal and ethical concerns, particularly in social, healthcare, and education applications. Decentralized architectures offer a promising alternative by keeping data closer to its source, yet efficient query processing remains a significant challenge. Link Traversal Query Processing (LTQP) enables querying across decentralized networks, however, it often suffers from long execution times and high data transfer costs due to the large number of Hypertext Transfer Protocol (HTTP) requests involved. In many scenarios, queries are highly selective with respect to the data model objects distributed across the network. For example, in a social media application where users store heterogeneous data, a query may focus solely on the posts and comments created by users, without requiring any of their additional user information. We refer to such queries as data-model selective. We propose a shape-based pruning approach that relies on shape indexes and a query-shape subsumption algorithm to reduce the search space and, consequently, the number of HTTP requests for such queries. We formalize this approach as a link pruning mechanism for LTQP and evaluate its effectiveness on social media queries using the SolidBench benchmark across multiple evaluation metrics. Our results show that shape-based pruning substantially improves query execution time, first-result arrival time, diefficiency, and network usage for data-model selective queries, while having insignificant impact on non-selective data-model queries. These gains come at the cost of only a minor increase in the number of triples per shape-index instance. Moreover, our approach is resilient, retaining performance benefits even in networks where some data providers do not supply shape-index information. This work demonstrates that shape-based metadata can significantly optimize LTQP in decentralized knowledge graphs for an important class of queries. By exposing such metadata, data providers not only enhance data quality and interoperability but also improve the efficiency of traversal-based query processing.

full text BibTeX other citation formats

To be published in 2026 in Semantic Web Journal.

Keywords:

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@article{tam_swj_2026,
  author = {Tam, Bryan Elliott and Van Herwegen, Joachim and Colpaert, Pieter and Verborgh, Ruben and Taelman, Ruben},
  title = {Traveling with a~Map: Reducing the Search Space of Link Traversal Queries Using {RDF} Shapes},
  journal = {Semantic Web Journal},
  year = 2026,
  publisher = {IOS Press},
  url = {https://www.semantic-web-journal.net/system/files/swj4106.pdf},
}

Alternatively, pick a reference of your choice below:

ACM
Bryan Elliott Tam, Joachim Van Herwegen, Pieter Colpaert, Ruben Verborgh, and Ruben Taelman. 2026. Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes. Semantic Web Journal (2026). Accepted for publication.
APA
Tam, B. E., Van Herwegen, J., Colpaert, P., Verborgh, R., & Taelman, R. (2026). Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes. Semantic Web Journal. Accepted for publication.
IEEE
B. E. Tam, J. Van Herwegen, P. Colpaert, R. Verborgh, and R. Taelman, “Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes,” Semantic Web Journal, 2026. Accepted for publication.
LNCS
Tam, B.E., Van Herwegen, J., Colpaert, P., Verborgh, R., Taelman, R.: Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes. Semantic Web Journal. (2026). Accepted for publication.
MLA
Tam, Bryan Elliott, et al. “Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes.” Semantic Web Journal, IOS Press, 2026. Accepted for publication.