Faculty of Computer Science
6050 University Avenue
Dalhousie University
Halifax, NS
COMPUTER SCIENCE SEMINAR
Speaker: Dr. Meng He
University of Waterloo
Title: Succinct Data Structures
Date: Thursday, July 14, 2011
Time: 11:30 a.m.
Location: Jacob Slonim Conference Room (430), Computer Science
Dalhousie University
6050 University Avenue, Halifax
Abstract:
The problem of efficiently storing and retrieving information is an essential topic in computer science. During the past decades, various techniques have been developed to index data so that useful information can be retrieved almost instantaneously by performing queries for keywords or phrases. In recent years, as the size of the data has grown rapidly, many techniques that are useful for small, older systems have become infeasible for large, modern applications, because they occupy too much storage. Most of this space is not raw data, but structural information added to improve search efficiency. Succinct data structures were proposed to address this problem, so that the information in large systems can be retrieved quickly, but the space requirement is little more than that of the raw data.
In this presentation, I will first introduce succinct data structures. I will then focus on my contributions to succinct data structures, including using the notion of succinct indexes in the design of succinct data structures, designing succinct geometric data structures, designing succinct data structures that are I/O-efficient, and using succinct data structures to improve the query and/or update efficiency of standard data structures. My research has applications in text retrieval systems, geographic information systems and bioinformatics.
Speaker Bio:
Meng He has been working as a postdoctoral fellow in the School of Computer Science of the University of Waterloo since January 2009. He obtained his PhD degree from University of Waterloo in June 2008, and between September 2007 and December 2008, he worked as a postdoctoral fellow in the School of Computer Science of Carleton University. Meng He’s research areas are algorithms, data structures and computational geometry, and his research has been focused on the design of algorithms and data structures for large data sets. He has authored twenty peer-reviewed publications on this subject, including papers in top journals and conferences such as ACM Transactions on Algorithms (TALG), the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), and the International Colloquium on Automata, Language, and Programming (ICALP).
During his postdoctoral work in University of Waterloo, Meng He taught two courses: one was a required computer science course on algorithms, and the other was an advanced fourth-year course on formal languages and parsing. Before that, in April 2009, he completed the Certificate in University Teaching program offered by the Centre for Teaching Excellence at University of Waterloo.
--
--------------------
David Langstroth
Room 205, Faculty of Computer Science
Dalhousie University
6050 University Avenue
Halifax, NS
B3H 1W5
tel: 902-494-8087
fax: 902-494-7710
