GPU-GIST – a case of generalized database indexing on modern hardware

Abstract

A lot of different indexes have been developed for accelerating search operations on large data sets. Search trees, representing the most prominent class, are ubiquitous in database management systems but are also widely used in non-DBMS applications. An approach for lowering the implementation complexity of these structures are index frameworks like generalized search trees (GiST). Common data management operations are implemented within the framework which can be specialized by data organization and evaluation strategies in order to model the actual index type. These frameworks are particularly useful in scientific and engineering applications where characteristics of the underlying data set are not known a priori and a lot of prototyping is required in order to find suitable index structures for the workload.