Information for


Ian MunroResearch interests

Ian Munro works in the general area of algorithms and data structures, straddling the line between theory and applications. Most of his work has been on data structures, with a particular interest in space efficient structures. The general goal is to develop data structures that are provably optimal in time and provably minimal in space requirements. A major theme in his recent work has been succinct data structures, that is the representation of structural information in (virtually) the information theoretic minimum space while permitting the necessary operations to be performed very quickly. For example, there are about 4n or 22n trees on n nodes; data structures have been developed so that a tree can be represented in roughly 2n bits while supporting, in constant time, the operations of moving to a child or the parent, or determining the size of the subtree rooted at a given node. This works relates to data compression and working with data in compressed form. A major application of this is in the indexing of text (e.g. English text or a genome) to permit fast search for any query substring. A theme in some of Munro’s earlier work was that of implicit data structures, where the only structural information is implicit in the order of the values. The heap is the “classic” example of an implicit priority queue. The research has involved the development of analogous structures supporting a broad array of operations. Other aspects of Professor Munro’s work include probabilistic techniques, such as the development and analysis of various types of hashing schemes, and amortized behaviour, i.e. guaranteeing that while any individual operation may be rather costly, any long sequence of operations can be performed quickly. This also involves dealing with competitive methods, that is ones whose behaviour on a sequence of operations, reacting to each request as presented, is close to the optimal one could achieve on that sequence if it were known in advance. This includes work related to the so called splay tree conjecture. Much of the work has been motivated by specific applications. For example, Dr. Munro was a member of the Waterloo team on the Oxford English Dictionary Project, a text data base research effort that led to the formation of Open Text Corporation. Current research includes projects supported by Cisco and Caris Universal Systems (a Canadian company dealing with large scale oceanographic data).

Degrees and awards

BA (New Brunswick), MSc (British Columbia), PhD (Toronto)

Fellow of the ACM (2009); ISAAC Best Paper Award (2007); University Professor, University of Waterloo (2006); IBM CAS Pioneer of Computing (2005); Fellow of the Royal Society of Canada (2003); Canada Research Chair I in Algorithm Design (2001); Marsland Faculty Fellowship in Information Technology, University of Waterloo (2000-2003)

Industrial and sabbatical experience

Dr. Munro has held visiting appointments at a number of well known research institutions including the Max Planck Institute for Informatics, Princeton University, the University of Arizona, and Warwick University. He has consulted or served as a board member for a variety of large and small information technology companies.

Representative publications

Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro: Sorting under partial information (without the ellipsoid algorithm). STOC 2010: 359-368

Gerth Stølting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro: Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs. SODA 2010: 1448-1456

Jean Cardinal, Samuel Fiorini, Gwenaël Joret, Raphaël M. Jungers, J. Ian Munro: An Efficient Algorithm for Partial Order Production. SIAM J. Comput. 39(7): 2927-2940 (preliminary version in STOC 2009)

M.Z. Rahman and J.I. Munro. Integer Representation and Counting in the Bit Probe Model. Algorithmica 56(1): 105-127 (2010) Preliminary version winner Best Paper Award in ISAAC 2007

Arash Farzan, J. Ian Munro: Dynamic Succinct Ordered Trees. ICALP (1) 2009: 439-450

Reza Dorrigiv, Alejandro López-Ortiz, J. Ian Munro: On the relative dominance of paging algorithms. Theor. Comput. Sci. 410(38-40): 3694-3701 (2009)

L. Arge, M.A. Bender, E.D. Demaine, B. Holland-Minkley, and J.I. Munro. An Optimal Cache-Oblivious Priority Queue and Its Application to Graph Algorithms. SIAM Journal on Computing, 36(6):1672-1695, 2007.

J. Barbay, M. He, J.I. Munro, and S. S. Rao. Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees. Proceedings of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 680-689, 2007.

University of Waterloo
Contact information: