No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing

Summary: Tabulation-1Permutation hashing enables fast, reliable sampling without repetition. With equal space, it achieves high-probability bounds directly, outperforms repetition-based methods and hashes like MurmurHash3/BLAKE3 in tight error regimes, validated empirically. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3be3520d02ec223d
Venue: VLDB
Year: 2022
Pagerank: 4.9793485e-05
Overall Rank: 11,920 | 19.86%
DOI: 10.14778/3565838.3565851

Incoming Non-self Citations Over Time

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

Authors

1. Anders Aamand (Massachusetts Institute of Technology)
2. Debarati Das (Pennsylvania State University)
3. Evangelos Kipouridis (University of Copenhagen)
4. Jakob B. T. Knudsen (University of Copenhagen)
5. Peter M. R. Rasmussen (University of Copenhagen)
6. Mikkel Thorup (University of Copenhagen)

BibTeX Citation

@article{aamand_vldb22,
        title = {{No Repetition: Fast and Reliable Sampling with Highly Concentrated Hashing}},
        author = {Aamand, Anders and Das, Debarati and Kipouridis, Evangelos and Knudsen, Jakob B. T. and Rasmussen, Peter M. R. and Thorup, Mikkel},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {13},
        pages = {3989--4001},
        doi = {10.14778/3565838.3565851},
        url = {https://doi.org/10.14778/3565838.3565851},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
707	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014640173
1,536	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010327422
3,540	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.2161972e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,388	Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond	2026	PODS
2	5,534	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
3	3,858	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS
4	4,564	Relative Error Streaming Quantiles	2021	PODS
5	252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD
6	1,826	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD
7	12,329	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
8	6,865	Fast Range-Summable Random Variables for Efficient Aggregate Estimation	2006	SIGMOD
9	1,229	Random Sampling from Hash Files	1990	SIGMOD
10	9,003	Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity	2022	SIGMOD