Rasmus Pagh

According to our database, Rasmus Pagh authored at least 145 papers between 1999 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy.

David Rasmussen Lolck, Rasmus Pagh

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

InfiniFilter: Expanding Filters to Infinity and Beyond.

Niv Dayan, Ioana O. Bercea, Pedro Reviriego, Rasmus Pagh

Proc. ACM Manag. Data, 2023

Differentially Private Selection from Secure Distributed Computing.

Ivan Damgård, Hannah Keller, Boel Nelson, Claudio Orlandi, Rasmus Pagh

IACR Cryptol. ePrint Arch., 2023

Optimal Non-Adaptive Cell Probe Dictionaries and Hashing.

Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir

CoRR, 2023

PLAN: Variance-Aware Private Mean Estimation.

Martin Aumüller, Christian Janos Lebeda, Boel Nelson, Rasmus Pagh

CoRR, 2023

Simple Set Sketching.

Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Smooth Binary Mechanism for Efficient Private Continual Observation.

Joel Daniel Andersson, Rasmus Pagh

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming.

Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All?

Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri

ACM Trans. Database Syst., 2022

Technical Perspective: Relative Error Streaming Quantiles.

Rasmus Pagh

SIGMOD Rec., 2022

Representing Sparse Vectors with Differential Privacy, Low Error, Optimal Space, and Fast Access.

Christian Janos Lebeda, Martin Aumüller, Rasmus Pagh

J. Priv. Confidentiality, 2022

Daisy Bloom Filters.

Ioana O. Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh

CoRR, 2022

Sampling near neighbors in search for fairness.

Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri

Commun. ACM, 2022

Improved Utility Analysis of Private CountSketch.

Rasmus Pagh, Mikkel Thorup

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

HyperLogLogLog: Cardinality Estimation With One Log More.

Matti Karppa, Rasmus Pagh

Proceedings of the KDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14, 2022

Infinitely Divisible Noise in the Low Privacy Regime.

Rasmus Pagh, Nina Mesing Stausholm

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search.

Matti Karppa, Martin Aumüller, Rasmus Pagh

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Fair near neighbor search via sampling.

Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, Francesco Silvestri

SIGMOD Rec., 2021

Advances and Open Problems in Federated Learning.

Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, Sen Zhao

Found. Trends Mach. Learn., 2021

2021 ACM PODS Alberto O. Mendelzon Test-of-Time Award.

Angela Bonifati, Rasmus Pagh, Thomas Schwentick

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

CountSketches, Feature Hashing and the Median of Three.

Kasper Green Larsen, Rasmus Pagh, Jakub Tetek

Proceedings of the 38th International Conference on Machine Learning, 2021

Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message.

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha

Proceedings of the 38th International Conference on Machine Learning, 2021

Efficient Differentially Private F₀ Linear Sketching.

Rasmus Pagh, Nina Mesing Stausholm

Proceedings of the 24th International Conference on Database Theory, 2021

On the Power of Multiple Anonymous Messages: Frequency Estimation and Selection in the Shuffle Model of Differential Privacy.

Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker

Proceedings of the Advances in Cryptology - EUROCRYPT 2021, 2021

Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access.

Martin Aumüller, Christian Janos Lebeda, Rasmus Pagh

Proceedings of the CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15, 2021

2020

Space-Efficient Feature Maps for String Alignment Kernels.

Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh

Data Sci. Eng., 2020

WOR and p's: Sketches for 𝓁_p-Sampling Without Replacement.

Edith Cohen, Rasmus Pagh, David P. Woodruff

CoRR, 2020

On the I/O complexity of the k-nearest neighbor problem.

Mayank Goswami, Riko Jacob, Rasmus Pagh

CoRR, 2020

Efficient Differentially Private F₀ Linear Sketching.

Rasmus Pagh, Nina Mesing Stausholm

CoRR, 2020

Oblivious Sketching of High-Degree Polynomial Kernels.

Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Confirmation Sampling for Exact Nearest Neighbor Search.

Tobias Christiani, Rasmus Pagh, Mikkel Thorup

Proceedings of the Similarity Search and Applications - 13th International Conference, 2020

On the I/O Complexity of the k-Nearest Neighbors Problem.

Mayank Goswami, Riko Jacob, Rasmus Pagh

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Fair Near Neighbor Search: Independent Range Sampling in High Dimensions.

Martin Aumüller, Rasmus Pagh, Francesco Silvestri

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

WOR and <i>p</i>'s: Sketches for ℓ_p-Sampling Without Replacement.

Edith Cohen, Rasmus Pagh, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead.

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh

