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.8127129e-05
Overall Rank: 2,219 | 85.09%
DOI: 10.14778/2777598.2777600
PDF: Download (CC BY-NC-ND 3.0)

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
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.0001409096
1,061	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012208639
1,828	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.547768e-05
1,974	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2806652e-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,295	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	8.6822982e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3084429e-05
3,607	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.1645803e-05
6,002	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9149725e-05
6,686	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.7066636e-05
8,172	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	5.3824434e-05
11,542	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9769913e-05
12,058	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.9769913e-05
12,089	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.9769913e-05
12,123	Demonstration of ScroogeDB: Getting More Bang For the Buck with Deterministic Approximation in the Cloud	2020	VLDB	4.9769913e-05
12,148	A Holistic Approach for Query Evaluation and Result Vocalization in Voice-Based OLAP	2019	SIGMOD	4.9769913e-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.00076265429
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033459417
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026776696
666	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00014989211
947	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012920489
1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.0001069161
1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3822742e-05
2,672	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.1456115e-05
3,667	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.1151219e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	309	Approximate Query Processing Using Wavelets	2000	VLDB
2	4,215	Approximating Predicates and Expressive Queries on Probabilistic Databases	2008	PODS
3	9,944	Approximate Query Processing for Interactive Data Science	2017	SIGMOD
4	448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
5	11,088	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
6	6,202	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
7	3,417	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,003	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
10	930	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD