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: 13096
Venue: VLDB
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,612 | 20.34%
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
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
1,516	Cardinality Estimation: An Experimental Survey	2018	VLDB	0.00010520885
3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.376137e-05

Semantically Similar Papers

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