Norbert Zeh - Research

Research interests

I am interested in the design and implementation of algorithms and data structures. My particular research interests include

Algorithms and data structures
I/O-efficient algorithms
Cache-oblivious algorithms
Graph algorithms
Computational geometry

My recent work has focused on the design of I/O-efficient algorithms for undirected graphs. Currently I am working on I/O-efficient algorithms for directed graphs, the design and implementation of practical I/O-efficient graph algorithms, and the solution of optimization problems on graphs through edge replacement.

Other topics that interest me are the application of algorithmic techniques to problems in parallel data mining (jointly with Andrew Rau-Chaplin), automatic term extraction (jointly with Evangelos Milios), and natural language processing (jointly with Vlado Keselj).

Current students

I currently have the pleasure of supervising the following students:

Kathryn Duffy (Ph.D., co-supervisor: Rob Beiko)
Current research: Methods for protein clustering.
Adan Cosgaya (Ph.D., co-supervisor: Andrew Rau-Chaplin)
Current research: Engineering I/O-efficient graph algorithms.
Oliver Baltzer (Ph.D., co-supervisor: Andrew Rau-Chaplin)
Thesis topic: Spatial OLAP
Chris Hamilton (Ph.D., co-supervisor: Jon Borwein)
Current research: Cache-oblivious geometric search problems.
Jeremy Moses (M.C.S.)
Thesis title: An Experimental Evaluation of Cache-Oblivious Range Search Structures.
Muthukumaran Chakkaravarti (M.C.S.)
Thesis title: An Experimental Evaluation of Cache-Oblivious Shortest-Path Algorithms.
Chris Whidden (BCS Hons)
Thesis title: Structural properties and fixed-parameter tractability of sorting by transpositions.
Tomas Hofmann (BCS Hons)
Thesis topic: TBA
Craig Gidney (BCS Hons)
Thesis topic: TBA

Former students

Patrick Nicholson (BCS Hons)
Thesis title: Computing of C/NC Values on Large Text Corpora via Frequency Filtering
Ian Hopkins (B.C.S. Honours, NSERC USRA, co-supervisor: Evangelos Milios)
Thesis title: Algorithmic Aspects of C/NC-Value Computation.
Hema Jampala (M.C.S.)
Thesis title: Cache-Oblivious Planar Shortest Paths and Separators.
Jean-Paul Deveaux (M.A.C.S., co-supervisor: Andrew Rau-Chaplin)
Project title: Adaptive Tuple Differential Coding in Statistical Datasets.
Haixia Tang (M.A.C.S., co-supervisor: Vlado Keselj)
Project title: A Suffix Array Based N-gram Extraction Algorithm.
Joel Muzzerall (B.C.S. Honours, NSERC USRA)
Thesis title: Towards a Middle-Game Engine for Dots-and-Boxes: Game Theory Meets Graph Algorithms.

Thesis topics

In general, I feel that students are more enthusiastic about their work if their thesis topic is a topic of their choice. So, if you have a topic you are interested in working on and you think that I might be interested in this topic, come and talk to me. The following is a list of topics I am looking for students to work on. If you share my interest in one of the above research areas, but none of the topics listed here excites you, come and talk to me.

Algorithms for large directed graphs

Description: The goal of this thesis is to make progress on solving fundamental problems on large directed graphs. The currently hot open problems, in increasing order of difficulty (according to what I believe), include reachability (can a vertex v reach a vertex w?), topological sorting, strong connectivity, breadth-first search, and shortest paths.

Level: Ph.D. thesis or Master's thesis

References:

L. Arge and N. Zeh. "I/O-efficient strong connectivity and depth-first search for directed planar graphs.'' In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 261–270, 2003.

L. Arge, L. Toma, N. Zeh. "I/O-efficient topological sorting of planar DAGs.'' In Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 85–93, 2003.

N. Zeh. "I/O-efficient graph algorithms." In EEF Summer School on Massive Data Sets. To appear. (Ask me for a copy.)

