中央研究院 資訊科學研究所

In-memory data management systems, such as key-value stores, have become an essential infrastructure in today’s big data processing and cloud computing. They rely on efficient index structures to access data. Ordered indexes, such as B+ tree and skip list, have a O(log N) lookup cost, where N is number of keys in an index. For an ordered index hosting billions of keys, it may take more than 30 key-comparisons in a lookup, which is significant. With availability of large memory and fast network in today’s data centers, this O(log N) time is taking a heavy toll on applications that rely on ordered indexes. In this talk, the speaker will introduce a new ordered index structure, named Wormhole, that takes O(log L) worst-case time for looking up a key with a length of L. The low cost is achieved by simultaneously leveraging strengths of three indexing structures, namely hash table, prefix tree, and B+ tree, to orchestrate a single fast ordered index.
 

Dr. Song Jiang is a professor of the CSE department at University of Texas at Arlington. His research interests include system infrastructure for big data processing, such as file and storage systems and data management systems, as well as I/O systems for high-performance computing. He was a recipient of a 2009 US National Science Foundation (NSF) CAREER award and his research activities have been continuously supported by the NSF. He has served on many conference program committees and proposal review panels.  He has been involved in projects at Baidu, IBM Research. and Facebook as a collaborator for providing high-quality Internet-wide services based on big data, resulting in many significant publications at top-tier conferences. For example, the paper on Facework’s Memcached workload characterization won the SIGMETRICS Test of Time Award in 2022.

Dr. Jiang’s research has generated substantial impact in industry where several of his proposed algorithms for memory and storage management have been officially adopted into mainstream systems, including the Linux kernel, the NetBSD kernel, and the storage engine of MySQL.