Proceedings of the 37th International Conference on Machine Learning, 2020

Composable Sketches for Functions of Frequencies: Beyond the Worst Case.

Edith Cohen, Ofir Geri, Rasmus Pagh

Proceedings of the 37th International Conference on Machine Learning, 2020

Pure Differentially Private Summation from Anonymous Messages.

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker

Proceedings of the 1st Conference on Information-Theoretic Cryptography, 2020

The Space Complexity of Inner Product Filters.

Rasmus Pagh, Johan Sivertsen

Proceedings of the 23rd International Conference on Database Theory, 2020

Private Aggregation from Fewer Anonymous Messages.

Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker

Proceedings of the Advances in Cryptology - EUROCRYPT 2020, 2020

2019

Similarity Sketching.

Rasmus Pagh

Proceedings of the Encyclopedia of Big Data Technologies., 2019

On the Power of Multiple Anonymous Messages.

Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker

IACR Cryptol. ePrint Arch., 2019

Advances and Open Problems in Federated Learning.

Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, Sen Zhao

CoRR, 2019

Oblivious Sketching of High-Degree Polynomial Kernels.

Michael Kapralov, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh

CoRR, 2019

Private Heavy Hitters and Range Queries in the Shuffled Model.

Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker

CoRR, 2019

Scalable and Differentially Private Distributed Aggregation in the Shuffled Model.

Badih Ghazi, Rasmus Pagh, Ameya Velingker

CoRR, 2019

Hardness of Bichromatic Closest Pair with Jaccard Similarity.

Rasmus Pagh, Nina Mesing Stausholm, Mikkel Thorup

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors.

Martin Aumüller, Tobias Christiani, Rasmus Pagh, Michael Vesterli

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

Enumerating Trillion Subgraphs On Distributed Systems.

Ha-Myung Park, Francesco Silvestri, Rasmus Pagh, Chin-Wan Chung, Sung-Hyon Myaeng, U Kang

ACM Trans. Knowl. Discov. Data, 2018

CoveringLSH: Locality-Sensitive Hashing without False Negatives.

Rasmus Pagh

ACM Trans. Algorithms, 2018

Simple multi-party set reconciliation.

Michael Mitzenmacher, Rasmus Pagh

Distributed Comput., 2018

Scalable Alignment Kernels via Space-Efficient Feature Maps.

Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh

CoRR, 2018

Set Similarity Search for Skewed Data.

Samuel McCauley, Jesper W. Mikkelsen, Rasmus Pagh

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Distance-Sensitive Hashing.

Martin Aumüller, Tobias Christiani, Rasmus Pagh, Francesco Silvestri

Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2018

Scalable and Robust Set Similarity Join.

Tobias Christiani, Rasmus Pagh, Johan Sivertsen

Proceedings of the 34th IEEE International Conference on Data Engineering, 2018

2017

Approximate furthest neighbor with application to annulus query.

Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala

Inf. Syst., 2017

Theory and Applications of Hashing (Dagstuhl Seminar 17181).

Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, Martin Aumüller

Dagstuhl Reports, 2017

I/O-Efficient Similarity Join.

Rasmus Pagh, Ninh Pham, Francesco Silvestri, Morten Stöckel

Algorithmica, 2017

Efficiently Correcting Matrix Products.

Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama

Algorithmica, 2017

Set similarity search beyond MinHash.

Tobias Christiani, Rasmus Pagh

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Distance Sensitive Bloom Filters Without False Negatives.

Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Parameter-free Locality Sensitive Hashing for Spherical Range Reporting.

Thomas D. Ahle, Martin Aumüller, Rasmus Pagh

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Hardness and Approximation of High-Dimensional Search Problems (Invited Talk).

Rasmus Pagh

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons.

Joachim Gudmundsson, Rasmus Pagh

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

2016

Cuckoo Hashing.

Rasmus Pagh

Encyclopedia of Algorithms, 2016

High-dimensional Spherical Range Reporting by Output-Sensitive Multi-Probing LSH.

Thomas D. Ahle, Martin Aumüller, Rasmus Pagh

CoRR, 2016

Triangle Counting in Dynamic Graph Streams.

Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, Rasmus Pagh

Algorithmica, 2016

Locality-sensitive Hashing without False Negatives.

Rasmus Pagh

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Complexity of Inner Product Similarity Join.

Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, Francesco Silvestri

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

Scalability and Total Recall with Fast CoveringLSH.

Ninh Pham, Rasmus Pagh

Proceedings of the 25th ACM International Conference on Information and Knowledge Management, 2016

2015

