With the continuous growth of datasets in Data Lakes, computing linear regression models poses significant challenges in terms of memory footprint and communication overhead when data is distributed across multiple machines. This thesis explores the problem of approximating matrix products in distributed settings where sketches of matrices must be computed independently using a shared random seed. Coordinated random sampling provides an alternative to classical linear sketching methods like Johnson-Lindenstrauss projection, and outperforms them when the matrices are sparse. The tradeoffs and limitations of the algorithm are analyzed both by using synthetic data and real-world datasets.
Con la continua crescita dei dataset all'interno dei Data Lake, l'elaborazione di modelli di regressione lineare pone sfide significative in termini di memoria e overhead di comunicazione quando i dati sono distribuiti su macchine distinte. Questa tesi esplora il problema di approssimare prodotti matriciali in contesti distribuiti, in cui gli sketch vengono generati in modo indipendente tramite un seed casuale condiviso. Il campionamento casuale coordinato (coordinated random sampling) offre una valida alternativa ai metodi classici di sketching lineare, come la proiezione di Johnson-Lindenstrauss, superandoli in termini di prestazioni in presenza di matrici sparse. I compromessi e le limitazioni dell'algoritmo sono analizzati sia utilizzando dati sintetici che dataset reali.
Experimental Evaluation of Matrix Product Sketching
RORATO, DAVIDE
2025/2026
Abstract
With the continuous growth of datasets in Data Lakes, computing linear regression models poses significant challenges in terms of memory footprint and communication overhead when data is distributed across multiple machines. This thesis explores the problem of approximating matrix products in distributed settings where sketches of matrices must be computed independently using a shared random seed. Coordinated random sampling provides an alternative to classical linear sketching methods like Johnson-Lindenstrauss projection, and outperforms them when the matrices are sparse. The tradeoffs and limitations of the algorithm are analyzed both by using synthetic data and real-world datasets.| File | Dimensione | Formato | |
|---|---|---|---|
|
Rorato_Davide.pdf
Accesso riservato
Dimensione
1.12 MB
Formato
Adobe PDF
|
1.12 MB | Adobe PDF |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/114290