Finding k-dominant Skyline with Partition Power

Skyline（天際線）查詢被廣泛運用在很多地方，諸如決策分析系統、多準則決策、數據挖掘、使用者喜好等等應用，對於多維度數據的決策上非常有用。然而隨著維度的增加， skyline查詢結果會大幅增加，再加上並不是每個維度對使用者而言都是重要的，因此skyline查詢結果可能有很多並不是想要的結果。過去的研究提出k-dominant skyline（k-支配天際線）的概念來解決這些問題，透過放寬dominate（支配）的條件來縮減skyline查詢的結果。 本研究針對高維度的資料集提出一種使用partition power（分區力）指標來排序資料並且能夠更有效的計算k-dominant skyline方法。透過partition power來排序資料不僅可以有效率的計算k-dominant skyline，還能夠刪減輸入資料集，而且刪減輸入資料集後也不會影響到輸出結果的品質。通過對合成資料集與真實資料集所進行的模擬實驗都驗證了本研究方法可以有效地計算k-dominant skyline。Skyline queries are widely used in many applications, such as decision analysis systems, multi-criteria decision-making, data mining, and user preferences. However, as the number of dimensions of data increases, the size of skyline query results will also increase dramatically. In addition, not every dimension is important or interesting to the user. Therefore, the skyline query results may contain many undesired data. Past research proposed the concept of k-dominant skyline to solve this problem and to reduce the size of skyline query results by relaxing the dominant conditions. This study proposes a method to rank data using the partition power index for high-dimensional datasets, and the proposed method can calculate the k-dominant skyline more efficiently. Ordering the data in the input datasets through the partition power index not only can efficiently calculate the k-dominant skyline, but also can filter the input dataset without affecting the quality of query results. Simulation experiments on both synthetic datasets and real datasets have verified that the proposed method can effectively calculate the k-dominant skyline.第一章 簡介 1 第二章 相關研究 3 2.1 One-Scan Algorithm(OSA) 3 2.2 Two-Scan Algorithm(TSA) 4 2.3 Sorted Retrieval Algorithm(SRA) 4 2.4 Two-Scan Algorithm with Domination Power(TSADP) 5 第三章 問題與方法描述 7 3.1 假設與參數定義 7 3.2 問題定義 8 3.3 基本構想 8 3.4 輸入資料的前處理 8 3.5 TSAPP方法 11 第四章 實驗結果分析 13 4.1 實驗環境 13 4.1.1 實驗資料來源 13 4.1.2 實驗平台 13 4.2實驗一：k值大小對刪減原始資料的影響 14 4.2.1 實驗設計與實作 14 4.2.2 實驗結果與分析 14 4.3實驗二：k值大小與domination power最大值對計算k-dominant skyline效能的影響 15 4.3.1 實驗設計與實作 15 4.3.2 實驗結果與分析 15 4.4實驗三：資料量對計算k-dominant skyline效能的影響 21 4.4.1 實驗設計與實作 21 4.4.2 實驗結果與分析 21 4.5實驗四：在真實資料集中不同k值對計算k-dominant skyline效能的影響 23 4.5.1 實驗設計與實作 23 4.5.2 實驗結果與分析 23 第五章 結論與未來方向 25 5-1 結論 25 5-2 未來方向 25 參考文獻 2