35 citations · 151 across the 21 of their papers we have counts for
4 papers · 1 filter
Skew Strikes Back: New Developments in the Theory of Join Algorithms
Hung Q. Ngo, Christopher Re, Atri Rudra
Evaluating the relational join is one of the central algorithmic and most well-studied problems in database systems. A staggering number of variants have been considered including…
Accurate Decoding of Pooled Sequenced Data Using Compressed Sensing
Denisa Duma, Mary Wootters, Anna C. Gilbert +6
In order to overcome the limitations imposed by DNA barcoding when multiplexing a large number of samples in the current generation of high-throughput sequencing instruments, we ha…
L2/L2-foreach sparse recovery with low risk
Anna C. Gilbert, Hung Q. Ngo, Ely Porat +2
In this paper, we consider the "foreach" sparse recovery problem with failure probability . The goal of which is to design a distribution over matrices and a de…
Beyond Worst-Case Analysis for Joins with Minesweeper
Hung Q. Ngo, Dung T. Nguyen, Christopher Ré +1
We describe a new algorithm, Minesweeper, that is able to satisfy stronger runtime guarantees than previous join algorithms (colloquially, `beyond worst-case guarantees') for data…