[Profile picture of Ruben Verborgh]

Ruben Verborgh

Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments

Ruben Eschauzier, Ruben Taelman, and Ruben Verborgh

Decentralized environments distribute personal data across numerous small, independent data sources; a necessity driven by legal and socio-economic constraints that prevent the technologically more convenient central aggregation. Link Traversal-based Query Processing (LTQP) is a query technique that respects these constraints by iteratively discovering and accessing data sources while enabling fine-grained access control. Unfortunately, current LTQP implementations are slow due to limited prior knowledge of queried data and the high volume of HTTP requests required. Prioritizing data sources likely to lead to query-relevant data can improve query result arrival times. However, while link prioritization algorithms have been studied for Linked Open Data (LOD), their performance in structured decentralized environments remains untested. Evaluating this performance is essential to establish a baseline as a reference point for improving future implementations. We formally define the R3 metric to measure prioritization performance, extend it to continuous efficiency, and account for real-world scenarios. Furthermore, we provide modular and open-source implementations of the prioritization algorithms from the literature. Finally, using the R3 metric with existing metrics from the literature, we benchmark these link prioritization algorithms in a simulated Solid environment. In this paper, we report the benchmark results, provide a thorough analysis, and lessons learned for future work. We find that existing prioritization algorithms fail to improve performance in structured decentralized environments, with no non-oracle method outperforming the look-up order produced by a FIFO queue. We conclude that prioritization algorithms have little benefit in a structured decentralized environment, and recommend that research shift to pruning irrelevant links or improving the query plan.

BibTeX other citation formats

To be published in 2025 in Proceedings of the 24th International Semantic Web Conference.

Keywords:

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@inproceedings{eschauzier_iswc_2025,
  author = {Eschauzier, Ruben and Taelman, Ruben and Verborgh, Ruben},
  title = {Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments},
  booktitle = {Proceedings of the 24th International Semantic Web Conference},
  year = 2025,
  month = nov,
  series = {Lecture Notes in Computer Science},
  publisher = {Springer},
}

Alternatively, pick a reference of your choice below:

ACM
Ruben Eschauzier, Ruben Taelman, and Ruben Verborgh. 2025. Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments. In Proceedings of the 24th International Semantic Web Conference (Lecture Notes in Computer Science), Springer. Accepted for publication.
APA
Eschauzier, R., Taelman, R., & Verborgh, R. (2025, November). Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments. Proceedings of the 24th International Semantic Web Conference. Accepted for publication.
IEEE
R. Eschauzier, R. Taelman, and R. Verborgh, “Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments,” in Proceedings of the 24th International Semantic Web Conference, 2025. Accepted for publication.
LNCS
Eschauzier, R., Taelman, R., Verborgh, R.: Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments. In: Proceedings of the 24th International Semantic Web Conference. Springer (2025). Accepted for publication.
MLA
Eschauzier, Ruben, et al. “Revisiting Link Prioritization for Efficient Traversal in Structured Decentralized Environments.” Proceedings of the 24th International Semantic Web Conference, Springer, 2025. Accepted for publication.

Discuss this article