{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:33:34Z","timestamp":1742952814441,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031220630"},{"type":"electronic","value":"9783031220647"}],"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:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-22064-7_36","type":"book-chapter","created":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T19:02:04Z","timestamp":1669230124000},"page":"505-519","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Decentralized Graph Processing for\u00a0Reachability Queries"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1601-5234","authenticated-orcid":false,"given":"Jo\u00ebl","family":"Mathys","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robin","family":"Fritsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6339-3134","authenticated-orcid":false,"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,24]]},"reference":[{"key":"36_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, pp. 188\u2013197. Association for Computing Machinery, New York (2006). https:\/\/doi.org\/10.1145\/1146381.1146411","DOI":"10.1145\/1146381.1146411"},{"key":"36_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-662-43951-7_32","volume-title":"Automata, Languages, and Programming","author":"D Adjiashvili","year":"2014","unstructured":"Adjiashvili, D., Rotbart, N.: Labeling schemes for bounded degree graphs. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 375\u2013386. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_32"},{"key":"36_CR3","doi-asserted-by":"publisher","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, SIGMOD 1989, pp. 253\u2013262. Association for Computing Machinery, New York (1989). https:\/\/doi.org\/10.1145\/67544.66950","DOI":"10.1145\/67544.66950"},{"key":"36_CR4","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. SIAM J. Discrete Math. 19(2), 448\u2013462 (2005). https:\/\/doi.org\/10.1137\/S0895480103433409","DOI":"10.1137\/S0895480103433409"},{"key":"36_CR5","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: a survey and a new algorithm for a distributed environment. Theor Comput. Syst. 37(3), 441\u2013456 (2004). https:\/\/doi.org\/10.1007\/s00224-004-1155-5","DOI":"10.1007\/s00224-004-1155-5"},{"key":"36_CR6","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Kaplan, H., Thorup, M., Zwick, U.: Adjacency labeling schemes and induced-universal graphs. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, pp. 625\u2013634. Association for Computing Machinery, New York (2015). https:\/\/doi.org\/10.1145\/2746539.2746545","DOI":"10.1145\/2746539.2746545"},{"key":"36_CR7","unstructured":"Alstrup, S., Rauhe, T.: Improved labeling scheme for ancestor queries. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 947\u2013953. Society for Industrial and Applied Mathematics, USA (2002)"},{"key":"36_CR8","doi-asserted-by":"publisher","unstructured":"Bonamy, M., Esperet, L., Groenland, C., Scott, A.: Optimal labelling schemes for adjacency, comparability, and reachability, p. 1109\u20131117. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3406325.3451102","DOI":"10.1145\/3406325.3451102"},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","volume":"12","author":"M Breuer","year":"1966","unstructured":"Breuer, M.: Coding the vertexes of a graph. IEEE Trans. Inf. Theory 12, 148\u2013153 (1966)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"36_CR10","doi-asserted-by":"publisher","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.C.: TF-label: a topological-folding labeling scheme for reachability querying in a large graph. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, pp. 193\u2013204. Association for Computing Machinery, New York (2013). https:\/\/doi.org\/10.1145\/2463676.2465286","DOI":"10.1145\/2463676.2465286"},{"key":"36_CR11","doi-asserted-by":"publisher","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003). https:\/\/doi.org\/10.1137\/S0097539702403098","DOI":"10.1137\/S0097539702403098"},{"key":"36_CR12","doi-asserted-by":"publisher","unstructured":"da Silva, R.F., Urrutia, S., Hvattum, L.M.: Extended high dimensional indexing approach for reachability queries on very large graphs. Exp. Syst. Appl. 181, 114962 (2021). https:\/\/doi.org\/10.1016\/j.eswa.2021.114962. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0957417421004036","DOI":"10.1016\/j.eswa.2021.114962"},{"key":"36_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/978-3-662-47666-6_45","volume-title":"Automata, Languages, and Programming","author":"S Dahlgaard","year":"2015","unstructured":"Dahlgaard, S., Knudsen, M.B.T., Rotbart, N.: A simple and optimal ancestry labeling scheme for trees. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 564\u2013574. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_45"},{"key":"36_CR14","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs. CoRR cs.DS\/0207082 (2002). https:\/\/arxiv.org\/abs\/cs\/0207082"},{"key":"36_CR15","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Korman, A.: An optimal ancestry labeling scheme with applications to xml trees and universal posets. J. ACM 63(1) (2016). https:\/\/doi.org\/10.1145\/2794076","DOI":"10.1145\/2794076"},{"key":"36_CR16","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2001, pp. 210\u2013219. Society for Industrial and Applied Mathematics, USA (2001)"},{"key":"36_CR17","doi-asserted-by":"publisher","unstructured":"Gilbert, J.R., Hutchinson, J.P., Tarjan, R.E.: A separator theorem for graphs of bounded genus. J. Algorithms 5(3), 391\u2013407 (1984). https:\/\/doi.org\/10.1016\/0196-6774(84)90019-1. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0196677484900191","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"36_CR18","doi-asserted-by":"publisher","unstructured":"Heinis, T., Alonso, G.: Efficient lineage tracking for scientific workflows. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, pp. 1007\u20131018. Association for Computing Machinery, New York (2008). https:\/\/doi.org\/10.1145\/1376616.1376716","DOI":"10.1145\/1376616.1376716"},{"key":"36_CR19","doi-asserted-by":"publisher","unstructured":"Jain, R., Tewari, R.: Reachability in high treewidth graphs. In: Lu, P., Zhang, G. (eds.) 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), vol. 149, pp. 12:1\u201312:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.12. https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2019\/11508","DOI":"10.4230\/LIPIcs.ISAAC.2019.12"},{"key":"36_CR20","doi-asserted-by":"publisher","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 334\u2013343. Association for Computing Machinery, New York (1988). https:\/\/doi.org\/10.1145\/62212.62244","DOI":"10.1145\/62212.62244"},{"key":"36_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-22006-7_12","volume-title":"Automata, Languages and Programming","author":"K Kawarabayashi","year":"2011","unstructured":"Kawarabayashi, K., Klein, P.N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 135\u2013146. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_12"},{"key":"36_CR22","doi-asserted-by":"publisher","unstructured":"Liu, Y.: Topological theory of graphs: de Gruyter (2017). https:\/\/doi.org\/10.1515\/9783110479492","DOI":"10.1515\/9783110479492"},{"key":"36_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/3-540-44612-5_53","volume-title":"Mathematical Foundations of Computer Science 2000","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Informative labeling schemes for graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 579\u2013588. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44612-5_53"},{"key":"36_CR24","doi-asserted-by":"publisher","unstructured":"Seufert, S., Anand, A., Bedathur, S., Weikum, G.: FERRARI: flexible and efficient reachability range assignment for graph indexing. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 1009\u20131020 (2013). https:\/\/doi.org\/10.1109\/ICDE.2013.6544893","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"36_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/3-540-16761-7_87","volume-title":"Automata, Languages and Programming","author":"K Simon","year":"1986","unstructured":"Simon, K.: An improved algorithm for transitive closure on acyclic digraphs. In: Kott, L. (ed.) ICALP 1986. LNCS, vol. 226, pp. 376\u2013386. Springer, Heidelberg (1986). https:\/\/doi.org\/10.1007\/3-540-16761-7_87"},{"key":"36_CR26","doi-asserted-by":"publisher","unstructured":"Thomassen, C.: Kuratowski\u2019s theorem. J. Graph Theor. 5(3), 225\u2013241 (1981). https:\/\/doi.org\/10.1002\/jgt.3190050304. https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/jgt.3190050304","DOI":"10.1002\/jgt.3190050304"},{"key":"36_CR27","doi-asserted-by":"publisher","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004). https:\/\/doi.org\/10.1145\/1039488.1039493","DOI":"10.1145\/1039488.1039493"},{"key":"36_CR28","doi-asserted-by":"publisher","unstructured":"Wang, H., He, H., Yang, J., Yu, P., Yu, J.: Dual labeling: answering graph reachability queries in constant time. In: 22nd International Conference on Data Engineering (ICDE 2006), pp. 75\u201375 (2006). https:\/\/doi.org\/10.1109\/ICDE.2006.53","DOI":"10.1109\/ICDE.2006.53"},{"issue":"1","key":"36_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00778-017-0468-3","volume":"27","author":"H Wei","year":"2017","unstructured":"Wei, H., Yu, J.X., Lu, C., Jin, R.: Reachability querying: an independent permutation labeling approach. VLDB J. 27(1), 1\u201326 (2017). https:\/\/doi.org\/10.1007\/s00778-017-0468-3","journal-title":"VLDB J."},{"key":"36_CR30","doi-asserted-by":"publisher","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: scalable reachability index for large graphs. Proc. VLDB Endow. 3(1\u20132), 276\u2013284 (2010). https:\/\/doi.org\/10.14778\/1920841.1920879","DOI":"10.14778\/1920841.1920879"}],"container-title":["Lecture Notes in Computer Science","Advanced Data Mining and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-22064-7_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T19:08:54Z","timestamp":1669230534000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-22064-7_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031220630","9783031220647"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-22064-7_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"24 November 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ADMA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Advanced Data Mining and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Brisbane, QLD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Australia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"adma2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/adma2022.uqcloud.net\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT3","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"198","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":"72","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":"36% - 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":"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":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}