*The copyrights for journal and conference proceedings papers generally belong to the publisher.
The papers may be downloaded for personal or research purposes only.
The official and final publications are available at
SpringerLink,
IEEE Explore,
ACM Digital Library,
and other publisher archives.*

More information about publications can be found on my pages on Google Scholar, DBLP, and arXiv.

[125] Optimal Non-Adaptive Cell Probe Dictionaries and HashingKasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir. Submitted, 2023 |

[124] PLAN: Variance-Aware Private Mean EstimationMartin Aumüller, Christian Janos Lebeda, Boel Nelson, Rasmus Pagh. Submitted, 2023 |

[123] Differentially Private Selection from Secure Distributed ComputingIvan Damgård, Hannah Keller, Boel Nelson, Claudio Orlandi, Rasmus Pagh. Submitted, 2023 |

[122] Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential PrivacyDavid Rasmussen Lolck, Rasmus Pagh. Submitted, 2023 |

[121] Daisy Bloom FiltersIoana Bercea, Jakob Bæk Tejs Houen, Rasmus Pagh. Submitted, 2023 |

[120] A Smooth Binary Mechanism for Efficient Private Continual ObservationJoel Daniel Andersson, Rasmus Pagh. Proceedings of Neural Information Processing Symposium (NeurIPS), 2023 |

[119] Pseudorandom Hashing for Space-bounded Computation with Applications in StreamingPraneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff. Proceedings of Foundations of Computer Science (FOCS), 2023 |

[118] InfiniFilter: Expanding Filters to Infinity and BeyondNiv Dayan, Ioana Bercea, Pedro Reviriego, Rasmus Pagh. Proceedings of ACM SIGMOD Conference, 2023 |

[117] Simple Set SketchingJakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer. Proceedings of Symposium on Simplicity in Algorithms (SOSA), 2023 |

[116] Improved Utility Analysis of Private CountSketchRasmus Pagh, Mikkel Thorup. Proceedings of Neural Information Processing Symposium (NeurIPS), 2022 |

[115] HyperLogLogLog: Cardinality Estimation With One Log MoreMatti Karppa, Rasmus Pagh. Proceedings of SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2022 |

[114] DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor SearchMatti 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, 2022Based 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 RegimeRasmus Pagh, Nina Mesing Stausholm. International Conference on Algorithmic Learning Theory (ALT), 2022 |

[111] Differentially private sparse vectors with low error, optimal space, and fast accessMartin Aumüller, Christian Janos Lebeda, Rasmus Pagh. Proceedings of Conference on Computer and Communications Security (CCS), 2021Also 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 MessageBadih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Amer Sinha. Proceedings of International Conference on Machine Learning (ICML), 2021Also appeared as an abstract in Foundations of Responsible Computing (FORC), 2021. |

[109] CountSketches, Feature Hashing and the Median of ThreeKasper Green Larsen, Rasmus Pagh, Jakub Tětek. Proceedings of International Conference on Machine Learning (ICML), 2021 |

[108] Efficient Differentially Private F_{0} Linear SketchingRasmus Pagh, Nina Mesing Stausholm. Proceedings of International Conference on Database Theory (ICDT), 2021 |

[107] On the Power of Multiple Anonymous MessagesBadih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, Ameya Velingker. Proceedings of Eurocrypt, 2021Appeared as an abstract in Foundations of Responsible Computing (FORC), 2020. |

[106] WOR and p’s: Sketches for ℓ_{p}-sampling Without ReplacementEdith Cohen, Rasmus Pagh, David P. Woodruff. Proceedings of Neural Information Processing Symposium (NeurIPS), 2020 |

[105] Confirmation Sampling for Exact Nearest Neighbor SearchTobias Christiani, Rasmus Pagh, Mikkel Thorup. Proceedings of Similarity Search and Applications (SISAP), 2020 |

[104] Composable Sketches for Functions of Frequencies: Beyond the Worst CaseEdith Cohen, Ofir Geri, Rasmus Pagh. Proceedings of International Conference on Machine Learning (ICML), 2020 |

