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.7882698e-05
Overall Rank: 2,231 | 85.05%
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
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,839	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.5187688e-05
1,981	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2505963e-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,225	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	8.7996555e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
3,611	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.1443694e-05
6,014	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.8956963e-05
6,700	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.6877938e-05
8,192	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	5.3646457e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-05
12,102	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.9605343e-05
12,133	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	4.9605343e-05
12,167	Demonstration of ScroogeDB: Getting More Bang For the Buck with Deterministic Approximation in the Cloud	2020	VLDB	4.9605343e-05
12,191	A Holistic Approach for Query Evaluation and Result Vocalization in Voice-Based OLAP	2019	SIGMOD	4.9605343e-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.00076079812
107	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033376274
175	Simple Random Sampling from Relational Databases	1986	VLDB	0.00026701703
667	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00014941252
951	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00012886042
1,435	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010659454
1,924	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3535088e-05
2,682	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.1203255e-05
3,670	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.0930166e-05

Semantically Similar Papers

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