Report on the First International Workshop on Incremental Re-computation: Provenance and Beyond

Abstract

In the last decade, advances in computing have deeply transformed data processing. Increasingly systems aim to process massive amounts of data efficiently, often with fast response times that are typically characterised by the 4V's, i.e., Volume, Variety, Velocity, and Veracity. While fast data processing is desirable, it is also often the case that the outcomes of computationally expensive processes become obsolete over time, due to changes in inputs, reference datasets, tools, libraries, and deployment environment. Given massive data processing, such changes must be carefully accounted for, and their impact on original computation assessed, to determine how much re-computation is needed in response to changes.

References

1. Anand, M. K., Bowers, S., McPhillips, T. M., and Lud¨ascher, B. Exploring Scientific Workflow Provenance Using Hybrid Queries over Nested Data and Lineage Graphs. In SSDBM (2009), pp. 237--254.
2. Cai, Y., Giarrusso, P. G., Rendel, T., and Ostermann, K. A theory of changes for higher-order languages: Incrementalizing γ-calculi by static differentiation. In ACM SIGPLAN Notices (2014), vol. 49, ACM, pp. 145--155.
3. Ca la, J., and Missier, P. Selective and Recurring Re-computation of Big Data Analytics Tasks: Insights from a Genomics Case Study. Big Data Research in press (aug 2018).
4. Cheney, J., Acar, U. A., and Perera, R. Toward a Theory of Self-explaining Computation. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 193--216.
5. Cheney, J., Chiticariu, L., and Tan, W.-C. Provenance in databases: Why, how, and where. Foundations and Trends in Databases 1, 4 (2009), 379--474.
6. Griffin, T., Libkin, L., and Trickey, H. An improved algorithm for the incremental recomputation of active relational expressions. IEEE Transactions on Knowledge and Data Engineering (1997).
7. Horn, R., Perera, R., and Cheney, J. Incremental relational lenses. Proc. ACM Program. Lang. 2, ICFP (July 2018), 74:1--74:30.
8. K¨ohler, S., Riddle, S., Zinn, D., McPhillips, T., and Lud¨ascher, B. Improving workflow fault tolerance through provenance-based recovery. In SSDBM (2011), pp. 207--224.
9. Krishnan, D. R., Quoc, D. L., Bhatotia, P., Fetzer, C., and Rodrigues, R. Incapprox: A data analytics system for incremental approximate computing. In 25th International Conference on World Wide Web (2016), pp. 1133--1144.
10. Lud¨ascher, B., Altintas, I., Berkley, C., Higgins, D., Jaeger, E., Jones, M., Lee, E. A., Tao, J., and Zhao, Y. Scientific Workflow Management and the Kepler System. Concurrency and Computation: Practice and Experience 18, 10 (2005), 1039--1065.
11. McSherry, F., Murray, D. G., Isaacs, R., and Isard, M. Differential dataflow. In CIDR (2013).
12. Murray, D. G., McSherry, F., Isaacs, R., Isard, M., Barham, P., and Abadi, M. Naiad: a timely dataflow system. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (2013), ACM, pp. 439--455.
13. Pham, Q., Malik, T., and Foster, I. Using Provenance for Repeatability. In TaPP (2013).
14. Souza, R., and Mattoso, M. Provenance of dynamic adaptations in user-steered dataflows. In IPAW (2018), pp. 16--29.