Jeff Vitter's Research Interests

In his research, Jeff Vitter seeks to exploit the rich interdependence between theory and practice in computer science. His work in algorithm design and analysis spans several application areas. The challenge in each case is to design algorithms that are both provably efficient and practical to implement.

Input/Output animation, © Scott Kim 2000

One theme in Dean Vitter's research is how to alleviate the input/output (I/O) bottleneck between fast internal memory and slow external storage (such as disk) that can occur when processing massive data sets. He has worked on efficient external memory algorithms in several domains, including geographic information systems (GIS), spatial databases, sorting, text and string indexing, matrix computations, graph traversal, range searching, data mining, and a variety of geometric and combinatorial problems. A related interest is how to take advantage of parallel disks or parallel hierarchical memories, in which communication with each parallel memory device takes place simultaneously. His group is involved in algorithm engineering using the TPIE system (Transparent Parallel I/O programming Environment). Another aspect of Dean Vitter's work involves novel machine learning and prediction mechanisms based upon data compression and locality, using the principle that the more compressible a sequence is, the more predictable it is. Examples include algorithms for caching, prefetching, data streams, database query optimization, data mining, and resource management in mobile computers. He has worked on efficient approaches to image, video, and text compression. He currently works on compressed data structures for searching, where the goal is to use a small amount of space equal to the entropy of the input data, yet still achieve fast search time. Previously, fast data structures for text indexing (such as suffix trees and suffix arrays) required several times more space than the data being indexed! Other interests include randomized, parallel, and incremental algorithms for computational geometry, graphics, random sampling, and random variate generation.

Several of Dean Vitter's recent publications, including a survey on external memory algorithms, in which the focus is on I/O, and a book on efficient algorithms for MPEG video compression, are available electronically via his online publication library. Alternatively, they're available via anonymous ftp at ftp.cs.duke.edu in directory pub/jsv/Papers. The full list of his publications appears in his curriculum vitæ.