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: 11388
Venue: VLDB
Year: 2015
Pagerank: 8.957715e-05
Overall Rank: 2,206 | 84.87%
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
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,799	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.7326398e-05
1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.3978414e-05
1,995	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.3403665e-05
2,023	Decomposed Bounded Floats for Fast Compression and Queries	2021	VLDB	9.2950046e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
3,595	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	7.2736195e-05
3,684	ThalamusDB: Approximate Query Processing on Multi-Modal Data	2024	SIGMOD	7.2033959e-05
5,906	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	6.0457047e-05
6,556	Hierarchical Residual Encoding for Multiresolution Time Series Compression	2023	SIGMOD	5.8404094e-05
8,002	Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints	2020	SIGMOD	5.5085906e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
11,749	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	5.093636e-05
11,781	Demonstration of BitGourmet: Data Analysis via Deterministic Approximation	2020	SIGMOD	5.093636e-05
11,815	Demonstration of ScroogeDB: Getting More Bang For the Buck with Deterministic Approximation in the Cloud	2020	VLDB	5.093636e-05
11,841	A Holistic Approach for Query Evaluation and Result Vocalization in Voice-Based OLAP	2019	SIGMOD	5.093636e-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.00077458002
104	Improved Query Performance with Variant Indexes	1997	SIGMOD	0.00033932213
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
648	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00015324657
931	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00013125812
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
1,872	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.5759874e-05
2,633	Relational Confidence Bounds Are Easy With The Bootstrap*	2005	SIGMOD	8.3224527e-05
3,597	Bit-Sliced Index Arithmetic	2001	SIGMOD	7.2721197e-05

Semantically Similar Papers

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