The R3 Metric: Measuring Performance of Link Prioritization during Traversal-based Query Processing

The decentralization envisioned for the current centralized web requires querying approaches capable of accessing multiple small data sources while complying with legal constraints related to personal data, such as licenses and the GDPR. Link Traversal-based Query Processing (LTQP) is a querying approach designed for highly decentralized environments that satisfies these legal requirements. An important optimization avenue in LTQP is the order in which links are dereferenced, which involves prioritizing links to query-relevant documents. However, assessing and comparing the algorithmic performance of these systems is challenging due to various compounding factors during query execution. Therefore, researchers need an implementation-agnostic and deterministic metric that accurately measures the marginal effectiveness of link prioritization algorithms in LTQP engines. In this paper, we motivate the need for accurately measuring link prioritization performance, define and test such a metric, and outline the challenges and potential extensions of the proposed metric. Our findings show that the proposed metric highlights differences in link prioritization performance depending on the queried data fragmentation strategy. The proposed metric allows for evaluating link prioritization performance and enables easily assessing the effectiveness of future link prioritization algorithms.

@inproceedings{eschauzier_amw_rcubemetric_2024,
  author = {Eschauzier, Ruben and Taelman, Ruben and Verborgh, Ruben},
  title = {The R3 Metric: Measuring Performance of Link Prioritization during Traversal-based Query Processing},
  month = sep,
  booktitle = {Proceedings of the 16th Alberto Mendelzon International Workshop on Foundations of Data Management},
  year = {2024},
  url = {https://rubeneschauzier.github.io/traversal-metric-workshop-paper/}
}