47 citations · 93 across the 6 of their papers we have counts for
5 papers · 1 filter
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…
On Dynamic Range Reporting in One Dimension
Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu
We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching i…