天際線查詢(skyline query) 是從一群資料當中挑出一組特定的天際線資料(skyline data)，這些資料有著無可取代的特性，有助於決策或是分析資料。隨著資料或特性數量的上升，在天際線查詢過程中所花費的時間也會跟著快速地上升，所以過往有許多研究是利用平行化來改善此問題，但在多核心和分散式因為其架構或是硬體限制，所能改善的部分亦有限制。本論文針對使用顯示卡(GPU) 處理特殊問題的通用圖形處理器架構(GPGPU) 來探討天際線查詢的問題，並發展GPGPU 天際線查詢(GPGPU skyline query,GSQ) 演算法，利用篩選機制來減少在尋找天際線資料過程中的比較次數，最後和其他在同樣架構下所發展的天際線查詢演算法做比較，發現GSQ 演算法在這當中是最能有效利用GPGPU 架構的演算法，在大部分情況下都能得到良好的表現。

Skyline query finds some special points from data, called skyline points, those are irreplaceable and help us making decision or using in data mining. Skyline query result size and execution time are rapid growth as number of components increasing, therefore some researcher using parallelism to improve this problem, but limited effect by framework hardware, like multi-core or distributed environment. This paper studies skyline query in general-purpose computing on graphics processing units (GPGPU) framework and proposes GPGPU skyline query (GSQ) algorithm, using filter method to reduce the number of data comparisons, in final simulation, GSQ is compared with other algorithms and we find GSQ is most effective in most cases.
II

