[發明專利]一種數據立方體的非層次數據結構摘要方法

在審

• 申請號: 202111104771.1
• 申請日: 2021-09-18
• 公開（公告）號: CN113792054A
• 公開（公告）日: 2021-12-14
• 發明（設計）人: 汪祥;姬翔;任開軍;晏瀟;朱俊星;任小麗;陳祥國;鄧科峰
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/29
• 代理公司: 長沙大珂知識產權代理事務所(普通合伙) 43236
• 代理人: 伍志祥

本發明公開了數據立方體的非層次數據結構摘要方法，包括以下步驟：獲取數據立方體D；將數據摘要任務轉換為非層次數據結構摘要問題，即用帶有誤差邊界的矩形區域覆蓋數據立方體，并使摘要大小最小化；從數據立方體D中提取一組α近似矩形的集合C，并確保C包含非層次數據結構摘要問題的最優解，獲得數據立方體D中每個位置(i,j)的邊界F_ij；從集合C中選擇α近似矩形以貪心算法的方式覆蓋數據立方體D，并使用基于堆的優化來提高效率；使用最優的近似矩形來表示數據立方體。本發明摘要規模較小，運行時間較短，解決了現有的數據摘要方法需要預先設定數據多維度層次結構的問題。

技術領域

本發明屬于數據處理技術領域，尤其涉及一種數據立方體的非層次數據結構摘要方法。

背景技術

數據立方體在氣象學、銷售和人口統計學等領域無處不在，而數據摘要能夠壓縮多維數據立方體，并提供觀察數據的不同視角，是一項重要的服務。現有的數據摘要方法需要預先設定的數據多維度的層次結構，而許多類型的數據(例如，降雨和溫度)并不存在這種結構。

多維數據立方體廣泛用于存儲多屬性維度的數據，例如氣象數據的位置和時間維度，銷售數據的位置和產品等維度，人口統計數據的地點、年齡和性別維度。如圖1所示，數據立方體在其維度上定義的網格中包含許多記錄。數據立方體可能非常大，這使得存儲和分析變得困難。例如，歐洲中期天氣預報中心(ECWMF)已經積累了270PB氣象數據。

數據摘要將數據立方體劃分為多個區域，并為數據壓縮和挖掘數據信息提供每個區域中記錄的近似值。例如，在圖2中，具有相同顏色的記錄被分配到同一區域，并通過該區域右下角的值進行近似。壓縮是通過只存儲數據摘要來實現的，它只有5條記錄(每條記錄一個區域)，而不是原始數據立方體的25條記錄。摘要還確保同一區域的記錄取相似的值，最壞情況的近似誤差為1。因此，摘要提供了有關數據的洞察，例如，該區域的左側部分具有相似的溫度(具有相同的顏色)和該區域右下方的溫度變化迅速(有3個小的摘要區域)。一些研究還使用數據摘要來有效地回答OLAP查詢。

許多研究已經研究了數據立方體的摘要，因為它支持數據壓縮和洞察發現。根據它們能否準確重建原始數據立方體，可分為無損方法和有損方法。有損方法更受歡迎，因為它們的摘要大小較小?，F有數據摘要算法的一個問題是它們需要預先假定的屬性維度層次結構。例如，在圖3中，產品維度有2層層次結構，可以在第一層展開為服裝和食物，然后服裝在第二層進一步擴展為夾克和長褲?，F有方法依賴于預設的層次結構來構建數據摘要。例如，(曼哈頓區,服裝)可以通過合并夾克和長褲被匯總為一個區域。然而，許多類型的數據，如溫度、降雨量、濕度等，并沒有預先假定的層次結構，因為它們的維度沒有明顯的語義(如經度、緯度和時間)。相反，數據摘要應該有助于發現層次結構來回答諸如哪個地區降雨量相似以及溫度相似的時間段等問題。

無損摘要方法確?？梢詮恼袦蚀_地恢復原始數。Lakshmanan等人使用商立方體來對數據立方體進行摘要，同時保留上卷和下鉆操作的語義。Sismanis等人設計了一個名為Dwarf的結構，它識別重復的前綴和后綴并將它們組合起來進行壓縮。王等人提出了濃縮數據立方體方法，它將多個元組壓縮為一個而不會丟失信息。

為了使摘要規模更小，一些方法進行有損摘要，其中從摘要重建的記錄可能與原始記錄不同。有損摘要的一個重要方面是它是否允許控制原始記錄和重建記錄之間的誤差閾值。據我們所知，現有的有損摘要方法都依賴于數據立方體維度的層次結構。