{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:14:59Z","timestamp":1775873699640,"version":"3.50.1"},"reference-count":99,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T00:00:00Z","timestamp":1598400000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>This article targets the Incremental View Maintenance (IVM) of sophisticated analytics (such as statistical models, machine learning programs, and graph algorithms) expressed as linear algebra programs. We present LAGO, a unified framework for linear algebra that automatically synthesizes efficient incremental trigger programs, thereby freeing the user from error-prone manual derivations, performance tuning, and low-level implementation details. The key technique underlying our framework is abstract interpretation, which is used to infer various properties of analytical programs. These properties give the reasoning power required for the automatic synthesis of efficient incremental triggers. We evaluate the effectiveness of our framework on a wide range of applications from regression models to graph computations.<\/jats:p>","DOI":"10.1145\/3385398","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:33:48Z","timestamp":1594125228000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Synthesis of Incremental Linear Algebra Programs"],"prefix":"10.1145","volume":"45","author":[{"given":"Amir","family":"Shaikhha","sequence":"first","affiliation":[{"name":"University of Oxford, United Kingdom"}]},{"given":"Mohammed","family":"Elseidy","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}]},{"given":"Stephan","family":"Mihaila","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}]},{"given":"Daniel","family":"Espino","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}]},{"given":"Christoph","family":"Koch","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2020,8,26]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the CIDR.","author":"Abadi Daniel","year":"2005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026899"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1596527.1596530"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090168"},{"key":"e_1_2_1_5_1","volume-title":"STREAM: The Stanford Data Stream Management System","author":"Arasu Arvind","year":"2016"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276386"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"James Berger. 1985. Statistical Decision Theory and Bayesian Analysis. Springer.  James Berger. 1985. Statistical Decision Theory and Bayesian Analysis. Springer.","DOI":"10.1007\/978-1-4757-4286-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16861"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/645500.655920"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/111713.111718"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920881"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011403516"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2345156.2254100"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2480856"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"V. Ciriani S. De Capitani di Vimercati S. Foresti and P. Samarati. 2009. Theory of privacy and anonymity. In Algorithms and Theory of Computation Handbook (2nd ed.) M. Atallah and M. Blanton (Eds.). CRC Press.  V. Ciriani S. De Capitani di Vimercati S. Foresti and P. Samarati. 2009. Theory of privacy and anonymity. In Algorithms and Theory of Computation Handbook (2nd ed.) M. Atallah and M. Blanton (Eds.). CRC Press.","DOI":"10.1201\/9781584888215-c18"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687576"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263744"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807275"},{"key":"e_1_2_1_21_1","unstructured":"Camil Demetrescu. 2001. Fully Dynamic Algorithms for Path Problems on Directed Graphs. Ph.D. Dissertation. University of Rome.  Camil Demetrescu. 2001. Fully Dynamic Algorithms for Path Problems on Directed Graphs. Ph.D. Dissertation. University of Rome."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796544"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2544174.2500613"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851476.1851593"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the CIDR.","author":"Elgamal Tarek","year":"2017"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093754.3093765"},{"key":"e_1_2_1_29_1","unstructured":"Diego Fabregat-Traver and Paolo Bientinesi. 2012. A domain-specific compiler for linear algebra operations. CoRR abs\/1205.5975 (2012).  Diego Fabregat-Traver and Paolo Bientinesi. 2012. A domain-specific compiler for linear algebra operations. CoRR abs\/1205.5975 (2012)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/173262.155113"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035937"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767930"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the PARA.","author":"Gilbert John R."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2613412"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Ashish Gupta and Inderpal Mumick. 1999. Materialized Views. The MIT Press.  Ashish Gupta and Inderpal Mumick. 1999. Materialized Views. The MIT Press.","DOI":"10.7551\/mitpress\/4472.001.0001"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/93605.98740"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272998.1273005"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196894"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989411"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90087-2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/355887.355890"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2039367"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the CIDR.","author":"Kraska Tim","year":"2013"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387884"},{"key":"e_1_2_1_50_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213958"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/3023549.3023589"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the ICDE. 523--534","author":"Luo S."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200062"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the CIDR.","author":"McSherry Frank","year":"2013"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.2946679"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350246"},{"key":"e_1_2_1_60_1","unstructured":"Michael B. Monagan Keith O. Geddes K. Michael Heal George Labahn Stefan M. Vorkoetter James McCarron and Paul DeMarco. 2005. Maple 10 Programming Guide. Maplesoft.  Michael B. Monagan Keith O. Geddes K. Michael Heal George Labahn Stefan M. Vorkoetter James McCarron and Paul DeMarco. 2005. Maple 10 Programming Guide. Maplesoft."},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the CIDR.","author":"Motwani Rajeev","year":"2003"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824089"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610519"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3384702"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/1978665.1978669"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the CIDR.","author":"Palkar Shoumik","year":"2017"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840306"},{"key":"e_1_2_1_71_1","volume-title":"SPARSKIT: A basic tool kit for sparse matrix computations - Version 2. Tech. Rep. Computer Science Department, Univ. of Minnesota","author":"Saad Youcef","year":"1994"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796818000102"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341701"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357765.3359520"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183653"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915244"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the ECOOP.","author":"Shaikhha Amir","year":"2019"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377923"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729893"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/3168812"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/2581122.2544155"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854060"},{"key":"e_1_2_1_84_1","volume-title":"Proceedings of the CIDR.","author":"Stonebraker Michael","year":"2007"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463707"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_2_1_87_1","volume-title":"Theano: A Python framework for fast computation of mathematical expressions. arXiv e-prints abs\/1605.02688 (May","author":"Team Theano Development","year":"2016"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465371"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.5555\/2342763.2342774"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.5555\/509058.509096"},{"key":"e_1_2_1_91_1","unstructured":"Stephen Wolfram. 1999. The Mathematica. Cambridge University Press.  Stephen Wolfram. 1999. The Mathematica. Cambridge University Press."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/381694.378860"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3058735"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067424"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781140"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.5555\/1863103.1863113"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.110"},{"key":"e_1_2_1_98_1","volume-title":"Proceedings of the CIDR.","author":"Zhang Yi","year":"2009"},{"key":"e_1_2_1_99_1","volume-title":"Proceedings of the ICDE. 1157--1160","author":"Zhang Y."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385398","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:14Z","timestamp":1750200074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,26]]},"references-count":99,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3385398"],"URL":"https:\/\/doi.org\/10.1145\/3385398","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,26]]},"assertion":[{"value":"2018-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}