[1] Wolf-Tilo Balke, Ulrich Guntzer, and Jason Xin Zheng. Efficient distributed skylining for web information systems. In Advances in Database Technology-EDBT, pages 256–273. Springer, 2004.
[2] Ilaria Bartolini, Paolo Ciaccia, and Marco Patella. Efficient sort-based skyline evaluation. ACM Transactions on Database Systems (TODS), 33(4):31, 2008.
[3] Angel C Bency and S Deepa Kanmani. A survey of skyline processing in various enveronment. Indian Journal of Computer Science and Engineering (IJCSE), 5(1): 5–8, 2014.
[4] Jon Louis Bentley, HT Kung, Mario Schkolnick, and Clark D Thompson. On the average number of maxima in a set of vectors and applications. Journal of the ACM(JACM), 25(4):536–543, 1978.
[5] Kenneth S Bogh, Ira Assent, and Matteo Magnani. Efficient gpu-based skyline computation. In Proceedings of the Ninth International Workshop on Data Management on New Hardware, page 5. ACM, 2013.
[6] Stephan Borzsony, Donald Kossmann, and KonradStocker. The skyline operator. In Data Engineering. Proceedings. 17th International Conference on, pages 421–430. IEEE, 2001.
[7] Chee-Yong Chan, HV Jagadish, Kian-Lee Tan, Anthony KH Tung, and Zhenjie Zhang. Finding k-dominant skylines in high dimensional space. In Proceedings of the ACM SIGMOD international conference on Management of data, pages 503–514. ACM, 2006.
[8] Chee-Yong Chan, HV Jagadish, Kian-Lee Tan, Anthony KH Tung, and Zhenjie Zhang. On high dimensional skylines. In Advances in Database Technology-EDBT, pages 478–495. Springer, 2006.
[9] Baichen Chen, Weifa Liang, and Jeffrey Xu Yu. Energy-efficient skyline query optimization in wireless sensor networks. Wireless Networks, 18(8):985–1004, 2012.
[10] Liang Chen, Kai Hwang, and Jian Wu. Mapreduce skyline query processing with a new angular partitioning approach. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), IEEE 26th International, pages 2262–2270. IEEE, 2012.
[11] Liang Chen, Li Kuang, and Jian Wu. Mapreduce based skyline services selection for qos-aware composition. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), IEEE 26th International, pages 2035–2042. IEEE, 2012.
[12] Hyunsik Choi, HaRim Jung, Ki Yong Lee, and Yon Dohn Chung. Skyline queries on keyword-matched data. Information Sciences, 232:449–463, 2013.
[13] Wonik Choi, Ling Liu, and Boseon Yu. Multi-criteria decision making with skyline computation. In Information Reuse and Integration (IRI), IEEE 13th International Conference on, pages 316–323. IEEE, 2012.
[14] Jan Chomicki, Parke Godfrey, Jarek Gryz, and Dongming Liang. Skyline with presorting. In IEEE International Conference on Data Engineering(ICDE), volume 3, pages 717–719, 2003.
[15] Bin Cui, Hua Lu, Quanqing Xu, Lijiang Chen, Yafei Dai, and Yongluan Zhou. Parallel distributed processing of constrained skyline queries by filtering. In Data Engineering. IEEE International Conference on Data Engineering(ICDE). IEEE 24th International Conference on, pages 546–555. IEEE, 2008.
[16] Lei-gang Dong, Xiao-wei Cui, Zhen-fu Wang, and Shu-wei Cheng. Finding kdominant skyline cube based on sharing-strategy. In Fuzzy Systems and Knowledge Discovery (FSKD), Seventh International Conference on, volume 4, pages 1694–1698. IEEE, 2010.
[17] Yunmin Go and Hwangjun Song. A novel distributed skyline query based service discovery in the mobile p2p cloud. In International Conference on ICT Convergence (ICTC), International Conference on, pages 608–609. IEEE, 2013.
[18] Hyeonseung Im and Sungwoo Park. Group skyline computation. Information Sciences, 188:151–169, 2012.
[19] Henning Kohler, Jing Yang, and Xiaofang hou. Efficient parallel skyline processing using hyperplane projections. In Proceedings of the ACM SIGMOD International Conference on Management of data, pages 85–96. ACM, 2011.
[20] Donald Kossmann, Frank Ramsak, and Steffen Rost. Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the 28th international conference on Very Large Data Bases, pages 275–286. VLDB Endowment, 2002.
[21] Jongwuk Lee, Jinhan Kim, and Seung won Hwang. Supporting efficient distributed skyline computation using skyline views. Information Sciences, 194:24–37, 2012.
[22] Ken CK Lee, Baihua Zheng, Huajing Li, and Wang-Chien Lee. Approaching the skyline in z order. In Proceedings of the 33rd international conference on Very large data bases, pages 279–290. VLDB Endowment, 2007.
[23] Xiaoyong Li, Yijie Wang, Xiaoling Li, and Guangdong Wang. Skyline query processing on interval uncertain data. In Service-Oriented Real-Time Distributed Computing Workshops (ISORCW), 15th IEEE International Symposium on, pages 87–92. IEEE, 2012.
[24] Stian Liknes, Akrivi Vlachou, Christos Doulkeridis, and Kjetil Norvag. Apskyline: Improved skyline computation for multicore architectures. In Database Systems for Advanced Applications, pages 312–326. Springer, 2014.
[25] Xin Lin, Jianliang Xu, and Haibo Hu. Range-based skyline queries in mobile environments. Knowledge and Data Engineering, IEEE Transactions on, 25(4):835–849, 2013.
[26] Xingjie Liu, De-Nian Yang, Mao Ye, and Wang-Chien Lee. U-skyline: A new skyline query for uncertain databases. Knowledge and Data Engineering, IEEE Transactions on, 25(4):945–960, 2013.
[27] Eric Lo, Kevin Y Yip, King-Ip Lin, and David W Cheung. Progressive skylining over web-accessible databases. Data & Knowledge Engineering, 57(2):122–147, 2006.
[28] Zhixin Ma, Qiang Zhang, and Wei Qi. Substitution: An efficient algorithm for probability skyline queries on discrete uncertain data. In Computer Science and Network Technology (ICCSNT), 2nd International Conference on, pages 1927–1933. IEEE, 2012.
[29] Duane G Merrill and Andrew S Grimshaw. Revisiting sorting for gpgpu stream architectures. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques, pages 545–546. ACM, 2010.
[30] Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger. An optimal and progressive algorithm for skyline queries. In Proceedings of the ACM SIGMOD international conference on Management of data, pages 467–478. ACM, 2003.
[31] Sungwoo Park, Taekyung Kim, Jonghyun Park, Jinha Kim, and Hyeonseung Im. Parallel skyline computation on multicore architectures. In Data Engineering. IEEE International Conference on Data Engineering (ICDE). IEEE 25th International Conference on, pages 760–771. IEEE, 2009.
[32] Yu Peng, Raymond Chi-Wing, and Qian Wan. Finding top-k preferable products. Knowledge and Data Engineering, IEEE Transactions on, 24(10):1774–1788, 2012.
[33] Yohan J Roh, Inchul Song, Joo Hyuk Jeon, Kyoung Gu Woo, and Myoung Ho Kim. Energy-efficient two-dimensional skyline query processing in wireless sensor networks. In IEEE Consumer Communications and Networking Conference (CCNC), pages 294–301. IEEE, 2013.
[34] Joachim Selke, Christoph Lofi, and Wolf-Tilo Balke. Highly scalable multiprocessing algorithms for preference-based database retrieval. In Database Systems for Advanced Applications, pages 246–260. Springer, 2010.
[35] Md. Anisuzzaman Siddique and Yasuhiko Morimoto. Extended k-dominant skyline in high dimensional space. In Information Science and Applications (ICISA), International Conference on, pages 1–8. IEEE, 2010.
[36] Md. Anisuzzaman Siddique, Asif Zaman, Md. Mahbubul Islam, and Yasuhiko Morimoto. Multicore based spatialk-dominant skyline computation. In Networking and Computing (ICNC), Third International Conference on, pages 188–194. IEEE, 2012.
[37] Kian-Lee Tan, Pin-Kwang Eng, and Beng Chin Ooi. Efficient progressive skyline computation. In Proceedings of the 27th International Conference on Very Large Data Bases, pages 301–310. Morgan Kaufmann Publishers Inc., 2001.
[38] Junchang Xin, Mei Bai, and Guoren Wang. Efficient threshold skyline query processing in uncertain databases. In Natural Computation (ICNC), Seventh International Conference on, volume 1, pages 311–315. IEEE, 2011.
[39] Gae-won You, Mu-Woong Lee, Hyeonseung Im, and Seung-won Hwang. The farthest spatial skyline queries. Information Systems, 38(3):286–301, 2013.
[40] Asif Zaman, Md. Mahbubul Islam, Md. Anisuzzaman Siddique, and Yasuhiko Morimoto. Distributed k-dominant skyline queries. In Computer and Information Technology (ICCIT), 15th International Conference on, pages 569–574. IEEE, 2012.
[41] Zhenjie Zhang, Xinyu Guo, Hua Lu, Anthony KH Tung, and Nan Wang. Discovering strong skyline points in high dimensional spaces. In Proceedings of the 14th ACM international conference on Information and knowledge management, pages 247– 248. ACM, 2005.
[42] Lin Zhu, Yufei Tao, and Shuigeng Zhou. Distributed skyline retrieval with low bandwidth consumption. Knowledge and Data Engineering, IEEE Transactions on, 21(3):384–400, 2009.