Ian Munro joined the University of Waterloo as a faculty member 50 years ago this fall, just before defending his PhD thesis at the University of Toronto.
The faculty members in Computer Science were young. Only one was over 40 and at least a quarter were under 30. Ian Munro, who had just turned 24, was the youngest professor in the department.
“I started university studies at UNB, but during my undergrad degree I went on an exchange plan to UBC from ‘66 to ‘67,” he recalls. “It was through this and summer jobs that I got into computing. When I began graduate studies, I had more computing experience than most students had — except maybe those at Waterloo.”
During his seven years of university education, Ian never spent more than two years in a row at the same university. “It’s funny in a way that I moved around a lot while in university,” he chuckled, “then got a job I’ve held for half a century.”
J.
Ian
Munro
is
the
Tier
I
Canada
Research
Chair
in
Algorithm
Design,
a
position
first
awarded
in
2001
and
renewed
most
recently
in
2016.
In
2003,
he
became
a
Fellow
of
the
Royal
Society
of
Canada,
and
in
2006
was
named
a
University
Professor.
In
2008,
University
Professor
Munro
was
named
a
Fellow
of
the
Association
for
Computing
Machinery
for
his
contributions
to
algorithms
and
data
structures.
Most
recently,
he
was
awarded
the
2016
Lifetime
Achievement
Award
from
CS-Can
|
Info-Can.
He
is
Canada’s
authority
on
data
structures
and
an
international
leader
in
the
field
of
algorithms
and
data
structures.
Ian has held numerous administrative positions at Waterloo, including Director of the Institute for Computer Research, Associate Chair of Undergraduate Studies, and Associate Chair of Graduate Studies. He also served on the board of Waterloo’s Centre for Education in Mathematics and Computing (CEMC). In his first 30 years, he taught students at all levels of study in computer science and related disciplines, but in the past 20 years he has focused primarily on teaching upper-year undergrads and graduates in his research area.
Over his career, Ian has made many fundamental and lasting contributions in sorting, selection and data structures, including optimal binary search trees, heaps and hashing. He stayed focused on these subjects, taking an expansive view, which included text search and data streams at a time when few others were exploring these areas.
“My first research interest was in data structures — in other words, the problem of organizing data so that the necessary operation can be performed efficiently — but I drifted into perceptrons, which are a forerunner of neural networks, and into arithmetic computation,” he said. “Later on, especially after I came to Waterloo, my focus moved back to data structures.”
An important theme in most of his research has been space efficiency. Computer memories have grown by eight or nine orders of magnitude since the seventies, as have the sizes of problems a computer can solve, but as computer memory is hierarchical, space in fast memory has remained a crucial and scarce resource. If anything, the need for space efficiency is greater today than ever.
Ian has worked extensively on three types of problems involving severe space restrictions.
“The first type of problem I worked on in the seventies and eighties was on searching in hash tables with no auxiliary memory,” he said. “The second topic was on implicit data structures, where one searches for values based on comparisons, determining which is larger, but no auxiliary information is permitted. Using such techniques, you can perform surprisingly fast searches, including find-the-next-larger searches and updates.”
The third topic, which he continues to work on today, is that of succinct data structures.
“In the last half of the eighties and into the nineties I became involved in a project, led by Gaston Gonnet and Frank Tompa, to develop techniques and software to computerize the Oxford English Dictionary, a project that ultimately led to the creation of OpenText Corporation.”
“A data structure that allows one to search for an arbitrary phrase in a text, reporting the number of times it occurs, is essentially a reference to a list of all these points, was one of the key advances in the project,” he explains. “The runtime of the search depended only on the phrase and is independent of the size of the text. The problem was that the space requirement for the Oxford English Dictionary was about five times the memory — including disk memory — we had, although the raw data fit into about half the available memory. A simpler but space efficient structure was adopted, even though search times depended on the size of the text. The problem was that the elegant structure required representing a binary tree with its number of nodes equal to the length of the text. Standard representations are just too big.”
The solution, discovered a couple of years later, was a representation using the mathematically minimum possible space — about two bits per node — but permitting the necessary operation to be performed in constant time, an operation independent of the tree size.
“This was when, with my graduate students and postdoctoral researchers, I began to work on similar problems of developing fast computational methods that use the minimum space.”
In 2013, a conference at Waterloo was held in his honour, with talks given by international and Canadian colleagues as well as current and former students. A festschrift was published as its proceedings. Known as Ianfest-66, the Conference on Space-Efficient Data Structures, Streams, and Algorithms was held over August 15 and 16 at the University of Waterloo to celebrate his 66th birthday.
In addition to his research contributions spanning some five decades, Ian has served on the boards of several technology companies. He has also remained keen to volunteer his time to introduce, encourage and nurture budding young computer scientists through his involvement with the Canadian Computing Competition, a fun challenge for secondary school students with an interest in algorithms and programming.
“I was on the Canadian Computing Competition and later the Canadian Computing Olympiad committees from 1995 to 2015, making up the questions and lectures for those who came to the second round of competitions in Waterloo,” he said. “I was also involved with the International Olympiad in Informatics from 2000 to 2010 as a leader of the Canadian team and for three years as a member of its International Scientific Committee.”
At 74, Ian has not slowed down.
He continues to supervise graduate students and mentor postdoctoral researchers, while educating and inspiring students and faculty alike. He has served on about 100 conference program committees and chaired a dozen. He has published more than 100 journal papers and 150 conference papers. During his five decades at Waterloo, he has mentored some 20 postdoctoral fellows, supervised 25 PhD students, and advised more than 60 master’s students, many of whom have gone on to hold prestigious positions in industry and academia.