9 citations · 15 across the 3 of their papers we have counts for
3 papers · 1 filter
Sampling to estimate arbitrary subset sums
Nick Duffield, Carsten Lund, Mikkel Thorup
Starting with a set of weighted items, we want to create a generic sample of a certain size that we can later use to estimate the total weight of arbitrary subsets. For this purpos…
Maintaining Information in Fully-Dynamic Trees with Top Trees
Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg +1
We introduce top trees as a design of a new simpler interface for data structures maintaining information in a fully-dynamic forest. We demonstrate how easy and versatile they are…
Dynamic Ordered Sets with Exponential Search Trees
Arne Andersson, Mikkel Thorup
We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures…