Theory and Practise of Monotone Minimal Perfect Hashing (2009)
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna
Minimal perfect hash functions have been shown to be useful to compress data in several data management tasks. In particular, order-preserving minimal perfect hash functions [12] have been used to...
Finding Associations and Computing Similarity via Biased Pair Sampling (2009)
Campagna, Andrea, Pagh, Rasmus
Sampling-based methods have previously been proposed for the problem of finding interesting associations in data, even for low-support items. While these methods do not guarantee precise results,...
Abstract Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses (2009)
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna
A minimal perfect hash function maps a set S of n keys into the set { 0, 1,..., n − 1} bijectively. Classical results state that minimal perfect hashing is possible in constant time using a...
(lat. On Dynamic Dictionaries Using Little Space)? (2008)
De Dictionariis, Dynamicis Pauco, Spatio Utentibus, Erik D. Demaine, Rasmus Pagh
1 Introduction The dictionary is one of the most fundamental data-structural problems in com-puter science. In its basic form, a dictionary allows some form of "lookup " on a set S...
Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes (2008)
Pagh, Rasmus, Rao, S. Srinivasa
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] over S, return the...
ABSTRACT Scalable Computation of Acyclic Joins (2008)
The join operation of relational algebra is a cornerstone of relational database systems. Computing the join of several relations is NP-hard in general, whereas special (and typical) cases are...
/ pagh/papers/ One-Probe Search (2008)
Abstract. We consider dictionaries that perform lookups by probing a single word of memory, knowing only the size of the data structure. We describe a randomized dictionary where a lookup returns the...
ABSTRACT Scalable Computation of Acyclic Joins (2008)
The join operation of relational algebra is a cornerstone of relational database systems. Computing the join of several relations is NP-hard in general, whereas special (and typical) cases are...
Anna Östlin, Rasmus Pagh, Copyright C, Anna Östlin, Rasmus Pagh, Anna Östlin, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
A New Trade-off for Deterministic Dictionaries (2008)
Abstract. We consider dictionaries over the universe U = {0, 1} w on a unit-cost RAM with word size w and a standard instruction set. We present a linear space deterministic dictionary with...
(lat. On Dynamic Dictionaries Using Little Space) ⋆ (2008)
Abstract. We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing...
Abstract An Optimal Bloom Filter Replacement ∗ (2008)
Anna Pagh, Rasmus Pagh, S. Srinivasa Rao
This paper considers space-efficient data structures for storing an approximation S ′ to a set S such that S ⊆ S ′ and any element not in S belongs to S ′ with probability at most ɛ. The...
Rolf Fagerberg, Anna Pagh, Rasmus Pagh
Abstract. We give a randomized algorithm for sorting strings in external memory. For K binary strings comprising N words in total, our algorithm finds the sorted order and the longest common prefix...
Succinct Data Structures for Retrieval and Approximate Membership (2008)
Dietzfelbinger, Martin, Pagh, Rasmus
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 elements of a given set...
Hashing, randomness and dictionaries (2007)
This progress report contains a description of the author's research activity during the PhD study's two-year part A. The research has been centered around issues relating to one of the...
Hash and Displace: Ecient Evaluation of Minimal Perfect Hash Functions (2007)
A new way of constructing (minimal) perfect hash functions is described. The technique is a mixture of two well-known ones, and yields simple as well as ecient hashing schemes. More specically, the...
A Trade-Off For Worst-Case Efficient Dictionaries (2007)
We consider dynamic dictionaries over the universe U = {0, 1}^w on a unit-cost RAM with word size w and a standard instruction set, and present a linear space deterministic dictionary accommodating...
On the Probe Complexities of Membership and Perfect Hashing (2007)
This paper considers the following static data structure problems.
Efficient Evaluation of Minimal Perfect Hash Functions (2007)
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS Report Series publications. Copies may be...
Guided tour of some results on hashing and dictionaries (2007)
This document presents some results on dictionaries in the form of step-by-step problems. Familiarity with the material on uinversal hash functions in the first four sections of [3] is assumed. Also,...
Rasmus Pagh, Ny Munkegade Bldg, Flemming Friche Rodler
We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. (Dynamic perfect...
Fast evaluation of union-intersection expressions (2007)
Bille, Philip, Pagh, Anna, Pagh, Rasmus
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 problem has...
Generic Global Constraints based on MDDs (2007)
Tiedemann, Peter, Andersen, Henrik Reif, Pagh, Rasmus
Constraint Programming (CP) has been successfully applied to both constraint satisfaction and constraint optimization problems. A wide variety of specialized global constraints provide critical...
Perfect Hashing for Data Management Applications (2007)
Botelho, Fabiano C., Pagh, Rasmus, Ziviani, Nivio
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 good perfect hash...
Linear probing with constant independence (2007)
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 since it uses the cache...
Optimality in External Memory Hashing (2007)
Morten Skaarup Jensen, Rasmus Pagh
Hash tables on external memory are commonly used for indexing in database management systems. In this paper we present an algorithm that, in an asymptotic sense, achieves the best possible I/O and...
Simple and space-efficient minimal perfect hash functions (2007)
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani
Abstract. A perfect hash function (PHF) h: U → [0, m − 1] for a key set S is a function that maps the keys of S to unique values. The minimum amount of space to represent a PHF for a given set S...
Simple and space-efficient minimal perfect hash functions (2007)
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani
Abstract. A perfect hash function (PHF) h: U → [0, m − 1] for a key set S is a function that maps the keys of S to unique values. The minimum amount of space to represent a PHF for a given set S...
Fast evaluation of union-intersection expressions (2007)
Philip Bille, Anna Pagh, Rasmus Pagh
Abstract. 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 problem...
Linear probing with constant independence (2007)
Anna Pagh, Rasmus Pagh, Ru Zi Ć
Abstract. 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 since it uses...
Linear Probing with Constant Independence (2006)
Pagh, Anna, Pagh, Rasmus, Ruzic, Milan
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 since it uses the cache...
A Generic Global Constraint based on MDDs (2006)
Tiedemann, Peter, Andersen, Henrik Reif, Pagh, Rasmus
The paper suggests the use of Multi-Valued Decision Diagrams (MDDs) as the supporting data structure for a generic global constraint. We give an algorithm for maintaining generalized arc consistency...
De Dictionariis Dynamicis Pauco Spatio Utentibus (2005)
Demaine, Erik D., Pagh, Rasmus, Patrascu, Mihai
We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing queries...
On Dynamic Range Reporting in One Dimension (2005)
Mortensen, Christian Worm, Pagh, Rasmus, Patrascu, Mihai
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 is a natural and...
(lat. On Dynamic Dictionaries Using Little Space) (2005)
Erik D. Demaine, De Dictionariis, Dynamicis Pauco, Spatio Utentibus, U. Paderborn, ...
We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing queries...
(lat. On Dynamic Dictionaries Using Little Space) (2005)
De Dictionariis, Dynamicis Pauco, Spatio Utentibus, Erik D. Demaine, Rasmus Pagh, ...
Abstract We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, upto constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing...
Space Efficient Hash Tables With Worst Case Constant Access Time (2005)
Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul
We generalize Cuckoo Hashing to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\e)\,n$ memory cells, for any constant $\e >...
On adaptive integer sorting (2004)
Anna Pagh, Rasmus Pagh, Mikkel Thorup
Abstract. This paper considers integer sorting on a RAM. We show that adaptive sorting of a sequence with qn inversions is asymptotically equivalent to multisorting groups of at most q keys, and a...
Space Efficient Hash Tables with Worst Case Constant Access Time (2003)
Fotakis,Dimitris, Pagh,Rasmus, Sanders,Peter, Spirakis,Paul G.
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells,...
Space Efficient Hash Tables with Worst Case Constant Access Time (2003)
Fotakis, Dimitris, Pagh, Rasmus, Sanders, Peter, Spirakis, Paul G., Alt, Helmut, Habib, Michel
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing} and show how this yields a simple hash table data structure that stores $n$ elements in $(1+\epsilon)\,n$ memory cells,...
Space efficient hash tables with worst case constant access time (2003)
Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis
Abstract. We generalize Cuckoo Hashing [23] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ffl) n memory cells, for any constant...
Low Redundancy In Static Dictionaries With Constant Query Time (2002)
A static dictionary is a data structure storing subsets of a finite universe U , answering membership queries. We show that on a unit cost RAM with word size (log jU j), a static dictionary for...
Hashing, Randomness and Dictionaries (2002)
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Hashing, randomness and dictionaries (2002)
Phd Dissertation, Rasmus Pagh, Rasmus Pagh
This thesis is centered around one of the most basic information retrieval problems, namely that of storing and accessing the elements of a set. Each element in the set has some associated...
Rasmus Pagh, Flemming Friche Rodler
We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. (Dynamic perfect...
Rasmus Pagh, Flemming Friche Rodler
Abstract. We present a simple and efficient dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et...
Rasmus Pagh, Flemming Friche Rodler
Bloom ltering is an important technique for space ecient storage of a conservative approximation of a set S. The set stored may have up to some specied number of false positive members, but all...
Rasmus Pagh, Flemming Friche Rodler
Abstract. Bloom ltering is an important technique for space ecient storage of a conservative approximation of a set S. The set stored may have up to some specied number of false positive members, but...
Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting ∗ (2001)
Rasmus Pagh, Jakob Pagter, Copyright C, Rasmus Pagh, Jakob Pagter, Rasmus Pagh, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Dispersing Hash Functions (2000)
A new hashing primitive is introduced: dispersing hash functions. A family of hash functions F is dispersing if, for any set S of a certain size and random h ∈ F, the expected value of |S | −...
Deterministic Dictionaries (2000)
Torben Hagerup, Johann Wolfgang, Peter Bro Miltersen, Rasmus Pagh
this paper, our primary interest lies in obtaining static dictionaries with optimal query time and minimal space consumption that can be constructed rapidly by deterministic algorithms. By general...
A New Trade-off for Deterministic Dictionaries (2000)
. We consider dictionaries over the universe U = f0; 1g w on a unit-cost RAM with word size w and a standard instruction set. We present a linear space deterministic dictionary with membership...
Faster Deterministic Dictionaries (2000)
We consider static dictionaries over the universe U = f0; 1g w on a unit-cost RAM with word size w. Construction of a static dictionary with linear space consumption and constant lookup time can be...
Dispersing Hash Functions (2000)
A new hashing primitive is introduced: dispersing hash functions. A family of hash functions F is dispersing if, for any set S of a certain size and random h 2 F , the expected value of jSj jh[S]j is...
Deterministic Dictionaries (2000)
Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh
this paper, our primary interest lies in obtaining static dictionaries with optimal query time and minimal space consumption that can be constructed rapidly by deterministic algorithms. By general...
Faster deterministic dictionaries (2000)
We consider static dictionaries over the universe U = {0, 1} w on a unit-cost RAM with word size w. Construction of a static dictionary with linear space consumption and constant lookup time can be...
Low redundancy in dictionaries with O(1) worst case lookup time (1999)
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS Report Series publications. Copies may be...
Low redundancy in static dictionaries with O(1) lookup time (1999)
Abstract. A static dictionary is a data structure for storing subsets of a nite universe U, so that membership queries can be answered e-ciently. We study this problem in a unit cost RAM model with...
Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions (1999)
A new way of constructing (minimal) perfect hash functions is described. The technique considerably reduces the overhead associated with resolving buckets in two-level hashing schemes. Evaluating a...
Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time (1999)
. A static dictionary is a data structure for storing subsets of a nite universe U , so that membership queries can be answered e- ciently. We study this problem in a unit cost RAM model with word...
Hash and displace: Efficient evaluation of minimal perfect hash functions (1999)
Copyright C, Rasmus Pagh, Rasmus Pagh, Rasmus Pagh
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
Low redundancy in static dictionaries with O(1) lookup time (1999)
Abstract. A static dictionary is a data structure for storing subsets of a finite universe U, so that membership queries can be answered efficiently. We study this problem in a unit cost RAM model...
is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS Report Series publications. Copies may be...
This document in subdirectoryRS/99/48/ Faster Deterministic Dictionaries
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
This document in subdirectoryRS/00/4/ A New Trade-off for Deterministic Dictionaries
Rasmus Pagh, Copyright C, Rasmus Pagh, Rasmus Pagh
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
This document in subdirectoryRS/00/36/ Dispersing Hash Functions ∗
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
This document in subdirectoryRS/02/9/ One-Probe Search ⋆
Anna Östlin, Rasmus Pagh, Copyright C, Anna Östlin, Rasmus Pagh, Anna Östlin, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...