Error-bounded Sampling for Analytics on Big Sparse Data

Summary: Introduces error-bounded stratified sampling for aggregation over massive, wide-range sparse data, preserving user-specified error guarantees. Distribution-aware strata reduce sample size by up to 99% versus uniform sampling, with robust performance in Microsoft’s search-query platform. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10999
Venue: VLDB
Year: 2014
Pagerank: 6.557612e-05
Overall Rank: 4,696 | 67.79%
DOI: 10.14778/2733004.2733012

Incoming Non-self Citations Over Time

Authors

1. Ying Yan (Microsoft)
2. Liang Jeff Chen (Microsoft)
3. Zheng Zhang (Microsoft)

BibTeX Citation

@article{yan_vldb14,
        title = {{Error-bounded Sampling for Analytics on Big Sparse Data}},
        author = {Yan, Ying and Chen, Liang Jeff and Zhang, Zheng},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {13},
        pages = {1508--1519},
        doi = {10.14778/2733004.2733012},
        url = {https://doi.org/10.14778/2733004.2733012},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
3,741	Spatial Online Sampling and Aggregation	2016	VLDB	7.1586403e-05
6,028	Hillview: A trillion-cell spreadsheet for big data	2019	VLDB	6.0019322e-05
6,121	The Cosmos Big Data Platform at Microsoft: Over a Decade of Progress and a Decade to Look Forward	2021	VLDB	5.9688569e-05
6,896	Wide Table Layout Optimization based on Column Ordering and Duplication	2017	SIGMOD	5.7440611e-05
7,787	A Practical Approach to Groupjoin and Nested Aggregates	2021	VLDB	5.5449593e-05
7,795	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD	5.5429229e-05
9,591	Sapprox: Enabling Efficient and Accurate Approximations on Sub-datasets with Distribution-aware Online Sampling	2017	VLDB	5.2518295e-05
10,111	Parallel Rule Discovery from Large Datasets by Sampling	2022	SIGMOD	5.1347137e-05
10,766	Incremental Rule Discovery in Response to Parameter Updates	2025	SIGMOD	5.093636e-05
12,112	STORM: Spatio-Temporal Online Reasoning and Management of Large Spatio-Temporal Data	2015	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00077458002
30	SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets	2008	VLDB	0.00051174276
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
1,009	Online Aggregation for Large MapReduce Jobs	2011	VLDB	0.00012684342
1,166	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00011850439
1,582	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010295367
2,312	Online Aggregation and Continuous Query support in MapReduce	2010	SIGMOD	8.7642158e-05
3,042	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.8231049e-05
3,096	Early Accurate Results for Advanced Analytics on MapReduce	2012	VLDB	7.7629371e-05
3,844	Distributed Online Aggregations	2009	VLDB	7.0782059e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	173	Simple Random Sampling from Relational Databases	1986	VLDB
2	6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
3	149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
4	508	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD
5	7,419	Structure-Aware Sampling: Flexible and Accurate Summarization	2011	VLDB
6	8,379	Sampling Big Ideas in Query Optimization	2023	PODS
7	1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
8	2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
9	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	8,108	Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters	2019	VLDB