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: 10502
Venue: VLDB
Year: 2011
Pagerank: 5.6229876e-05
Overall Rank: 7,419 | 49.10%
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,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
8,616	CoopStore: Optimizing Precomputed Summaries for Aggregation	2020	VLDB	5.4004741e-05
11,519	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.093636e-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
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013619394
1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012401532

Semantically Similar Papers

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