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

Research output: Research - peer-reviewJournal article

DOI

  • Kenneth Sejdenfaden Bøgh
    Kenneth Sejdenfaden Bøgh
  • Sean Chester
    Sean ChesterNorwegian 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