天際線運算注重於單筆資料之間的優劣比較，而實務上許多應用必須組合多種因素綜合評估，因此衍生以群組考量支配關係的G-skyline運算，而此議題對於多準則決策分析至關重要。過去G-skyline研究，運算結果會包含過多的群組，導致使用者無法在眾多組合中選擇，為了精確搜索出所需資訊，我們提供使用者可以指定特殊資料點，透過運算將搜索出包含此指定資料點的G-skyline群組，對於實務上將更有利於決策。
在本文中，我們提出G-RUG平行演算法加速生成候選集，利用精簡群組結構(RUG)輸出G-skyline群組。此方法有四個特點：一、配合兩種修剪策略，大幅減少支配關係測試次數；二、有明確的終止條件，可以不用比較所有資料，便能生成所需候選組；三、不用建構有向天際線圖(DSG)，在時間及空間上更有效益；四、將資料以維度拆分任務平行計算，更有效率處理高維度數據。最後以實驗模擬得知，我們所提出的方法在執行效率上確實大幅降低執行時間。

Skyline operator paid more attention to the comparison of the advantages and disadvantages of data point, but in practice, many applications must combine multiple factors to make comprehensive evaluation. Therefore, the G-skyline operation based on the dominance relationship among groups of data points is derived. Moreover, this issue has a decisive influence on multi-criteria decision analysis. For the past G-skyline research, the calculation result will involve too many groups, which makes users unable to choose among many combinations. In order to search for the required information, we propose a method allowing users to designate a special data point, and the G-skyline groups containing the specified data point will be found out through simplified calculation. This improved approach will be more conducive to decision-making in practice.
In this thesis, we propose the G-RUG parallel algorithm to accelerate the generation of candidate set, while using reduced unit group (RUG) to output G-skyline groups. This method has four characteristics as follows: I. Two pruning strategies can be used to greatly reduce the number of tests for dominating relationship; II. Include clear termination conditions, so that required candidate group can generate without comparing all the data; III. There is no need to construct a directed skyline graph (DSG), so it can be more effective in terms of time and space; IV. Split the data into dimensions and perform parallel calculations, resulting in more efficient processing of high-dimensional data. Finally, experimental simulations show that this algorithm is faster than other methods in the past in terms of execution efficiency.

[1] H. Blunck and J. Vahrenhold, "In-place algorithms for computing0 (layers of) maxima." in Scandinavian Workshop on Algorithm Theory 57, pp.1-21, 2010.
[2] S. Borzsony, D. Kossmann and K. Stocker, "The skyline operator." in Proceedings 17th International Conference on Data Engineering, pp.421-430, 2001.
[3] Z. D. Bai, H. K. Hwang and T. H. Tsai, "Berry-Esseen bounds for the number of maxima in planar regions." Electronic Journal of Probability, vol. 8, 2003.
[4] Z. D. Bai, H. K. Hwang, W. Q. Liang and T. H. Tsai, "Limit theorems for the number of maxima in random samples from planar regions." Electronic Journal of Probability. J. Probability, vol. 6, pp.1-41, 2001.
[5] N. Bell and J. Hoberock, "Thrust: A productivity-oriented library for CUDA." in GPU computing gems Jade edition, vol. 2, pp.359-371, 2011.
[6] W. M. Chen, H. K. Hwang and T. H. Tsai, "Maxima-finding algorithms for multidimensional samples: a two-phase approach." Computational Geometry, vol. 45, no.1-2, pp.33-53, 2012.
[7] C. A. C. Coello, D. A. Van Veldhuizen and G. B. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, vol. 5, 2007.
[8] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., vol. 16, 2001.
[9] M. Ehrgott, Multicriteria optimization, Springer Science & Business Media, 2006.
[10] A. Guttman, "R-trees: A dynamic index structure for spatial searching." in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pp.47-57, 1984.
[11] H. Im and S. Park, "Group skyline computation." Information Sciences, 188, pp.151-169, 2012.
[12] H. T. Kung, F. Luccio and F. P. Preparata, "On finding the maxima of a set of vectors." Journal of the ACM (JACM), 22.4, pp.469-476, 1975.
[13] J. Liu, L. Xiong, J. Pei, J. Luo and H. Zhang, "Finding pareto optimal groups: Group-based skyline." in Proceedings of the VLDB Endowment, vol. 8, no.13, pp.2086-2097, 2015.
[14] C. Li, N. Zhang, N. Hassan, S. Rajasekaran and G. Das. "On skyline groups." in Conference on Information and Knowledge Management, pp.2119-2123, 2012.
[15] H. Li, S. Jang and J. Yoo, "An efficient multi-layer grid method for skyline queries in distributed environments." pp.112-119, 2011.
[16] H. Lu, C. S. Jensen and Z. Zhang. "Flexible and efficient resolution of skyline query size constraints." IEEE Transactions on Knowledge and Data Engineering, 23.7, pp.991-1005, 2010.
[17] B. Li, J. Li, K. Tang and X. Yao, "Many-objective evolutionary algorithms: A survey." ACM Computing Surveys, vol. 48, no.1, pp.1-35, 2015.
[18] M. Magnani and I. Assent. "From stars to galaxies: skyline queries on aggregate data." in Proceedings of the 16th International Conference on Extending Database Technology, pp.477-488, 2013.
[19] C. Wang, C. Wang, G. Guo, X. Ye and S. Y. Philip, "Efficient computation of g-skyline groups." IEEE Transactions on Knowledge and Data Engineering, vol.30, no.4, pp.674-688, Apr. 2018.
[20] W. Yu, Z. Qin, J. Liu, L. Xiong, X. Chen and H. Zhang, "Fast algorithms for pareto optimal group-based skyline." in Conference on Information and Knowledge Management, pp.417-426, 2017.
[21] N. Zhang, C. Li, N. Hassan, S. Rajasekaran and G. Das, "On skyline groups." IEEE Transactions on Knowledge and Data Engineering, 26.4, pp.942-956, 2013.
[22] H. Zhu, P. Zhu, X. Li, Q. Liu and P. Xun "Parallelization of group-based skyline computation for multi-core processors." Concurrency and Computation Practice and Experience, vol. 29, no.18, pp.4195-4215, 2017.
[23] NVIDIA, "NVIDIA Turing GPU Architecture Whitepaper" https://www.nvidia.com/content/dam/en-zz/Solutions/design-visualization/technologies/turing-architecture/NVIDIA-Turing-Architecture-Whitepaper.pdf
[24] NVIDIA, "CUDA Toolkit Documentation" https://docs.nvidia.com/cuda/cuda-c-prog-ramming-guide/index.html
[25] NVIDIA, "CUDA C programming guide", https://docs.nvidia.com/cuda/archi-ve/9.0/cuda-c-programming-guide/index.html, 2017.