Metraipolis › archive › dc_50ed86e29f73

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.11701
License (as archived)
CC0-1.0
Archived
2026-10-09T06:35:35.479Z
SHA-256 of the archived text
092fa5748658a358f2a6e3f86b59cc9944f6115c43b0d1d03123eebe06fc155d
Stable URL of this page
https://metraipolis.com/documento/dc_50ed86e29f73

How to cite

Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes — arXiv:2610.11701 — arXiv (en), https://arxiv.org/abs/2610.11701 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_50ed86e29f73 (Metraipolis archive dc_50ed86e29f73, sha256 092fa5748658a358f2a6e3f86b59cc9944f6115c43b0d1d03123eebe06fc155d)
BibTeX
@misc{dc50ed86e29f73,
  title = {Traveling with a Map: Reducing the Search Space of Link Traversal Queries Using RDF Shapes — arXiv:2610.11701},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.11701},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_50ed86e29f73; sha256 092fa5748658a358f2a6e3f86b59cc9944f6115c43b0d1d03123eebe06fc155d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11701. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 but often suffers from long execution times and high data transfer costs due to the large number of HTTP requests involved. Many 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 target only users' posts and comments, ignoring their other 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 thus the number of HTTP requests. We formalize this approach as a link pruning mechanism for LTQP and evaluate it on social media queries from the SolidBench benchmark across multiple 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 a negligible impact on non-selective data-model queries. These gains cost only a minor increase in triples per shape-index instance. Our approach is also resilient, retaining its benefits even when some data providers do not supply shape indexes. 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.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.DB, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2610.11701 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:55:36.506Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).