There is a large class of prior work. Below, we list a few that we built upon as we did this work. We are aware that this is a partial list and apologize in advance for omissions.
Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches by Cormode, Garofalakis, Haas and Jermaine.
Optimized stratified sampling for approximate query processing by Chaudhuri, Das and Narasayya.
BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data by Agarwal, Panda, Mozafari, Madden and Stoica.
A Sampling Algebra for Aggregate Estimation by Nirkhiwale, Dobra and Jermaine.
