BlinkFill: Semi supervised Programming By Example for Syntactic String Transformations
The recent Programming By Example (PBE) techniques such as FlashFill have shown great promise for enabling end users to perform data transformation tasks using input output examples. Since examples are inherently an under specification, there are typically a large number of hypotheses conforming to the examples, and the PBE techniques suffer from scalability issues for finding the intended program amongst the large space. We present a semi supervised learning technique to significantly reduce this ambiguity by using the logical information present in the input data to guide the synthesis algorithm. We develop a data structure InputDataGraph to succinctly represent a large set of logical patterns that are shared across the input data, and use this graph to efficiently learn substring expressions in a new PBE system BlinkFill. We evaluate BlinkFill on 207 real world benchmarks and show that BlinkFill is significantly faster (on average 41x) and requires fewer input output examples (1.27 vs 1.53) to learn the desired transformations in comparison to FlashFill.
Proc. VLDB Endow.