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.5400509e-05
Overall Rank: 7,375 | 50.42%
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
5,501	SemBench: A Benchmark for Semantic Query Processing Engines	2026	VLDB	6.1027188e-05
10,401	A Backend-Agnostic Compiler for Approximate Query Processing with Probabilistic Tensor Algebra	2026	SIGMOD	4.9793485e-05
11,184	FAAQP: Fast and Accurate Approximate Query Processing based on Bitmap-augmented Sum-Product Network	2025	SIGMOD	4.9793485e-05
11,315	Improving Time Series Data Compression in Apache IoTDB	2025	VLDB	4.9793485e-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
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
318	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021167555
784	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014012614
931	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013011667
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010693831
1,542	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	0.00010308631
1,797	IDEBench: A Benchmark for Interactive Data Exploration	2020	SIGMOD	9.6187325e-05
1,829	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	9.5510333e-05
1,916	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	9.3837729e-05
3,424	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	7.3117029e-05
4,462	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.5880099e-05
4,781	Learned Approximate Query Processing: Make it Light, Accurate and Fast	2021	CIDR	6.4162085e-05
5,534	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	6.0923159e-05
6,221	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	5.8463347e-05
8,331	LAQy: Efficient and Reusable Query Approximations via Lazy Sampling	2023	SIGMOD	5.3532622e-05
9,209	NeuroSketch: Fast and Approximate Evaluation of Range Aggregate Queries with Neural Networks	2023	SIGMOD	5.2061781e-05

Semantically Similar Papers

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