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.
2025
Experimental Evaluation of Matrix Product Sketching
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.
Matrix Sketching
Coordinated Sampling
Matrix Product
File in questo prodotto:
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/114290