[發明專利]基于布爾矩陣分解的圖數據壓縮方法

有效

• 申請號: 202210438892.8
• 申請日: 2022-04-25
• 公開（公告）號: CN114826278B
• 公開（公告）日: 2023-04-28
• 發明（設計）人: 翟學萌;潘夢陽;李爍;胡光岷
• 申請（專利權）人: 電子科技大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 成都虹盛匯泉專利代理有限公司 51268
• 代理人: 王偉

本發明公開了一種基于布爾矩陣分解的圖數據壓縮方法，具體包括：對原始圖數據進行拆分，使用自我中心網絡表示，并進行重排序；使用鄰接矩陣對排序后的自我中心網絡集合進行表示，生成采樣矩陣；將采樣矩陣分解成字典矩陣與稀疏碼矩陣的乘積；布爾原子挖掘；原子進行線性組合，得到采樣恢復矩陣，然后根據采樣階段獲得的采樣節點集合，將各個節點之間的連邊關系按照采樣恢復矩陣進行恢復，得到恢復的圖數據。本發明的方法通過使用布爾矩陣分解的方式，對矩陣分解得到的字典矩陣與稀疏碼矩陣進行約束，使得字典矩陣和稀疏碼矩陣都是布爾型矩陣，可以降低圖數據表征的誤差率，同時提高表征得到的原子的準確率，實現對圖數據的壓縮。

技術領域

本發明屬于互聯網技術領域，具體涉及一種圖數據壓縮方法。

背景技術

近年來，隨著互聯網的發展，數據量也在爆炸式增長，通過社交媒體中產生的信息構建網絡圖，進行分析，對科學研究提供了強有力的支撐，例如蛋白質網絡分析蛋白質特性，用戶商品網絡用于商品推薦，社交網絡圖用于用戶好友推薦等。而由于內存的限制，圖規模的不斷擴大，如今許多圖已無法完整放入內存，這對其存儲與分析都帶來了巨大的挑戰。大規模圖數據還存在結構復雜的問題，其耦合度高，導致在進行一些信息查詢操作時時間開銷極大，且緩存命中率不高，這不利于圖數據的管理。

增加存儲空間與減小存儲需求可以應對以上問題。例如外存模式圖處理系統和分布式內存圖處理系統，通過增加存儲空間來解決問題，但是這只是治標不治本，昂貴的硬件成本以及時間開銷并沒有被較低，在此種情況下，對減小存儲空間需求方法的呼聲越來越高。

圖壓縮是為了應對圖規模增長對圖存儲與圖分析的帶來挑戰的技術。通過對圖數據進行壓縮，可以有效的將降低其規模，去除其中冗余信息，將其中稀疏的有效信息抓取出來，從而使其便于存儲。當前的圖壓縮算法多種多樣，它們主要關注兩個性能指標：壓縮率和運行性能。采用復雜編碼的技術可以獲得優異的壓縮率，但其運行效率較低；而編碼簡單的可以擁有極低的時間復雜度，但其壓縮率卻不高。顯然，二者不可兼得，圖壓縮就是在這兩個目標之間進行平衡。

圖壓縮算法一般包括兩個階段：節點排序和編碼。“Boldi?P,Vigna?S.Thewebgraph?framework?I:compression?techniques[C]//Proceedings?of?the?13thinternational?conference?on?World?Wide?Web.2004:595-602”開發了一個通用的網頁圖壓縮框架WebGraph，它們利用網頁在字典序排序下的局部性與相似性，提出了BV編碼，該編碼結合了多種編碼方法，例如間隙碼、差分編碼、引用編碼等。其中間隙碼利用了局部性，將節點的鄰居編碼為鄰居間的間隙，而引用編碼則利用了相似性，將重復出現過的鄰居序列通過引用表示，從而減少需要存儲的鄰居數。

文獻“Chierichetti?F,Kumar?R,Lattanzi?S,et?al.On?compressing?socialnetworks[C]//Proceedings?of?the?15th?ACM?SIGKDD?international?conference?onKnowledge?discovery?and?data?mining.2009:219-228”將局部性、相似性帶到了社交網絡中，將捕獲兩個特性的問題轉換成了最小對數間隙排列的自然組合優化問題，并提出了Shingle節點排序算法，通過每個節點的一階鄰居結構生成該節點的表示，將這些表示進行排序，默認具有相似表示的節點們具有相似的一階鄰居結構，從而捕捉相似性與局部性。同時，將社交網絡中用戶之間相互關注的極大可能考慮進來，從而進一步減少存儲空間，提高壓縮率。