Fetching the paper…
Reading the bibliography…
Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical.
Notes on open addressing
D. E. Knuth · 1963
Earlier work this paper cites.
A new hashing method with application for game playing
A. L. Zobrist · 1970
Earlier work this paper cites.
The Art of Computer Programming, Volume III: Sorting and Searching
D. E. Knuth · 1973
Earlier work this paper cites.
Universal classes of hash functions
L. Carter and M. N. Wegman · 1979
Earlier work this paper cites.
New classes and applications of hash functions
M. N. Wegman and L. Carter · 1981
Earlier work this paper cites.
Storing a sparse table with 0(1) worst case access time
M. L. Fredman, J. Komlós, and E. Szemerédi · 1984
Earlier work this paper cites.
Probabilistic counting algorithms for data base applications
P. Flajolet and G. N. Martin · 1985
Earlier work this paper cites.
A new universal class of hash functions and dynamic hashing in real time
M. Dietzfelbinger and F. Meyer auf der Heide · 1990
Earlier work this paper cites.
Randomized algorithms and pseudorandom numbers
H. J. Karloff and P. Raghavan · 1993
Earlier work this paper cites.
Randomized Algorithms
R. Motwani and P. Raghavan · 1995
Earlier work this paper cites.
Chernoff-Hoeffding bounds for applications with limited independence
J. P. Schmidt, A. Siegel, and A. Srinivasan · 1995
Earlier work this paper cites.
Universal hashing and k k -wise independent random variables via integer arithmetic without primes
M. Dietzfelbinger · 1996
Earlier work this paper cites.
Randomized search trees
R. Seidel and C. R. Aragon · 1996
Earlier work this paper cites.
Syntactic clustering of the web
A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig · 1997
Earlier work this paper cites.
A reliable randomized algorithm for the closest-pair problem
M. Dietzfelbinger, T. Hagerup, J. Katajainen, and M. Penttonen · 1997
Earlier work this paper cites.
Graph and hashing algorithms for modern architectures: Design and performance
J. R. Black, C. U. Martel, and H. Qi · 1998
Earlier work this paper cites.
Linear hash functions
N. Alon, M. Dietzfelbinger, P. B. Miltersen, E. Petrank, and G. Tardos · 1999
Earlier work this paper cites.
The space complexity of approximating the frequency moments
N. Alon, Y. Matias, and M. Szegedy · 1999
Earlier work this paper cites.
Balanced allocations
Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal · 1999
Cited alongside, same era.
Min-wise independent permutations
A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher · 2000
Cited alongside, same era.
Even strongly universal hashing is pretty fast
M. Thorup · 2000
Cited alongside, same era.
A small approximately min-wise independent family of hash functions
P. Indyk · 2001
Cited alongside, same era.
The power of two random choices: A survey of techniques and results
M. Mitzenmacher, A. W. Richa, and R. Sitaraman · 2001
Cited alongside, same era.
Finding frequent items in data streams
M. Charikar, K. Chen, and M. Farach-Colton · 2002
Cited alongside, same era.
On the k k -independence required by linear probing and minwise independence
M. Pǎtraşcu and M. Thorup · 2010
Later among the works it cites.
Straggler identification in round-trip data streams via newton’s identities and invertible bloom filters
D. Eppstein and M. T. Goodrich · 2011
Later among the works it cites.
What’s the difference?: efficient set reconciliation without prior context
D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese · 2011
Later among the works it cites.
Invertible bloom lookup tables
M. T. Goodrich and M. Mitzenmacher · 2011
Later among the works it cites.
Timeouts with time-reversed linear probing
M. Thorup · 2011
Later among the works it cites.
One permutation hashing
P. Li, A. B. Owen, and C.-H. Zhang · 2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
M. Dietzfelbinger and P. Woelfel · 2003
Cited alongside, same era.
Cuckoo hashing
R. Pagh and F. F. Rodler · 2004
Cited alongside, same era.
On universal classes of extremely random constant-time hash functions
A. Siegel · 2004
Cited alongside, same era.
How caching affects hashing
G. L. Heileman and W. Luo · 2005
Cited alongside, same era.
k k -wise independent random graphs
N. Alon and A. Nussboim · 2008
Cited alongside, same era.
Why simple hash functions work: exploiting the entropy in a data stream
M. Mitzenmacher and S. P. Vadhan · 2008
Cited alongside, same era.
Biff (bloom filter) codes: Fast error correction for large data sets
M. Mitzenmacher and G. Varghese · 2012
Later among the works it cites.
The power of simple tabulation-based hashing
M. Pǎtraşcu and M. Thorup · 2012
Later among the works it cites.
Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
M. Thorup and Y. Zhang · 2012
Later among the works it cites.
Twisted tabulation hashing
M. Pǎtraşcu and M. Thorup · 2013
Later among the works it cites.
Simple tabulation, fast expanders, double tabulation, and high independence
M. Thorup · 2013
Later among the works it cites.
Generating k-independent variables in constant time
T. Christiani and R. Pagh · 2014
Later among the works it cites.
Approximately minwise independence with twisted tabulation
S. Dahlgaard and M. Thorup · 2014
Later among the works it cites.
Densifying one permutation hashing via rotation for fast near ne ighbor search
A. Shrivastava and P. Li · 2014
Later among the works it cites.
From independence to expansion and back again
T. Christiani, R. Pagh, and M. Thorup · 2015
Closest in time.
Hashing for statistics over k-partitions
S. Dahlgaard, M. B. T. Knudsen, E. Rotenberg, and M. Thorup · 2015
Closest in time.
The power of two choices with simple tabulation
S. Dahlgaard, M. B. T. Knudsen, E. Rotenberg, and M. Thorup · 2016
Closest in time.