Lune

PLDI2024Top-tier venue

From Batch to Stream: Automatic Generation of Online Algorithms

Ziteng Wang, Shankara Pailoor, Aaryan Prakash, Yuepeng Wang, Isil Dillig

Abstract

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 relational function signature (RFS), 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 Opera and evaluate it on over 50 tasks spanning two domains: statistical computations and online auctions. Our results show that Opera can automatically derive the online version of the original algorithm for 98% of the tasks. Our experiments also demonstrate that Opera significantly outperforms alternative approaches, including adaptations of SyGuS solvers to this problem as well as two of Opera's own ablations.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Homomorphism Calculus for User-Defined Aggregations cites Bottom-up synthesis of recursive functional programs using angelic execution
  • Trace-Guided Inductive Synthesis of Recursive Functional Programs cites Bottom-up synthesis of recursive functional programs using angelic execution
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Homomorphism Calculus for User-Defined AggregationsZiteng Wang, Ruijie Fang, Linus Zheng, Dixin Tang et al.OOPSLA 2025

Builds on12

  1. Bottom-up synthesis of recursive functional programs using angelic executionAnders Miltner, Adrian Trejo Nuñez, Ana Brendel, Swarat Chaudhuri et al.POPL 2022 · 38 citations
  2. Automated transpilation of imperative to functional code using neural-guided program synthesisBenjamin Mariano, Yanju Chen, Yu Feng, Greg Durrett et al.OOPSLA 2022 · 27 citations
  3. Data Extraction via Semantic Regular Expression SynthesisQiaochu Chen, Arko Banerjee, Çagatay Demiralp, Greg Durrett et al.OOPSLA 2023 · 24 citations
  4. Automating Incremental Graph Processing with Flexible MemoizationShufeng Gong, Chao Tian, Qiang Yin, Wenyuan Yu et al.VLDB 2021 · 23 citations
  5. Trace-Guided Inductive Synthesis of Recursive Functional ProgramsYongwei Yuan, Arjun Radhakrishna, Roopsha SamantaPLDI 2023 · 17 citations

Related papers

  1. Learning to Synthesize Relational InvariantsJingbo Wang, Chao WangASE 2022 · 9 citations
  2. APEROL: Adaptive Parallel Edge-to-Cloud Runtime Optimization for Layered Workflow ExecutionDimitrios Banelas, Alkis Simitsis, Nikos GiatrakosVLDB 2026
  3. Semi-symbolic inference for efficient streaming probabilistic programmingEric Atkinson, Charles Yuan, Guillaume Baudart, Louis Mandel et al.OOPSLA 2022 · 11 citations
  4. Mobius: Synthesizing Relational Queries with Recursive and Invented PredicatesAalok Thakkar, Nathaniel Sands, George Petrou, Rajeev Alur et al.OOPSLA 2023 · 5 citations
  5. Learning to Represent Programs with Property SignaturesAugustus Odena, Charles SuttonICLR 2020 · 34 citations
Dusk over the sea between two cliffs drawn in fine vertical lines