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.7015395e-05
Overall Rank: 4,253 | 71.41%
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,609	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.0689501e-05
6,282	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.8237283e-05
6,873	Consistent Range Approximation for Fair Predictive Modeling	2023	VLDB	5.6591328e-05
7,704	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.4741304e-05
9,014	Memory-Efficient and Flexible Detection of Heavy Hitters in High-Speed Networks	2023	SIGMOD	5.2374944e-05
11,239	Holistic query Approximation via RL Modeling	2025	VLDB	4.9793485e-05
11,424	New Trends in Data Forgetting for Sustainable Data Management	2025	VLDB	4.9793485e-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.00061066921
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055043581
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.0002211981
417	MauveDB: Supporting Model-based User Views in Database Systems	2006	SIGMOD	0.00018631353
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,542	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010308631
1,720	A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data	2014	SIGMOD	9.7965659e-05
1,797	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.6187325e-05
1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3837729e-05
2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2112617e-05
2,027	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1618139e-05
2,461	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.4319356e-05
3,419	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3190065e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
5,085	Differential Privacy and the US Census	2019	PODS	6.282326e-05
8,295	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.3612406e-05
8,363	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.3472423e-05

Semantically Similar Papers

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