From Batch to Stream: Automatic Generation of Online Algorithms
<|reference_start|>From Batch to Stream: Automatic Generation of Online Algorithms: 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.<|reference_end|>
@article{wang2024from,
    title={From Batch to Stream: Automatic Generation of Online Algorithms},
    author={Ziteng Wang, Shankara Pailoor, Aaryan Prakash, Yuepeng Wang, Isil
  Dillig},
    journal={Proc. ACM Program. Lang. 8, PLDI, Article 188 (June 2024), 32
  pages},
    year={2024},
    doi={10.1145/3656418},
    archivePrefix={arXiv},
    eprint={2404.04743},
    primaryClass={cs.PL}
}