[發明專利]一種基于最小略圖的流模式下有向標簽圖的略圖構建方法

有效

• 申請號: 201710421147.1
• 申請日: 2017-06-07
• 公開（公告）號: CN107203635B
• 公開（公告）日: 2020-08-11
• 發明（設計）人: 宋春瑤;葛瑤;袁曉潔
• 申請（專利權）人: 南開大學
• 主分類號: G06F16/51
• 分類號: G06F16/51;G06F3/06
• 代理公司: 天津佳盟知識產權代理有限公司 12002
• 代理人: 李益書

一種基于最小略圖的流模式下有向標簽圖的略圖構建方法。在這個數據爆炸的時代，各類應用每天都會產生海量的數據，同時各類應用所產生的數據也在不斷地飛速增長中。當前大量應用所產生的海量數據都可以用圖模型、特別是有標簽圖模型來表示。為適應大數據的數據容量大以及輸入輸出速度快的特征，圖壓縮與略圖上的查詢成為了支持很多應用的一種有效手段。為了得到流模式下有標簽圖的略圖，提出本發明的略圖構建方法，該方法包括：對圖數據上點的標簽和標識符進行兩級哈希映射；對圖數據上邊的標簽進行哈希映射；利用一組質數的特性將多個邊標簽壓縮在一個整數中；對流模式下滑動窗口的子窗口劃分；對流模式下失效數據的自動處理。

技術領域

本發明屬于圖數據處理的技術領域。

背景技術

在這個數據爆炸的時代，各類應用每天都會產生海量的數據，同時各類應用所產生的數據也在不斷地飛速增長中。常見的應用如社交網絡平臺微博，電話網絡，web服務器請求，道路網絡等等，這些應用都可以方便的用圖結構，特別是有標簽圖結構來進行表示。包括但不限于以上所提到的這些應用，這些應用所涉及的數據都是以一種流模式的方式不斷產生的。

由于數據量的巨大，基于原始圖的查詢是很困難的。一方面是由于原始圖的規模太大，基于原始圖的查詢可能需要不斷地將部分原始圖讀入內存，這是十分耗費資源和計算時間的。另一方面，在大規模原始圖上的搜索查詢也是十分耗費時間的。

當前數據應用的另一個特點是大部分都是流模式下的數據應用，即圖上的邊是一條一條到來的，而到來的速率十分密集，有可能是井噴式的。而更靠近當前時間的數據可能是更有意義的，用戶可能會更感興趣。

為適應大數據的數據容量大以及輸入輸出速度快的特征，并滿足各種在線應用數據實時處理的需求，基于圖壓縮與略圖的查詢研究成為了支持很多應用的一種有效手段。然而研究多是基于靜態圖以及非標簽圖處理的。因此，如何構建支持流模式下有標簽圖動態處理的略圖成為一個難題。

發明內容

本發明目的是解決流模式下大規模圖數據的處理與查詢這一問題，提供一種基于最小略圖的流模式下有向標簽圖的略圖構建方法。本發明通過對圖數據頂點的兩級哈希映射以及對邊標簽的質數表示，將有向標簽圖數據的方向與標簽信息壓縮到略圖中，保留了原始圖的完整信息與圖結構，使壓縮后的略圖能夠支持原始圖上的各項查詢。

本發明提供的基于最小略圖的流模式下有向標簽圖的略圖構建方法，以最小略圖思想為基礎，構建出的略圖可以僅使用原始圖亞線性的存儲空間的前提條件下，保留原圖上點和邊的標簽信息以及圖結構信息，同時快速支持原始圖支持的各項通用圖查詢；同時，由于流模式下子窗口的使用，使略圖可以自動處理失效數據，以適應流模式下滑動窗口的特殊需求；具體步驟如下：

第1、根據最大存儲空間要求或壓縮比率要求分配略圖存儲空間

使用略圖的目的是為了利用有限的存儲空間，通常是只使用原圖存儲空間亞線性的存儲空間來進行存儲。因此，在構建略圖之前，需要根據事先要求的壓縮比率或允許使用的最大存儲空間來為略圖分配存儲空間。由于略圖占用的存儲空間與圖數據點標簽、點標識符以及邊標簽的映射范圍相關，因此需要在給定壓縮比率要求或略圖占用最大存儲空間的基礎上確定點標簽、點標識符以及邊標簽的映射范圍。具體分為兩種情況，具體方法如下：

(1)根據最大存儲空間要求分配略圖存儲空間

給定能夠存儲n個數據單元的空間，同時已知不同點標簽的總數量為l₁，不同點標識符的總數量為l₂，不同邊標簽的總數量為l₃(對于未知數據的統計信息可通過對數據一小段時間的運行統計得出)。通常情況下，哈希函數的映射范圍會遠小于被映射數據項的實際數量，以達到存儲壓縮的目的。在滿足存儲空間上限要求的前提下，點標簽與點標識符的映射范圍與點標簽總數量和點標識符總數量呈正比，邊標簽的映射范圍遠小于邊標簽的實際數量，則：