Ian Munro

Biography

Dr. Ian Munro is a professor in the Cheriton School of Computer Science, University of Waterloo, University Avenue West, Waterloo, ON, Canada.

Research Interest

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).