{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T18:47:28Z","timestamp":1762109248073,"version":"build-2065373602"},"reference-count":82,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T00:00:00Z","timestamp":1732579200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T00:00:00Z","timestamp":1732579200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Millennium Science Initiative Program, Chile","award":["ICN17-002"],"award-info":[{"award-number":["ICN17-002"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s00778-024-00885-6","type":"journal-article","created":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T11:16:03Z","timestamp":1732619763000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Evaluating regular path queries on compressed adjacency matrices"],"prefix":"10.1007","volume":"34","author":[{"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[]},{"given":"Adri\u00e1n","family":"G\u00f3mez-Brand\u00f3n","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,26]]},"reference":[{"issue":"7","key":"885_CR1","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1109\/32.42731","volume":"14","author":"R Agrawal","year":"1988","unstructured":"Agrawal, R.: Alpha: An extension of relational algebra to express a class of recursive queries. IEEE Trans. Softw. Eng. 14(7), 879\u2013885 (1988)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"885_CR2","doi-asserted-by":"crossref","unstructured":"Aho, A.V., Ullman, J.D.: The universality of data retrieval languages. In: Proc. 6th POPL, pp 110\u2013120 (1979)","DOI":"10.1145\/567752.567763"},{"key":"885_CR3","volume-title":"Data Structures and Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: Data Structures and Algorithms. Addison-Wesley (1974)"},{"key":"885_CR4","doi-asserted-by":"crossref","unstructured":"Aimonier-Davat, J., Skaf-Molli, H., Molli, P., Dang, M., N\u00e9delec, B.: Join ordering of SPARQL property path queries. In: Proc. 20th ESWC, pp 38\u201354 (2023)","DOI":"10.1007\/978-3-031-33455-9_3"},{"issue":"2","key":"885_CR5","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s10115-014-0770-y","volume":"44","author":"S \u00c1lvarez-Garc\u00eda","year":"2015","unstructured":"\u00c1lvarez-Garc\u00eda, S., Brisaboa, N.R., Fern\u00e1ndez, J., Mart\u00ednez-Prieto, M., Navarro, G.: Compressed vertical partitioning for efficient RDF management. Knowl. Inf. Syst. 44(2), 439\u2013474 (2015)","journal-title":"Knowl. Inf. Syst."},{"key":"885_CR6","doi-asserted-by":"crossref","unstructured":"Amossen RR, Pagh R (2009) Faster join-projects and sparse matrix multiplications. In: Proc. 12th ICDT, pp 121\u2013126","DOI":"10.1145\/1514894.1514909"},{"key":"885_CR7","doi-asserted-by":"crossref","unstructured":"Angles, R., Arenas, M., Barcel\u00f3, P., Hogan, A., Reutter, J.L., Vrgoc, D.: Foundations of modern query languages for graph databases. ACM Comput. Surv. 50(5):68:1\u201368:40 (2017)","DOI":"10.1145\/3104031"},{"key":"885_CR8","doi-asserted-by":"crossref","unstructured":"Angles, R., Arenas, M., Barcel\u00f3, P., Boncz, P.A., Fletcher, G.H.L., Guti\u00e9rrez. C., Lindaaker, T., Paradies, M., Plantikow, S., Sequeda, J.F., van Rest, O., Voigt, H.: G-CORE: A core for future graph query languages. In: Proc. SIGMOD, pp 1421\u20131432 (2018)","DOI":"10.1145\/3183713.3190654"},{"issue":"3","key":"885_CR9","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.3390\/a2031031","volume":"2","author":"A Apostolico","year":"2009","unstructured":"Apostolico, A., Drovandi, G.: Graph compression by BFS. Algorithms 2(3), 1031\u20131044 (2009)","journal-title":"Algorithms"},{"key":"885_CR10","unstructured":"Arlazarov, V., Dinic, E., Kronrod, M., Farad\u017eev, I.: On economical construction of the transitive closure of a directed graph. Dokl Akad Nauk SSSR 194(11):487\u2013488, in Russian. English translation in Soviet Math. Dokl. 11:5, 1209\u20131210 (1970)"},{"key":"885_CR11","unstructured":"Arroyuelo, D., Castillo, J.P.: Trie-compressed adaptive set intersection. In: Proc. 34th CPM, pp 1:1\u20131:19 (2023)"},{"key":"885_CR12","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., de\u00a0Bernardo, G., Gagie, T., Navarro, G.: Faster dynamic compressed $$d$$-ary relations. In: Proc. 26th SPIRE, LNCS 11811, pp 419\u2013433 (2019)","DOI":"10.1007\/978-3-030-32686-9_30"},{"key":"885_CR13","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., Navarro, G., Reutter, J.L., Rojas-Ledesma, J.: Optimal joins using compressed quadtrees. ACM Trans. Database Syst. 47(2), article 8 (2022)","DOI":"10.1145\/3514231"},{"key":"885_CR14","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., G\u00f3mez-Brand\u00f3n, A., Navarro, G.: Evaluating regular path queries on compressed adjacency matrices. In: Proc. 30th SPIRE, pp 35\u201348 (2023)","DOI":"10.1007\/978-3-031-43980-3_4"},{"key":"885_CR15","doi-asserted-by":"crossref","unstructured":"Arroyuelo, D., G\u00f3mez-Brand\u00f3n, A., Hogan, A., Navarro, G., Reutter, J.L., Rojas-Ledesma, J., Soto, A.: (2024) The Ring: Worst-case optimal joins in graph databases using (almost) no extra space. ACM Trans. Database Syst. 49(2), article 5","DOI":"10.1145\/3644824"},{"key":"885_CR16","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00778-023-00811-2","volume":"33","author":"D Arroyuelo","year":"2024","unstructured":"Arroyuelo, D., G\u00f3mez-Brand\u00f3n, A., Hogan, A., Navarro, G., Rojas-Ledesma, J.: Optimizing RPQs over a compact graph representation. Very Large Databases J. 33, 349\u2013374 (2024)","journal-title":"Very Large Databases J."},{"key":"885_CR17","unstructured":"Arroyuelo, D., G\u00f3mez-Brand\u00f3n, A., Navarro, G.: (2024) Sparse Boolean matrix algebra. https:\/\/github.com\/adriangbrandon\/rpq-matrix"},{"key":"885_CR18","doi-asserted-by":"crossref","unstructured":"Azimov, R., Epelbaum, I., Grigorev, S.V.: (2021) Context-free path querying with all-path semantics by matrix multiplication. In: Proc. 4th GRADES-NDA, pp 4:1\u20134:7","DOI":"10.1145\/3461837.3464513"},{"key":"885_CR19","doi-asserted-by":"crossref","unstructured":"Barbay, J., Kenyon, C.: (2008) Alternation and redundancy analysis of the intersection problem. ACM Trans. Algorithms 4(1), 4:1\u20134:18","DOI":"10.1145\/1328911.1328915"},{"key":"885_CR20","unstructured":"Barcel\u00f3, P.: Querying graph databases. In: Proc. 32nd PODS, pp 175\u2013188 (2013)"},{"key":"885_CR21","doi-asserted-by":"crossref","unstructured":"de\u00a0Bernardo, G., \u00c1lvarez-Garc\u00eda, S., Brisaboa, N.R., Navarro, G., Pedreira, O.: Compact querieable representations of raster data. In: Proc. 20th SPIRE, pp 96\u2013108 (2013)","DOI":"10.1007\/978-3-319-02432-5_14"},{"key":"885_CR22","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.jcss.2022.09.001","volume":"131","author":"G de Bernardo","year":"2023","unstructured":"de Bernardo, G., Gagie, T., Ladra, S., Navarro, G., Seco, D.: Faster compressed quadtrees. J. Comput. Syst. Sci. 131, 86\u2013104 (2023)","journal-title":"J. Comput. Syst. Sci."},{"key":"885_CR23","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., Santini, M., Vigna, S.: Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In: Proc. 20th WWW, pp 587\u2013596 (2011)","DOI":"10.1145\/1963405.1963488"},{"key":"885_CR24","doi-asserted-by":"crossref","unstructured":"Bonifati, A., Martens, W., Timm, T.: Navigating the maze of Wikidata query logs. In: Proc. WWW, pp 127\u2013138 (2019)","DOI":"10.1145\/3308558.3313472"},{"key":"885_CR25","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s00778-019-00558-9","volume":"2\u20133","author":"A Bonifati","year":"2020","unstructured":"Bonifati, A., Martens, W., Timm, T.: An analytical study of large SPARQL query logs. VLDB J. 2\u20133, 655\u2013679 (2020)","journal-title":"VLDB J."},{"key":"885_CR26","doi-asserted-by":"publisher","first-page":"5643","DOI":"10.1007\/s11227-022-04890-w","volume":"79","author":"N Brisaboa","year":"2023","unstructured":"Brisaboa, N., Cerdeira-Pena, A., de Bernardo, G., Fari\u00f1a, A., Navarro, G.: Space\/time-efficient rdf stores based on circular suffix sorting. J. Supercomput. 79, 5643\u20135683 (2023)","journal-title":"J. Supercomput."},{"issue":"1","key":"885_CR27","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1016\/j.is.2013.08.003","volume":"39","author":"NR Brisaboa","year":"2014","unstructured":"Brisaboa, N.R., Ladra, S., Navarro, G.: Compact representation of Web graphs with extended functionality. Inf. Syst. 39(1), 152\u2013174 (2014)","journal-title":"Inf. Syst."},{"key":"885_CR28","unstructured":"Clark, D.R.: Compact PAT trees. PhD thesis, University of Waterloo, Canada (1996)"},{"key":"885_CR29","doi-asserted-by":"crossref","unstructured":"Coimbra, M.E., Hrotk\u00f3, J., Francisco, A.P., Russo, L.M.S., de\u00a0Bernardo, G., Ladra, S., Navarro, G.: (2022) A practical succinct dynamic graph representation. Inf. Comput. 285B:article 104,862","DOI":"10.1016\/j.ic.2021.104862"},{"issue":"3","key":"885_CR30","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"885_CR31","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)","edition":"3"},{"key":"885_CR32","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: Proc. 11th SODA, pp 743\u2013752 (2000)"},{"key":"885_CR33","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Xu, Y., Wu, M., Lee, V.E.: Aggregation support for modern graph analytics in TigerGraph. In: Proc. SIGMOD, pp 377\u2013392 (2020)","DOI":"10.1145\/3318464.3386144"},{"key":"885_CR34","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Francis, N., Green, A., Hare, K., Li, B., Libkin, L., Lindaaker, T., Marsault, V., Martens, W., Michels, J., Murlak, F., Plantikow, S., Selmer, P., van Rest, O., Voigt, H., Vrgo\u010d, D., Wu, M., Zemke, F.: Graph pattern matching in GQL and SQL\/PGQ. In: Proc. SIGMOD, pp 2246\u20132258 (2022)","DOI":"10.1145\/3514221.3526057"},{"key":"885_CR35","volume-title":"A Discipline of Programming","author":"E Dijkstra","year":"1976","unstructured":"Dijkstra, E.: A Discipline of Programming. Prentice Hall (1976). (chapter 25)"},{"key":"885_CR36","unstructured":"Eaton, J.W., Bateman, D., Hauberg, S., Wehbring, R.: GNU Octave version 6.3.0 manual: a high-level interactive language for numerical computations (2021)"},{"issue":"524","key":"885_CR37","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/3318221","volume":"62","author":"A Elgohary","year":"2019","unstructured":"Elgohary, A., Boehm, M., Haas, P.J., Reiss, F.R., Reinwald, B.: Compressed linear algebra for declarative large-scale machine learning. Commun. ACM 62(524), 83\u201391 (2019)","journal-title":"Commun. ACM"},{"key":"885_CR38","doi-asserted-by":"crossref","unstructured":"Erling, O., Mikhailov, I.: RDF support in the Virtuoso DBMS. In: Networked Knowledge \u2013 Networked Media, Springer, pp 7\u201324 (2009)","DOI":"10.1007\/978-3-642-02184-8_2"},{"key":"885_CR39","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1038\/s41586-022-05172-4","volume":"610","author":"A Fawzi","year":"2022","unstructured":"Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredes, B., Barekatain, M., Novikov, A., Ruiz, F.J.R., Schrittwieser, J., Swirszcz, G., Silver, D., Hassabis, D., Kohli, P.: Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47\u201353 (2022)","journal-title":"Nature"},{"key":"885_CR40","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Meyer, A.R.: Boolean matrix multiplication and transitive closure. In: Proc. 12th SWAT, pp 129\u2013131 (1971)","DOI":"10.1109\/SWAT.1971.4"},{"key":"885_CR41","doi-asserted-by":"crossref","unstructured":"Francis, N., Green, A., Guagliardo, P., Libkin, L., Lindaaker, T., Marsault, V., Plantikow, S., Rydberg, M., Selmer, P., Taylor, A.: Cypher: An Evolving Query Language for Property Graphs. In: Proc. SIGMOD, pp 1433\u20131445 (2018)","DOI":"10.1145\/3183713.3190657"},{"issue":"3","key":"885_CR42","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"885_CR43","first-page":"1252","volume":"11","author":"ME Furman","year":"1970","unstructured":"Furman, M.E.: Application of a method of fast multiplication of matrices in the problem of Finding the transitive closure of a graph. Soviet Math. Doklady 11(5), 1252 (1970)","journal-title":"Soviet Math. Doklady"},{"issue":"2","key":"885_CR44","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10115-013-0648-4","volume":"40","author":"C Hern\u00e1ndez","year":"2014","unstructured":"Hern\u00e1ndez, C., Navarro, G.: Compressed representations for web and social graphs. Knowl. Inf. Syst. 40(2), 279\u2013313 (2014)","journal-title":"Knowl. Inf. Syst."},{"issue":"2","key":"885_CR45","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1080\/00031305.1998.10480559","volume":"52","author":"JL Hintze","year":"1998","unstructured":"Hintze, J.L., Nelson, R.D.: Violin plots: A box plot-density trace synergism. Am. Stat. 52(2), 181\u2013184 (1998)","journal-title":"Am. Stat."},{"key":"885_CR46","doi-asserted-by":"crossref","unstructured":"Hogan, A., Riveros, C., Rojas, C., Soto, A.: A worst-case optimal join algorithm for SPARQL. In: Proc. 18th ISWC, pp 258\u2013275 (2019)","DOI":"10.1007\/978-3-030-30793-6_15"},{"issue":"9","key":"885_CR47","first-page":"1098","volume":"40","author":"DA Huffman","year":"1952","unstructured":"Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc Inst. Electr. Radio Eng. 40(9), 1098\u20131101 (1952)","journal-title":"Proc Inst. Electr. Radio Eng."},{"issue":"4","key":"885_CR48","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"885_CR49","doi-asserted-by":"crossref","unstructured":"Jakobsson, H.: Mixed-approach algorithms for transitive closure (extended abstract). In: Proc. 10th PODS, pp 199\u2013205 (1991)","DOI":"10.1145\/113413.113431"},{"issue":"1","key":"885_CR50","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1002\/rsa.3240010106","volume":"1","author":"RM Karp","year":"1990","unstructured":"Karp, R.M.: The transitive closure of a random digraph. Random Struct. Algorithms 1(1), 73\u201394 (1990)","journal-title":"Random Struct. Algorithms"},{"key":"885_CR51","unstructured":"Knuth, D.E.: (2009) The Art of Computer Programming, volume 4: Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional"},{"key":"885_CR52","doi-asserted-by":"crossref","unstructured":"Losemann, K., Martens, W.: The complexity of evaluating path expressions in SPARQL. In: Proc.\u00a031st PODS, pp 101\u2013112 (2012)","DOI":"10.1145\/2213556.2213573"},{"key":"885_CR53","doi-asserted-by":"crossref","unstructured":"Malyshev, S., Kr\u00f6tzsch, M., Gonz\u00e1lez, L., Gonsior, J., Bielefeldt, A.: Getting the most out of Wikidata: semantic technology usage in Wikipedia\u2019s knowledge graph. In: Proc. ISWC, pp 376\u2013394 (2018)","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"885_CR54","unstructured":"Manola, F., Miller, E.: RDF Primer. W3C Recommendation, http:\/\/www.w3.org\/TR\/rdf-primer\/ (2004)"},{"issue":"7","key":"885_CR55","doi-asserted-by":"publisher","first-page":"1790","DOI":"10.14778\/3587136.3587151","volume":"16","author":"W Martens","year":"2023","unstructured":"Martens, W., Niewerth, M., Popp, T., Rojas, C., Vansummeren, S., Vrgoc, D.: Representing paths in graph database pattern matching. Proc VLDB Endowment 16(7), 1790\u20131803 (2023)","journal-title":"Proc VLDB Endowment"},{"issue":"6","key":"885_CR56","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235\u20131258 (1995)","journal-title":"SIAM J. Comput."},{"key":"885_CR57","volume-title":"A computer oriented geodetic data base; and a new technique in file sequencing","author":"GM Morton","year":"1966","unstructured":"Morton, G.M.: A computer oriented geodetic data base; and a new technique in file sequencing. Tech. rep, IBM Ltd (1966)"},{"issue":"2","key":"885_CR58","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"JI Munro","year":"1971","unstructured":"Munro, J.I.: Efficient determination of the transitive closure of a directed graph. Inf. Process. Lett. 1(2), 56\u201358 (1971)","journal-title":"Inf. Process. Lett."},{"key":"885_CR59","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: Proc. 16th FSTTCS, pp 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"885_CR60","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures - A practical approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures - A practical approach. Cambridge University Press (2016)"},{"issue":"4","key":"885_CR61","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0190(94)90128-7","volume":"52","author":"E Nuutila","year":"1994","unstructured":"Nuutila, E.: An efficient transitive closure algorithm for cyclic digraphs. Inf. Process. Lett. 52(4), 207\u2013213 (1994)","journal-title":"Inf. Process. Lett."},{"key":"885_CR62","unstructured":"Nuutila, E.: Efficient transitive closure computation in large digraphs. PhD thesis, Finnish Academy of Technology, Finland (1995)"},{"key":"885_CR63","doi-asserted-by":"crossref","unstructured":"Penn, G.: Efficient transitive closure of sparse matrices over closed semirings. Theoret. Comput. Sci. 354(1), 72\u201381 (2006)","DOI":"10.1016\/j.tcs.2005.11.008"},{"key":"885_CR64","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01940892","volume":"10","author":"PW Purdom","year":"1970","unstructured":"Purdom, P.W.: A transitive closure algorithm. BIT 10, 76\u201394 (1970)","journal-title":"BIT"},{"key":"885_CR65","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.is.2018.10.001","volume":"80","author":"C Quijada-Fuentes","year":"2019","unstructured":"Quijada-Fuentes, C., Penabad, M.R., Ladra, S., Guti\u00e9rrez, G.: Set operations over compressed binary relations. Inf. Syst. 80, 76\u201390 (2019)","journal-title":"Inf. Syst."},{"key":"885_CR66","doi-asserted-by":"crossref","unstructured":"van Rest, O., Hong, S., Kim, J., Meng, X., Chafi, H.: PGQL: A property graph query language. In: Proc. GRADES, p\u00a07 (2016)","DOI":"10.1145\/2960414.2960421"},{"key":"885_CR67","doi-asserted-by":"crossref","unstructured":"Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM (2003)","DOI":"10.1137\/1.9780898718003"},{"key":"885_CR68","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"H Samet","year":"2006","unstructured":"Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann (2006)"},{"issue":"2","key":"885_CR69","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0020-0190(82)90114-4","volume":"15","author":"A Schoor","year":"1982","unstructured":"Schoor, A.: Fast algorithm for sparse matrix multiplication. Inf. Process. Lett. 15(2), 87\u201389 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"885_CR70","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0898-1221(81)90008-0","volume":"7","author":"M Sharir","year":"1981","unstructured":"Sharir, M.: A strong-connectivity algorithm and its applications to data flow analysis. Comput. Math. Appl. 7(1), 67\u201372 (1981)","journal-title":"Comput. Math. Appl."},{"key":"885_CR71","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik 13, 354\u2013356 (1969)","journal-title":"Numerische Mathematik"},{"issue":"2","key":"885_CR72","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"885_CR73","doi-asserted-by":"crossref","unstructured":"Tetzel, F., Kasperovics, R., Lehner, W.: Graph traversals for regular path queries. In: Proc. 2nd GRADES-NDA, pp 5:1\u20135:8 (2019)","DOI":"10.1145\/3327964.3328494"},{"key":"885_CR74","unstructured":"Thompson, B.B., Personick, M., Cutcher, M.: The Bigdata\u00aeRDF Graph Database. In: Linked Data Management, Chapman and Hall\/CRC, pp 193\u2013237 (2014)"},{"issue":"2","key":"885_CR75","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10(2), 308\u2013315 (1975)","journal-title":"J. Comput. Syst. Sci."},{"issue":"10","key":"885_CR76","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2629489","volume":"57","author":"D Vrandecic","year":"2014","unstructured":"Vrandecic, D., Kr\u00f6tzsch, M.: Wikidata: a free collaborative knowledgebase. Commun. ACM 57(10), 78\u201385 (2014)","journal-title":"Commun. ACM"},{"issue":"1","key":"885_CR77","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on Boolean matrices. J. ACM 9(1), 11\u201312 (1962)","journal-title":"J. ACM"},{"key":"885_CR78","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proc. 44th STOC, pp 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"885_CR79","doi-asserted-by":"crossref","unstructured":"Yakovets, N., Godfrey, P., Gryz, J.: Query Planning for Evaluating SPARQL Property Paths. In: Proc. SIGMOD, pp 1875\u20131889 (2016)","DOI":"10.1145\/2882903.2882944"},{"key":"885_CR80","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proc. 9th PODS, pp 230\u2013242 (1990)","DOI":"10.1145\/298514.298576"},{"key":"885_CR81","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.ic.2018.02.006","volume":"261","author":"H Yu","year":"2018","unstructured":"Yu, H.: An improved combinatorial algorithm for Boolean matrix multiplication. Inf. Comput. 261, 240\u2013247 (2018)","journal-title":"Inf. Comput."},{"issue":"1","key":"885_CR82","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Trans. Algorithms 1(1), 2\u201313 (2005)","journal-title":"ACM Trans. Algorithms"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00885-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-024-00885-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00885-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T05:53:21Z","timestamp":1737957201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-024-00885-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,26]]},"references-count":82,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["885"],"URL":"https:\/\/doi.org\/10.1007\/s00778-024-00885-6","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2024,11,26]]},"assertion":[{"value":"24 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"2"}}