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: h998899832a64b2d8
Venue: SIGMOD
Year: 2020
Pagerank: 6.6762181e-05
Overall Rank: 4,270 | 71.38%
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,622	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.0460189e-05
6,300	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.8017237e-05
6,897	Consistent Range Approximation for Fair Predictive Modeling	2023	VLDB	5.6377501e-05
7,723	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.4534466e-05
9,043	Memory-Efficient and Flexible Detection of Heavy Hitters in High-Speed Networks	2023	SIGMOD	5.2177048e-05
11,303	Holistic query Approximation via RL Modeling	2025	VLDB	4.9605343e-05
11,483	New Trends in Data Forgetting for Sustainable Data Management	2025	VLDB	4.9605343e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055201845
287	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022060616
418	MauveDB: Supporting Model-based User Views in Database Systems	2006	SIGMOD	0.00018567032
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,541	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010288394
1,721	A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data	2014	SIGMOD	9.7821782e-05
1,804	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.5971444e-05
1,924	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3535088e-05
2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.1775869e-05
2,040	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1319608e-05
2,469	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.401808e-05
3,428	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.2957009e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
5,109	Differential Privacy and the US Census	2019	PODS	6.2585886e-05
8,315	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.341013e-05
8,381	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.327038e-05

Semantically Similar Papers

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