Papers โบ In-Database Regression in Input Sparsity Time
In-Database Regression in Input Sparsity Time
Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Sketching is a powerful dimensionality reduction technique for accelerating algorithms for data analysis. A crucial step in sketching methods is to compute a subspace embedding (SE) for a large matrix ๐ โโ^(N รd). SE's are the primary tool for obtaining extremely efficient solutions for many linear-algebraic tasks, such as least squares regression and low rank approximation. Computing an SE often requires an explicit representation of ๐ and running time proportional to the size of ๐. However, if ๐= ๐โ ๐โ โฆ๐โ is the result of a database join query on several smaller tables ๐แตข โโ^(nแตข รdแตข), then this running time can be prohibitive, as ๐ itself can have as many as O(nโ nโ โฏnโ) rows. In this work, we design subspace embeddings for database joins which can be computed significantly faster than computing the join. For the case of a two table join ๐ = ๐โ ๐โ we give input-sparsity algorithms for computing subspace embeddings, with running time bounded by the number of non-zero entries in ๐โ,๐โ. This results in input-sparsity time algorithms for high accuracy regression, significantly improving upon the running time of prior FAQ-based methods for regression. We extend our results to arbitrary joins for the ridge regression problem, also considerably improving the running time of prior methods. Empirically, we apply our method to real datasets and show that it is significantly faster than existing algorithms.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change ยท a person checks every report against the paper or source before anything changes; decisions are listed on /corrections