{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T01:46:09Z","timestamp":1784166369025,"version":"3.55.0"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1762299,CCF-1918889CNS-1908304, CCF-1901376, CNS-2120696,CCF-2210831,CCF-2319471"],"award-info":[{"award-number":["CCF-1762299,CCF-1918889CNS-1908304, CCF-1901376, CNS-2120696,CCF-2210831,CCF-2319471"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>\n            Online streaming algorithms, tailored for continuous data processing, offer substantial benefits but are often more intricate to design than their offline counterparts. This paper introduces a novel approach for automatically synthesizing online streaming algorithms from their offline versions. In particular, we propose a novel methodology, based on the notion of\n            <jats:italic toggle=\"yes\">relational function signature (RFS)<\/jats:italic>\n            , for deriving an online algorithm given its offline version. Then, we propose a concrete synthesis algorithm that is an instantiation of the proposed methodology. Our algorithm uses the RFS to decompose the synthesis problem into a set of independent subtasks and uses a combination of symbolic reasoning and search to solve each subproblem. We implement the proposed technique in a new tool called\n            <jats:sc>Opera<\/jats:sc>\n            and evaluate it on over 50 tasks spanning two domains: statistical computations and online auctions. Our results show that\n            <jats:sc>Opera<\/jats:sc>\n            can automatically derive the online version of the original algorithm for 98% of the tasks. Our experiments also demonstrate that\n            <jats:sc>Opera<\/jats:sc>\n            significantly outperforms alternative approaches, including adaptations of SyGuS solvers to this problem as well as two of\n            <jats:sc>Opera<\/jats:sc>\n            \u2019s own ablations.\n          <\/jats:p>","DOI":"10.1145\/3656418","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"1014-1039","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["From Batch to Stream: Automatic Generation of Online Algorithms"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-8487-8093","authenticated-orcid":false,"given":"Ziteng","family":"Wang","sequence":"first","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9253-9585","authenticated-orcid":false,"given":"Shankara","family":"Pailoor","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3142-3345","authenticated-orcid":false,"given":"Aaryan","family":"Prakash","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3370-2431","authenticated-orcid":false,"given":"Yuepeng","family":"Wang","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Burnaby, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8006-1230","authenticated-orcid":false,"given":"I\u015f\u0131l","family":"Dillig","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"[n.d.]. https:\/\/storm.apache.org\/"},{"key":"e_1_3_1_3_2","unstructured":"2010. . https:\/\/web.archive.org\/web\/20240314171007\/https:\/\/stackoverflow.com\/questions\/3903538\/online-algorithmfor-calculating-absolute-deviation Accessed: 2024-03-14."},{"key":"e_1_3_1_4_2","unstructured":"2013. . https:\/\/stackoverflow.com\/questions\/17104673\/incremental-entropy-computation Accessed: 2024-03-14."},{"key":"e_1_3_1_5_2","unstructured":"2014. . https:\/\/stackoverflow.com\/questions\/26191456\/algorithm-for-a-running-harmonic-mean Accessed: 2024-03-14."},{"key":"e_1_3_1_6_2","unstructured":"2018. . https:\/\/stackoverflow.com\/questions\/52070293\/efficient-online-linear-regression-algorithm-in-python Accessed: 2024-03-14."},{"key":"e_1_3_1_7_2","unstructured":"2023. . https:\/\/stackoverflow.com\/questions\/75545944\/efficient-algorithm-for-online-variance-over-image-batches Accessed: 2024-03-14."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517889"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.11.043"},{"key":"e_1_3_1_10_2","volume-title":"Ph. D. Dissertation","author":"Acar Umut A.","year":"2005","unstructured":"Umut A. Acar. 2005. Self-adjusting computation. Ph. D. Dissertation. School of Computer Science, Carnegie Mellon University."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186634"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2429376.2429382"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837628"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1136\/bmj.331.7521.903"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-99524-9_24"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694371"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038923"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594304"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3622863"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1291151.1291199"},{"key":"e_1_3_1_21_2","unstructured":"Josh Day. [n.d.]. https:\/\/github.com\/joshday\/OnlineStats.jl"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014657"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_46"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254087"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509511"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062355"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314612"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-81685-8_39"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11245-5_5"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737977"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165214"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3586052"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461550"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/800181.810335"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926423"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375634.1375642"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814305"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594324"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/800168.811543"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062345"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796899003500"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","unstructured":"Ruyi Ji Yuwei Zhao Yingfei Xiong Di Wang Lu Zhang and Zhenjiang Hu. 2024. Decomposition-Based Synthesis for Applying Divide-and-Conquer-Like Algorithmic Paradigms. ACM Trans. Program. Lang. Syst. (feb 2024). https:\/\/doi.org\/10.1145\/3648440 10.1145\/3648440 Just Accepted.","DOI":"10.1145\/3648440"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","unstructured":"Asterios Katsifodimos and Sebastian Schelter. 2016. Apache Flink: Stream Analytics at Scale. In 2016 IEEE International Conference on Cloud Engineering Workshop (IC2EW). 193\u2013193. https:\/\/doi.org\/10.1109\/IC2EW.2016.56 10.1109\/IC2EW.2016.56","DOI":"10.1109\/IC2EW.2016.56"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/502981"},{"key":"e_1_3_1_46_2","unstructured":"Jay Kreps Neha Narkhede Jun Rao et al. 2011. Kafka: A distributed messaging system for log processing. In Proceedings of the NetDB Vol. 11. Athens Greece 1\u20137."},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14295-6_38"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806632"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026547031739"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276342"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3527315"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/3540543961_7"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158089"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341699"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498682"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137770"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357177"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632870"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","unstructured":"Philippe Pierre Pebay. 2008. Formulas for robust one-pass parallel computation of covariances and arbitrary-order statistical moments. (01 2008). https:\/\/doi.org\/10.2172\/1028931 10.2172\/1028931","DOI":"10.2172\/1028931"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908093"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048076"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/158511.158710"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3371120"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/263699.263758"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385398"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375599"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168907"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993557"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3622800"},{"key":"e_1_3_1_70_2","unstructured":"Peter A. Tucker Kristin Tufte Vassilis Papadimos and David Maier. 2010. NEXMark \u2013 A Benchmark for Queries over Data Streams. https:\/\/github.com\/nexmark\/nexmark"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90147-A"},{"key":"e_1_3_1_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3276525"},{"key":"e_1_3_1_75_2","doi-asserted-by":"crossref","unstructured":"Ziteng Wang Shankara Pailoor Aaryan Prakash Yuepeng Wang and Isil Dillig. 2024. From Batch to Stream: Automatic Generation of Online Algorithms. arXiv:2404.04743 [cs.PL]","DOI":"10.1145\/3656418"},{"key":"e_1_3_1_76_2","volume-title":"Approximation theory and numerical methods","author":"Watson G. A.","year":"1980","unstructured":"G. A. Watson. 1980. Approximation theory and numerical methods. John Wiley & Sons."},{"key":"e_1_3_1_77_2","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1962.10490022"},{"key":"e_1_3_1_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591255"},{"key":"e_1_3_1_79_2","first-page":"10","volume-title":"Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (Boston, MA) (HotCloud\u201910)","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (Boston, MA) (HotCloud\u201910). USENIX Association, USA, 10."},{"key":"e_1_3_1_80_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522737"},{"key":"e_1_3_1_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485489"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656418","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:41:28Z","timestamp":1751661688000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":80,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656418"],"URL":"https:\/\/doi.org\/10.1145\/3656418","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}