天際線查詢(skyline query) 已經有許多文獻提出相關演算法討論如何減少運
行時間，但這都是假定輸入僅為單一資料表的情況，在實際使用資料庫時資料可
能分散在各個資料表中，若輸入為兩張以上的資料表之情況，則需將表格先進行
關聯式連接(relational join)，再利用skyline query 演算法，但這樣可能有冗余的運
算，於是延伸出skyline-join 問題。本論文提出適合Graphics Processing Unit(GPU)
平行計算的skyline-join 演算法，以join 分量的數值分群，配合k-d 樹輔助可以有
效篩選資料並且減少比較次數，且運用bit 運算在壓縮資料的同時加速join 的過
程。實驗結果顯示可大幅降低整體時間。

Skyline query, aims at seeking the representative data points. Many researchers have
proposed related algorithms to reduce the execution time. However, data may be scattered
in multiple tables. If there are two or more tables, the algorithm needs to join the table
first, and then executes the skyline query algorithm. This method may cause redundant
caculation, hence the problem is extended to skyline-join query. This thesis proposes a
skyline-join algorithm that is suitable for parallel computing by Graphics Processing Unit.
The join attribute is used for grouping, and the k-d tree concept is applied to find the local
skyline for accelerating. In addition,the join operation can be accelerated by bitstring
operations. The experimental results indicate that the proposed method is more effective
than the other popular algorithms for skyline-join query over multiple tables.

[1] Professional CUDA C Programming. GBR: Wrox Press Ltd., 1st ed., 2014.
[2] M. Amiruzzaman and S. Jamonnak, “Multi-dimensional Skyline Query to Find Best
Shopping Mall for Customers,” in 2020 6th Conference on Data Science and Machine
Learning Applications, pp. 71–76, 2020.
[3] W.-T. Balke, U. Güntzer, and J. X. Zheng, “Efficient distributed skylining for web
information systems,” in International Conference on Extending Database Technology,
pp. 256–273, 2004.
[4] I. Keles and K. Hose, “Skyline Queries over Knowledge Graphs,” in International
Semantic Web Conference, pp. 293–310, 2019.
[5] X. Lin, X. Jianliang, and H. Haibo, “Authentication of location-based skyline
queries,” in Proceedings of the 20th ACM international conference on Information
and knowledge management, pp. 1583–1588, 2011.
[6] W. Jin, M. Ester, Z. Hu, and J. Han, “The Multi-Relational Skyline Operator,” in
2007 IEEE 23rd International Conference on Data Engineering, pp. 1276–1280.
[7] S. Borzsony, D. Kossmann, and K. Stocker, “The skyline operator,” in Proceedings
17th international conference on data engineering, pp. 421–430, IEEE, 2001.
[8] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting,” in Proceedings
of the 19th International Conference on Data Engineering, vol. 3, pp. 717–
719, 2003.
[9] I. Bartolini, P. Ciaccia, and M. Patella, “SaLSa: computing the skyline without scanning
the whole sky,” in Proceedings of the 15th ACM international conference on
Information and knowledge management, pp. 405–414, 2006.
[10] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: An online algorithm
for skyline queries,” in Proceedings of the 28th International Conference on
Very Large Databases, pp. 275–286, 2002.
[11] C. K. Lee, B. Zheng, H. Li, and W.-C. Lee, “Approaching the skyline in Z order,”
in Proceedings of the 33rd International Conference on Very Large Data Bases,
pp. 279–290, 2007.
[12] B. He, K. Yang, R. Fang, M. Lu, N. Govindaraju, Q. Luo, and P. Sander, “Relational
Joins on Graphics Processors,” Proceedings of the 2008 ACM SIGMOD international
conference on Management of data, p. 511–524, 2008.
[13] J. Rao and K. A. Ross, “Cache conscious indexing for decision-support in main memory,”
in Proceedings of 25th International Conference on Very Large Data Bases,
pp. 78–89, 1999.
[14] P. A. Boncz, S. Manegold, and M. L. Kersten, “Database architecture optimized
for the new bottleneck: Memory access,” in Proceedings of the 25th International
Conference on Very Large Data Bases, vol. 99, pp. 54–65, 1999.
[15] B. He, M. Lu, K. Yang, R. Fang, N. K. Govindaraju, Q. Luo, and P. V. Sander,
“Relational Query Coprocessing on Graphics Processors,” ACM Trans. Database
Syst., vol. 34, no. 4, 2009.
[16] Y. Xu, P. Kostamaa, X. Zhou, and L. Chen, “Handling data skew in parallel joins in
shared-nothing systems,” in Proceedings of the 2008 ACM SIGMOD international
conference on Management of data, pp. 1043–1052, 2008.
[17] L. Cheng, S. Kotoulas, T. E. Ward, and G. Theodoropoulos, “Improving the robustness
and performance of parallel joins over distributed systems,” Journal of Parallel
and Distributed Computing, vol. 109, pp. 310–323, 2017.
[18] J. Zhang, Z. Lin, B. Li, W. Wang, and D. Meng, “Efficient Skyline Query over Multiple
Relations,” Procedia Computer Science, vol. 80, pp. 2211–2215, 2016.
[19] A. Vlachou, C. Doulkeridis, and N. Polyzotis, “Skyline query processing over joins,”
in Proceedings of the 2011 ACM SIGMOD International Conference on Management
of data, pp. 73–84, 2011.
[20] M. Nagendra and K. S. Candan, “Skyline-Sensitive Joins with LR-Pruning,” Edbt
’12, p. 252–263, 2012.
[21] M. Nagendra and K. S. Candan, “Efficient Processing of Skyline-Join Queries over
Multiple Data Sources,” ACM Trans. Database Syst., vol. 40, no. 2, 2015.
[22] J. Zhang, J. Gu, S. Cheng, B. Li, W. Wang, and D. Meng, “Efficient algorithms of
parallel Skyline join over data streams,” in International Conference on Algorithms
and Architectures for Parallel Processing, pp. 184–199, 2018.
[23] 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, pp. 33–53, 2012.
[24] N. Bell and J. Hoberock, “Thrust: A productivity-oriented library for CUDA,” GPU
computing gems Jade edition, vol. 2, pp. 359–371, 2011.
[25] J.Lin, “A Study of Accelerating Skyline-Join Query Using GPUs,” in Master Thesis,
2019.
[26] “Basketball-Reference.com - Basketball Statistics and History.” https:
//Basketball-Reference.com, 2022.