[103] Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication OverheadBadih Ghazi, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh. Proceedings of International Conference on Machine Learning (ICML), 2020Appears 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 KernelsYasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh. Data Science and Engineering, 2020Supersedes the preliminary version in ICDM 2019 |

[101] On the I/O complexity of the k-nearest neighbor problemMayank Goswami, Riko Jacob, Rasmus Pagh. Proceedings of Principles of Database Systems (PODS), 2020 |

[100] Fair Near Neighbor Search: Independent Range Sampling in High DimensionsMartin Aumüller, Rasmus Pagh, Francesco Silvestri. Proceedings of Principles of Database Systems (PODS), 2020Superseded by [113] Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All?, 2022. |

[99] Pure Differentially Private Summation from Anonymous MessagesBadih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. Proceedings of Information Theoretic Cryptography (ITC), 2020 |

[98] Private Aggregation from Fewer Anonymous MessagesBadih Ghazi, Pasin Manurangsi, Rasmus Pagh, Ameya Velingker. Eurocrypt, 2020Subsumes arXiv:1906.08320 |

[97] The space complexity of inner product filtersRasmus Pagh, Johan Sivertsen. International Conference on Database Theory (ICDT), 2020 |

[96] Oblivious Sketching of High-Degree Polynomial KernelsThomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Houen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh. Proceedings of 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020Based on arXiv:1909.01410 and arXiv:1909.01821 |

[95] Hardness of Bichromatic Closest Pair with Jaccard SimilarityRasmus Pagh, Nina Mesing Stausholm, Mikkel Thorup. European Symposium on Algorithms (ESA), 2019 |

[94] PUFFINN: Parameterless and Universally Fast FInding of Nearest NeighborsMartin Aumüller, Tobias Christiani, Rasmus Pagh, Michael Vesterli. European Symposium on Algorithms (ESA), 2019 |

[93] Space-efficient Feature Maps for String Alignment KernelsYasuo Tabei, Yoshihiro Yamanishi, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining (ICDM), 2019Superseded by [102] Space-efficient Feature Maps for String Alignment Kernels, 2020. |

[92] Enumerating Trillion Subgraphs On Distributed SystemsHa-Myung Park, Francesco Silvestri, Rasmus Pagh, Chin-Wan Chung, Sung-Hyon Myaeng, U Kang. ACM Transactions on Knowledge Discovery from Data, 2018Code and data sets. |

[91] Set Similarity Search for Skewed DataSamuel McCauley, Jesper W. Mikkelsen, Rasmus Pagh. Proceedings of Principles of Database Systems (PODS), 2018 |

[90] Distance-sensitive HashingMartin Aumüller, Tobias Christiani, Rasmus Pagh, Francesco Silvestri. Proceedings of Principles of Database Systems (PODS), 2018 |

[89] CoveringLSH: Locality-sensitive Hashing without False NegativesRasmus Pagh. ACM Transactions on Algorithms, 2018Special issue for SODA 2016. |

[88] Scalable and robust set similarity joinTobias Christiani, Rasmus Pagh, Johan Sivertsen. Proceedings of International Conference on Data Engineering (ICDE), 2018The proceedings version is an abridged form of the full paper on arXiv. |

[87] Simple Multi-Party Set ReconciliationMichael Mitzenmacher, Rasmus Pagh. Distributed Computing, 2017 |

[86] Range-efficient consistent sampling and locality-sensitive hashing for polygonsJoachim Gudmundsson, Rasmus Pagh. Proceedings of 28th International Symposium on Algorithms and Computation (ISAAC), 2017 |

[85] Set Similarity Search Beyond MinhashTobias Christiani, Rasmus Pagh. Proceedings of 47th ACM Symposium on Theory of Computing (STOC), 2017Presentation slides. Also presented as a poster. |

[84] I/O-efficient Similarity JoinRasmus Pagh, Ninh Pham, Francesco Silvestri, Morten Stöckel. Algorithmica 78:1263–1283, 2017 |

[83] Distance Sensitive Bloom Filters Without False NegativesMayank Goswami, Rasmus Pagh, Francesco Silvestri, Johan Sivertsen. Proceedings of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017 |

