Structure-Aware Sampling: Flexible and Accurate Summarization

Summary: Introduces variance-optimal, structure-aware sampling that exploits hierarchies, order, and product spaces to improve range-query accuracy. Unlike range-specialized summaries, it retains flexible, unbiased subset-sum estimation and confidence bounds, including for queries spanning multiple ranges. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h957dd729edc4a343
Venue: VLDB
Year: 2011
Pagerank: 5.4971023e-05
Overall Rank: 7,557 | 49.20%
DOI: 10.14778/3402707.3402721

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen (AT&T)
2. Graham Cormode (AT&T)
3. Nick Duffield (AT&T)

BibTeX Citation

@article{cohen_vldb11,
        title = {{Structure-Aware Sampling: Flexible and Accurate Summarization}},
        author = {Cohen, Edith and Cormode, Graham and Duffield, Nick},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {11},
        pages = {819--830},
        doi = {10.14778/3402707.3402721},
        url = {https://doi.org/10.14778/3402707.3402721},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05
8,776	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.2800094e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013381261
1,077	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012154948

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,655	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
2	2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
3	175	Simple Random Sampling from Relational Databases	1986	VLDB
4	4,792	Error-bounded Sampling for Analytics on Big Sparse Data	2014	VLDB
5	6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
6	7,513	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
7	8,553	Sampling Big Ideas in Query Optimization	2023	PODS
8	8,739	Modeling High-Dimensional Index Structures using Sampling	2001	SIGMOD
9	3,305	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS
10	153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD