Søren Dahlgaard

collaborators

3 papers

cs.DS2014

A simple and optimal ancestry labeling scheme for trees

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Noy Rotbart

We present a $l g n + 2 l g l g n + 3$ ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple $2 l g n$ solution. Motivat…

cs.DS2014

Approximately Minwise Independence with Twisted Tabulation

Søren Dahlgaard, Mikkel Thorup

A random hash function $h$ is $ε$ -minwise if for any set $S$ , $∣ S ∣ = n$ , and element $x \in S$ , $Pr [h (x) = min h (S)] = (1 \pm ε) / n$ . Minwise hash functions with low bi…

cs.DS2014

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…