10 citations · 21 across the 11 of their papers we have counts for
5 papers · 1 filter
Hashing for statistics over k-partitions
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg +1
In this paper we analyze a hash function for -partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. Thi…
The Power of Two Choices with Simple Tabulation
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg +1
The power of two choices is a classic paradigm for load balancing when assigning balls to bins. When placing a ball, we pick two bins according to two hash functions …
A simple and optimal ancestry labeling scheme for trees
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
We present a ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple solution. Motivat…
Approximately Minwise Independence with Twisted Tabulation
Søren Dahlgaard, Mikkel Thorup
A random hash function is -minwise if for any set , , and element , . Minwise hash functions with low bi…
Dynamic and Multi-functional Labeling Schemes
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart
We investigate labeling schemes supporting adjacency, ancestry, sibling, and connectivity queries in forests. In the course of more than 20 years, the existence of $\log n + O(\log…