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.
For a list of publications ordered by number of citations, see my Google Scholar page.
| [55] Thresholds for Extreme Orientability Po-Shen Loh, Rasmus Pagh. Submitted, 2012 |
| [54] A New Approach to Parallelizing the Column-Row Method Andrea Campagna, Konstantin Kutzkov, Rasmus Pagh. Submitted, 2012 |
| [53] Consistent subset sampling Konstantin Kutzkov, Rasmus Pagh. Under revision, 2012 |
| [52] Compressed Matrix Multiplication Rasmus Pagh. Proceedings of ACM Innovations in Theoretical Computer Science (ITCS), 2012 Presentation slides. |
| [51] I/O-Efficient Data Structures for Colored Range and Prefix Reporting Kasper Green Larsen, Rasmus Pagh. Proceedings of 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012 Presentation slides. |
| [50] Frequent Pairs in Data Streams: Exploiting Parallelism and Skew Andrea Campagna, Konstantin Kutzkov, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining Workshops (KDCloud), 2011 |
| [49] Colorful Triangle Counting and a MapReduce Implementation Rasmus Pagh, Charalampos E. Tsourakakis. Information Processing Letters, 2011 Revised version to appear. |
| [48] Finding Associations and Computing Similarity via Biased Pair Sampling Andrea Campagna, Rasmus Pagh. Knowledge and Information Systems, 2011 Invited paper from ICDM 2009. To appear. |
| [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. Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2011 Presentation slides. |
| [44] On Finding Frequent Patterns in Event Sequences Andrea Campagna, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining, 2010 |
| [43] On Finding Similar Items in a Stream of Transactions Andrea Campagna, Rasmus Pagh. Proceedings of IEEE International Conference on Data Mining Workshops (KDCloud), 2010 |
| [42] Better Size Estimation for Sparse Matrix Products Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh. Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM), LNCS 6302, 2010 Presentation slides. Note: The version published in the RANDOM proceedings contained a mistake that matters whenever z<n. This has been corrected in the arXiv version (v2). |
| [41] Fast Prefix Search in Little Space, with Applications Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Proceedings of the 18th European Symposium on Algorithms (ESA), LNCS 2161, 2010 Presentation slides. |
| [40] Tight Thresholds for Cuckoo Hashing via XORSAT Martin 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 Hashing Rasmus 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 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. Proceedings of the 9th IEEE International Conference on Data Mining, 2009 Presentation slides. Superseded by [48] Finding Associations and Computing Similarity via Biased Pair Sampling, 2011. |
| [35] Storing a Compressed Function with Constant Time Access Jóhannes B. Hreinsson, Morten Krøyer, Rasmus Pagh. Proceedings of the 17th European Symposium on Algorithms (ESA), LNCS 5757, 2009 Presentation slides. |
| [34] Faster join-projects and sparse matrix multiplications Rasmus Resen Amossen, Rasmus Pagh. Proceedings of 12th International Conference on Database Theory (ICDT), 2009 Presentation slides. (.mov format.) |
| [33] Theory and Practise of Monotone Minimal Perfect Hashing Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, Sebastiano Vigna. Proceedings of the 11th 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. Proceedings of the 20th ACM-SIAM 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. Proceedings of the 28th ACM 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. Proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 5125, 2008 Presentation slides. |
| [27] Linear probing with constant independence Anna Pagh, Rasmus Pagh, Milan Ružić. Proceedings of 39th ACM 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. Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS), 2007 Presentation slides. Implementation available in CMPH. |
| [25] Fast evaluation of union-intersection expressions Philip Bille, Anna Pagh, Rasmus Pagh. Proceedings of the 18th International Symposium on Algorithms And Computation (ISAAC), LNCS 4835, 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. Proceedings of the 25th ACM Symposium on Principles of Database Systems, 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. Proceedings of the 18th ACM 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. Proceedings of the 5th 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. Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 1373, 2006 |
| [20] An Optimal Bloom Filter Replacement Anna Pagh, Rasmus Pagh, S. Srinivasa Rao. Proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005 Presentation slides. |
| [19] On Adaptive Integer Sorting Anna Pagh, Rasmus Pagh, Mikkel Thorup. Proceedings of the 12th European Symposium on Algorithms (ESA), LNCS 3221, 2004 Presentation slides. |
| [18] On Dynamic Range Reporting in One Dimension Christian Worm Mortensen, Rasmus Pagh, Mihai Pătraşcu. Proceedings of 37th ACM Symposium on Theory of Computing (STOC), 2005 Presentation slides. |
| [17] 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. |
| [16] Cuckoo Hashing Rasmus Pagh, Flemming Friche Rodler. Journal of Algorithms 51, 2004 Other resources: Description on Wikipedia; Open problems on cuckoo hashing. |
| [15] Space Efficient Hash Tables with Worst Case Constant Access Time Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis. Proceedings of the 20th Symposium on Theoretical Aspects of Computer Science (STACS), 2003 Presentation slides. Superseded by [17] Space Efficient Hash Tables with Worst Case Constant Access Time, 2005. |
| [14] Uniform Hashing in Constant Time and Linear Space Anna Östlin, Rasmus Pagh. Proceedings of 35th ACM 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. Proceedings of 29th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 2380, 2002 Presentation slides. |
| [12] Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting Rasmus Pagh, Jakob Pagter. Proceedings of 13th ACM-SIAM 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. Proceedings of the 9th European Symposium on Algorithms (ESA), LNCS 2161, 2001 Presentation slides. Extended version. |
| [9] Cuckoo Hashing Rasmus Pagh, Flemming Friche Rodler. Proceedings of the 9th European Symposium on Algorithms (ESA), LNCS 2161, 2001 Presentation slides. Superseded by [16] Cuckoo Hashing, 2004. Received best student paper award. |
| [8] On the Cell Probe Complexity of Membership and Perfect Hashing Rasmus Pagh. Proceedings of 33rd ACM 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 |
| [6] A new trade-off for deterministic dictionaries Rasmus Pagh. Proceedings of the 7th 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. Proceedings of the 4th 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. Proceedings of 11th ACM-SIAM 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. Proceedings of the 6th 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. Proceedings of 26th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 1644, 1999 Presentation slides. Superseded by [11] Low Redundancy in Static Dictionaries with Constant Query Time, 2001. |
| Cuckoo Hashing Rasmus Pagh. Encyclopedia of Algorithms, Springer, 2008 |
| Basic External Memory Data Structures Rasmus Pagh. Algorithms for Memory Hierarchies. Advanced lectures, LNCS 2625, 2003 Presentation slides. |
| Hashing, randomness and dictionaries Rasmus Pagh. PhD thesis, University of Aarhus, x + 167 pp., 2002 Presentation slides. (.mov and .ppt format.) |
| Tetris er svært Rasmus Pagh. Aktuel Naturvidenskab 4, 2002 |
| Overbeviselsens kunst Rasmus Pagh. Aktuel Naturvidenskab 5, 2001 Also in Jyllandsposten, September 22, 2002. |
| Naturvidenskab@home Jan Gorodkin, Rasmus Pagh. Aktuel Naturvidenskab 4, 2001 |
| Kan computere gætte? Rasmus Pagh. Aktuel Naturvidenskab 3, 2001 |
| Cuckoo Hashing for Undergraduates Rasmus 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 |
Updated: 2012-02-07