{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T16:09:04Z","timestamp":1787242144344,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031194320","type":"print"},{"value":"9783031194337","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T00:00:00Z","timestamp":1665878400000},"content-version":"vor","delay-in-days":288,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Time-efficient solutions for querying RDF knowledge graphs depend on indexing structures with low response times to answer SPARQL queries rapidly. Hypertries\u2014an indexing structure we recently developed for tensor-based triple stores\u2014have achieved significant runtime improvements over several mainstream storage solutions for RDF knowledge graphs. However, the space footprint of this novel data structure is still often larger than that of many mainstream solutions. In this work, we detail means to reduce the memory footprint of hypertries and thereby further speed up query processing in hypertrie-based RDF storage solutions. Our approach relies on three strategies: (1) the elimination of duplicate nodes via hashing, (2) the compression of non-branching paths, and (3) the storage of single-entry leaf nodes in their parent nodes. We evaluate these strategies by comparing them with baseline hypertries as well as popular triple stores such as Virtuoso, Fuseki, GraphDB, Blazegraph and gStore. We rely on four datasets\/benchmark generators in our evaluation: SWDF, DBpedia, WatDiv, and WikiData. Our results suggest that our modifications significantly reduce the memory footprint of hypertries by up to 70% while leading to a relative improvement of up to 39% with respect to average Queries per Second and up to 740% with respect to Query Mixes per Hour.<\/jats:p>","DOI":"10.1007\/978-3-031-19433-7_4","type":"book-chapter","created":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T02:20:33Z","timestamp":1665886833000},"page":"57-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Hashing the\u00a0Hypertrie: Space- and Time-Efficient Indexing for\u00a0SPARQL in\u00a0Tensors"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9617-1466","authenticated-orcid":false,"given":"Alexander","family":"Bigerl","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8803-6758","authenticated-orcid":false,"given":"Lixi","family":"Conrads","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9310-3804","authenticated-orcid":false,"given":"Charlotte","family":"Behning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9648-5417","authenticated-orcid":false,"given":"Muhammad","family":"Saleem","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7112-3516","authenticated-orcid":false,"given":"Axel-Cyrille","family":"Ngonga Ngomo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,16]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Ali, W., Saleem, M., Yao, B., Hogan, A., Ngomo, A.C.N.: A survey of rdf stores & sparql engines for querying knowledge graphs (2021)","DOI":"10.36227\/techrxiv.14376884.v1"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-319-11964-9_13","volume-title":"The Semantic Web \u2013 ISWC 2014","author":"G Alu\u00e7","year":"2014","unstructured":"Alu\u00e7, G., Hartig, O., \u00d6zsu, M.T., Daudjee, K.: Diversified stress testing of RDF data management systems. In: Mika, P., et al. (eds.) ISWC 2014. LNCS, vol. 8796, pp. 197\u2013212. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11964-9_13"},{"key":"4_CR3","doi-asserted-by":"publisher","unstructured":"Arroyuelo, D., Hogan, A., Navarro, G., Reutter, J.L., Rojas-Ledesma, J., Soto, A.: Worst-case optimal graph joins in almost no space, pp. 102\u2013114. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3448016.3457256","DOI":"10.1145\/3448016.3457256"},{"key":"4_CR4","doi-asserted-by":"publisher","unstructured":"Atre, M., Chaoji, V., Zaki, M.J., Hendler, J.A.: Matrix \u201cbit\u201d loaded: a scalable lightweight join query processor for RDF data. In: Proceedings of the 19th International Conference on World Wide Web, WWW 2010, pp. 41\u201350. Association for Computing Machinery, New York (2010). https:\/\/doi.org\/10.1145\/1772690.1772696","DOI":"10.1145\/1772690.1772696"},{"key":"4_CR5","doi-asserted-by":"publisher","unstructured":"Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, 25\u201328 October 2008, pp. 739\u2013748. IEEE Computer Society (2008). https:\/\/doi.org\/10.1109\/FOCS.2008.43","DOI":"10.1109\/FOCS.2008.43"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-030-62419-4_4","volume-title":"The Semantic Web \u2013 ISWC 2020","author":"A Bigerl","year":"2020","unstructured":"Bigerl, A., Conrads, F., Behning, C., Sherif, M.A., Saleem, M., Ngonga Ngomo, A.-C.: Tentris \u2013 a tensor-based triple store. In: Pan, J.Z., et al. (eds.) ISWC 2020. LNCS, vol. 12506, pp. 56\u201373. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-62419-4_4"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-319-68204-4_5","volume-title":"The Semantic Web \u2013 ISWC 2017","author":"F Conrads","year":"2017","unstructured":"Conrads, F., Lehmann, J., Saleem, M., Morsey, M., Ngonga Ngomo, A.-C.: Iguana: a generic framework for benchmarking the read-write performance of triple stores. In: d\u2019Amato, C., et al. (eds.) ISWC 2017. LNCS, vol. 10588, pp. 48\u201365. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68204-4_5"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1002\/andp.19163540702","volume":"354","author":"A Einstein","year":"1916","unstructured":"Einstein, A.: Die Grundlage der allgemeinen Relativit\u00e4tstheorie. Annalen der Physik 354, 769\u2013822 (1916). https:\/\/doi.org\/10.1002\/andp.19163540702","journal-title":"Annalen der Physik"},{"key":"4_CR9","unstructured":"Erling, O.: Virtuoso, a hybrid RDBMS\/graph column store. http:\/\/vos.openlinksw.com\/owiki\/wiki\/VOS\/VOSArticleVirtuosoAHybridRDBMSGraphColumnStore. Accessed 17 Mar 2018"},{"key":"4_CR10","unstructured":"Foundation, A.S.: Apache jena documentation - TDB architecture (2019). https:\/\/jena.apache.org\/documentation\/tdb\/architecture. Accessed 25 Apr 2019"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-030-30793-6_15","volume-title":"The Semantic Web \u2013 ISWC 2019","author":"A Hogan","year":"2019","unstructured":"Hogan, A., Riveros, C., Rojas, C., Soto, A.: A worst-case optimal join algorithm for SPARQL. In: Ghidini, C., et al. (eds.) ISWC 2019. LNCS, vol. 11778, pp. 258\u2013275. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30793-6_15"},{"key":"4_CR12","doi-asserted-by":"publisher","unstructured":"Leis, V., Kemper, A., Neumann, T.: The adaptive radix tree: artful indexing for main-memory databases. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 38\u201349 (2013). https:\/\/doi.org\/10.1109\/ICDE.2013.6544812","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Malhotra, J., Bakal, J.: A survey and comparative study of data deduplication techniques. In: 2015 International Conference on Pervasive Computing (ICPC), pp. 1\u20135 (2015). https:\/\/doi.org\/10.1109\/PERVASIVE.2015.7087116","DOI":"10.1109\/PERVASIVE.2015.7087116"},{"issue":"4","key":"4_CR14","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: Patricia-practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968). https:\/\/doi.org\/10.1145\/321479.321481","journal-title":"J. ACM"},{"key":"4_CR15","doi-asserted-by":"publisher","unstructured":"Navarro, G., Reutter, J.L., Rojas-Ledesma, J.: Optimal joins using compact data structures. In: 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark. LIPIcs, vol. 155, pp. 21:1\u201321:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.21, https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.21","DOI":"10.4230\/LIPIcs.ICDT.2020.21"},{"key":"4_CR16","doi-asserted-by":"publisher","unstructured":"Neumann, T., Weikum, G.: Rdf-3x: a risc-style engine for RDF. In: Proceedings VLDB Endowment, vol. 1, no. 1, pp. 647\u2013659 (2008). https:\/\/doi.org\/10.14778\/1453856.1453927","DOI":"10.14778\/1453856.1453927"},{"key":"4_CR17","unstructured":"Ontotext USA, I.: Storage - GraphDB free 8.9 documentation. http:\/\/graphdb.ontotext.com\/documentation\/free\/storage.html#storage-literal-index. Accessed 16 Apr 2019"},{"issue":"1\u20132","key":"4_CR18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01454201","volume":"54","author":"M Ricci","year":"1900","unstructured":"Ricci, M., Levi-Civita, T.: M\u00e9thodes de calcul diff\u00e9rentiel absolu et leurs applications. Mathematische Annalen 54(1\u20132), 125\u2013201 (1900)","journal-title":"Mathematische Annalen"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-319-25007-6_4","volume-title":"The Semantic Web - ISWC 2015","author":"M Saleem","year":"2015","unstructured":"Saleem, M., Mehmood, Q., Ngonga Ngomo, A.-C.: FEASIBLE: a feature-based SPARQL benchmark generation framework. In: Arenas, M., et al. (eds.) ISWC 2015. LNCS, vol. 9366, pp. 52\u201369. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-25007-6_4"},{"key":"4_CR20","unstructured":"SYSTAP, LLC: Bigdata Database Architecture - Blazegraph (2013). https:\/\/blazegraph.com\/docs\/bigdata_architecture_whitepaper.pdf. Accessed 29 Nov 2019"},{"key":"4_CR21","doi-asserted-by":"publisher","unstructured":"Veldhuizen, T.L.: Triejoin: a simple, worst-case optimal join algorithm. In: Proceedings of 17th International Conference on Database Theory (ICDT), Athens, Greece, 24\u201328 March 2014, pp. 96\u2013106. OpenProceedings.org (2014). https:\/\/doi.org\/10.5441\/002\/icdt.2014.13","DOI":"10.5441\/002\/icdt.2014.13"},{"issue":"4","key":"4_CR22","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s00778-013-0337-7","volume":"23","author":"L Zou","year":"2014","unstructured":"Zou, L., \u00d6zsu, M.T., Chen, L., Shen, X., Huang, R., Zhao, D.: Gstore: a graph-based sparql query engine. VLDB J. 23(4), 565\u2013590 (2014). https:\/\/doi.org\/10.1007\/s00778-013-0337-7","journal-title":"VLDB J."}],"container-title":["Lecture Notes in Computer Science","The Semantic Web \u2013 ISWC 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-19433-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T02:29:35Z","timestamp":1665887375000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-19433-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031194320","9783031194337"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-19433-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"16 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ISWC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Semantic Web Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 October 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 October 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"semweb2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iswc2022.semanticweb.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"239","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}