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

在審

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

1.一種數據立方體的非層次數據結構摘要方法，其特征在于，包括以下步驟：

獲取數據立方體D，所述數據立方體存儲多屬性緯度的數據；

將數據摘要任務轉換為非層次數據結構摘要問題，即用帶有誤差邊界的矩形區域覆蓋數據立方體，并使摘要大小最小化；

從數據立方體D中提取一組α近似矩形的集合C，并確保C包含非層次數據結構摘要問題的最優解，獲得數據立方體D中每個位置(i，j)的邊界F_ij；

從集合C中選擇α近似矩形以貪心算法的方式覆蓋數據立方體D，并使用基于堆的優化來提高效率；

使用最優的α近似矩形來表示數據立方體。

2.根據權利要求1所述的數據立方體的非層次數據結構摘要方法，其特征在于，層次數據結構摘要問題的公式表示如下：

給定一個數據立方體D和誤差門限α，將數據立方體摘要至矩形集合使得是一個α近似矩形，∪R_k＝D，且矩形的數量|S|是最小的。

3.根據權利要求1所述的數據立方體的非層次數據結構摘要方法，其特征在于，α近似矩形的確定步驟如下：從近似矩形的每一個記錄d_ij出發，通過將其位置(i，j)作為矩形的左下角坐標，擴展出α相似矩形，對于左下角為(i，j)右上角為(a，b)的矩形R，如果滿足

則該矩形為α相似矩形。

4.根據權利要求1所述的數據立方體的非層次數據結構摘要方法，其特征在于，允許不同的α近似矩形重疊。

5.根據權利要求1所述的數據立方體的非層次數據結構摘要方法，其特征在于，近似矩形中包含記錄d_ij，將α近似矩形的鍵定義為c×a₁+b₁，其中c是常數，[a₁，b₁]是矩形的左下點，并預先根據記錄的鍵對α近似矩形進行排序。

6.根據權利要求1所述的數據立方體的非層次數據結構摘要方法，其特征在于，所述堆的優化步驟如下：

使用大根堆管理候選α相似矩形，相似矩形的分數被初始化，計數器記錄相似矩形的分數在哪次迭代中最后更新；

在每次迭代中，從堆中彈出一個矩形并檢查其分數是否更新到當前迭代，如果檢查通過，則將矩形添加到結果集S；如果檢查失敗，更新元組的分數和計數器并將其再次推入堆中。

7.根據權利要求1所述的數據立方體的非層次數據結構摘要方法，其特征在于，假設選擇了L個矩形使V(S)的值最大化，假設最優解為最開始選出的L個矩形為S_L，則有其中S為矩形集合，V(S)為S中所包含矩形區域的數據單元的數量，|S|為矩形的數量。