[82] Parameter-free Locality Sensitive Hashing for Spherical Range ReportingThomas D. Ahle, Martin Aumüller, Rasmus Pagh. Proceedings of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017 |

[81] Efficiently Correcting Matrix ProductsLeszek Gasieniec, Christos Levcopoulos, Andrzej Lingas, Rasmus Pagh, Takeshi Tokuyama. Algorithmica , 2016 |

[80] Approximate Furthest Neighbor with Application to Annulus QueryRasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala. Information Systems, special issue for SISAP, 2016 |

[79] Scalability and Total Recall with Fast CoveringLSHNinh Pham, Rasmus Pagh. Proceedings of International Conference on Information and Knowledge Management (CIKM), 2016 |

[78] On the Complexity of Inner Product Similarity JoinThomas D. Ahle, Rasmus Pagh, Ilya Razenshteyn, Francesco Silvestri. Proceedings of the 35th ACM Symposium on Principles of Database Systems (PODS), 2016 |

[77] Triangle counting in dynamic graph streamsLaurent Bulteau, Vincent Froese, Konstantin Kutzkov, Rasmus Pagh. Algorithmica 76, 2016Strengthens the result of the SWAT '14 paper of the same name. |

[76] Locality-sensitive Hashing without False NegativesRasmus Pagh. Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016Presentation slides. Superseded by [89] CoveringLSH: Locality-sensitive Hashing without False Negatives, 2018. A simple Python implementation is available. |

[75] Approximate Furthest Neighbor in High DimensionsRasmus Pagh, Francesco Silvestri, Johan Sivertsen, Matthew Skala. Proceedings of 8th International Conference on Similarity Search and Applications (SISAP), 2015Superseded by [80] Approximate Furthest Neighbor with Application to Annulus Query, 2016. |

[74] I/O-efficient Similarity Join in High DimensionsRasmus Pagh, Ninh Pham, Francesco Silvestri, Morten Stöckel. Proceedings of the 23rd European Symposium on Algorithms (ESA), 2015Presentation slides. Superseded by [84] I/O-efficient Similarity Join, 2017. |

[73] From Independence to Expansion and BackTobias Christiani, Rasmus Pagh, Mikkel Thorup. Proceedings of 47th ACM Symposium on Theory of Computing (STOC), 2015Presentation slides. |

[72] Approximate Range Emptiness in Constant Time and Optimal SpaceMayank Goswami, Allan Grønlund, Kasper Green Larsen, Rasmus Pagh. Proceedings of Symposium on Discrete Algorithms (SODA), 2015Presentation slides. |

[71] MapReduce Triangle Enumeration With GuaranteesHa-Myung Park, Francesco Silvestri, U Kang, Rasmus Pagh. Proceedings of Conference on Information and Knowledge Management (CIKM), 2014Superseded by [92] Enumerating Trillion Subgraphs On Distributed Systems, 2018. Code and data sets. |

[70] Generating k-independent variables in constant timeTobias Christiani, Rasmus Pagh. Proceedings of Foundations of Computer Science (FOCS), 2014Presentation slides. Full version available on arXiv. |

[69] The Input/Output Complexity of Sparse Matrix MultiplicationRasmus Pagh, Morten Stöckel. Proceedings of European Symposium on Algorithms (ESA), 2014Presentation slides. Also presented at SIAM Conference on Applied Linear Algebra, 2015. |

[68] Triangle counting in dynamic graph streamsKonstantin Kutzkov, Rasmus Pagh. Proceedings of 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2014Presentation slides. Superseded by [77] Triangle counting in dynamic graph streams, 2016. |

[67] Consistent subset samplingKonstantin Kutzkov, Rasmus Pagh. Proceedings of 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2014Presentation slides. Full version available on arXiv. |

[66] Listing TrianglesAndreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, Uri Zwick. Proceedings of 41st 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. Proceedings of the 33rd ACM Symposium on Principles of Database Systems (PODS), 2014 |

[64] The Input/Output Complexity of Triangle EnumerationRasmus Pagh, Francesco Silvestri. Proceedings of the 33rd ACM Symposium on Principles of Database Systems (PODS), 2014 |