Cache-oblivious algorithms for planar graphs

Description: The goal of this thesis is to develop cache-oblivious algorithms for fundamental problems on planar graphs. An algorithm is cache-oblivious if it takes full advantage of the presence of cache memory while not knowing the parameters such as cache size and cache line length. The problems to be studied are computing planar separators, planarity testing, shortest paths, strong connectivity, and depth-first search.

Level: Ph.D. thesis or Master's thesis

References

L. Arge, G. S. Brodal, and L. Toma. "On external memory MST, SSSP and multi-way planar graph separation." In Proceedings of Scandinavian Workshop on Algorithm Theory (SWAT 2000). Springer-Verlag, 2000.

L. Arge and N. Zeh. "I/O-efficient strong connectivity and depth-first search for directed planar graphs.'' In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 261–270, 2003.

A. Maheshwari and N. Zeh. "I/O-optimal algorithms for planar graphs using separators." In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), San Francisco, January 6–8, 2002, pp.372–381.

N. Zeh. "I/O-efficient graph algorithms." In EEF Summer School on Massive Data Sets. To appear. (Ask me for a copy.)

Practical algorithms for large graphs

Description: A large number of theoretically efficient algorithms for fundamental problems on large graphs have been developed. However, most of them are too complicated to be of any practical value. This thesis aims at rectifying this situation through the development and implementation of practical algorithms. Ideally, one hopes for simple theoretically optimal algorithms, but theoretically suboptimal algorithms that perform well in practice and even use heuristic approaches are also of interest.

Level: Master's or Honour's thesis/project

References

