演讲人： 易珂 香港科技大学
时间： 2011-08-09 10:30-2011-08-09 11:30
地点：FIT 1-222
内容：

B-trees and hash tables are two fundamental external memory data structures widely used in database systems. They can be used to solve a number of very basic data structure problems: dictionary, predecessor, range reporting, and range sum. Despite the long history and extensive studies, it is still not known if they are optimal for these problems in the dynamic setting, namely, when insertions and deletions of elements are to be supported, though the static case is better understood. What makes the dyamic case interesting in external memory is the possibility of using a buffer to significantly lower the amortized update I/O cost. In this talk, I will survey the recent results in this area, and present one particular result of my own.

个人简介:

Ke Yi received his B.E. from Tsinghua University and Ph.D. from Duke University, in 2001 and 2006 respectively, both in computer science. After spending one year at AT&T Labs as a researcher, he has been an Assistant Professor in the Department of Computer Science and Engineering at Hong Kong University of Science and Technology since 2007. His research interests include algorithms, data structures, and databases. For more information, please see his webpage: http://www.cs.ust.hk/~yike/