## Project MorpheusIntegrating Linear Algebra with JoinsKeywords: Relational Joins / Database Dependencies Large-scale Machine Learning Feature Engineering R-based Analytics Systems |

Providing machine learning (ML) over relational data is a mainstream requirement for data analytics systems.
While almost all the ML tools require the input data to be presented as a single table, many datasets are multi-table,
which forces data scientists to join those tables first, leading 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.

By integrating linear algebra with the fundamental and ubiquitous relational join operation, this work sets the
stage for a holistic unification of linear and relational algebras for seamless feature engineering and learning
over structured data.
There is also a long-standing and yet unresolved debate in the data management community as to whether it is better
to bring linear algebra to relational systems or relational algebra to linear algebra systems.
While this work is largely orthogonal to this debate, we hope and believe that advancing our understanding of the
fundamental interactions of these frameworks will lead to more usable and efficient advanced analytics systems.

Blog post on Morpheus

- Paper at VLDB 2017
- Technical Report
- Morpheus Code on GitHub (R library for normalized matrix and factorized linear algebra; example ML algorithms)
- Real-world datasets (Based on the Hamlet datasets)

- Lingjiao Chen
- Arun Kumar
- Jeffrey Naughton
- Jignesh Patel