[63] Efficient Estimation for High Similarities using Odd SketchesMichael Mitzenmacher, Rasmus Pagh, Ninh Pham. Proceedings of 23rd International World Wide Web Conference (WWW), 2014Presentation slides. Winner of best paper award. Selected as a Notable Computing Article of 2014 by ACM Computing Reviews. |

[62] Thresholds for Extreme OrientabilityPo-Shen Loh, Rasmus Pagh. Algorithmica 69 (3), 2014 |

[61] How to Approximate A Set Without Knowing Its Size in AdvanceRasmus Pagh, Gil Segev, Udi Wieder. Proceedings of 54th IEEE Foundations of Computer Science (FOCS), 2013 |

[60] Fast and Scalable Polynomial Kernels via Explicit Feature MapsNinh Pham, Rasmus Pagh. Proceedings of 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2013Source code is available in Matlab (by Ninh Pham) and C++ (by Johan von Tangen Sivertsen). |

[59] Compressed Matrix MultiplicationRasmus Pagh. ACM Transactions on Computation Theory, August 2013Presentation 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 HashingRasmus Pagh, Zhewei Wei, Ke Yi, Qin Zhang. Algorithmica, March 2013 |

[57] Practical Perfect Hashing Algorithm in Nearly Optimal SpaceFabiano C. Botelho, Rasmus Pagh, Nivio Ziviani. Information Systems Journal 38(1), 2013Implementation available in CMPH. |

[56] On the streaming complexity of computing local clustering coefficientsKonstantin Kutzkov, Rasmus Pagh. Proceedings of 6th ACM conference on Web Search and Data Mining (WSDM), 2013 |

[55] On Parallelizing Matrix Multiplication by the Column-Row MethodAndrea Campagna, Konstantin Kutzkov, Rasmus Pagh. Proceedings of the 15th Workshop on Algorithm Engineering and Experiments (ALENEX), 2013 |

[54] Better Size Estimation for Sparse Matrix ProductsRasmus Resen Amossen, Andrea Campagna, Rasmus Pagh. Algorithmica, March 2013Presentation slides. Note: A preliminary version appeared at RANDOM 2010. |

[53] A Near-linear Time Approximation Algorithm for Angle-based Outlier Detection in High-dimensional DataNinh Pham, Rasmus Pagh. Proceedings of 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2012Source code is available here. |

[52] Compressed Matrix MultiplicationRasmus Pagh. Proceedings of ACM Innovations in Theoretical Computer Science (ITCS), 2012Presentation slides. Superseded by [59] Compressed Matrix Multiplication, August 2013. |

[51] I/O-Efficient Data Structures for Colored Range and Prefix ReportingKasper Green Larsen, Rasmus Pagh. Proceedings of 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012Presentation slides. |

[50] Colorful Triangle Counting and a MapReduce ImplementationRasmus Pagh, Charalampos E. Tsourakakis. Information Processing Letters 112 (7), 2012 |

[49] Finding Associations and Computing Similarity via Biased Pair SamplingAndrea Campagna, Rasmus Pagh. Knowledge and Information Systems 31 (3), 2012Invited paper from IEEE 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 SkewAndrea Campagna, Konstantin Kutzkov, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining Workshops (KDCloud), 2011 |

[47] Linear probing with 5-wise independenceAnna Pagh, Rasmus Pagh, Milan Ružić. SIAM Review 53, 2011Published 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 HashingDjamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. ACM Journal of Experimental Algorithmics 16, 2011Implementations available in Sux. |

[45] A New Data Layout For Set Intersection on GPUsRasmus Resen Amossen, Rasmus Pagh. Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2011Presentation slides. Note: Tightness of the space bound shown in this paper is now known. |

[44] On Finding Frequent Patterns in Event SequencesAndrea Campagna, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining, 2010 |

[43] On Finding Similar Items in a Stream of TransactionsAndrea Campagna, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining Workshops (KDCloud), 2010 |

[42] Better Size Estimation for Sparse Matrix ProductsRasmus Resen Amossen, Andrea Campagna, Rasmus Pagh. Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM), LNCS 6302, 2010Presentation 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 ApplicationsDjamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Proceedings of the 18th European Symposium on Algorithms (ESA), LNCS 2161, 2010Presentation slides. |

