Automatic Generation of Online Algorithms from Batch Versions

This research article presents a novel methodology for automatically synthesizing online streaming algorithms from their offline counterparts. The authors introduce a synthesis algorithm that utilizes the concept of relational function signatures (RFS) to derive online implementations from offline algorithms. The methodology decomposes the synthesis problem into independent subtasks, which are solved using a combination of symbolic reasoning and search techniques. The proposed approach is implemented in a tool named Opera, which has been evaluated on over 50 tasks across two domains: statistical computations and online auctions. Results indicate that Opera can successfully derive the online version of the original algorithm for 98% of the tasks, significantly outperforming alternative approaches, including adaptations of SyGuS solvers. The paper also discusses the challenges of designing online algorithms compared to offline ones and highlights the advantages of the proposed synthesis technique in automating the conversion process.