{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:47:38Z","timestamp":1769078858719,"version":"3.49.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T00:00:00Z","timestamp":1642636800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["World Wide Web"],"published-print":{"date-parts":[[2022,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Implementing complex algorithms for big data, artificial intelligence, and graph processing requires enormous effort. Succinct, declarative programs to solve complex problems that can be efficiently executed for batching and streaming data are in demand. This paper presents Nexus, a distributed Datalog evaluation system. It evaluates Datalog programs using the<jats:italic>semi-naive<\/jats:italic>algorithm for batch and streaming data using incremental and asynchronous iteration. Furthermore, we evaluate Datalog programs with aggregates to determine the advantages of implementing the<jats:italic>semi-naive<\/jats:italic>algorithm using incremental iteration on its performance. Our experimental results show that Nexus significantly outperforms acyclic dataflow-based systems.<\/jats:p>","DOI":"10.1007\/s11280-021-00960-w","type":"journal-article","created":{"date-parts":[[2022,1,20]],"date-time":"2022-01-20T12:07:10Z","timestamp":1642680430000},"page":"971-1003","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Fast datalog evaluation for batch and stream graph processing"],"prefix":"10.1007","volume":"25","author":[{"given":"Muhammad","family":"Imran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor E.","family":"G\u00e9vay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorge-Arnulfo","family":"Quian\u00e9-Ruiz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Volker","family":"Markl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,20]]},"reference":[{"issue":"6","key":"960_CR1","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1007\/s00778-014-0357-y","volume":"23","author":"A Alexandrov","year":"2014","unstructured":"Alexandrov, A., Bergmann, R., Ewen, S., Freytag, J. C., Hueske, F., Heise, A., Kao, O., Leich, M., Leser, U., Markl, V., Naumann, F., Peters, M., Rheinl\u00e4nder, A., Sax, M. J., Schelter, S., H\u00f6ger, M., Tzoumas, K., Warneke, D.: The Stratosphere platform for big data analytics. VLDB J. 23(6), 939\u2013964 (2014)","journal-title":"VLDB J."},{"issue":"1","key":"960_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1017\/S1471068402001515","volume":"3","author":"F Arni","year":"2003","unstructured":"Arni, F., Ong, K., Tsur, S., Wang, H., Zaniolo, C.: The deductive database system LDL++. Theory Pract. Log. Program. 3(1), 61\u201394 (2003)","journal-title":"Theory Pract. Log. Program."},{"key":"960_CR3","doi-asserted-by":"crossref","unstructured":"Bancilhon, F.: Naive Evaluation of Recursively Defined Relations. In: On Knowledge Base Management Systems, pp. 165\u2013178. Springer (1986)","DOI":"10.1007\/978-1-4612-4980-1_17"},{"key":"960_CR4","doi-asserted-by":"crossref","unstructured":"Bancilhon, F.: Naive Evaluation of Recursively Defined Relations, pp. 165\u2013178. Springer, Berlin (1986)","DOI":"10.1007\/978-1-4612-4980-1_17"},{"key":"960_CR5","doi-asserted-by":"crossref","unstructured":"Bancilhon, F., Ramakrishnan, R.: An Amateur\u2019s Introduction to Recursive Query Processing Strategies. In: Readings in Artificial Intelligence and Databases, pp. 376\u2013430. Elsevier (1989)","DOI":"10.1016\/B978-0-934613-53-8.50030-3"},{"key":"960_CR6","doi-asserted-by":"crossref","unstructured":"Begoli, E., Camacho-rodr\u00edguez, J., Hyde, J., Mior, M.J., Lemire, D.: Apache Calcite: A foundational framework for optimized query processing over heterogeneous data sources. In: Proceedings of the 2018 International Conference on Management of Data, pp. 221\u2013230 (2018)","DOI":"10.1145\/3183713.3190662"},{"key":"960_CR7","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: Srinivasan, S., Ramamritham, K., Kumar, A., Ravindra, M.P., Bertino, E., Kumar, R. (eds.) Proceedings of the 20th international conference on World Wide Web, pp 587\u2013596. ACM Press (2011)","DOI":"10.1145\/1963405.1963488"},{"key":"960_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: The WebGraph Framework I: Compression Techniques. In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), pp. 595\u2013601. ACM Press, Manhattan (2004)","DOI":"10.1145\/988672.988752"},{"key":"960_CR9","doi-asserted-by":"publisher","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Comput. Netw. ISDN Syst. 30(1), 107\u2013117. https:\/\/doi.org\/10.1016\/S0169-7552(98)00110-X. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S016975529800110X. Proceedings of the Seventh International World Wide Web Conference (1998)","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"960_CR10","unstructured":"Carbone, P., Katsifodimos, A., Ewen, S., Markl, V., Haridi, S., Tzoumas, K.: Apache Flink: Stream and batch processing in a single engine. Bullet. IEEE Comput. Soc. Tech. Committee Data Eng. 36(4) (2015)"},{"issue":"1","key":"960_CR11","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1109\/69.43410","volume":"1","author":"S Ceri","year":"1989","unstructured":"Ceri, S., Gottlob, G., Tanca, L.: What you always wanted to know about datalog (and never dared to ask). IEEE Trans. Knowl. data Eng. 1(1), 146\u2013166 (1989)","journal-title":"IEEE Trans. Knowl. data Eng."},{"key":"960_CR12","doi-asserted-by":"crossref","unstructured":"Chothia, Z., Liagouris, J., McSherry, F., Roscoe, T.: Explaining Outputs in Modern Data Analytics. Technical report, ETH Zurich (2016)","DOI":"10.14778\/2994509.2994530"},{"key":"960_CR13","doi-asserted-by":"publisher","unstructured":"Contreras-Rojas, B., Quian\u00e9-Ruiz, J. A., Kaoudi, Z., Thirumuruganathan, S.: Tagsniff: Simplified big data debugging for dataflow jobs. In: Proceedings of the ACM Symposium on Cloud Computing, SoCC \u201919, pp. 453\u2013464. Association for Computing Machinery, New York. https:\/\/doi.org\/10.1145\/3357223.3362738 (2019)","DOI":"10.1145\/3357223.3362738"},{"issue":"11","key":"960_CR14","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.14778\/2350229.2350245","volume":"5","author":"S Ewen","year":"2012","unstructured":"Ewen, S., Tzoumas, K., Kaufmann, M., Markl, V.: Spinning fast iterative data flows. Proc. VLDB Endow. 5(11), 1268\u20131279 (2012)","journal-title":"Proc. VLDB Endow."},{"key":"960_CR15","doi-asserted-by":"crossref","unstructured":"Fan, Z., Zhu, J., Zhang, Z., Albarghouthi, A., Koutris, P., Patel, J.: Scaling-up in-memory Datalog processing: observations and techniques. arXiv:1812.03975 (2018)","DOI":"10.14778\/3311880.3311886"},{"key":"960_CR16","unstructured":"G\u00e9vay, G. E., Rabl, T., Bre\u00df, S., Madai-Tahy, L., Markl, V.: Labyrinth: Compiling imperative control flow to parallel dataflows. arXiv:1809.06845 (2018)"},{"key":"960_CR17","unstructured":"G\u00f6bel, N., Bach, D., McSherry, F., Sandstede, M.: Declarative dataflow. https:\/\/github.com\/comnik\/declarative-dataflow. [Online; accessed 20-July-2020] (2019)"},{"key":"960_CR18","unstructured":"Gonzalez, J. E., Xin, R. S., Dave, A., Crankshaw, D., Franklin, M. J., Stoica, I.: GraphX: Graph Processing in a Distributed Dataflow Framework. In: 11Th USENIX Symposium on Operating Systems Design and Implementation OSDI 14), pp. 599\u2013613 (2014)"},{"key":"960_CR19","doi-asserted-by":"crossref","unstructured":"Gu, J., Watanabe, Y. H., Mazza, W. A., Shkapsky, A., Yang, M., Ding, L., Zaniolo, C.: RaSQL: Greater power and performance for big data analytics with recursive-aggregate-SQL on Spark. In: Proceedings of the 2019 International Conference on Management of Data, pp. 467\u2013484 (2019)","DOI":"10.1145\/3299869.3324959"},{"key":"960_CR20","doi-asserted-by":"crossref","unstructured":"Imran, M., G\u00e9vay, G.E., Markl, V.: Distributed graph analytics with Datalog queries in Flink. LSGDA 2020 - International Workshop on Large Scale Graph Data Analytics. http:\/\/www.redaktion.tu-berlin.de\/fileadmin\/fg131\/Publikation\/Papers\/datalog-to-flink_2020.pdf (2020)","DOI":"10.1007\/978-3-030-61133-0_6"},{"key":"960_CR21","doi-asserted-by":"crossref","unstructured":"Imran, M., G\u00e9vay, G. E., Markl, V.: Distributed Graph Analytics with Datalog Queries in Flink. In: Qin, L., Zhang, W., Zhang, Y., Peng, Y., Kato, H., Wang, W., Xiao, C. (eds.) Software Foundations for Data Interoperability and Large Scale Graph Data Analytics, pp 70\u201383. Springer International Publishing, Cham (2020)","DOI":"10.1007\/978-3-030-61133-0_6"},{"issue":"12","key":"960_CR22","doi-asserted-by":"publisher","first-page":"2040","DOI":"10.14778\/2824032.2824132","volume":"8","author":"A Kejariwal","year":"2015","unstructured":"Kejariwal, A., Kulkarni, S., Ramasamy, K.: Real time analytics: Algorithms and systems. Proc. VLDB Endow. 8(12), 2040\u20132041 (2015). https:\/\/doi.org\/10.14778\/2824032.2824132","journal-title":"Proc. VLDB Endow."},{"key":"960_CR23","doi-asserted-by":"crossref","unstructured":"Lloyd, J. W.: Foundations of logic programming. Springer, Berlin (1984)","DOI":"10.1007\/978-3-642-96826-6"},{"key":"960_CR24","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M. H., Bik, A. J., Dehnert, J. C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 135\u2013146 (2010)","DOI":"10.1145\/1807167.1807184"},{"key":"960_CR25","unstructured":"McSherry, F.: Differential datalog. https:\/\/github.com\/frankmcsherry\/blog\/blob\/master\/posts\/2016-06-21.md [Online; Accessed 19 2021]"},{"key":"960_CR26","doi-asserted-by":"crossref","unstructured":"Murray, D. G., McSherry, F., Isaacs, R., Isard, M., Barham, P., Abadi, M.: Naiad: a timely dataflow system. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pp. 439\u2013455 (2013)","DOI":"10.1145\/2517349.2522738"},{"key":"960_CR27","doi-asserted-by":"crossref","unstructured":"Palla, G., Der\u00e9nyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814\u2013818 (2005)","DOI":"10.1038\/nature03607"},{"key":"960_CR28","doi-asserted-by":"publisher","unstructured":"Parr, T., Harwell, S., Fisher, K.: Adaptive LL(*) parsing: The power of dynamic analysis. In: Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA \u201914, pp. 579\u2013598. Association for Computing Machinery, New York. https:\/\/doi.org\/10.1145\/2660193.2660202 (2014)","DOI":"10.1145\/2660193.2660202"},{"issue":"6","key":"960_CR29","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1093\/comjnl\/45.6.631","volume":"45","author":"JW Raymond","year":"2002","unstructured":"Raymond, J.W., Gardiner, E.J., Willett, P.: Rascal: Calculation of graph similarity using maximum common edge subgraphs. Comput. J. 45(6), 631\u2013644 (2002). https:\/\/doi.org\/10.1093\/comjnl\/45.6.631","journal-title":"Comput. J."},{"key":"960_CR30","unstructured":"Ryzhyk, L., Budiu, M.: Differential Datalog. In: Datalog 2.0 \u2013 3Rd International Workshop on the Resurgence of Datalog in Academia and Industry. CEUR-WS (2019)"},{"key":"960_CR31","doi-asserted-by":"crossref","unstructured":"Seo, J., Guo, S., Lam, M. S.: Socialite: Datalog Extensions for Efficient Social Network Analysis. In: 2013 IEEE 29Th International Conference on Data Engineering (ICDE), pp. 278\u2013289. IEEE (2013)","DOI":"10.1109\/ICDE.2013.6544832"},{"issue":"14","key":"960_CR32","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.14778\/2556549.2556572","volume":"6","author":"J Seo","year":"2013","unstructured":"Seo, J., Park, J., Shin, J., Lam, M. S.: Distributed SociaLite: A Datalog-based language for large-scale graph analysis. Proc. VLDB Endowment 6(14), 1906\u20131917 (2013)","journal-title":"Proc. VLDB Endowment"},{"key":"960_CR33","doi-asserted-by":"crossref","unstructured":"Shkapsky, A., Yang, M., Interlandi, M., Chiu, H., Condie, T., Zaniolo, C.: Big Data Analytics with Datalog Queries on Spark. In: SIGMOD, pp. 1135\u20131149 (2016)","DOI":"10.1145\/2882903.2915229"},{"issue":"2","key":"960_CR34","doi-asserted-by":"publisher","first-page":"141","DOI":"10.14778\/3282495.3282500","volume":"12","author":"P Suboti\u0107","year":"2018","unstructured":"Suboti\u0107, P., Jordan, H., Chang, L., Fekete, A., Scholz, B.: Automatic index selection for large-scale Datalog computation. Proc. VLDB Endowment 12(2), 141\u2013153 (2018)","journal-title":"Proc. VLDB Endowment"},{"key":"960_CR35","unstructured":"Vieille, L.: A Database-Complete Proof Procedure Based on Sld-Resolution. In: ICLP (1987)"},{"issue":"12","key":"960_CR36","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.14778\/2824032.2824052","volume":"8","author":"J Wang","year":"2015","unstructured":"Wang, J., Balazinska, M., Halperin, D.: Asynchronous and fault-tolerant recursive Datalog evaluation in shared-nothing engines. Proc. VLDB Endowment 8 (12), 1542\u20131553 (2015)","journal-title":"Proc. VLDB Endowment"},{"key":"960_CR37","doi-asserted-by":"crossref","unstructured":"Wang, Q., Zhang, Y., Wang, H., Geng, L., Lee, R., Zhang, X., Yu, G.: Automating incremental and asynchronous evaluation for recursive aggregate data processing. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 2439\u20132454 (2020)","DOI":"10.1145\/3318464.3389712"},{"issue":"4","key":"960_CR38","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1002\/pmic.200300636","volume":"4","author":"SH Yook","year":"2004","unstructured":"Yook, S. H., Oltvai, Z. N., Barab\u00e1si, A. L.: Functional and topological characterization of protein interaction networks. Proteomics 4(4), 928\u2013942 (2004)","journal-title":"Proteomics"},{"issue":"10-10","key":"960_CR39","first-page":"95","volume":"10","author":"M Zaharia","year":"2010","unstructured":"Zaharia, M., Chowdhury, M., Franklin, M. J., Shenker, S., Stoica, I., et al.: Spark: Cluster computing with working sets. HotCloud 10(10-10), 95 (2010)","journal-title":"HotCloud"},{"key":"960_CR40","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Acharya, A., Chen, H., Arora, S., Chen, A., Liu, V., Loo, B. T.: Optimizing declarative graph queries at large scale. In: Proceedings of the 2019 International Conference on Management of Data, pp. 1411\u20131428 (2019)","DOI":"10.1145\/3299869.3300064"},{"key":"960_CR41","unstructured":"Apache Giraph. http:\/\/giraph.apache.org\/. [Online; Accessed 12 Apr. 2020]"},{"key":"960_CR42","unstructured":"Gelly: Flink Graph API. https:\/\/ci.apache.org\/projects\/flink\/flink-docs-stable\/dev\/libs\/gelly\/. [Online; Accessed 12 Apr. 2020]"},{"key":"960_CR43","unstructured":"GTGraph. http:\/\/www.cse.psu.edu\/~kxm85\/software\/GTgraph\/. [Online; Accessed 12 Apr. 2020]"},{"key":"960_CR44","unstructured":"Livejournal dataset. http:\/\/snap.stanford.edu\/data\/com-LiveJournal.html. [Online; Accessed 2 Mar. 2021]"},{"key":"960_CR45","unstructured":"Orkut dataset. http:\/\/snap.stanford.edu\/data\/com-Orkut.html. [Online; Accessed 12 Mar. 2021]"}],"container-title":["World Wide Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-021-00960-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11280-021-00960-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11280-021-00960-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T17:20:01Z","timestamp":1726507201000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11280-021-00960-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,20]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["960"],"URL":"https:\/\/doi.org\/10.1007\/s11280-021-00960-w","relation":{},"ISSN":["1386-145X","1573-1413"],"issn-type":[{"value":"1386-145X","type":"print"},{"value":"1573-1413","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,20]]},"assertion":[{"value":"22 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}