{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T10:22:04Z","timestamp":1777890124089,"version":"3.51.4"},"reference-count":68,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T00:00:00Z","timestamp":1702425600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SW"],"published-print":{"date-parts":[[2023,12,13]]},"abstract":"<jats:p>While the Web of Data in principle offers access to a wide range of interlinked data, the architecture of the Semantic Web today relies mostly on the data providers to maintain access to their data through SPARQL endpoints. Several studies, however, have shown that such endpoints often experience downtime, meaning that the data they maintain becomes inaccessible. While decentralized systems based on Peer-to-Peer (P2P) technology have previously shown to increase the availability of knowledge graphs, even when a large proportion of the nodes fail, processing queries in such a setup can be an expensive task since data necessary to answer a single query might be distributed over multiple nodes. In this paper, we therefore propose an approach to optimizing SPARQL queries over decentralized knowledge graphs, called Lothbrok. While there are potentially many aspects to consider when optimizing such queries, we focus on three aspects: cardinality estimation, locality awareness, and data fragmentation. We empirically show that Lothbrok is able to achieve significantly faster query processing performance compared to the state of the art when processing challenging queries as well as when the network is under high load.<\/jats:p>","DOI":"10.3233\/sw-233438","type":"journal-article","created":{"date-parts":[[2023,6,24]],"date-time":"2023-06-24T07:43:33Z","timestamp":1687592613000},"page":"1121-1165","source":"Crossref","is-referenced-by-count":5,"title":["Optimizing SPARQL queries over decentralized knowledge graphs"],"prefix":"10.1177","volume":"14","author":[{"given":"Christian","family":"Aebeloe","sequence":"first","affiliation":[{"name":"Department of Computer Science, Aalborg University, Selma Lagerl\u00f6fs Vej 300, DK-9220 Aalborg \u00d8, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriela","family":"Montoya","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aalborg University, Selma Lagerl\u00f6fs Vej 300, DK-9220 Aalborg \u00d8, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katja","family":"Hose","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Aalborg University, Selma Lagerl\u00f6fs Vej 300, DK-9220 Aalborg \u00d8, Denmark"},{"name":"Institute of Logic and Computation, TU Wien, Favoritenstra\u00dfe 9\u201311, 1040 Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/SW-233438_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25007-6_7"},{"key":"10.3233\/SW-233438_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_2"},{"key":"10.3233\/SW-233438_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-21348-0_1"},{"key":"10.3233\/SW-233438_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_1"},{"key":"10.3233\/SW-233438_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450037"},{"key":"10.3233\/SW-233438_ref7","unstructured":"A.\u00a0Ailamaki, D.J.\u00a0DeWitt, M.D.\u00a0Hill and D.A.\u00a0Wood, DBMSs on a modern processor: Where does time go?, in: VLDB\u201999, Proceedings of 25th International Conference on Very Large Data Bases, Edinburgh, Scotland, UK, September 7\u201310, 1999, M.P.\u00a0Atkinson, M.E.\u00a0Orlowska, P.\u00a0Valduriez, S.B.\u00a0Zdonik and M.L.\u00a0Brodie, eds, Morgan Kaufmann, 1999, pp.\u00a0266\u2013277, http:\/\/www.vldb.org\/conf\/1999\/P28.pdf."},{"key":"10.3233\/SW-233438_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3460210.3493577"},{"key":"10.3233\/SW-233438_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_13"},{"key":"10.3233\/SW-233438_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11964-9_13"},{"key":"10.3233\/SW-233438_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-15615-6_13"},{"key":"10.3233\/SW-233438_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41338-4_18"},{"key":"10.3233\/SW-233438_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449911"},{"key":"10.3233\/SW-233438_ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380177"},{"issue":"7","key":"10.3233\/SW-233438_ref15","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"10.3233\/SW-233438_ref16","unstructured":"D.\u00a0Brickley, R.V.\u00a0Guha and B.\u00a0McBride, in: RDF Schema 1.1, W3C Recommendation, Vol.\u00a025, 2014, pp.\u00a02004\u20132014."},{"key":"10.3233\/SW-233438_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988760"},{"key":"10.3233\/SW-233438_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/2814864.2814886"},{"key":"10.3233\/SW-233438_ref19","unstructured":"W.W.W.\u00a0Consortium et al., SPARQL 1.1 overview (2013)."},{"key":"10.3233\/SW-233438_ref20","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2002.1022239"},{"key":"10.3233\/SW-233438_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989340"},{"key":"10.3233\/SW-233438_ref22","unstructured":"M.\u00a0Dumontier, A.\u00a0Callahan, J.\u00a0Cruz-Toledo, P.\u00a0Ansell, V.\u00a0Emonet, F.\u00a0Belleau and A.\u00a0Droit, Bio2RDF release 3: A larger, more connected network of linked data for the life sciences, in: Proceedings of the ISWC 2014 Posters & Demonstrations Track a Track Within the 13th International Semantic Web Conference, ISWC 2014, Riva del Garda, Italy, October 21, 2014, M.\u00a0Horridge, M.\u00a0Rospocher and J.\u00a0van Ossenbruggen, eds, CEUR Workshop Proceedings, Vol.\u00a01272, CEUR-WS.org, 2014, pp.\u00a0401\u2013404, https:\/\/ceur-ws.org\/Vol-1272\/paper_121.pdf."},{"key":"10.3233\/SW-233438_ref23","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.websem.2013.01.002","article-title":"Binary RDF representation for publication and exchange (HDT)","volume":"19","author":"Fern\u00e1ndez","year":"2013","journal-title":"J. Web Semant."},{"key":"10.3233\/SW-233438_ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2577302"},{"key":"10.3233\/SW-233438_ref25","doi-asserted-by":"crossref","unstructured":"L.\u00a0Gal\u00e1rraga, K.A.\u00a0Jakobsen, K.\u00a0Hose and T.B.\u00a0Pedersen, Answering provenance-aware queries on RDF data cubes under memory budgets, in: ISWC, 2018, pp.\u00a0547\u2013565.","DOI":"10.1007\/978-3-030-00671-6_32"},{"key":"10.3233\/SW-233438_ref26","unstructured":"O.\u00a0G\u00f6rlitz and S.\u00a0Staab, SPLENDID: SPARQL endpoint federation exploiting VOID descriptions, in: Proceedings of the Second International Workshop on Consuming Linked Data (COLD2011), Bonn, Germany, October 23, 2011, O.\u00a0Hartig, A.\u00a0Harth and J.F.\u00a0Sequeda, eds, CEUR Workshop Proceedings, Vol.\u00a0782, CEUR-WS.org, 2011, https:\/\/ceur-ws.org\/Vol-782\/GoerlitzAndStaab_COLD2011.pdf."},{"key":"10.3233\/SW-233438_ref27","unstructured":"D.\u00a0Graux, G.\u00a0Sejdiu, H.\u00a0Jabeen, J.\u00a0Lehmann, D.\u00a0Sui, D.\u00a0Muhs and J.\u00a0Pfeffer, Profiting from kitties on Ethereum: Leveraging blockchain RDF with SANSA, in: Proceedings of the Posters and Demos Track of the 14th International Conference on Semantic Systems Co-Located with the 14th International Conference on Semantic Systems (SEMANTiCS 2018), Vienna, Austria, September 10\u201313, 2018, A.\u00a0Khalili and M.\u00a0Koutraki, eds, CEUR Workshop Proceedings, Vols\u00a02198, CEUR-WS.org, 2018, https:\/\/ceur-ws.org\/Vol-2198\/paper_124.pdf."},{"key":"10.3233\/SW-233438_ref28","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2014.40"},{"key":"10.3233\/SW-233438_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-62466-8_24"},{"key":"10.3233\/SW-233438_ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772733"},{"key":"10.3233\/SW-233438_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48472-3_48"},{"key":"10.3233\/SW-233438_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_6"},{"issue":"13","key":"10.3233\/SW-233438_ref35","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.14778\/3484224.3484235","article-title":"Computing how-provenance for SPARQL queries via query rewriting","volume":"14","author":"Hern\u00e1ndez","year":"2021","journal-title":"Proc. VLDB Endow."},{"key":"10.3233\/SW-233438_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18818-8_19"},{"key":"10.3233\/SW-233438_ref37","unstructured":"K.\u00a0Hose, Knowledge graph (R)evolution and the web of data, in: Proceedings of the 7th Workshop on Managing the Evolution and Preservation of the Data Web (MEPDaW) Co-Located with the 20th International Semantic Web Conference (ISWC 2021), Virtual Event, October 25th, 2021, CEUR Workshop Proceedings, Vol.\u00a03225, CEUR-WS.org, 2021, pp.\u00a01\u20137, https:\/\/ceur-ws.org\/Vol-3225\/paper1.pdf."},{"key":"10.3233\/SW-233438_ref38","doi-asserted-by":"publisher","DOI":"10.1145\/2237867.2237869"},{"key":"10.3233\/SW-233438_ref39","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2013.6547414"},{"key":"10.3233\/SW-233438_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18818-8_17"},{"key":"10.3233\/SW-233438_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46523-4_21"},{"key":"10.3233\/SW-233438_ref42","doi-asserted-by":"publisher","first-page":"31322","DOI":"10.1109\/ACCESS.2021.3056622","article-title":"Knowledge graph completeness: A systematic literature review","volume":"9","author":"Issa","year":"2021","journal-title":"IEEE Access"},{"key":"10.3233\/SW-233438_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32327-1_21"},{"issue":"4","key":"10.3233\/SW-233438_ref44","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/j.websem.2010.07.001","article-title":"Atlas: Storing, updating and querying RDF(s) data on top of DHTs","volume":"8","author":"Kaoudi","year":"2010","journal-title":"J. Web Semant."},{"key":"10.3233\/SW-233438_ref45","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.369054"},{"issue":"4","key":"10.3233\/SW-233438_ref46","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1145\/42404.42410","article-title":"Dynamic hash tables","volume":"31","author":"Larson","year":"1988","journal-title":"Commun. ACM"},{"key":"10.3233\/SW-233438_ref47","doi-asserted-by":"publisher","DOI":"10.1145\/2872518.2890529"},{"key":"10.3233\/SW-233438_ref48","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313652"},{"key":"10.3233\/SW-233438_ref49","unstructured":"G.\u00a0Montoya, C.\u00a0Aebeloe and K.\u00a0Hose, Towards efficient query processing over heterogeneous RDF interfaces, in: Proceedings of the 2nd Workshop on Decentralizing the Semantic Web Co-Located with the 17th International Semantic Web Conference, DeSemWeb@ISWC 2018, Monterey, California, USA, October 8, 2018, R.\u00a0Verborgh, T.\u00a0Kuhn and T.\u00a0Berners-Lee, eds, CEUR Workshop Proceedings, Vols\u00a02165, CEUR-WS.org, 2018, https:\/\/ceur-ws.org\/Vol-2165\/paper4.pdf."},{"key":"10.3233\/SW-233438_ref50","unstructured":"G.\u00a0Montoya, I.\u00a0Keles and K.\u00a0Hose, Analysis of the effect of query shapes on performance over LDF interfaces, in: Proceedings of the QuWeDa 2019: 3rd Workshop on Querying and Benchmarking the Web of Data Co-Located with 18th International Semantic Web Conference (ISWC 2019), Auckland, New Zealand, October 26\u201330, 2019, M.\u00a0Saleem, A.\u00a0Hogan, R.\u00a0Usbeck, A.N.\u00a0Ngomo and R.\u00a0Verborgh, eds, CEUR Workshop Proceedings, Vol.\u00a02496, CEUR-WS.org, 2019, pp.\u00a051\u201366, https:\/\/ceur-ws.org\/Vol-2496\/paper4.pdf."},{"key":"10.3233\/SW-233438_ref52","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68288-4_28"},{"key":"10.3233\/SW-233438_ref53","unstructured":"G.\u00a0Montoya, M.\u00a0Vidal and M.\u00a0Acosta, A heuristic-based approach for planning federated SPARQL queries, in: Proceedings of the Third International Workshop on Consuming Linked Data, COLD 2012, Boston, MA, USA, November 12, 2012, J.F.\u00a0Sequeda, A.\u00a0Harth and O.\u00a0Hartig, eds, CEUR Workshop Proceedings, Vol.\u00a0905, CEUR-WS.org, 2012, https:\/\/ceur-ws.org\/Vol-905\/MontoyaEtAl_COLD2012.pdf."},{"key":"10.3233\/SW-233438_ref55","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767868"},{"key":"10.3233\/SW-233438_ref56","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s10619-010-7067-2","article-title":"Cardinality estimation and dynamic length adaptation for bloom filters","volume":"28","author":"Papapetrou","year":"2010","journal-title":"Distributed Parallel Databases"},{"key":"10.3233\/SW-233438_ref57","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389702"},{"issue":"3","key":"10.3233\/SW-233438_ref58","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/1567274.1567278","article-title":"Semantics and complexity of SPARQL","volume":"34","author":"P\u00e9rez","year":"2009","journal-title":"ACM Trans. Database Syst."},{"key":"10.3233\/SW-233438_ref59","doi-asserted-by":"publisher","DOI":"10.5441\/002\/edbt.2021.59"},{"key":"10.3233\/SW-233438_ref60","doi-asserted-by":"publisher","DOI":"10.1145\/3487553.3524253"},{"key":"10.3233\/SW-233438_ref61","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2017.12.005"},{"key":"10.3233\/SW-233438_ref62","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2018.09.016"},{"key":"10.3233\/SW-233438_ref63","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313556"},{"key":"10.3233\/SW-233438_ref64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25073-6_38"},{"key":"10.3233\/SW-233438_ref65","doi-asserted-by":"publisher","DOI":"10.1145\/3184558.3191554"},{"key":"10.3233\/SW-233438_ref66","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s11280-010-0107-z","article-title":"Comparing data summaries for processing live queries over linked data","volume":"14","author":"Umbrich","year":"2011","journal-title":"World Wide Web"},{"issue":"6","key":"10.3233\/SW-233438_ref67","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.3233\/SW-170254","article-title":"SPARQLES: Monitoring public SPARQL endpoints","volume":"8","author":"Vandenbussche","year":"2017","journal-title":"Semantic Web"},{"key":"10.3233\/SW-233438_ref68","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1016\/j.websem.2016.03.003","article-title":"Triple pattern fragments: A low-cost knowledge graph interface for the web","volume":"37\u201338","author":"Verborgh","year":"2016","journal-title":"J. Web Semant."},{"key":"10.3233\/SW-233438_ref69","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13486-9_16"},{"issue":"10","key":"10.3233\/SW-233438_ref70","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629489","article-title":"Wikidata: A free collaborative knowledgebase","volume":"57","author":"Vrandecic","year":"2014","journal-title":"Commun. ACM"},{"key":"10.3233\/SW-233438_ref71","doi-asserted-by":"publisher","DOI":"10.1109\/tkde.2022.3150080"},{"issue":"1","key":"10.3233\/SW-233438_ref72","doi-asserted-by":"publisher","first-page":"63","DOI":"10.3233\/SW-150175","article-title":"Quality assessment for linked data: A survey","volume":"7","author":"Zaveri","year":"2016","journal-title":"Semantic Web"},{"issue":"4","key":"10.3233\/SW-233438_ref73","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1504\/IJWGS.2018.095647","article-title":"Blockchain challenges and opportunities: A survey","volume":"14","author":"Zheng","year":"2018","journal-title":"Int. J. Web Grid Serv."}],"container-title":["Semantic Web"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/SW-233438","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:27:06Z","timestamp":1777613226000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/SW-233438"}},"subtitle":[],"editor":[{"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Chile"}],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,12,13]]},"references-count":68,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.3233\/sw-233438","relation":{},"ISSN":["2210-4968","1570-0844"],"issn-type":[{"value":"2210-4968","type":"electronic"},{"value":"1570-0844","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12,13]]}}}