Association Rule Mining using Maximum Entropy.

Rasmus Pagh, Morten Stöckel

CoRR, 2015

From Independence to Expansion and Back Again.

Tobias Christiani, Rasmus Pagh, Mikkel Thorup

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Approximate Range Emptiness in Constant Time and Optimal Space.

Mayank Goswami, Allan Grønlund Jørgensen, Kasper Green Larsen, Rasmus Pagh

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Approximate Furthest Neighbor in High Dimensions.

Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala

Proceedings of the Similarity Search and Applications - 8th International Conference, 2015

Large-Scale Similarity Joins With Guarantees (Invited Talk).

Rasmus Pagh

Proceedings of the 18th International Conference on Database Theory, 2015

2014

Cache-Oblivious Hashing.

Rasmus Pagh, Zhewei Wei, Ke Yi, Qin Zhang

Algorithmica, 2014

Thresholds for Extreme Orientability.

Po-Shen Loh, Rasmus Pagh

Algorithmica, 2014

Better Size Estimation for Sparse Matrix Products.

Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh

Algorithmica, 2014

Efficient estimation for high similarities using odd sketches.

Michael Mitzenmacher, Rasmus Pagh, Ninh Pham

Proceedings of the 23rd International World Wide Web Conference, 2014

Triangle Counting in Dynamic Graph Streams.

Konstantin Kutzkov, Rasmus Pagh

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Consistent Subset Sampling.

Konstantin Kutzkov, Rasmus Pagh

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Is min-wise hashing optimal for summarizing set intersection?

Rasmus Pagh, Morten Stöckel, David P. Woodruff

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

The input/output complexity of triangle enumeration.

Rasmus Pagh, Francesco Silvestri

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Listing Triangles.

Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, Uri Zwick

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Generating k-Independent Variables in Constant Time.

Tobias Christiani, Rasmus Pagh

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

The Input/Output Complexity of Sparse Matrix Multiplication.

Rasmus Pagh, Morten Stöckel

Proceedings of the Algorithms - ESA 2014, 2014

MapReduce Triangle Enumeration With Guarantees.

Ha-Myung Park, Francesco Silvestri, U Kang, Rasmus Pagh

Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, 2014

2013

Compressed matrix multiplication.

Rasmus Pagh

ACM Trans. Comput. Theory, 2013

Practical perfect hashing in nearly optimal space.

Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani

Inf. Syst., 2013

On the streaming complexity of computing local clustering coefficients.

Konstantin Kutzkov, Rasmus Pagh

Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, 2013

Fast and scalable polynomial kernels via explicit feature maps.

Ninh Pham, Rasmus Pagh

Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013

How to Approximate a Set without Knowing Its Size in Advance.

Rasmus Pagh, Gil Segev, Udi Wieder

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

On parallelizing matrix multiplication by the column-row method.

Andrea Campagna, Konstantin Kutzkov, Rasmus Pagh

Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, 2013

2012

Finding associations and computing similarity via biased pair sampling.

Andrea Campagna, Rasmus Pagh

Knowl. Inf. Syst., 2012

Colorful triangle counting and a MapReduce implementation.

Rasmus Pagh, Charalampos E. Tsourakakis

Inf. Process. Lett., 2012

I/O-efficient data structures for colored range and prefix reporting.

Kasper Green Larsen, Rasmus Pagh

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

A near-linear time approximation algorithm for angle-based outlier detection in high-dimensional data.

Ninh Pham, Rasmus Pagh

Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012

2011

Linear Probing with 5-wise Independence.

Anna Pagh, Rasmus Pagh, Milan Ruzic

SIAM Rev., 2011

Theory and practice of monotone minimal perfect hashing.

Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna

ACM J. Exp. Algorithmics, 2011

A New Data Layout for Set Intersection on GPUs.

Rasmus Resen Amossen, Rasmus Pagh

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Frequent Pairs in Data Streams: Exploiting Parallelism and Skew.

Andrea Campagna, Konstantin Kutzkov, Rasmus Pagh

Proceedings of the Data Mining Workshops (ICDMW), 2011

2010

On Finding Frequent Patterns in Directed Acyclic Graphs

Andrea Campagna, Rasmus Pagh

CoRR, 2010

On Finding Similar Items in a Stream of Transactions.

Andrea Campagna, Rasmus Pagh

Proceedings of the ICDMW 2010, 2010

On Finding Frequent Patterns in Event Sequences.

Andrea Campagna, Rasmus Pagh

Proceedings of the ICDM 2010, 2010

