Work-Efficient Parallel Skyline Computation for the GPU

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

The skyline operator returns records in a dataset that provide optimal trade-offs of multiple dimensions. State-of-the-art skyline computation involves complex tree traversals, data-ordering, and conditional branching to minimize the number of point-to-point comparisons. Meanwhile, GPGPU computing offers the potential for parallelizing skyline computation across thousands of cores. However, attempts to port skyline algorithms to the GPU have prioritized throughput and failed to outperform sequential algorithms.

In this paper, we introduce a new skyline algorithm, designed for the GPU, that uses a global, static partitioning scheme. With the partitioning, we can permit controlled branching to exploit transitive relationships and avoid most point-to-point comparisons. The result is a non-traditional GPU algorithm, SkyAlign, that prioritizes work-effciency and respectable throughput, rather than maximal throughput, to achieve orders of magnitude faster performance.
OriginalsprogEngelsk
TidsskriftProceedings of the VLDB Endowment
Vol/bind8
Nummer9
Sider (fra-til)962-973
Antal sider12
ISSN2150-8097
DOI
StatusUdgivet - maj 2015
BegivenhedInternational Conference on Very Large Databases - Kohala Coast, Hawaii, USA
Varighed: 31 aug. 20155 sep. 2015
Konferencens nummer: 41

Konference

KonferenceInternational Conference on Very Large Databases
Nummer41
LandUSA
ByKohala Coast, Hawaii
Periode31/08/201505/09/2015

Se relationer på Aarhus Universitet Citationsformater

Aktiviteter

Projekter

ID: 86499964