5 papers · 1 filter
Load Balancing with Dynamic Set of Balls and Bins
Anders Aamand, Jakob Bæk Tejs Knudsen, Mikkel Thorup
In dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any b…
No Repetition: Fast Streaming with Highly Concentrated Hashing
Anders Aamand, Debarati Das, Evangelos Kipouridis +3
To get estimators that work within a certain error bound with high probability, a common strategy is to design one that works with constant probability, and then boost the probabil…
Fast hashing with Strong Concentration Bounds
Anders Aamand, Jakob B. T. Knudsen, Mathias B. T. Knudsen +2
Previous work on tabulation hashing by Patrascu and Thorup from STOC'11 on simple tabulation and from SODA'13 on twisted tabulation offered Chernoff-style concentration bounds on h…
Non-Empty Bins with Simple Tabulation Hashing
Anders Aamand, Mikkel Thorup
We consider the hashing of a set with using a simple tabulation hash function and analyse the number of non-empty bins, that is,…
Power of Choices with Simple Tabulation
Anders Aamand, Mathias Bæk Tejs Knudsen, Mikkel Thorup
Suppose that we are to place balls into bins sequentially using the -choice paradigm: For each ball we are given a choice of bins, according to hash functions $h…