[40] Tight Thresholds for Cuckoo Hashing via XORSATMartin Dietzfelbinger, Andreas Goerdt, Michael Mitzenmacher, Andrea Montanari, Rasmus Pagh, Michael Rink. Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 6198, 2010 |

[39] Cache-oblivious HashingRasmus Pagh, Zhewei Wei, Ke Yi, Qin Zhang. Proceedings of the 29th ACM Symposium on Principles of Database Systems (PODS), 2010 |

[38] Linear probing with constant independenceAnna Pagh, Rasmus Pagh, Milan Ružić. SIAM Journal on Computing 39, 2009Special issue for STOC 2007. Optimality of 5-wise independence has been shown by Pătraşcu and Thorup in in 2010. |

[37] Dispersing Hash FunctionsRasmus Pagh. Random Structures and Algorithms 35, 2009 |

[36] Finding Associations and Computing Similarity via Biased Pair SamplingAndrea Campagna, Rasmus Pagh. Proceedings of 9th IEEE International Conference on Data Mining (ICDM), 2009Presentation 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 AccessJóhannes B. Hreinsson, Morten Krøyer, Rasmus Pagh. Proceedings of the 17th European Symposium on Algorithms (ESA), LNCS 5757, 2009Presentation slides. |

[34] Faster join-projects and sparse matrix multiplicationsRasmus Resen Amossen, Rasmus Pagh. Proceedings of 12th International Conference on Database Theory (ICDT), 2009Presentation 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(N^{2/3} Z^{2/3} + N^{0.862} Z^{0.546}). In addition, the condition Z>N is required. Presentation in .mov format. |

[33] Theory and Practise of Monotone Minimal Perfect HashingDjamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX), 2009Superseded by [46] Theory and Practice of Monotone Minimal Perfect Hashing, 2011. Implementations available in Sux. |

[32] Monotone Minimal Perfect Hashing: Searching a Sorted TableDjamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009Presentation slides. Implementation available in Sux. |

[31] Secondary indexing in one dimension: Beyond B-trees and bitmap indexesRasmus Pagh, S. Srinivasa Rao. Proceedings of the 28th ACM Symposium on Principles of Database Systems (PODS), 2009Presentation slides. |

[30] Optimality in External Memory HashingMorten Skaarup Jensen, Rasmus Pagh. Algorithmica 52, 2008 |

[29] Uniform Hashing in Constant Time and Optimal SpaceAnna Pagh, Rasmus Pagh. SIAM Journal on Computing 38, 2008 |

[28] Succinct Data Structures for Retrieval and Approximate MembershipMartin Dietzfelbinger, Rasmus Pagh. Proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 5125, 2008Presentation slides. |

[27] Linear probing with constant independenceAnna Pagh, Rasmus Pagh, Milan Ružić. Proceedings of 39th ACM Symposium on Theory of Computing (STOC), 2007Presentation slides. Superseded by [38] Linear probing with constant independence, 2009. |

[26] Simple and Space-Efficient Minimal Perfect Hash FunctionsFabiano C. Botelho, Rasmus Pagh, Nivio Ziviani. Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS), 2007Presentation slides. Superseded by [57] Practical Perfect Hashing Algorithm in Nearly Optimal Space, 2013. Implementation available in CMPH. |

[25] Fast evaluation of union-intersection expressionsPhilip Bille, Anna Pagh, Rasmus Pagh. Proceedings of the 18th International Symposium on Algorithms And Computation (ISAAC), LNCS 4835, 2007Presentation 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 joinsAnna Pagh, Rasmus Pagh. Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS), 2006Presentation slides. (.mov format.) |

[23] Deterministic load balancing and dictionaries in the parallel disk modelMette Berger, Esben Rune Hansen, Rasmus Pagh, Mihai Pătraşcu, Milan Ružić, Peter Tiedemann. Proceedings of the 18th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2006Presentation slides. |

