LINVIEW: incremental view maintenance for complex analytical queries

Milos Nikolic, Mohammed ElSeidy, Christoph Koch

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 algebra 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 performance benefit over re-evaluation. We develop techniques based on matrix factorizations to contain such epidemics of change. As a consequence, our techniques make incremental view maintenance of linear algebra practical and usually substantially cheaper than re-evaluation. We show, both analytically and experimentally, the usefulness of these techniques when applied to standard analytics tasks. Our evaluation demonstrates the efficiency of LINVIEW in generating parallel incremental programs that outperform re-evaluation techniques by more than an order of magnitude.
Original languageEnglish
Title of host publicationProceedings of the 2014 ACM SIGMOD International Conference on Management of Data
Place of PublicationSnowbird, Utah, USA
PublisherACM
Pages253-264
Number of pages12
ISBN (Print)978-1-4503-2376-5
DOIs
Publication statusPublished - 18 Jun 2014
Event2014 SIGMODPODS Conference - Utah, Snowbird, United States
Duration: 22 Jun 201427 Jun 2014

Conference

Conference2014 SIGMODPODS Conference
Country/TerritoryUnited States
CitySnowbird
Period22/06/1427/06/14

Fingerprint

Dive into the research topics of 'LINVIEW: incremental view maintenance for complex analytical queries'. Together they form a unique fingerprint.

Cite this