[128] Continual Counting with Gradual Privacy Expiration
Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, Jalaj Upadhyay. Submitted, 2024
|
[127] Aleph Filter: To Infinity in Constant Time
Niv Dayan, Ioana Bercea, Rasmus Pagh. Submitted, 2024
|
[126] Profile Reconstruction from Private Sketches
Hao WU, Rasmus Pagh. International Conference on Machine Learning (ICML), 2024
|
[125] Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, Or Zamir. International Colloquium on Automata, Languages and Programming (ICALP), 2024
|
[124] Daisy Bloom Filters
Ioana Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh. Scandinavian Symposium on Algorithm Theory (SWAT), 2024
|
[123] PLAN: Variance-Aware Private Mean Estimation
Martin Aumüller, Christian Janos Lebeda, Boel Nelson, Rasmus Pagh. Privacy Enhancing Technologies Symposium (PETS), 2024
|
[122] Differentially Private Selection from Secure Distributed Computing
Ivan Damgård, Hannah Keller, Boel Nelson, Claudio Orlandi, Rasmus Pagh. The Web Conference (WWW), 2024
|
[121] Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy
David Rasmussen Lolck, Rasmus Pagh. Symposium on Discrete Algorithms (SODA), 2024
|
[120] A Smooth Binary Mechanism for Efficient Private Continual Observation
Joel Daniel Andersson, Rasmus Pagh. Neural Information Processing Symposium (NeurIPS), 2023
|
[119] Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff. Foundations of Computer Science (FOCS), 2023
|
[118] InfiniFilter: Expanding Filters to Infinity and Beyond
Niv Dayan, Ioana Bercea, Pedro Reviriego, Rasmus Pagh. ACM SIGMOD Conference, 2023
|
[117] Simple Set Sketching
Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer. Symposium on Simplicity in Algorithms (SOSA), 2023
|
[116] Improved Utility Analysis of Private CountSketch
Rasmus Pagh, Mikkel Thorup. Neural Information Processing Symposium (NeurIPS), 2022
|
[115] HyperLogLogLog: Cardinality Estimation With One Log More
Matti Karppa, Rasmus Pagh. SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2022
|
[114] DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
Matti Karppa, Martin Aumüller, Rasmus Pagh. International Conference on Artificial Intelligence and Statistics (AISTATS), 2022
|
[113] 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 Transactions on Database Systems, 2022
Based on our paper in PODS '20 and the paper of Har-Peled and Mahabadi in NeurIPS '19. An abridged version appeared in SIGMOD Record, March 2021, with a nice introduction by Qin Zhang. A version aimed at a broad audience appeared in Communications of the ACM, August 2022.
|
[112] Infinitely Divisible Noise in the Low Privacy Regime
Rasmus Pagh, Nina Mesing Stausholm. International Conference on Algorithmic Learning Theory (ALT), 2022
|
[111] Differentially private sparse vectors with low error, optimal space, and fast access
Martin Aumüller, Christian Janos Lebeda, Rasmus Pagh. Conference on Computer and Communications Security (CCS), 2021
Also appeared as a poster in Theory and Practice of Differential Privacy (TPDP), 2021.
|
[110] 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. International Conference on Machine Learning (ICML), 2021
Also appeared as an abstract in Foundations of Responsible Computing (FORC), 2021.
|
[109] CountSketches, Feature Hashing and the Median of Three
Kasper Green Larsen, Rasmus Pagh, Jakub Tětek. International Conference on Machine Learning (ICML), 2021
|
[108] Efficient Differentially Private F0 Linear Sketching
Rasmus Pagh, Nina Mesing Stausholm. International Conference on Database Theory (ICDT), 2021
|
[107] On the Power of Multiple Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker. Eurocrypt, 2021
Appeared as an abstract in Foundations of Responsible Computing (FORC), 2020.
|
[106] WOR and p’s: Sketches for ℓp-sampling Without Replacement
Edith Cohen, Rasmus Pagh, David P. Woodruff. Neural Information Processing Symposium (NeurIPS), 2020
|
[105] Confirmation Sampling for Exact Nearest Neighbor Search
Tobias Christiani, Rasmus Pagh, Mikkel Thorup. Similarity Search and Applications (SISAP), 2020
|
[104] Composable Sketches for Functions of Frequencies: Beyond the Worst Case
Edith Cohen, Ofir Geri, Rasmus Pagh. International Conference on Machine Learning (ICML), 2020
|
[103] Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh. International Conference on Machine Learning (ICML), 2020
Appears as an abstract in Foundations of Responsible Computing (FORC), 2020. The arXiv version corrects a calculation error in Theorem 13.
|
[102] Space-efficient Feature Maps for String Alignment Kernels
Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh. Data Science and Engineering, 2020
Supersedes the preliminary version in ICDM 2019
|
[101] On the I/O complexity of the k-nearest neighbor problem
Mayank Goswami, Riko Jacob, Rasmus Pagh. Principles of Database Systems (PODS), 2020
|
[100] Fair Near Neighbor Search: Independent Range Sampling in High Dimensions
Martin Aumüller, Rasmus Pagh, Francesco Silvestri. Principles of Database Systems (PODS), 2020
Superseded by [113] Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All?, 2022.
|
[99] Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. Information Theoretic Cryptography (ITC), 2020
|
[98] Private Aggregation from Fewer Anonymous Messages
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. Eurocrypt, 2020
Subsumes arXiv:1906.08320
|
[97] The space complexity of inner product filters
Rasmus Pagh, Johan Sivertsen. International Conference on Database Theory (ICDT), 2020
|
[96] Oblivious Sketching of High-Degree Polynomial Kernels
Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Houen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh. Symposium on Discrete Algorithms (SODA), 2020
Based on arXiv:1909.01410 and arXiv:1909.01821
|
[95] Hardness of Bichromatic Closest Pair with Jaccard Similarity
Rasmus Pagh, Nina Mesing Stausholm, Mikkel Thorup. European Symposium on Algorithms (ESA), 2019
|
[94] PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
Martin Aumüller, Tobias Christiani, Rasmus Pagh, Michael Vesterli. European Symposium on Algorithms (ESA), 2019
|
[93] Space-efficient Feature Maps for String Alignment Kernels
Yasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh. International Conference on Data Mining (ICDM), 2019
Superseded by [102] Space-efficient Feature Maps for String Alignment Kernels, 2020.
|
[92] Enumerating Trillion Subgraphs On Distributed Systems
Ha-Myung Park, Francesco Silvestri, Rasmus Pagh, Chin-Wan Chung, Sung-Hyon Myaeng, U Kang. ACM Transactions on Knowledge Discovery from Data, 2018
Code and data sets.
|
[91] Set Similarity Search for Skewed Data
Samuel McCauley, Jesper W. Mikkelsen, Rasmus Pagh. Principles of Database Systems (PODS), 2018
|
[90] Distance-sensitive Hashing
Martin Aumüller, Tobias Christiani, Rasmus Pagh, Francesco Silvestri. Principles of Database Systems (PODS), 2018
|
[89] CoveringLSH: Locality-sensitive Hashing without False Negatives
Rasmus Pagh. ACM Transactions on Algorithms, 2018
Special issue for SODA 2016.
|
[88] Scalable and robust set similarity join
Tobias Christiani, Rasmus Pagh, Johan Sivertsen. International Conference on Data Engineering (ICDE), 2018
The proceedings version is an abridged form of the full paper on arXiv.
|
[87] Simple Multi-Party Set Reconciliation
Michael Mitzenmacher, Rasmus Pagh. Distributed Computing, 2017
|
[86] Range-efficient consistent sampling and locality-sensitive hashing for polygons
Joachim Gudmundsson, Rasmus Pagh. International Symposium on Algorithms and Computation (ISAAC), 2017
|
[85] Set Similarity Search Beyond Minhash
Tobias Christiani, Rasmus Pagh. Symposium on Theory of Computing (STOC), 2017
Presentation slides. Also presented as a poster.
|
[84] I/O-efficient Similarity Join
Rasmus Pagh, Ninh Pham, Francesco Silvestri, Morten Stöckel. Algorithmica 78:1263–1283, 2017
|
[83] Distance Sensitive Bloom Filters Without False Negatives
Mayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen. Symposium on Discrete Algorithms (SODA), 2017
|
[82] Parameter-free Locality Sensitive Hashing for Spherical Range Reporting
Thomas D. Ahle, Martin Aumüller, Rasmus Pagh. Symposium on Discrete Algorithms (SODA), 2017
|
[81] Efficiently Correcting Matrix Products
Leszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama. Algorithmica, 2016
|
[80] Approximate Furthest Neighbor with Application to Annulus Query
Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala. Information Systems, special issue for SISAP, 2016
|
[79] Scalability and Total Recall with Fast CoveringLSH
Ninh Pham, Rasmus Pagh. International Conference on Information and Knowledge Management (CIKM), 2016
|
[78] On the Complexity of Inner Product Similarity Join
Thomas D. Ahle, Rasmus Pagh, Ilya Razenshteyn, Francesco Silvestri. Symposium on Principles of Database Systems (PODS), 2016
|
[77] Triangle counting in dynamic graph streams
Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, Rasmus Pagh. Algorithmica 76, 2016
Strengthens the result of the SWAT '14 paper of the same name.
|
[76] Locality-sensitive Hashing without False Negatives
Rasmus Pagh. Symposium on Discrete Algorithms (SODA), 2016
Presentation slides. Superseded by [89] CoveringLSH: Locality-sensitive Hashing without False Negatives, 2018. A simple Python implementation is available.
|
[75] Approximate Furthest Neighbor in High Dimensions
Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala. International Conference on Similarity Search and Applications (SISAP), 2015
Superseded by [80] Approximate Furthest Neighbor with Application to Annulus Query, 2016.
|
[74] I/O-efficient Similarity Join in High Dimensions
Rasmus Pagh, Ninh Pham, Francesco Silvestri, Morten Stöckel. European Symposium on Algorithms (ESA), 2015
Presentation slides. Superseded by [84] I/O-efficient Similarity Join, 2017.
|
[73] From Independence to Expansion and Back
Tobias Christiani, Rasmus Pagh, Mikkel Thorup. Symposium on Theory of Computing (STOC), 2015
Presentation slides.
|
[72] Approximate Range Emptiness in Constant Time and Optimal Space
Mayank Goswami, Allan Grønlund, Kasper Green Larsen, Rasmus Pagh. Symposium on Discrete Algorithms (SODA), 2015
Presentation slides.
|
[71] MapReduce Triangle Enumeration With Guarantees
Ha-Myung Park, Francesco Silvestri, U Kang, Rasmus Pagh. Conference on Information and Knowledge Management (CIKM), 2014
Superseded by [92] Enumerating Trillion Subgraphs On Distributed Systems, 2018. Code and data sets.
|
[70] Generating k-independent variables in constant time
Tobias Christiani, Rasmus Pagh. Foundations of Computer Science (FOCS), 2014
Presentation slides. Full version available on arXiv.
|
[69] The Input/Output Complexity of Sparse Matrix Multiplication
Rasmus Pagh, Morten Stöckel. European Symposium on Algorithms (ESA), 2014
Presentation slides. Also presented at SIAM Conference on Applied Linear Algebra, 2015.
|
[68] Triangle counting in dynamic graph streams
Konstantin Kutzkov, Rasmus Pagh. Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2014
Presentation slides. Superseded by [77] Triangle counting in dynamic graph streams, 2016.
|
[67] Consistent subset sampling
Konstantin Kutzkov, Rasmus Pagh. Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2014
Presentation slides. Full version available on arXiv.
|
[66] Listing Triangles
Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, Uri Zwick. International Colloquium on Automata, Languages and Programming (ICALP), 2014
|
[65] Is Min-Wise Hashing Optimal for Summarizing Set Intersection?
Rasmus Pagh, Morten Stöckel, David P. Woodruff. Symposium on Principles of Database Systems (PODS), 2014
|
[64] The Input/Output Complexity of Triangle Enumeration
Rasmus Pagh, Francesco Silvestri. Symposium on Principles of Database Systems (PODS), 2014
|
[63] Efficient Estimation for High Similarities using Odd Sketches
Michael Mitzenmacher, Rasmus Pagh, Ninh Pham. International World Wide Web Conference (WWW), 2014
Presentation slides. Winner of best paper award. Selected as a Notable Computing Article of 2014 by ACM Computing Reviews.
|
[62] Thresholds for Extreme Orientability
Po-Shen Loh, Rasmus Pagh. Algorithmica 69 (3), 2014
|
[61] How to Approximate A Set Without Knowing Its Size in Advance
Rasmus Pagh, Gil Segev, Udi Wieder. Foundations of Computer Science (FOCS), 2013
|
[60] Fast and Scalable Polynomial Kernels via Explicit Feature Maps
Ninh Pham, Rasmus Pagh. Conference on Knowledge Discovery and Data Mining (KDD), 2013
Source code is available in Matlab (by Ninh Pham) and C++ (by Johan von Tangen Sivertsen).
|
[59] Compressed Matrix Multiplication
Rasmus Pagh. ACM Transactions on Computation Theory, August 2013
Presentation slides. Special issue for ITCS 2012. Selected as a Notable Computing Article of 2013 by ACM Computing Reviews. The version on this page corrects a typo in the pseudocode of the published version.
|
[58] Cache-oblivious Hashing
Rasmus Pagh, Zhewei Wei, Ke Yi, Qin Zhang. Algorithmica, March 2013
|
[57] Practical Perfect Hashing Algorithm in Nearly Optimal Space
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani. Information Systems Journal 38(1), 2013
Implementation available in CMPH.
|
[56] On the streaming complexity of computing local clustering coefficients
Konstantin Kutzkov, Rasmus Pagh. Conference on Web Search and Data Mining (WSDM), 2013
|
[55] On Parallelizing Matrix Multiplication by the Column-Row Method
Andrea Campagna, Konstantin Kutzkov, Rasmus Pagh. Workshop on Algorithm Engineering and Experiments (ALENEX), 2013
|
[54] Better Size Estimation for Sparse Matrix Products
Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh. Algorithmica, March 2013
Presentation slides. Note: A preliminary version appeared at RANDOM 2010.
|
[53] A Near-linear Time Approximation Algorithm for Angle-based Outlier Detection in High-dimensional Data
Ninh Pham, Rasmus Pagh. SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2012
Source code is available here.
|
[52] Compressed Matrix Multiplication
Rasmus Pagh. Innovations in Theoretical Computer Science (ITCS), 2012
Presentation slides. Superseded by [59] Compressed Matrix Multiplication, August 2013.
|
[51] I/O-Efficient Data Structures for Colored Range and Prefix Reporting
Kasper Green Larsen, Rasmus Pagh. Symposium on Discrete Algorithms (SODA), 2012
Presentation slides.
|
[50] Colorful Triangle Counting and a MapReduce Implementation
Rasmus Pagh, Charalampos E. Tsourakakis. Information Processing Letters 112 (7), 2012
|
[49] Finding Associations and Computing Similarity via Biased Pair Sampling
Andrea Campagna, Rasmus Pagh. Knowledge and Information Systems 31 (3), 2012
Invited paper from ICDM 2009. Can be seen as a generalization of Edith Cohen, David D. Lewis: Approximating Matrix Multiplication for Pattern Recognition Tasks. J. Algorithms 30(2): 211-252 (1999) (not cited in the paper).
|
[48] Frequent Pairs in Data Streams: Exploiting Parallelism and Skew
Andrea Campagna, Konstantin Kutzkov, Rasmus Pagh. International Conference on Data Mining Workshops (KDCloud), 2011
|
[47] Linear probing with 5-wise independence
Anna Pagh, Rasmus Pagh, Milan Ružić. SIAM Review 53, 2011
Published in the SIGEST section, which "highlights a recent paper from one of SIAM's nine specialized research journals, chosen on the basis of exceptional interest to the entire SIAM community".
|
[46] Theory and Practice of Monotone Minimal Perfect Hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. ACM Journal of Experimental Algorithmics 16, 2011
Implementations available in Sux.
|
[45] A New Data Layout For Set Intersection on GPUs
Rasmus Resen Amossen, Rasmus Pagh. International Parallel & Distributed Processing Symposium (IPDPS), 2011
Presentation slides. Note: Tightness of the space bound shown in this paper is now known.
|
[44] On Finding Frequent Patterns in Event Sequences
Andrea Campagna, Rasmus Pagh. International Conference on Data Mining (ICDM), 2010
|
[43] On Finding Similar Items in a Stream of Transactions
Andrea Campagna, Rasmus Pagh. International Conference on Data Mining Workshops (KDCloud), 2010
|
[42] Better Size Estimation for Sparse Matrix Products
Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh. International Workshop on Randomization and Computation (RANDOM), 2010
Presentation slides. Superseded by [54] Better Size Estimation for Sparse Matrix Products, March 2013. Note: The version published in the RANDOM proceedings contained a mistake that matters whenever z<n. This has been corrected in the journal version.
|
[41] Fast Prefix Search in Little Space, with Applications
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. European Symposium on Algorithms (ESA), 2010
Presentation slides.
|
[40] Tight Thresholds for Cuckoo Hashing via XORSAT
Martin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink. International Colloquium on Automata, Languages and Programming (ICALP), 2010
|
[39] Cache-oblivious Hashing
Rasmus Pagh, Zhewei Wei, Ke Yi, Qin Zhang. Symposium on Principles of Database Systems (PODS), 2010
|
[38] Linear probing with constant independence
Anna Pagh, Rasmus Pagh, Milan Ružić. SIAM Journal on Computing 39, 2009
Special issue for STOC 2007. Optimality of 5-wise independence has been shown by Pătraşcu and Thorup in in 2010.
|
[37] Dispersing Hash Functions
Rasmus Pagh. Random Structures and Algorithms 35, 2009
|
[36] Finding Associations and Computing Similarity via Biased Pair Sampling
Andrea Campagna, Rasmus Pagh. International Conference on Data Mining (ICDM), 2009
Presentation slides. Superseded by [49] Finding Associations and Computing Similarity via Biased Pair Sampling, 2012. Can be seen as a generalization of Edith Cohen, David D. Lewis: Approximating Matrix Multiplication for Pattern Recognition Tasks. J. Algorithms 30(2): 211-252 (1999) (not cited in the paper).
|
[35] Storing a Compressed Function with Constant Time Access
Jóhannes B. Hreinsson, Morten Krøyer, Rasmus Pagh. European Symposium on Algorithms (ESA), 2009
Presentation slides.
|
[34] Faster join-projects and sparse matrix multiplications
Rasmus Resen Amossen, Rasmus Pagh. International Conference on Database Theory (ICDT), 2009
Presentation slides. Note: There is an error in section 3.2, where 2/(1+β+k) should be replaced by (1+β)/(1+β+k), which makes the running time O(N2/3 Z2/3 + N0.862 Z0.546). In addition, the condition Z>N is required. Presentation in .mov format.
|
[33] Theory and Practise of Monotone Minimal Perfect Hashing
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Workshop on Algorithm Engineering and Experiments (ALENEX), 2009
Superseded by [46] Theory and Practice of Monotone Minimal Perfect Hashing, 2011. Implementations available in Sux.
|
[32] Monotone Minimal Perfect Hashing: Searching a Sorted Table
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Symposium on Discrete Algorithms (SODA), 2009
Presentation slides. Implementation available in Sux.
|
[31] Secondary indexing in one dimension: Beyond B-trees and bitmap indexes
Rasmus Pagh, S. Srinivasa Rao. Symposium on Principles of Database Systems (PODS), 2009
Presentation slides.
|
[30] Optimality in External Memory Hashing
Morten Skaarup Jensen, Rasmus Pagh. Algorithmica 52, 2008
|
[29] Uniform Hashing in Constant Time and Optimal Space
Anna Pagh, Rasmus Pagh. SIAM Journal on Computing 38, 2008
|
[28] Succinct Data Structures for Retrieval and Approximate Membership
Martin Dietzfelbinger, Rasmus Pagh. International Colloquium on Automata, Languages and Programming (ICALP), 2008
Presentation slides.
|
[27] Linear probing with constant independence
Anna Pagh, Rasmus Pagh, Milan Ružić. Symposium on Theory of Computing (STOC), 2007
Presentation slides. Superseded by [38] Linear probing with constant independence, 2009.
|
[26] Simple and Space-Efficient Minimal Perfect Hash Functions
Fabiano C. Botelho, Rasmus Pagh, Nivio Ziviani. International Workshop on Algorithms and Data Structures (WADS), 2007
Presentation slides. Superseded by [57] Practical Perfect Hashing Algorithm in Nearly Optimal Space, 2013. Implementation available in CMPH.
|
[25] Fast evaluation of union-intersection expressions
Philip Bille, Anna Pagh, Rasmus Pagh. International Symposium on Algorithms And Computation (ISAAC), 2007
Presentation slides. Note: A practical version of our approach has been proposed by Bolin Ding and Arnd Christian König, VLDB 2011.
|
[24] Scalable computation of acyclic joins
Anna Pagh, Rasmus Pagh. Symposium on Principles of Database Systems (PODS), 2006
Presentation slides. (.mov format.)
|
[23] Deterministic load balancing and dictionaries in the parallel disk model
Mette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Pătraşcu, Milan Ružić, Peter Tiedemann. Symposium on Parallel Algorithms and Architectures (SPAA), 2006
Presentation slides.
|
[22] De Dictionariis Dynamicis Pauco Spatio Utentibus
Erik Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Pătraşcu. Latin American Symposium on Theoretical Informatics (LATIN), 2006
Presentation slides. Note: A stronger result has been shown by Arbitman, Naor, and Segev in 2010.
|
[21] External String Sorting: Faster and Cache-Oblivious
Rolf Fagerberg, Anna Pagh, Rasmus Pagh. Symposium on Theoretical Aspects of Computer Science (STACS), 2006
|
[20] An Optimal Bloom Filter Replacement
Anna Pagh, Rasmus Pagh, S. Srinivasa Rao. Symposium on Discrete Algorithms (SODA), 2005
Presentation slides.
|
[19] On Dynamic Range Reporting in One Dimension
Christian Worm Mortensen, Rasmus Pagh, Mihai Pătraşcu. Symposium on Theory of Computing (STOC), 2005
Presentation slides.
|
[18] Space Efficient Hash Tables with Worst Case Constant Access Time
Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis. Theory of Computing Systems 38, 2005
Special issue for STACS 2003.
|
[17] On Adaptive Integer Sorting
Anna Pagh, Rasmus Pagh, Mikkel Thorup. European Symposium on Algorithms (ESA), 2004
Presentation slides.
|
[16] Cuckoo Hashing
Rasmus Pagh, Flemming Friche Rodler. Journal of Algorithms 51, 2004
Other resources: Description on Wikipedia; Open problems on cuckoo hashing. Implementation in C available.
|
[15] Space Efficient Hash Tables with Worst Case Constant Access Time
Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis. Symposium on Theoretical Aspects of Computer Science (STACS), 2003
Presentation slides. Superseded by [18] Space Efficient Hash Tables with Worst Case Constant Access Time, 2005.
|
[14] Uniform Hashing in Constant Time and Linear Space
Anna Östlin, Rasmus Pagh. Symposium on Theory of Computing (STOC), 2003
Presentation slides. Superseded by [29] Uniform Hashing in Constant Time and Optimal Space, 2008.
|
[13] One-Probe Search
Anna Östlin, Rasmus Pagh. International Colloquium on Automata, Languages and Programming (ICALP), LNCS 2380, 2002
Presentation slides. Marius Zimand has observed that the proof of Lemma 10 is incorrect; however, a correct proof can be obtained via the max-flow min-cut theorem
|
[12] Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting
Rasmus Pagh, Jakob Pagter. Symposium on Discrete Algorithms (SODA), 2002
Presentation slides.
|
[11] Low Redundancy in Static Dictionaries with Constant Query Time
Rasmus Pagh. SIAM Journal on Computing 31, 2001
Note: Stronger results have been shown by Mihai Pătraşcu in in 2008.
|
[10] Lossy Dictionaries
Rasmus Pagh, Flemming Friche Rodler. European Symposium on Algorithms (ESA), 2001
Presentation slides. Extended version.
|
[9] Cuckoo Hashing
Rasmus Pagh, Flemming Friche Rodler. European Symposium on Algorithms (ESA), 2001
Presentation slides. Superseded by [16] Cuckoo Hashing, 2004. Received best student paper award. Implementation in C available.
|
[8] On the Cell Probe Complexity of Membership and Perfect Hashing
Rasmus Pagh. Symposium on Theory of Computing (STOC), 2001
Presentation slides.
|
[7] A Trade-Off for Worst-Case Efficient Dictionaries
Rasmus Pagh. Nordic Journal of Computing 7, 2000
Special issue for SWAT 2000.
|
[6] A new trade-off for deterministic dictionaries
Rasmus Pagh. Scandinavian Workshop on Algorithm Theory (SWAT), 2000
Presentation slides. Superseded by [7] A Trade-Off for Worst-Case Efficient Dictionaries, 2000.
|
[5] Deterministic Dictionaries
Torben Hagerup, Peter Bro Miltersen, Rasmus Pagh. Journal of Algorithms 41, 2001
Note: Stronger results have been shown by Milan Ružić in in 2008.
|
[4] Dispersing Hash Functions
Rasmus Pagh. International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2000
Presentation slides. Superseded by [37] Dispersing Hash Functions, 2009.
|
[3] Faster Deterministic Dictionaries
Rasmus Pagh. Symposium on Discrete Algorithms (SODA), 2000
Presentation slides. Superseded by [5] Deterministic Dictionaries, 2001.
|
[2] Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions
Rasmus Pagh. International Workshop on Algorithms and Data Structures (WADS), LNCS 1663, 1999
Presentation slides. Superseded by [26] Simple and Space-Efficient Minimal Perfect Hash Functions, 2007.
|
[1] Low Redundancy in Static Dictionaries with O(1) Lookup Time
Rasmus Pagh. International Colloquium on Automata, Languages and Programming (ICALP), 1999
Presentation slides. Superseded by [11] Low Redundancy in Static Dictionaries with Constant Query Time, 2001.
|
Allan Grønlund (1), Amer Sinha (1), Ameya Velingker (4), Amir Zandieh (1), Andrea Campagna (8), Andrea Montanari (1), Andreas Björklund (1), Andreas Goerdt (1), Andrzej Lingas (1), Anna Pagh (9), Anna Östlin (2), Badih Ghazi (5), Boel Nelson (2), Charalampos E. Tsourakakis (1), Chin-Wan Chung (1), Christian Janos Lebeda (2), Christian Worm Mortensen (1), Christos Levcopoulos (1), Claudio Orlandi (1), David P. Woodruff (4), David Rasmussen Lolck (1), Dimitris Fotakis (2), Djamal Belazzougui (4), Edith Cohen (2), Erik Demaine (1), Esben Rune Hansen (1), Fabiano C. Botelho (2), Flemming Friche Rodler (4), Francesco Silvestri (12), Friedhelm Meyer auf der Heide (1), Gil Segev (1), Giuseppe Persiano (1), Ha-Myung Park (2), Hannah Keller (1), Hao WU (1), Ilya Razenshteyn (1), Ioana Bercea (3), Ivan Damgård (1), Jakob Bæk Tejs Houen (3), Jakob Pagter (1), Jakub Tětek (1), Jalaj Upadhyay (1), Jan Gorodkin (1), Jesper W. Mikkelsen (1), Joachim Gudmundsson (1), Joel Daniel Andersson (2), Johan Sivertsen (5), Jóhannes B. Hreinsson (1), Kasper Green Larsen (4), Ke Yi (2), Kevin Yeo (1), Konstantin Kutzkov (6), Laurent Bulteau (1), Leszek Gasieniec (1), Martin Aumüller (8), Martin Dietzfelbinger (2), Matthew Skala (2), Matti Karppa (2), Mayank Goswami (3), Mette Berger (1), Michael Kapralov (1), Michael Mitzenmacher (3), Michael Rink (1), Michael Vesterli (1), Mihai Pătraşcu (3), Mikkel Thorup (6), Milan Ružić (4), Monika Henzinger (1), Morten Krøyer (1), Morten Skaarup Jensen (1), Morten Stöckel (5), Nina Mesing Stausholm (3), Ninh Pham (6), Niv Dayan (2), Nivio Ziviani (2), Noah Golowich (2), Ofir Geri (1), Or Zamir (1), Paolo Boldi (4), Pasin Manurangsi (4), Paul Spirakis (2), Pedro Reviriego (1), Peter Bro Miltersen (1), Peter Sanders (2), Peter Tiedemann (1), Philip Bille (1), Po-Shen Loh (1), Praneeth Kacham (1), Qin Zhang (2), Rasmus Pagh (150), Rasmus Resen Amossen (4), Ravi Kumar (4), Riko Jacob (1), Rolf Fagerberg (1), S. Srinivasa Rao (2), Samuel McCauley (1), Sariel Har-Peled (1), Sebastiano Vigna (4), Sepideh Mahabadi (1), Stefan Walzer (1), Sung-Hyon Myaeng (1), Takeshi Tokuyama (1), Teresa Anna Steiner (1), Thomas D. Ahle (3), Tobias Christiani (7), Toniann Pitassi (1), Torben Hagerup (1), U Kang (2), Udi Wieder (1), Uri Zwick (1), Vincent Froese (1), Virginia Vassilevska Williams (1), Yasuo Tabei (2), Yoshihiro Yamanishi (2), Zhewei Wei (2),