Work-Efficient Parallel Skyline Computation for the GPU

Summary: Introduces SkyAlign, a work-efficient GPU skyline with global static partitioning and controlled branching to exploit transitive relations and cut point-to-point comparisons. Delivers speedups over prior GPU skylines by prioritizing work-efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11394
Venue: VLDB
Year: 2015
Pagerank: 5.093636e-05
Overall Rank: 12,162 | 16.56%
DOI: 10.14778/2777598.2777602

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Kenneth S. Bøgh (Aarhus University)
2. Sean Chester (Aarhus University)
3. Ira Assent (Aarhus University)

BibTeX Citation

@article{bgh_vldb15,
        title = {{Work-Efficient Parallel Skyline Computation for the GPU}},
        author = {Bøgh, Kenneth S. and Chester, Sean and Assent, Ira},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {9},
        pages = {962--973},
        doi = {10.14778/2777598.2777602},
        url = {https://doi.org/10.14778/2777598.2777602},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,978	Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures	2017	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
243	Efficient Progressive Skyline Computation	2001	VLDB	0.00023495903
631	Relational Joins on Graphics Processors	2008	SIGMOD	0.00015591241
3,409	Approaching the Skyline in Z Order	2007	VLDB	7.4368546e-05
3,429	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.4203247e-05
5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.2133548e-05
6,473	Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce	2013	VLDB	5.8698599e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,574	Pipelined Query Processing in Coprocessor Environments	2018	SIGMOD
2	631	Relational Joins on Graphics Processors	2008	SIGMOD
3	9,320	QSkycube: Efficient Skycube Computation Using Point-Based Space Partitioning	2011	VLDB
4	10,370	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD
5	5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
6	6,473	Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce	2013	VLDB
7	1,360	Efficient Computation of the Skyline Cube	2005	VLDB
8	11,978	Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures	2017	SIGMOD
9	3,429	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD
10	6,467	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD