921 citations
- University of CopenhagenDK2 papers
- Aarhus UniversityDK1 paper
- Aix-Marseille UniversitéFR1 paper
- AT&T (United States)US1 paper
- Center for Massive Data AlgorithmicsDK1 paper
- Centre de Physique ThéoriqueFR1 paper
- Centre National de la Recherche ScientifiqueFR1 paper
- Dana-Farber Cancer InstituteUS1 paper
- Harvard UniversityUS1 paper
- Institut national de recherche en sciences et technologies du numériqueFR1 paper
- Laboratoire Pluridisciplinaire de Recherche en Ingénierie des Systèmes, Mécanique et EnergétiqueFR1 paper
- Leipzig UniversityDE1 paper
6 papers · 1 filter
Counting Paths and Packings in Halves
Andreas Björklund, Thore Husfeldt, Petteri Kaski +1
It is shown that one can count -edge paths in an -vertex graph and -set -packings on an -element universe, respectively, in time and ${n \choose mk…
Succinct Data Structures for Retrieval and Approximate Membership
Martin Dietzfelbinger, Rasmus Pagh
The retrieval problem is the problem of associating data with keys in a set. Formally, the data structure must store a function f: U ->{0,1}^r that has specified values on the elem…
Fast evaluation of union-intersection expressions
Philip Bille, Anna Pagh, Rasmus Pagh
We show how to represent sets in a linear space data structure such that expressions involving unions and intersections of sets can be computed in a worst-case efficient way. This…
Perfect Hashing for Data Management Applications
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani
Perfect hash functions can potentially be used to compress data in connection with a variety of data management tasks. Though there has been considerable work on how to construct g…
Linear Probing with Constant Independence
Anna Pagh, Rasmus Pagh, Milan Ruzic
Hashing with linear probing dates back to the 1950s, and is among the most studied algorithms. In recent years it has become one of the most important hash table organizations sinc…
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…