臺灣博碩士論文加值系統

skyline query經常運用於多準則決策系統或支援決策分析系統中，可以根據使用者的偏好篩選出符合需求的最佳結果集合。隨著資訊量增加，資料來源不同，表格之間存在共有的屬性，可以根據共有的屬性進行join運算。若是將資料進行join再查找skyline相當浪費資源，因為join會使得資料分量和資料量急遽上升，且產生眾多非skyline資料，造成篩選運算成本變多，影響整體執行時間。本論文提出兩階段的篩選機制，配合樹狀資料結構輔助可以有效篩選資料並且減少比較次數。實驗結果與常見的演算法比較，本研究提出的方法能快速有效的篩選資料。

Skyline query is often used in multi-criteria decision-making systems or in decision support systems. It can be used to sort out the best result in accordance with the user's preferences. As the amount of information increases, the data may come from different sources and different data tables may have common attributes that can be used to carry out join operation. It is a waste of resources to join the data first and then search for the skyline, because join operation will increase substantially the data component as well as the data volume and generate a lot of non-skyline data, resulting in more screening computation costs and affecting the overall execution time. This paper proposes a two-stage screening mechanism, which can effectively sort data and reduce the number of comparisons through the support of a tree data structure. The experimental results show that the method proposed in this study can sort the data more quickly and effectively then other popular algorithms.

摘要 iii
Abstract iv
目錄 v
圖目錄 vii
表目錄 viii
符號 ix
第一章 緒論 1
1.1 研究動機 3
1.2 論文架構 3
第二章 文獻探討 5
2.1 skyline query 5
2.2 skyline相關問題 5
2.3 skyline join query 7
第三章 研究方法 11
3.1 問題描述 11
3.2 演算法流程圖 12
3.3 資料分群 15
3.4 計算group skyline 15
3.5 篩選資料 21
3.6 join 23
第四章 模擬實驗 25
4.1 實驗設定 25
4.2 模擬環境 25
4.3 結果分析 25
4.3.1資料分佈型態 26
4.3.2 資料量 28
4.3.3 分量 31
4.3.4 real dataset 34
第五章 結論 36
文獻 37

[1] M.J. Atallah, and Y. Qi, "Computing All Skyline Probabilities for Uncertain Data." Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 279-287, Jun. 2009.
[2] A. Awasthi, A. Bhattacharya, S. Gupta, and U.K. Singh, "K-Dominant Skyline Join Queries: Extending the Join Paradigm to K-Dominant Skylines." 2017 IEEE 33rd International Conference on Data Engineering, pp. 99-102, Apr. 2017.
[3] I. Bartolini, P. Ciaccia, and M. Patella, "SaLSa: computing the skyline without scanning the whole sky." Proceedings of the 15th ACM international conference on Information and knowledge management, pp. 405-414, Nov. 2006.
[4] S. Borzsonyi, D. Kossmann, and K. Stocker, "The skyline operator." Proceedings 17th International Conference on Data Engineering, pp. 421-430, Apr. 2001.
[5] 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, Jan. 2012.
[6] B. Chen, W. Liang, and J.X. Yu, "Energy-efficient skyline query optimization in wireless sensor networks." Wireless Networks, vol. 18, no. 8, pp. 985-1004, Nov. 2012.
[7] J. Chomicku, P. Godfrey, J. Gryzm, and D. Liang, "Skyline with Pre-sorting." Proceedings 19th International Conference on Data Engineering, pp. 717-719, Mar. 2003.
[8] B. Cui, H. Lu, Q. Xu, L. Chen, Y. Dai, and Y. Zhou, "Parallel Distributed Processing of Constrained Skyline Queries by Filtering." 2008 IEEE 24th International Conference on Data Engineering, pp. 546-555, Apr. 2008.
[9] X. Dinga, X. Lianb, L. Chenb, and H. Jin, "Continuous monitoring of skylines over uncertain data streams." Information Sciences, vol. 184, no. 1, pp. 196-124, Feb. 2012.
[10] W. Jin, M. Ester, Z. Hu, and J. Han, "The Multi-Relational Skyline Operator." 2007 IEEE 23rd International Conference on Data Engineering, pp. 1276-1280, Apr. 2007.
[11] M.E. Khalefa, M.F. Mokbel, and J.J. Levandoski, "Skyline Query Processing for Incomplete Data." 2008 IEEE 24th International Conference on Data Engineering, pp. 556-565, Apr. 2008.
[12] M.E. Khalefa, M.F. Mokbel, and J.J. Levandoski, "Skyline query processing for uncertain data." Proceedings of the 19th ACM international conference on Information and knowledge management, pp. 1293-1296, Oct. 2010.
[13] D. Kossmann, F. Ramsak, and S. Rost, "Shooting Stars in the Sky: An Online Algorithm for Skyline Queries." Proceedings of the 28th international conference on Very Large Data Bases, pp. 275-286, Aug. 2002.
[14] H. T. Kung, F. Luccio, and F.P. Preparata, "On finding the maxima of a set of vectors." Journal of the ACM, vol. 22, no. 4, pp. 469-476, Oct. 1975.
[15] X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, "Selecting Stars: The k Most Representative Skyline Operator." 2007 IEEE 23rd International Conference on Data Engineering, pp. 86-95, Apr. 2007.
[16] X. Miao, Y. Gao, L. Chen, G. Chen, Q. Li, and T. Jiang, " On Efficient k-Skyband Query Processing over Incomplete Data." Database Systems for Advanced Applications, vol. 41, pp. 424-439, Aug. 2014.
[17] K. Mouratidis, S. Bakiras, and D. Papadias, "Continuous monitoring of top-k queries over sliding windows." Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pp. 635-646, Jun. 2006.
[18] S. Sun, Z. Huang, H. Zhong, D. Dai, H. Liu, and J. Li, "Efficient monitoring of skyline queries over distributed data streams." Knowledge and Information Systems, vol. 25, no. 3, pp. 575-606, Dec. 2010.
[19] K. Tan, P. Eng, and B. Ooi, "Efficient Progressive Skyline Computation." Proceedings of the 27th International Conference on Very Large Data Bases, pp. 301-310, Sep. 2001.
[20] A. Vlachou, C. Doulkeridis, and N. Polyzotis, "Skyline Query Processing over Joins." Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pp. 73-84, Jun. 2011.
[21] M.L. Yiu, and N. Mamoulis, "Efficient processing of top-k dominating queries on multi-dimensional data." Proceedings of the 33rd international conference on Very large data bases, pp. 483-494, Sep. 2007.
[22] Q. Yu, and A. Bouguettaya, "Efficient Service Skyline Computation for Composite Service Selection." IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 4, pp. 776-789, Apr. 2013.
[23] J. Zhang, J.Z. Gu, S. Cheng, B. Li, W. Wang, and D. Meng, "Efficient Algorithms of Parallel Skyline Join over Data Streams." International Conference on Algorithms and Architectures for Parallel Processing, pp. 184-199, Dec. 2018