Towards Linear Algebra over Normalized Data

By Lingjiao Chen, Arun Kumar, Jeffrey F. Naughton, Jignesh M. Patel. 2016

99 citations recorded by the source corpus.

Providing machine learning (ML) over relational data is a mainstream requirement for data analytics systems. While almost all ML tools require the input data to be presented as a single table, many datasets are multi-table. This forces data scientists to join those tables first, which often leads to data redundancy and runtime waste. Recent works on "factorized" ML mitigate this issue for a few specific ML algorithms by pushing ML through joins. But their approaches require a manual rewrite of ML implementations. Such piecemeal methods create a massive development overhead when extending such ideas to other ML algorithms. In this paper, we show that it is possible to mitigate this overhead by leveraging a popular formal algebra to represent the computations of many ML algorithms: linear algebra. We introduce a new logical data type to represent normalized data and devise a framework of algebraic rewrite rules to convert a large set of linear algebra operations over denormalized data into operations over normalized data. We show how this enables us to automatically "factorize" several popular ML algorithms, thus unifying and generalizing several prior works. We prototype our framework in the popular ML environment R and an industrial R-over-RDBMS tool. Experiments with both synthetic and real normalized data show that our framework also yields significant speed-ups, up to 36x on real data.

Subfields: Computer Networks and Communications, Information Systems, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Yuji Roh
2. Lingjiao Chen
3. Arun Kumar
4. Geon Heo
5. Steven Euijong Whang
6. Peter Christen

In Information Systems

1. Arun Kumar
2. Lingjiao Chen
3. Geon Heo
4. Yuji Roh
5. Steven Euijong Whang

In Management Science and Operations Research

1. Arun Kumar
2. Lingjiao Chen
3. Geon Heo
4. Yuji Roh
5. Steven Euijong Whang
6. Side Li
7. Peter Christen

Citations in the corpus

• A Survey on Data Collection for Machine Learning: A Big Data - AI Integration Perspective (2018, background): “Data augmentation Deriving Latent Semantics [35], [36], [37] Entity Augmentation [30], [31] Data Integration [38], [39], [40], [41], [42], [43], [44]”
• Enabling and Optimizing Non-linear Feature Interactions in Factorized Linear Algebra (2019, methodology): “Thus, she writes ML algorithms as if only one table exists, but under the covers, the tool in [6] rewrites the algorithm to operate on C and E.”