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: h4de5bb912454def0
Venue: VLDB
Year: 2024
Pagerank: 5.5273291e-05
Overall Rank: 7,365 | 50.64%
DOI: 10.14778/3648160.3648181
PDF: Download (CC BY-NC-ND 4.0)

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
4,996	SemBench: A Benchmark for Semantic Query Processing Engines	2026	VLDB	6.3095672e-05
10,479	A Backend-Agnostic Compiler for Approximate Query Processing with Probabilistic Tensor Algebra	2026	SIGMOD	4.9605343e-05
11,252	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	4.9605343e-05
11,377	Improving Time Series Data Compression in Apache IoTDB	2025	VLDB	4.9605343e-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
285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022143946
320	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021128745
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
935	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00012968914
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,435	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010659454
1,541	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010288394
1,804	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.5971444e-05
1,839	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.5187688e-05
1,924	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3535088e-05
3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.2845431e-05
4,480	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.566036e-05
4,792	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.4010108e-05
5,552	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	6.0707348e-05
6,198	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8362492e-05
8,349	LAQy: Efficient and Reusable Query Approximations via Lazy Sampling	2023	SIGMOD	5.3332512e-05
9,240	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	5.1867235e-05

Semantically Similar Papers

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