PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression

Summary: PairwiseHist: histogram-based AQP using recursive hypothesis testing to produce accurate pairwise-aware synopses. Operates directly on Generalized Deduplication-compressed data, giving higher accuracy, lower latency, much smaller synopses and faster builds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13574
Venue: VLDB
Year: 2024
Pagerank: 5.6354898e-05
Overall Rank: 7,351 | 49.57%
DOI: 10.14778/3648160.3648181

Incoming Non-self Citations Over Time

Authors

1. Aaron Hurst (Aarhus University)
2. Daniel E. Lucani (Aarhus University)
3. Qi Zhang (Aarhus University)

BibTeX Citation

@article{hurst_vldb24,
        title = {{PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression}},
        author = {Hurst, Aaron and Lucani, Daniel E. and Zhang, Qi},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {6},
        pages = {1432--1445},
        doi = {10.14778/3648160.3648181},
        url = {https://doi.org/10.14778/3648160.3648181},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,868	SemBench: A Benchmark for Semantic Query Processing Engines	2026	VLDB	5.3546848e-05
10,185	A Backend-Agnostic Compiler for Approximate Query Processing with Probabilistic Tensor Algebra	2026	SIGMOD	5.093636e-05
10,760	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	5.093636e-05
10,923	Improving Time Series Data Compression in Apache IoTDB	2025	VLDB	5.093636e-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
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
772	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014147905
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010460864
1,767	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.805856e-05
1,799	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.7326398e-05
1,872	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.5759874e-05
3,366	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.4748604e-05
4,405	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.7218674e-05
4,789	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.5072039e-05
5,421	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	6.2245831e-05
6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.9443409e-05
8,161	LAQy: Efficient and Reusable Query Approximations via Lazy Sampling	2023	SIGMOD	5.4752972e-05
9,101	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	5.324758e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,819	Space efficiency in Synopsis construction algorithms	2005	VLDB
2	435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB
3	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
4	3,370	Revisiting Reuse for Approximate Query Processing	2017	VLDB
5	1,962	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
6	5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB
7	6,206	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD
8	10,760	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD
9	10,634	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
10	610	Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences	1997	SIGMOD