[22] De Dictionariis Dynamicis Pauco Spatio UtentibusErik Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Pătraşcu. Proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN), 2006Presentation slides. Note: A stronger result has been shown by Arbitman, Naor, and Segev in 2010. |

[21] External String Sorting: Faster and Cache-ObliviousRolf Fagerberg, Anna Pagh, Rasmus Pagh. Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 1373, 2006 |

[20] An Optimal Bloom Filter ReplacementAnna Pagh, Rasmus Pagh, S. Srinivasa Rao. Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005Presentation slides. |

[19] On Dynamic Range Reporting in One DimensionChristian Worm Mortensen, Rasmus Pagh, Mihai Pătraşcu. Proceedings of 37th ACM Symposium on Theory of Computing (STOC), 2005Presentation slides. |

[18] Space Efficient Hash Tables with Worst Case Constant Access TimeDimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis. Theory of Computing Systems 38, 2005Special issue for STACS 2003. |

[17] On Adaptive Integer SortingAnna Pagh, Rasmus Pagh, Mikkel Thorup. Proceedings of the 12th European Symposium on Algorithms (ESA), LNCS 3221, 2004Presentation slides. |

[16] Cuckoo HashingRasmus Pagh, Flemming Friche Rodler. Journal of Algorithms 51, 2004Other resources: Description on Wikipedia; Open problems on cuckoo hashing. Implementation in C available. |

[15] Space Efficient Hash Tables with Worst Case Constant Access TimeDimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis. Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS), 2003Presentation slides. Superseded by [18] Space Efficient Hash Tables with Worst Case Constant Access Time, 2005. |

[14] Uniform Hashing in Constant Time and Linear SpaceAnna Östlin, Rasmus Pagh. Proceedings of 35th ACM Symposium on Theory of Computing (STOC), 2003Presentation slides. Superseded by [29] Uniform Hashing in Constant Time and Optimal Space, 2008. |

[13] One-Probe SearchAnna Östlin, Rasmus Pagh. Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 2380, 2002Presentation slides. |

[12] Optimal Time-Space Trade-Offs for Non-Comparison-Based SortingRasmus Pagh, Jakob Pagter. Proceedings of 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002Presentation slides. |

[11] Low Redundancy in Static Dictionaries with Constant Query TimeRasmus Pagh. SIAM Journal on Computing 31, 2001Note: Stronger results have been shown by Mihai Pătraşcu in in 2008. |

[10] Lossy DictionariesRasmus Pagh, Flemming Friche Rodler. Proceedings of the 9th European Symposium on Algorithms (ESA), LNCS 2161, 2001Presentation slides. Extended version. |

[9] Cuckoo HashingRasmus Pagh, Flemming Friche Rodler. Proceedings of the 9th European Symposium on Algorithms (ESA), LNCS 2161, 2001Presentation 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 HashingRasmus Pagh. Proceedings of 33rd ACM Symposium on Theory of Computing (STOC), 2001Presentation slides. |

[7] A Trade-Off for Worst-Case Efficient DictionariesRasmus Pagh. Nordic Journal of Computing 7, 2000Special issue for SWAT 2000. |

[6] A new trade-off for deterministic dictionariesRasmus Pagh. Proceedings of the 7th Scandinavian Workshop on Algorithm Theory (SWAT), 2000Presentation slides. Superseded by [7] A Trade-Off for Worst-Case Efficient Dictionaries, 2000. |

[5] Deterministic DictionariesTorben Hagerup, Peter Bro Miltersen, Rasmus Pagh. Journal of Algorithms 41, 2001Note: Stronger results have been shown by Milan Ružić in in 2008. |

[4] Dispersing Hash FunctionsRasmus Pagh. Proceedings of the 4th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2000Presentation slides. Superseded by [37] Dispersing Hash Functions, 2009. |

[3] Faster Deterministic DictionariesRasmus Pagh. Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000Presentation slides. Superseded by [5] Deterministic Dictionaries, 2001. |

[2] Hash and Displace: Efficient Evaluation of Minimal Perfect Hash FunctionsRasmus Pagh. Proceedings of the 6th international Workshop on Algorithms and Data Structures (WADS), LNCS 1663, 1999Presentation slides. Superseded by [26] Simple and Space-Efficient Minimal Perfect Hash Functions, 2007. |

