An Optimized Radix-Tree for Hardware-Accelerated Dictionary Generation for Semantic Web Databases

In this paper, a data structure and a hardware acceleration for dictionary generation for Semantic Web databases are presented. Current hardware accelerators for databases are based on co-processor designs supporting software-centric applications: only single, selected operations of query processing are offloaded to the FPGA with time-consuming data transfers. In contrast, we propose a novel FPGA-centric design, which creates and manages specialized database structures. As part of the design, a scalable and parallel architecture for dictionary generation is introduced. We propose optimizations for Radix-Trees, which are designed to exploit characteristics of FPGA structures. Furthermore, the tree is parameterizable which enables the adaptation of properties to the specific characteristics of the generated data structure. The configuration influences memory and logic utilization. Optimal parameters are determined by simulative evaluation using existing Semantic Web input data sets. The proposed hardware design is integrated into an existing Semantic Web database system and the results are analyzed with a focus on utilization and throughput. The required memory of the optimized Radix-Tree is reduced by 94% and a speed-up of 70% is achieved.