BitGourmet: Deterministic Approximation via Optimized Bit Selection

Summary: BitGourmet deterministically approximates SQL aggregates by storing data as bit-vectors and processing an optimal subset of bit positions to guarantee result bounds. Leverages bit-level cost/error models, a multi-objective optimizer, specialized operators and predictive buffering; reports speedups vs exact processing and tighter errors than sampling. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 383
Venue: CIDR
Year: 2020
Pagerank: 5.093636e-05
Overall Rank: 11,749 | 19.40%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Saehan Jo (Cornell University)
2. Immanuel Trummer (Cornell University)

BibTeX Citation

@inproceedings{jo_cidr20,
        address = {Amsterdam, Netherlands},
        series = {{CIDR} '20},
        title = {{BitGourmet: Deterministic Approximation via Optimized Bit Selection}},
        booktitle = {Proceedings of the {Conference} on {Innovative} {Data} {Systems} {Research}},
        author = {Jo, Saehan and Trummer, Immanuel},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,684	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	7.2033959e-05
7,316	SpareLLM: Automatically Selecting Task-Specific Minimum-Cost Large Language Models under Equivalence Constraint	2025	SIGMOD	5.646695e-05
11,781	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	5.093636e-05
11,815	Demonstration of ScroogeDB: Getting More Bang For the Buck with Deterministic Approximation in the Cloud	2020	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,995	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.3403665e-05
2,206	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB	8.957715e-05
2,413	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.6116764e-05
2,663	Partial Results in Database Systems	2014	SIGMOD	8.2818137e-05
3,157	Turbo-Charging Estimate Convergence in DBO	2009	VLDB	7.6911286e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,595	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.2736195e-05
6,021	Identifying the Extent of Completeness of Query Answers over Partially Complete Databases	2015	SIGMOD	6.0050351e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
2	2,206	DAQ: A New Paradigm for Approximate Query Processing	2015	VLDB
3	3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
4	2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
5	1,894	Optimizing Queries On Compressed Bitmaps	2000	VLDB
6	4,136	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
7	10,634	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
8	4,849	Bitvector-aware Query Optimization for Decision Support Queries	2020	SIGMOD
9	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	11,781	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD