Institute of Information Science Academia Sinica
Topic: Dictionaries Revisited
Speaker: Prof. Martin Farach-Colton (Rutgers University)
Date: 2019-03-06 (Wed) 14:00 – 16:00
Location: Auditorium106 at IIS new Building
Host: Tsan-sheng Hsu


The dictionary is the most studied class of data structures, with dozens examples, including balanced search trees, hash tables, B-trees, log-structured merge trees, B^epsilon trees and many others.  But some surprisingly basic questions have still not been answered about them. In this talk, we will revisit some examples of these basic questions.  Our focus will be upper and lower bounds for the performance of dictionary data structures in external memory.


Martin Farach-Colton is a professor of computer science at Rutgers University.  He was Founder and CTO at Tokutek, Inc, an enterprise database company, which was acquired by Percona in 2015.

Farach-Colton works on pure and applied algorithms in I/O-efficient storage systems, streaming algorithms and string matching.  He has coauthored over 150 articles.  He has won several awards, including a Sloan Foundation Fellowship, a Test-of-Time award, several Best Paper awards, and teaching awards.  He was named a distinguished alum of the University of Maryland Computer Science Department on the occasion of their 40th anniversary.

Farach-Colton received his B.S. in Mathematics and Chemistry from the University of South Carolina in 1984.  He received his M.D. from Johns Hopkins in 1988 and his Ph.D. from the University of Maryland in 1991.  He has been a Member of Technical Staff at Bell Labs (1997-98) and was an early employee of Google, Inc. (2000-2002).