Adapting Tree Structures for Processing with SIMD Instructions

by prof. Christoph Freytag, Berlin Humboldt-Universit├Ąt

April 11th 2014 @ 10:00, in Levico

In this invited talk prof. Christoph Freytag will present his work about

Adapting Tree Structures for Processing with SIMD Instructions

Abstract

In this talk, we show how to accelerate the processing of tree-based index structures by using SIMD instructions. We adapt the B+-Tree and prefix B-Tree (trie) by changing the search algorithm on inner nodes from binary search to k-ary search. We develop adaptations of tree structures that satisfy the specific constraints of SIMD instructions. We present algorithms for transforming the original tree layout into a SIMD-friendly layout. Our adapted B+-Tree speeds up search processes by a factor of up to eight for small data types compared to the original B+-Tree using binary search. Furthermore, our adapted prefix B-Tree enables a high search performance even for larger data types. This work was done together with Steffen Zeuch and Frank Huber.

Speaker:

Johann-Christoph Freytag is currently full professor for Databases and Information Systems (DBIS) at the Computer Science Department of the Humboldt-Universit├Ąt zu Berlin, Germany.

Before joining the department in 1994, he was a research staff member at the IBM Almaden Research Center (1985-1987), a researcher at the European Computer-Industry-Research Centre (ECRC, in Munich, Germany, 1987-1989), and the head of Digital's Database Technology Center (also in Munich, 1990-1993). He holds a Ph.D. in Applied Mathematics/Computer Science from Harvard University, MA.