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.698367e-05
Overall Rank: 4,254 | 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,610	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	6.0660772e-05
6,285	Mosaic: A Sample-Based Database System for Open World Query Processing	2020	CIDR	5.8209714e-05
6,877	Consistent Range Approximation for Fair Predictive Modeling	2023	VLDB	5.6564538e-05
7,710	ReStore - Neural Data Completion for Relational Databases	2021	SIGMOD	5.471539e-05
9,022	Memory-Efficient and Flexible Detection of Heavy Hitters in High-Speed Networks	2023	SIGMOD	5.235015e-05
11,247	Holistic query Approximation via RL Modeling	2025	VLDB	4.9769913e-05
11,430	New Trends in Data Forgetting for Sustainable Data Management	2025	VLDB	4.9769913e-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.00061067652
24	Data Integration: A Theoretical Perspective	2002	PODS	0.00055018384
286	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00022112534
417	MauveDB: Supporting Model-based User Views in Database Systems	2006	SIGMOD	0.00018625112
1,061	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012208639
1,543	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010305662
1,722	A Sample-and-Clean Framework for Fast and Accurate Query Processing on Dirty Data	2014	SIGMOD	9.7921604e-05
1,797	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.6143465e-05
1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3822742e-05
2,003	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.2071735e-05
2,028	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1584244e-05
2,461	Leveraging Aggregate Constraints For Deduplication	2007	SIGMOD	8.4279724e-05
3,417	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3184905e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3084429e-05
5,088	Differential Privacy and the US Census	2019	PODS	6.279352e-05
8,301	NetCube: A Scalable Tool for Fast Data Mining and Compression	2001	VLDB	5.3587028e-05
8,367	Probabilistic Database Summarization for Interactive Data Exploration	2017	VLDB	5.344711e-05

Semantically Similar Papers

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