Data Driven Approximation with Bounded Resources

Summary: BEAS answers arbitrary relational queries under an α-fraction data-access budget, returning exact results when possible and otherwise deterministic approximations. Its access schema, relevance/coverage metric, approximability theorem, and evaluation algorithms support aggregates and unpredictable queries. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11778
Venue: VLDB
Year: 2017
Pagerank: 5.3828806e-05
Overall Rank: 8,701 | 40.31%
DOI: 10.14778/3099622.3099627

Incoming Non-self Citations Over Time

Authors

1. Yang Cao (Beihang University; University of Edinburgh)
2. Wenfei Fan (Beihang University; University of Edinburgh)

BibTeX Citation

@article{cao_vldb17,
        title = {{Data Driven Approximation with Bounded Resources}},
        author = {Cao, Yang and Fan, Wenfei},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {9},
        pages = {973--984},
        doi = {10.14778/3099622.3099627},
        url = {https://doi.org/10.14778/3099622.3099627},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
8,492	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.4145838e-05
11,867	Block as a Value for SQL over NoSQL	2019	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,072	Regret-Minimizing Representative Databases	2010	VLDB	0.0001230281
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
2,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.1927747e-05
4,393	Bounded Conjunctive Queries	2014	VLDB	6.7280426e-05
5,878	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	6.0539311e-05
6,841	Querying Big Data by Accessing Small Data	2015	PODS	5.7574257e-05
7,484	On Scale Independence for Querying Big Data	2014	PODS	5.6074278e-05
9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	5.3346995e-05
12,029	Bounded Query Rewriting Using Views	2016	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,674	Benchmarking Approximate Consistent Query Answering	2021	PODS
2	8,260	Efficient Uncertainty Tracking for Complex Queries with Attribute-level Bounds	2021	SIGMOD
3	2,206	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB
4	9,002	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD
5	3,907	Accelerating Approximate Aggregation Queries with Expensive Predicates	2021	VLDB
6	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS
7	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD
8	6,841	Querying Big Data by Accessing Small Data	2015	PODS
9	9,353	On Efficient Approximate Queries over Machine Learning Models	2023	VLDB
10	11,990	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD