Memory and performance optimized prefix tries
Indexes are essential in data management systems to increase the speed of data retrievals. Wide-spread data structures to provide fast and memory-efficient indexes are prefix tries and this talk will give an introduction in their use cases and optimization directions. Most trie implementations today optimize their internal data alignment for cache and vector unit efficiency. These measures usually improve performance, while having a negative impact on memory efficiency.
We will therefore discuss trade-offs within the design space of trie-based main memory key-value stores and present new approaches to achieve extreme space efficiency. The talk compares performance optimized tries with data structures which even optimize their memory allocator to pack each node as efficiently as possible. Such data structures, like the Hyperion search trie, do not depend on CPU vector units, but scan the internal data structures linearly. Interestingly, these linear data structures are able to achieve a competitive point query and an exceptional range query performance, especially for string data sets.
Bio:
Prof. Dr.-Ing. André Brinkmann is a full professor at the computer science department of the Johannes Gutenberg University, Germany and head of its data center (since 2011). He received his Ph.D. in electrical engineering in 2004 from the University of Paderborn and has been an assistant professor in the computer science department of the University of Paderborn from 2008 to 2011. Furthermore, he has been the managing director of the Paderborn Centre for Parallel Computing during this time frame. His research interests focus on the application of algorithm engineering techniques in the area of data center management, hpc, cloud computing, and storage systems. He has published more than 100 papers in renowned conferences and journals and is, besides others, an associated editor of the ACM Transactions on Storage, a member of the advisory board of the French Grid'5000, the European Modular Microserver DataCentre project M2DC, and of the "Mainzer Zentrum für Digitalität in den Geistes- und Kulturwissenschaften" mainzed.