SkyAlign: a portable, work-efficient skyline algorithm for multicore and GPU architectures

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal article

    Kenneth Sejdenfaden Bøgh, Sean Chester, Norwegian University of Science and Technology (NTNU), Trondheim,
  • Ira Assent
The skyline operator determines points in a multidimensional dataset that offer some optimal trade-off. State-of-the-art CPU skyline algorithms exploit quad-tree partitioning with complex branching to minimise the number of point-to-point comparisons. Branch-phobic GPU skyline algorithms rely on compute throughput rather than partitioning, but fail to match the performance of sequential algorithms. In this paper, we introduce a new skyline algorithm, SkyAlign, that is designed for the GPU, and a GPU-friendly, grid-based tree structure upon which the algorithm relies. The search tree allows us to dramatically reduce the amount of work done by the GPU algorithm by avoiding most point-to-point comparisons at the cost of some compute throughput. This trade-off allows SkyAlign to achieve orders of magnitude faster performance than its predecessors. Moreover, a NUMA-oblivious port of SkyAlign outperforms native multicore state of the art on challenging workloads by an increasing margin as more cores and sockets are utilised.
Original languageEnglish
JournalThe V L D B Journal
Volume25
Issue number6
Pages (from-to)817-841
Number of pages25
ISSN1066-8888
DOIs
StatePublished - Dec 2016

See relations at Aarhus University Citationformats

ID: 104246879