47 citations · 93 across the 6 of their papers we have counts for
8 papers
Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes
Rasmus Pagh, S. Srinivasa Rao
Let S be a finite, ordered alphabet, and let x = x_1 x_2 ... x_n be a string over S. A "secondary index" for x answers alphabet range queries of the form: Given a range [a_l,a_r] o…
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…
Generic Global Constraints based on MDDs
Peter Tiedemann, Henrik Reif Andersen, Rasmus Pagh
Constraint Programming (CP) has been successfully applied to both constraint satisfaction and constraint optimization problems. A wide variety of specialized global constraints pro…
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…