[Profile picture of Ruben Verborgh]

Ruben Verborgh

How Does the Link Queue Evolve during Traversal-Based Query Processing?

Ruben Eschauzier, Ruben Taelman, and Ruben Verborgh

Link Traversal-based Query Processing (LTQP) is an integrated querying approach that allows the query engine to start with zero knowledge of the data to query and discover data sources on the fly. The query engine starts with some seed documents and dynamically discovers new data sources by dereferencing hyperlinks in previously ingested data. Given the dynamic nature of source discovery, query processing tends to be relatively slow. Optimization techniques exist, such as exploiting existing structural information, but they depend on a deep understanding of the link queue during LTQP. To this end, we investigate the evolution of the types of link sources in the link queue and introduce metrics that describe key link queue characteristics. This paper analyses the link queue to guide future work on LTQP query optimization approaches that exploit structural information within a Solid environment. We find that queries exhibit two different execution patterns, one where the link queue is primarily empty and the other where the link queue fills faster than the engine can process. Our results show that the link queue is not functioning optimally and that our current approach to link discovery is not sufficiently selective.

full text BibTeX other citation formats

Published in 2023 in Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs.

Keywords:

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@inproceedings{eschauzier_quweda_2023,
  author = {Eschauzier, Ruben and Taelman, Ruben and Verborgh, Ruben},
  title = {How Does the Link Queue Evolve during Traversal-Based Query Processing?},
  booktitle = {Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs},
  editor = {Saleem, Muhammad and Ngonga Ngomo, Axel-Cyrille},
  year = 2023,
  month = oct,
  series = {CEUR Workshop Proceedings},
  url = {https://rubeneschauzier.github.io/QuWeDa2023-Link-Queue-Analysis-Camera-Ready/QuWeDa_2023_Link_Queue_Analysis_Final.pdf},
}

Alternatively, pick a reference of your choice below:

ACM
Ruben Eschauzier, Ruben Taelman, and Ruben Verborgh. 2023. How Does the Link Queue Evolve during Traversal-Based Query Processing? In Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs (CEUR Workshop Proceedings).
APA
Eschauzier, R., Taelman, R., & Verborgh, R. (2023). How Does the Link Queue Evolve during Traversal-Based Query Processing? In M. Saleem & A.-C. Ngonga Ngomo (Eds.), Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs.
IEEE
R. Eschauzier, R. Taelman, and R. Verborgh, “How Does the Link Queue Evolve during Traversal-Based Query Processing?,” in Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs, 2023.
LNCS
Eschauzier, R., Taelman, R., Verborgh, R.: How Does the Link Queue Evolve during Traversal-Based Query Processing? In: Saleem, M. and Ngonga Ngomo, A.-C. (eds.) Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs (2023).
MLA
Eschauzier, Ruben, et al. “How Does the Link Queue Evolve during Traversal-Based Query Processing?” Proceedings of the 7th Workshop on Storing, Querying and Benchmarking Knowledge Graphs, edited by Muhammad Saleem and Axel-Cyrille Ngonga Ngomo, 2023.

Discuss this article