[1] Low Redundancy in Static Dictionaries with O(1) Lookup TimeRasmus Pagh. Proceedings of 26th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 1644, 1999Presentation slides. Superseded by [11] Low Redundancy in Static Dictionaries with Constant Query Time, 2001. |

Set Similarity - a SurveyRasmus Pagh. Algorithms and Data Structures Symposium (WADS), 2019 |

Similarity SketchingRasmus Pagh. Encyclopedia of Big Data Technologies, Springer, 2018 |

Hardness and Approximation of High-Dimensional Search ProblemsRasmus Pagh. International Symposium on Mathematical Foundations of Computer Science (MFCS), 2017 |

Dimension Reduction with CertaintyRasmus Pagh. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery (ECML-PKDD), 2016 |

Large-Scale Similarity Joins With GuaranteesRasmus Pagh. Similarity Search and Applications (SISAP), Invited talk, 2015Presentation slides. Further details can be found in our papers in ESA '15 and SODA '16. |

Correlated Locality-Sensitive HashingRasmus Pagh. ALGO plenary talk, 2015Presentation slides. |

On Multiseed Lossless FiltrationRasmus Pagh. Symposium on Combinatorial Pattern Matching (CPM), Invited talk, 2015Presentation slides. |

Large-Scale Similarity Joins With GuaranteesRasmus Pagh. International Conference on Database Theory (ICDT), Invited paper, 2015Presentation slides. Further details can be found in our paper in ESA '15. |

Association Rule Mining using Maximum EntropyRasmus Pagh, Morten Stöckel. Technical report, 2015 |

Cuckoo HashingRasmus Pagh. Encyclopedia of Algorithms, Springer, 2008 |

High-performance pseudorandomnessRasmus Pagh. Invited talk at Symposium on Experimental Algorithms (SEA), 2014 |

Basic External Memory Data StructuresRasmus Pagh. Algorithms for Memory Hierarchies. Advanced lectures, LNCS 2625, 2003Presentation slides. |

Hashing, randomness and dictionariesRasmus Pagh. PhD thesis, University of Aarhus, x + 167 pp., 2002Presentation slides. (.mov and .ppt format.) |

Fast Random Access to Wavelet Compressed Volumetric Data Using HashingRasmus Pagh, Flemming Friche Rodler. BRICS RS-01-34, 2001 |

Tetris er sværtRasmus Pagh. Aktuel Naturvidenskab 4, 2002 |

Overbeviselsens kunstRasmus Pagh. Aktuel Naturvidenskab 5, 2001Also in Jyllandsposten, September 22, 2002. |

Naturvidenskab@homeJan Gorodkin, Rasmus Pagh. Aktuel Naturvidenskab 4, 2001 |

Kan computere gætte?Rasmus Pagh. Aktuel Naturvidenskab 3, 2001 |

Big DataRasmus Pagh. OpenITU talk, 2015 |

Understanding Algorithms and Algorithms for Understanding (Big Data)Rasmus Pagh. Inaugural lecture, 2013 |

Cuckoo Hashing for UndergraduatesRasmus Pagh. Lecture note, 2006 |

Will the I/O model survive till the 22nd century?Rasmus Pagh. Talk at the Dagstuhl seminar on Cache-oblivious and cache-aware algorithms, 2004 |

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), Ha-Myung Park (2), Hannah Keller (1), Ilya Razenshteyn (1), Ioana Bercea (2), Ivan Damgård (1), Jakob Bæk Tejs Houen (3), Jakob Pagter (1), Jakub Tětek (1), Jan Gorodkin (1), Jesper W. Mikkelsen (1), Joachim Gudmundsson (1), Joel Daniel Andersson (1), Johan Sivertsen (5), Jóhannes B. Hreinsson (1), Kasper Green Larsen (4), Ke Yi (2), 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), Morten Krøyer (1), Morten Skaarup Jensen (1), Morten Stöckel (5), Nina Mesing Stausholm (3), Ninh Pham (6), Niv Dayan (1), 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 (147), 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), 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),

Updated: 2023-09-22