Work-Efficient Parallel Skyline Computation for the GPU

Kenneth Sejdenfaden Bøgh, Sean Chester, Ira Assent

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-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.
Original languageEnglish
JournalProceedings of the VLDB Endowment
Pages (from-to)962-973
Number of pages12
Publication statusPublished - May 2015
EventInternational Conference on Very Large Databases - Kohala Coast, Hawaii, United States
Duration: 31 Aug 20155 Sept 2015
Conference number: 41


ConferenceInternational Conference on Very Large Databases
Country/TerritoryUnited States
CityKohala Coast, Hawaii


  • GPU
  • skyline
  • work-efficiency
  • Databases
  • Query processing


Dive into the research topics of 'Work-Efficient Parallel Skyline Computation for the GPU'. Together they form a unique fingerprint.

Cite this