Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets

Summary: Zippy: cache-conscious top-k aggregation for high-cardinality data that leverages skew with cache-resident structures and an adaptive multi-pass candidate-identification to avoid full exact aggregation. Lightweight hashing/partition pruning, adversarial-robustness, and incremental reuse for rolling/paginated queries; median ~3x speedup for monotonic aggregates vs state-of-the-art. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h9479c9026928143e
Venue: VLDB
Year: 2024
Pagerank: 4.9769913e-05
Overall Rank: 11,672 | 21.56%
DOI: 10.14778/3636218.3636222
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Tarique Siddiqui (Microsoft)
2. Vivek Narasayya (Microsoft)
3. Marius Dumitru (Microsoft)
4. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@article{siddiqui_vldb24,
        title = {{Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets}},
        author = {Siddiqui, Tarique and Narasayya, Vivek and Dumitru, Marius and Chaudhuri, Surajit},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {4},
        pages = {644--656},
        doi = {10.14778/3636218.3636222},
        url = {https://doi.org/10.14778/3636218.3636222},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081971778
9	Online Aggregation	1997	SIGMOD	0.00076265429
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00064013679
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033518428
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030586757
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024844328
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023136934
425	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018485358
625	Adaptive Aggregation on Chip Multiprocessors	2007	VLDB	0.00015472161
963	Memory-Efficient Hash Joins	2015	VLDB	0.00012815832
1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011957053
1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010033698
1,662	Rapid Sampling for Visualizations with Ordering Guarantees	2015	VLDB	9.9502569e-05
2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD	8.7615858e-05
3,784	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	7.0197908e-05
4,184	YADING: Fast Clustering of Large-Scale Time Series Data	2015	VLDB	6.7508911e-05
6,197	Patience is a Virtue: Revisiting Merge and Sort on Modern Processors	2014	SIGMOD	5.8518899e-05
7,068	Efficient Top-K Query Processing on Massively Parallel Hardware	2018	SIGMOD	5.6060783e-05
9,355	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.1876576e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,355	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD
2	2,799	Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries	2018	VLDB
3	3,328	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB
4	7,396	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
5	8,109	Ranking Large Temporal Data	2012	VLDB
6	7,518	Computing A Well-Representative Summary of Conjunctive Query Results	2024	PODS
7	8,458	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
8	3,380	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
9	2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD
10	3,784	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD