Analysis and Application of Adaptive Sampling
Summary: Links descriptive complexity to query-size estimation: some definable queries lack fast estimators, yet on bounded-degree structures every FO query has a fast adaptive-sampling estimator. Offers average-case analysis and improved upper bound for the original adaptive sampler, compares it to newer adaptive and Monte‑Carlo variants (incomparable), and shows adaptive sampling can beat Monte‑Carlo when data maxima are known. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,827 | Containment Join Size Estimation: Models and Methods | 2003 | SIGMOD | 4.6411831e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 367 | Sequential Sampling Procedures For Query Size Estimation | 1992 | SIGMOD | 0.00025509745 |
| 688 | Estimating the Size of Generalized Transitive Closures | 1989 | VLDB | 0.00018134733 |
| 6,255 | Queries are easier than you thought (probably) | 1992 | PODS | 5.1367617e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,962 | Adaptive threshold sampling | 2022 | SIGMOD | 4.2294678e-05 |
| 2,995 | A Sampling Algebra for Aggregate Estimation | 2013 | VLDB | 7.7587199e-05 |
| 184 | New Sampling-Based Summary Statistics for Improving Approximate Query Answers | 1998 | SIGMOD | 0.00036625711 |
| 11,446 | Index-Based Join Size Estimation Using Adaptive Sampling | 2021 | SIGMOD | 4.1945683e-05 |
| 39 | Statistical Estimators for Relational Algebra Expressions | 1988 | PODS | 0.00074745564 |
| 315 | Error-Constrained COUNT Query Evaluation in Relational Databases | 1991 | SIGMOD | 0.0002802103 |
| 8,350 | alpha to omega: The Greek Alphabet of Sampling | 2020 | CIDR | 4.5404832e-05 |
| 367 | Sequential Sampling Procedures For Query Size Estimation | 1992 | SIGMOD | 0.00025509745 |
| 92 | Practical Selectivity Estimation through Adaptive Sampling | 1990 | SIGMOD | 0.00051315959 |
| 762 | Query Size Estimation by Adaptive Sampling (Extended Abstract) | 1990 | PODS | 0.00017036868 |