Ian Munro

Computational efficiency

Ian Munro is exploring problems of efficient computation from two directions. The first problem explores the notion of trying to simultaneously get the best possible time and the best possible space in database querying and indexing – provably. The specific problem is with text indexing – searching for specific phrases within gigabytes or terabytes of data to instantly find all places of occurrence. For instance, a search for a specific amino acid sequence in a DNA database would return all instances of the sequence in the time required to run the pattern.

Professor Munro’s second focus seeks to develop algorithms that create the best possible movement of information within and between different hierarchies of memory, without special configuration at each level of memory. This cache-oblivious access optimizes the efficiency with which storage and retrieval happens. Munro has found that the size of the problem and functional parameters do not affect the efficiency of this solution. This kind of efficiency will have implications for industries dealing with large problems – cost of computation will be less.

University of Waterloo Mathematics, Annual Report 2004