{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:40:18Z","timestamp":1756464018191},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,5]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>\n            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\n            <jats:italic>controlled branching<\/jats:italic>\n            to exploit transitive relationships and avoid most point-to-point comparisons. The result is a non-traditional GPU algorithm, SkyAlign, that prioritizes work-efficiency and respectable throughput, rather than maximal throughput, to achieve orders of magnitude faster performance.\n          <\/jats:p>","DOI":"10.14778\/2777598.2777605","type":"journal-article","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T16:09:36Z","timestamp":1431706176000},"page":"962-973","source":"Crossref","is-referenced-by-count":20,"title":["Work-efficient parallel skyline computation for the GPU"],"prefix":"10.14778","volume":"8","author":[{"given":"Kenneth S.","family":"B\u00f8gh","sequence":"first","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sean","family":"Chester","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ira","family":"Assent","sequence":"additional","affiliation":[{"name":"Aarhus University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412343"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485278.2485283"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113358"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/IRI.2012.6303026"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260846"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1620585.1620588"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376670"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0246-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.10.005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2236584.2236592"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.05.005"},{"key":"e_1_2_1_13_1","first-page":"279","volume-title":"Proc. VLDB","author":"Lee K. C. K.","year":"2007","unstructured":"K. C. K. Lee , B. Zheng , H. Li , and W.-C. Lee . Approaching the skyline in Z order . In Proc. VLDB , pages 279 -- 290 , 2007 . K. C. K. Lee, B. Zheng, H. Li, and W.-C. Lee. Approaching the skyline in Z order. In Proc. VLDB, pages 279--290, 2007."},{"key":"e_1_2_1_14_1","first-page":"37","volume-title":"Proc. EDBT","author":"Mullesgaard K.","year":"2014","unstructured":"K. Mullesgaard , J. L. Pedersen , H. Lu , and Y. Zhou . Efficient skyline computation in MapReduce . In Proc. EDBT , pages 37 -- 48 , 2014 . K. Mullesgaard, J. L. Pedersen, H. Lu, and Y. Zhou. Efficient skyline computation in MapReduce. In Proc. EDBT, pages 37--48, 2014."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061320"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556580"},{"key":"e_1_2_1_17_1","first-page":"301","volume-title":"Proc. VLDB","author":"Tan K.-L.","year":"2001","unstructured":"K.-L. Tan , P.-K. Eng , and B. C. Ooi . Efficient progressive skyline computation . In Proc. VLDB , pages 301 -- 310 , 2001 . K.-L. Tan, P.-K. Eng, and B. C. Ooi. Efficient progressive skyline computation. In Proc. VLDB, pages 301--310, 2001."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376642"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2013.18"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559897"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2777598.2777605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:18:14Z","timestamp":1672222694000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2777598.2777605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5]]},"references-count":20,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["10.14778\/2777598.2777605"],"URL":"https:\/\/doi.org\/10.14778\/2777598.2777605","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,5]]}}}