Tight Thresholds for Cuckoo Hashing via XORSAT.

Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Fast Prefix Search in Little Space, with Applications.

Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna

Proceedings of the Algorithms, 2010

2009

Linear Probing with Constant Independence.

Anna Pagh, Rasmus Pagh, Milan Ruzic

SIAM J. Comput., 2009

Dispersing hash functions.

Rasmus Pagh

Random Struct. Algorithms, 2009

Monotone minimal perfect hashing: searching a sorted table with <i>O</i>(1) accesses.

Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Secondary indexing in one dimension: beyond b-trees and bitmap indexes.

Rasmus Pagh, Srinivasa Rao Satti

Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

Faster join-projects and sparse matrix multiplications.

Rasmus Resen Amossen, Rasmus Pagh

Proceedings of the Database Theory, 2009

Storing a Compressed Function with Constant Time Access.

Jóhannes B. Hreinsson, Morten Krøyer, Rasmus Pagh

Proceedings of the Algorithms, 2009

Theory and Practise of Monotone Minimal Perfect Hashing.

Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna

Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009

2008

Cuckoo Hashing.

Rasmus Pagh

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Uniform Hashing in Constant Time and Optimal Space.

Anna Pagh, Rasmus Pagh

SIAM J. Comput., 2008

Succinct Data Structures for Retrieval and Approximate Membership

Martin Dietzfelbinger, Rasmus Pagh

CoRR, 2008

Optimality in External Memory Hashing.

Morten Skaarup Jensen, Rasmus Pagh

Algorithmica, 2008

Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract).

Martin Dietzfelbinger, Rasmus Pagh

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Generic Global Constraints based on MDDs

Peter Tiedemann, Henrik Reif Andersen, Rasmus Pagh

CoRR, 2007

Perfect Hashing for Data Management Applications

Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani

CoRR, 2007

Simple and Space-Efficient Minimal Perfect Hash Functions.

Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Fast Evaluation of Union-Intersection Expressions.

Philip Bille, Anna Pagh, Rasmus Pagh

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006

A Generic Global Constraint based on MDDs

Peter Tiedemann, Henrik Reif Andersen, Rasmus Pagh

CoRR, 2006

External String Sorting: Faster and Cache-Oblivious.

Rolf Fagerberg, Anna Pagh, Rasmus Pagh

Proceedings of the STACS 2006, 2006

Deterministic load balancing and dictionaries in the parallel disk model.

Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Patrascu, Milan Ruzic, Peter Tiedemann

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Scalable computation of acyclic joins.

Anna Pagh, Rasmus Pagh

Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

De Dictionariis Dynamicis Pauco Spatio Utentibus (<i>lat.</i> On Dynamic Dictionaries Using Little Space).

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005

Space Efficient Hash Tables with Worst Case Constant Access Time.

Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul G. Spirakis

Theory Comput. Syst., 2005

De Dictionariis Dynamicis Pauco Spatio Utentibus

Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu

CoRR, 2005

On dynamic range reporting in one dimension.

Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

An optimal Bloom filter replacement.

Anna Pagh, Rasmus Pagh, S. Srinivasa Rao

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Cuckoo hashing.

Rasmus Pagh, Flemming Friche Rodler

J. Algorithms, 2004

On Adaptive Integer Sorting.

Anna Pagh, Rasmus Pagh, Mikkel Thorup

Proceedings of the Algorithms, 2004

2003

Uniform hashing in constant time and linear space.

Anna Östlin, Rasmus Pagh

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Optimal time-space trade-offs for non-comparison-based sorting.

Rasmus Pagh, Jakob Pagter

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

One-Probe Search.

Anna Östlin, Rasmus Pagh

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Basic External Memory Data Structures.

Rasmus Pagh

Proceedings of the Algorithms for Memory Hierarchies, 2002

2001

Low Redundancy in Static Dictionaries with Constant Query Time.

Rasmus Pagh

SIAM J. Comput., 2001

Deterministic Dictionaries.

Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh

J. Algorithms, 2001

On the cell probe complexity of membership and perfect hashing.

Rasmus Pagh

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Lossy Dictionaries.

Rasmus Pagh, Flemming Friche Rodler

Proceedings of the Algorithms, 2001

2000

A Trade-Off for Worst-Case Efficient Dictionaries.

Rasmus Pagh

Nord. J. Comput., 2000

A New Trade-Off for Deterministic Dictionaries.

Rasmus Pagh

Proceedings of the Algorithm Theory, 2000

Faster deterministic dictionaries.

Rasmus Pagh

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions.

Rasmus Pagh

Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time.

Rasmus Pagh

Proceedings of the Automata, 1999