Work-Efficient Parallel Skyline Computation for the GPU

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

Work-Efficient Parallel Skyline Computation for the GPU. / Bøgh, Kenneth Sejdenfaden; Chester, Sean; Assent, Ira.

In: Proceedings of the VLDB Endowment, Vol. 8, No. 9, 05.2015, p. 962-973.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

Bøgh, KS, Chester, S & Assent, I 2015, 'Work-Efficient Parallel Skyline Computation for the GPU', Proceedings of the VLDB Endowment, vol. 8, no. 9, pp. 962-973. https://doi.org/10.14778/2777598.2777605

APA

CBE

MLA

Bøgh, Kenneth Sejdenfaden, Sean Chester, and Ira Assent. "Work-Efficient Parallel Skyline Computation for the GPU". Proceedings of the VLDB Endowment. 2015, 8(9). 962-973. https://doi.org/10.14778/2777598.2777605

Vancouver

Author

Bøgh, Kenneth Sejdenfaden ; Chester, Sean ; Assent, Ira. / Work-Efficient Parallel Skyline Computation for the GPU. In: Proceedings of the VLDB Endowment. 2015 ; Vol. 8, No. 9. pp. 962-973.

Bibtex

@article{d8f6f88a33054379968110a7411431d0,
title = "Work-Efficient Parallel Skyline Computation for the GPU",
abstract = "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.",
keywords = "GPU, skyline, work-efficiency, Databases, Query processing",
author = "B{\o}gh, {Kenneth Sejdenfaden} and Sean Chester and Ira Assent",
year = "2015",
month = "5",
doi = "10.14778/2777598.2777605",
language = "English",
volume = "8",
pages = "962--973",
journal = "Proceedings of the VLDB Endowment",
issn = "2150-8097",
publisher = "VLDB Endowment",
number = "9",

}

RIS

TY - JOUR

T1 - Work-Efficient Parallel Skyline Computation for the GPU

AU - Bøgh, Kenneth Sejdenfaden

AU - Chester, Sean

AU - Assent, Ira

PY - 2015/5

Y1 - 2015/5

N2 - 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.

AB - 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.

KW - GPU

KW - skyline

KW - work-efficiency

KW - Databases

KW - Query processing

U2 - 10.14778/2777598.2777605

DO - 10.14778/2777598.2777605

M3 - Journal article

VL - 8

SP - 962

EP - 973

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

SN - 2150-8097

IS - 9

ER -