以贪婪演算法作为矩阵分群之范例.ppt

建構XML多維度資料區間索引之研究 演說者：張 晏 嘉 日期：2006/11/1 大葉大學 資訊工程學系 大綱 簡介 相關研究 研究方法 實驗結果 結論與未來工作 簡介 由於電子資訊化的發展，時序性資料被廣泛的利用以及研究。 以XML作為時序性資料之儲存架構下，檢索資料相當費時。 針對XML所提出之索引架構並無法提供穩定的效能。 以穩定且快速為目標，設計新的時序性資料索引架構。 分析時序性資料資訊，將其建構於多維度矩陣上，以貪婪演算法將資料分群。 時序性資料 代表著某段時間區段內資料所有變化情況之歷史紀錄。 儲存於XML上會利用時間標籤來標記與時間的關聯。 當資料有所變動會在文件中新增資料來記錄該資料必威体育精装版資訊。 時序性資料之索引方式 分群架構： 以鍵值分群。 以時間分群。 時序性資料之索引方式（續） 群組之索引架構以樹狀結構居多。 B-tree、B+-tree、AP-tree…等等。 分群目標 同時考量時間與鍵值屬性。 針對時間或鍵值屬性之資料檢索都能提高效能。 新分群方式能擴展至更多屬性之檢索。 分群目標(續) 資料分群上必須滿足下列幾項要求 ： 資料的經過分群後，各個群組內的資料總數必須儘可能相同。 分群的架構必須要能支援資料的增、刪、修。 分群過後，任何群組於矩陣內所代表的是一個矩形區塊。 資料轉換至矩陣之方式 資料的屬性當作一個維度。 資料中所有該屬性的數值集合成為該維度的區間組合。 分群策略 嘗試以限制區塊內資料筆數來達到均化群組內資料數量之目的。 利用貪婪演算法由內部向外擴展的方式來作為分群方法。 貪婪演算法可保證目前分群的群組都符合所訂立的條件。 分群重點 以二維矩陣為基礎，初步規範分群的重點 ： A = A1 ? A2 ? …? An Ai ? Aj = ?, for i ? j |count(Ai) – count(Aj)| 門檻值, count(Ak) 代表Ak區塊中所包含的資料筆數。 貪婪矩陣分群流程 步驟一： 由矩陣中取得一點，這一點必須為矩陣中尚未分割的區塊裡，X座標最接近原點的座標集合中，Y座標最接近原點的座標。當無法從矩陣取得任何一點時，則跳到步驟四執行。 步驟二： 由此點向外擴展搜尋一塊符合條件的最大矩形區塊。 步驟三： 將區塊劃分為已分割，並跳回步驟一執行。 步驟四： 結束分割。 以貪婪演算法作為矩陣分群之範例 Block_Tree之定義 Block_Tree初始為一個空的樹（tree）。 Block_Tree的每一個節點（node）代表矩陣所分割的一個區塊。 根（root）到任一葉節點（leaf node）的路徑（path）代表的是一種分群方式，該路徑所有的節點的聯集便為原本的矩陣，而節點與節點間並無交集。 任一條根到葉節點的路徑所包含的節點數代表該分群方式所分割的區塊總數。 任一條根到葉節點的路徑中任兩個節點中所包含資料筆數總和相減小於某個門檻值（預設區塊條件資料筆數）。 Block_Tree之範例 改良式貪婪矩陣分群法之流程 步驟一：對於Block_Tree的每一個葉節點分別處理：由矩陣中取得一點，這一點必須不包含在該葉節點與根的路徑中任一節點的範圍內，並且為矩陣中最內部的一點，當無法從矩陣取得任何一點時，則跳到步驟四執行。 步驟二：由此點為起點搜尋符合條件筆數的最大矩形區塊。 步驟三：將區塊資訊加入到Block_Tree內所對應路徑中葉節點的子節點，成為該路徑新的葉節點回到步驟一執行。 步驟四：結束分割。 實驗模擬 本文在Visual Studio .NET上以C#進行開發。而在實驗上，以亂數產生二維矩陣模擬資料轉換至二維度矩陣上之狀態。 矩陣大小： 20 X 20 、40 X 20 、50 X 30 資料量（資料於矩陣中所佔之比例）： 30%、40% 區塊資料筆數： 10筆、15筆、20筆 以程式模擬矩陣分群之結果 結論與未來工作 新的分群架構。 鍵值與時間。 多維度矩陣。 均化各群組資料數量。 將二維的分群擴展至多維度。 針對新分群架構開發索引結構。 分群策略（續） 當資料有所變化時，會在時間維度最末端新增一個區間。 該區間的數值為資料變動的時間。 新區間記錄目前必威体育精装版資料狀態。 資料的增、刪、修不會改變舊有資料於矩陣上的位置。 以貪婪演算法作為矩陣分群之範例 * * Y軸 X軸 大小：20 X 20 ，資料量：40% ，區塊條件筆數：10筆 鍵值 時間 1/1 2/1 3/1 4/1 Joe Tom John 5/1