Sample Debiasing in the Themis Open World Database System

Summary: Themis is the first open-world DB that rebalances biased samples to approximate population-wide query results. It blends sample reweighting with Bayesian nets, using a priori population info to beat AQP and baselines with latency and robustness to gaps. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5881
Venue: SIGMOD
Year: 2020
Pagerank: 6.8337021e-05
Overall Rank: 4,205 | 71.16%
DOI: 10.1145/3318464.3380606

Incoming Non-self Citations Over Time

Authors

1. Laurel Orr (University of Washington)
2. Magdalena Balazinska (University of Washington)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{orr_sigmod20,
        title = {{Sample Debiasing in the Themis Open World Database System}},
        author = {Orr, Laurel and Balazinska, Magdalena and Suciu, Dan},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380606},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380606},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,510	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.1919207e-05
6,262	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.9361728e-05
7,556	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.5997742e-05
7,838	Consistent Range Approximation for Fair Predictive Modeling	2023	VLDB	5.5343411e-05
8,851	Memory-Efficient and Flexible Detection of Heavy Hitters in High-Speed Networks	2023	SIGMOD	5.357707e-05
10,831	Holistic query Approximation via RL Modeling	2025	VLDB	5.093636e-05
11,063	New Trends in Data Forgetting for Sustainable Data Management	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
22	Data Integration: A Theoretical Perspective	2002	PODS	0.00056204792
280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022454217
408	MauveDB: Supporting Model-based User Views in Database Systems	2006	SIGMOD	0.00019008806
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010460864
1,736	A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data	2014	SIGMOD	9.8984415e-05
1,767	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.805856e-05
1,872	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.5759874e-05
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
1,995	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.3403665e-05
2,410	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.6126774e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,370	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.4700891e-05
5,566	Differential Privacy and the US Census	2019	PODS	6.1712366e-05
8,121	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.4834308e-05
8,191	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.4699738e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,630	Pushing the Boundaries of Crowd-enabled Databases with Query-driven Schema Expansion	2012	VLDB
2	3,684	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD
3	4,556	A Temporal-Probabilistic Database Model for Information Extraction	2013	VLDB
4	12,222	A Social Network Database that Learns How to Answer Queries	2013	CIDR
5	2,367	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR
6	2,990	Knowledge Expansion over Probabilistic Knowledge Bases	2014	SIGMOD
7	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
8	9,280	Themis: A GPU-accelerated Relational Query Execution Engine	2025	VLDB
9	8,324	THEMIS: Fairness in Federated Stream Processing under Overload	2016	SIGMOD
10	6,262	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR