Dr. Jeffrey Vitter, professor in the Department of Computer Science and Engineering at Texas A&M University and incoming provost and executive vice chancellor at the University of Kansas, will present a keynote address at the 21st Annual Symposium on Combinatorial Pattern Matching.
The symposium, whose proceedings are part of the Springer series on Lecture Notes in Computer Science, will take place June 21–23 in New York. It is the premier conference worldwide on the subject of pattern matching, and it investigates a variety of topics in bioinformatics, coding and data compression, data mining, string algorithms, and text search.
Vitter’s address, “Compression, Indexing, and Retrieval for Massive String Data ,” deals with the intersection of two fields he helped found: compressed data structures and external memory algorithms. In compressed data structures, the goal is to operate directly on compressed representations of data, yet still achieve fast response time. For example, in the 1990s, the state-of-the-art methods to support fast pattern matching in a given string required an index structure many times larger than the string data it was indexing. Research over the last 12 years has reduced the index size to a fraction of the string data size, and in addition, the indexing structure can reproduce the original data at will, so the original data can be discarded. In the external memory setting, the problem instances considered involve massive amounts of data, and the challenge is to design algorithms that avoid a bottleneck in I/O communication.
Vitter recently published a reference book in the field, Algorithms and Data Structures for External Memory.
Information on the symposium is available online at http://cs.nyu.edu/parida/CPM2010/ .