DAQ: A New Paradigm for Approximate Query Processing

Summary: DAQ replaces probabilistic AQP with deterministic approximation, forming a closed algebra and key design principles. Demonstrates a deterministic online approximation using a bitsliced index; MSBs first; speedups over exact aggregation and beating sampling for extremes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb0a4cb424087aabd
Venue: VLDB
Year: 2015
Pagerank: 8.80823e-05
Overall Rank: 2,224 | 85.05%
DOI: 10.14778/2777598.2777600

Incoming Non-self Citations Over Time

Authors

1. Navneet Potti (University of Wisconsin)
2. Jignesh M. Patel (University of Wisconsin)

BibTeX Citation

@article{potti_vldb15,
        title = {{DAQ: A New Paradigm for Approximate Query Processing}},
        author = {Potti, Navneet and Patel, Jignesh M.},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {9},
        pages = {898--909},
        doi = {10.14778/2777598.2777600},
        url = {https://doi.org/10.14778/2777598.2777600},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,829	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.5510333e-05
1,973	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2834606e-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,450	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	8.4474092e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
3,613	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.162283e-05
6,004	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9166815e-05
6,682	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.7093663e-05
8,166	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	5.3849926e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-05
12,052	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.9793485e-05
12,083	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.9793485e-05
12,117	Demonstration of ScroogeDB: Getting More Bang For the Buck with Deterministic Approximation in the Cloud	2020	VLDB	4.9793485e-05
12,142	A Holistic Approach for Query Evaluation and Result Vocalization in Voice-Based OLAP	2019	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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.00076195956
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033460288
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026784195
664	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00014995058
948	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012914559
1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010693831
1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3837729e-05
2,677	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.1461074e-05
3,666	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.1179861e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	309	Approximate Query Processing Using Wavelets	2000	VLDB
2	4,213	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
3	9,937	Approximate Query Processing for Interactive Data Science	2017	SIGMOD
4	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
5	11,079	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
6	6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
7	3,419	Revisiting Reuse for Approximate Query Processing	2017	VLDB
8	1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD
9	2,000	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	931	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD