Abstract

The skyline query is used for multi-criteria searching, and returns the most interesting points of a potentially very large data set with respect to any mono- tone preference function. The skycube consists of the skylines for all possible non-empty subsets of dimensions. Existing work has almost exclusively focused on efficiently computing skylines and skycubes on one or more CPUs, ignoring the high parallelism possible on Graphics Processing Units. Furthermore, cur- rent algorithms scale badly for large, high-dimensional data since the amount of computations needed grows exponentially. In this thesis we investigate the challenges of efficient skyline and skycube computations that exploit the compu- tational power of the GPU. We also study the limitations and strength of both the CPU and the GPU to determine how fully utilize both. We present a sort- ing based, data-parallel skyline algorithm which runs efficiently on the GPU, and discuss it properties. We then use this algorithm as a basis for developing several efficient GPU based skycube algorithms, each of which shows the impact of different optimization opportunities in the domain of data-parallel skycube computations. In a thorough experimental evaluation, we demonstrate that our algorithms are substantially faster and scale much better than the state-of-the- art algorithms on large, high-dimensional datasets.