From Batch to Stream: Automatic Generation of Online Algorithms

被引:0
作者
Wang, Ziteng [1 ]
Pailoor, Shankara [1 ]
Prakash, Aaryan [1 ]
Wang, Yuepeng [2 ]
Dillig, Isil [1 ]
机构
[1] Univ Texas Austin, Austin, TX 78712 USA
[2] Simon Fraser Univ, Burnaby, BC, Canada
来源
PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL | 2024年 / 8卷 / PLDI期
基金
加拿大自然科学与工程研究理事会; 美国国家科学基金会;
关键词
Program Synthesis; Online Algorithms; Incremental Computation; Stream Processing; LIBRARY;
D O I
10.1145/3656418
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页数:26
相关论文
共 50 条
[31]   Scheduling with conflicts: online and offline algorithms [J].
Guy Even ;
Magnús M. Halldórsson ;
Lotem Kaplan ;
Dana Ron .
Journal of Scheduling, 2009, 12 :199-224
[32]   Online and Dynamic Algorithms for Set Cover [J].
Gupta, Anupam ;
Krishnaswamy, Ravishankar ;
Kumar, Amit ;
Panigrahi, Debmalya .
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :537-550
[33]   A NEW MEASURE FOR THE STUDY OF ONLINE ALGORITHMS [J].
BENDAVID, S ;
BORODIN, A .
ALGORITHMICA, 1994, 11 (01) :73-91
[34]   Randomized algorithms for online bounded bidding [J].
Epstein, Leah ;
Levin, Asaf .
INFORMATION PROCESSING LETTERS, 2010, 110 (12-13) :503-506
[35]   Tight Bounds on Online Checkpointing Algorithms [J].
Bar-On, Achiya ;
Dinur, Itai ;
Dunkelman, Orr ;
Hod, Rani ;
Keller, Nathan ;
Ronen, Eyal ;
Shamir, Adi .
ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (03)
[36]   Efficient algorithms for online decision problems [J].
Kalai, A ;
Vempala, S .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 71 (03) :291-307
[37]   A hybrid distributed batch-stream processing approach for anomaly detection [J].
Pishgoo, Boshra ;
Azirani, Ahmad Akbari ;
Raahemi, Bijan .
INFORMATION SCIENCES, 2021, 543 :309-327
[38]   AN AUTOMATIC SELECTION METHOD OF KEY SEARCH ALGORITHMS [J].
SHISHIBORI, M ;
AOE, J ;
PARK, KH ;
MOCHIZUKI, H .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1995, E78D (04) :383-393
[39]   Quantum Online Streaming Algorithms with Logarithmic Memory [J].
Kamil Khadiev ;
Aliya Khadieva .
International Journal of Theoretical Physics, 2021, 60 :608-616
[40]   Online Stochastic Matching: New Algorithms and Bounds [J].
Brian Brubach ;
Karthik Abinav Sankararaman ;
Aravind Srinivasan ;
Pan Xu .
Algorithmica, 2020, 82 :2737-2783