LINVIEW: incremental view maintenance for complex analytical queries

Many analytics tasks and machine learning problems can be naturally expressed by iterative linear algebra programs. In this paper, we study the incremental view maintenance problem for such complex analytical queries. We develop a framework, called Linview, for capturing deltas of linear al-gebra programs and understanding their computational cost. Linear algebra operations tend to cause an avalanche effect where even very local changes to the input matrices spread out and infect all of the intermediate results and the final view, causing incremental view maintenance to lose its per-formance benefit over re-evaluation. We develop techniques based on matrix factorizations to contain such epidemics of change. As a consequence, our techniques make incremen-tal view maintenance of linear algebra practical and usually substantially cheaper than re-evaluation. We show, both an-alytically and experimentally, the usefulness of these tech-niques when applied to standard analytics tasks. Our evalu-ation demonstrates the efficiency of Linview in generating parallel incremental programs that outperform re-evaluation techniques by more than an order of magnitude. 1