TPIE Manual. (http://www.cs.duke.edu/TPIE)

N. Zeh. "I/O-efficient graph algorithms." In EEF Summer School on Massive Data Sets. To appear. (Ask me for a copy.)

Other topics

Ask me.

Norbert Zeh	Research
Home Teaching CSCI 3110 CSCI 6104 Grading Policies Office hours Research Interests Thesis topics Publications Journal papers Conference papers Technical reports Theses Book chapters Curriculum vitae	I am always looking for students. Talk to me, if you are interested in writing your thesis under my supervision. I am also interested in co-supervising students on applications of algorithmic techniques to applied areas. Potential co-supervisors are Evangelos Milios, Andrew Rau-Chaplin, and Vlado Keselj. Research interests I am interested in the design and implementation of algorithms and data structures. My particular research interests include Algorithms and data structures I/O-efficient algorithms Cache-oblivious algorithms Graph algorithms Computational geometry My recent work has focused on the design of I/O-efficient algorithms for undirected graphs. Currently I am working on I/O-efficient algorithms for directed graphs, the design and implementation of practical I/O-efficient graph algorithms, and the solution of optimization problems on graphs through edge replacement. Other topics that interest me are the application of algorithmic techniques to problems in parallel data mining (jointly with Andrew Rau-Chaplin), automatic term extraction (jointly with Evangelos Milios), and natural language processing (jointly with Vlado Keselj). Current students I currently have the pleasure of supervising the following students: Kathryn Duffy (Ph.D., co-supervisor: Rob Beiko) Current research: Methods for protein clustering. Adan Cosgaya (Ph.D., co-supervisor: Andrew Rau-Chaplin) Current research: Engineering I/O-efficient graph algorithms. Oliver Baltzer (Ph.D., co-supervisor: Andrew Rau-Chaplin) Thesis topic: Spatial OLAP Chris Hamilton (Ph.D., co-supervisor: Jon Borwein) Current research: Cache-oblivious geometric search problems. Jeremy Moses (M.C.S.) Thesis title: An Experimental Evaluation of Cache-Oblivious Range Search Structures. Muthukumaran Chakkaravarti (M.C.S.) Thesis title: An Experimental Evaluation of Cache-Oblivious Shortest-Path Algorithms. Chris Whidden (BCS Hons) Thesis title: Structural properties and fixed-parameter tractability of sorting by transpositions. Tomas Hofmann (BCS Hons) Thesis topic: TBA Craig Gidney (BCS Hons) Thesis topic: TBA Former students Patrick Nicholson (BCS Hons) Thesis title: Computing of C/NC Values on Large Text Corpora via Frequency Filtering Ian Hopkins (B.C.S. Honours, NSERC USRA, co-supervisor: Evangelos Milios) Thesis title: Algorithmic Aspects of C/NC-Value Computation. Hema Jampala (M.C.S.) Thesis title: Cache-Oblivious Planar Shortest Paths and Separators. Jean-Paul Deveaux (M.A.C.S., co-supervisor: Andrew Rau-Chaplin) Project title: Adaptive Tuple Differential Coding in Statistical Datasets. Haixia Tang (M.A.C.S., co-supervisor: Vlado Keselj) Project title: A Suffix Array Based N-gram Extraction Algorithm. Joel Muzzerall (B.C.S. Honours, NSERC USRA) Thesis title: Towards a Middle-Game Engine for Dots-and-Boxes: Game Theory Meets Graph Algorithms. Thesis topics In general, I feel that students are more enthusiastic about their work if their thesis topic is a topic of their choice. So, if you have a topic you are interested in working on and you think that I might be interested in this topic, come and talk to me. The following is a list of topics I am looking for students to work on. If you share my interest in one of the above research areas, but none of the topics listed here excites you, come and talk to me. Algorithms for large directed graphs Description: The goal of this thesis is to make progress on solving fundamental problems on large directed graphs. The currently hot open problems, in increasing order of difficulty (according to what I believe), include reachability (can a vertex v reach a vertex w?), topological sorting, strong connectivity, breadth-first search, and shortest paths. Level: Ph.D. thesis or Master's thesis References: L. Arge and N. Zeh. "I/O-efficient strong connectivity and depth-first search for directed planar graphs.'' In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 261–270, 2003. L. Arge, L. Toma, N. Zeh. "I/O-efficient topological sorting of planar DAGs.'' In Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 85–93, 2003. N. Zeh. "I/O-efficient graph algorithms." In EEF Summer School on Massive Data Sets. To appear. (Ask me for a copy.) Cache-oblivious algorithms for planar graphs Description: The goal of this thesis is to develop cache-oblivious algorithms for fundamental problems on planar graphs. An algorithm is cache-oblivious if it takes full advantage of the presence of cache memory while not knowing the parameters such as cache size and cache line length. The problems to be studied are computing planar separators, planarity testing, shortest paths, strong connectivity, and depth-first search. Level: Ph.D. thesis or Master's thesis References L. Arge, G. S. Brodal, and L. Toma. "On external memory MST, SSSP and multi-way planar graph separation." In Proceedings of Scandinavian Workshop on Algorithm Theory (SWAT 2000). Springer-Verlag, 2000. L. Arge and N. Zeh. "I/O-efficient strong connectivity and depth-first search for directed planar graphs.'' In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 261–270, 2003. A. Maheshwari and N. Zeh. "I/O-optimal algorithms for planar graphs using separators." In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), San Francisco, January 6–8, 2002, pp.372–381. N. Zeh. "I/O-efficient graph algorithms." In EEF Summer School on Massive Data Sets. To appear. (Ask me for a copy.) Practical algorithms for large graphs Description: A large number of theoretically efficient algorithms for fundamental problems on large graphs have been developed. However, most of them are too complicated to be of any practical value. This thesis aims at rectifying this situation through the development and implementation of practical algorithms. Ideally, one hopes for simple theoretically optimal algorithms, but theoretically suboptimal algorithms that perform well in practice and even use heuristic approaches are also of interest. Level: Master's or Honour's thesis/project References TPIE Manual. (http://www.cs.duke.edu/TPIE) N. Zeh. "I/O-efficient graph algorithms." In EEF Summer School on Massive Data Sets. To appear. (Ask me for a copy.) Other topics Ask me.