{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:27:40Z","timestamp":1750307260565,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,12,6]],"date-time":"2010-12-06T00:00:00Z","timestamp":1291593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2010,12,6]]},"abstract":"<jats:p>A dominance test, which decides the dominance relationship between tuples, is a core operation in skyline computation. Optimizing dominance tests can thus improve the performance of all existing skyline algorithms. Towards this goal, this paper proposes a vectorization of dominance tests in SIMD architectures. Specifically, our vectorization can perform the dominance test of multiple consecutive dimensions in parallel, thereby achieving a speedup of SIMD parallelism degree in theory. However, achieving such performance gain is non-trivial due to complex control dependencies within the dominance test. To address this problem, we devise an efficient vectorization, called VSkyline, which performs the dominance test with SIMD instructions by determining incomparability in a block of four dimensional values. Experimental results using a performance monitor show that VSkyline considerably reduces the numbers of both executed instructions and branch mispredictions.<\/jats:p>","DOI":"10.1145\/1893173.1893176","type":"journal-article","created":{"date-parts":[[2010,12,1]],"date-time":"2010-12-01T20:18:10Z","timestamp":1291234690000},"page":"19-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["VSkyline"],"prefix":"10.1145","volume":"39","author":[{"given":"Sung-Ryoung","family":"Cho","sequence":"first","affiliation":[{"name":"Sungkyunkwan University, Suwon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jongwuk","family":"Lee","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology, Pohang, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seung-Won","family":"Hwang","sequence":"additional","affiliation":[{"name":"Pohang University of Science and Technology, Pohang, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hwansoo","family":"Han","sequence":"additional","affiliation":[{"name":"Sungkyunkwan University, Suwon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sang-Won","family":"Lee","sequence":"additional","affiliation":[{"name":"Sungkyunkwan University, Suwon, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,12,6]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"266","volume-title":"VLDB","author":"Ailamaki A.","year":"1999"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260846"},{"key":"e_1_2_1_4_1","first-page":"229","volume-title":"VLDB","author":"Godfrey P.","year":"2005"},{"key":"e_1_2_1_5_1","first-page":"275","volume-title":"VLDB","author":"Kossmann D.","year":"2002"},{"key":"e_1_2_1_6_1","first-page":"279","volume-title":"VLDB","author":"Lee K. C.","year":"2007"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872814"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.42"},{"volume-title":"Morgan Kaufmann Publishers Inc.","year":"2008","author":"Patterson D. A.","key":"e_1_2_1_9_1"},{"volume-title":"Intel Press","year":"2005","author":"Reinders J.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","first-page":"301","volume-title":"VLDB","author":"Tan K.","year":"2001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376642"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559897"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1893173.1893176","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1893173.1893176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:35Z","timestamp":1750243955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1893173.1893176"}},"subtitle":["vectorization for efficient skyline computation"],"short-title":[],"issued":{"date-parts":[[2010,12,6]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,12,6]]}},"alternative-id":["10.1145\/1893173.1893176"],"URL":"https:\/\/doi.org\/10.1145\/1893173.1893176","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2010,12,6]]},"assertion":[{"value":"2010-12-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}