[發明專利]大規模流圖在線自適應采樣空間的三角形計數方法及裝置

有效

• 申請號: 202110777154.1
• 申請日: 2021-07-09
• 公開（公告）號: CN113448732B
• 公開（公告）日: 2022-07-01
• 發明（設計）人: 羅鑫;馬麗娜
• 申請（專利權）人: 北京睿芯高通量科技有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京科龍寰宇知識產權代理有限責任公司 11139
• 代理人: 孫皓晨

本發明公開一種大規模流圖在線自適應采樣空間的三角形計數方法及裝置，其中方法是在數據圖流的規模未知和可用內存足夠的情況下，當有新邊到達時，能夠通過蓄水池的兩次抽樣，增量式、自適應的維護蓄水池空間，保證了實時采樣率不低于用戶給定的閾值，以便于能夠查找到更多的三角形數目，從而提高三角形數目評估的準確性。同時，能夠實時地計算全局三角形的數目與局部三角形的數目，可應用于多種現實場景，在保證充分利用內存資源、硬件資源的同時，為三角形進行計數評估的提供更高的準確性。

技術領域

本發明涉及數據處理技術領域，具體而言，涉及一種在線自適應采樣空間的三角形計數方法及裝置，更具體地為一種基于大規模流圖中在線自適應采樣空間的三角形計數方法及裝置。

背景技術

大規模流圖的在線三角形數目檢測具有廣泛的應用場景。考慮到流圖的數據流龐大及內存容量有限，很難將流圖完整的存儲在內存中，因此目前三角形計數算法是采用基于抽樣的近似計算方法。相關的最新研究都是針對有界抽樣空間來維護一定的均勻樣本，然后再使用各種三角形計數算法。

由于流圖的規模是無法提前獲知的，以上方法的缺陷在于：隨著流圖量的增加而導致采樣率不斷降低，進而影響到結果的準確性。

申請號為201810499136.X的中國專利公開了一種基于隨機抽樣的數據流圖中的三角形計數方法及裝置，該專利對數據流圖中的三角形計數評估采用了三個模塊單元，即為抽樣單元、子圖統計單元和原圖估算單元。具體來講，首先，是對接收的原始數據流圖中的邊進行抽樣得到子圖，并計算存留比；然后，對抽樣獲得的子圖中的三角形的數量進行統計；最后，再根據統計得到的子圖中三角形的數量及所述的存留比，估算接收到的原始數據流圖中的三角形數量。

其中，抽樣單元采樣蓄水池抽樣方法對接收的原始數據流圖中的邊進行抽樣，給出了計算存留比a為：

這里的m表示截止到目前一共接收到的邊的總數量，k表示蓄水池抽樣方法抽取的子圖中邊的數量。在原圖估算單元中，使用以下公式來得出原始數據流圖中三角形數量N為：

N＝n*a³。

該專利公開的技術方案僅支持全局三角形計數評估，不能對局部三角形數量進行評估。其中，全局三角形數量是指整個原始數據流圖中出現的三角形數目的總和；而局部三角形則對應于數據流圖中每個節點所形成的三角形。如圖1所示，在該無向圖中，全局三角形有4個，分別為(A,B,E)、(F,B,E)、(B,C,E)及(C,D,E)；對于局部三角形，節點A有一個，為(A,B,E)；節點B有3個，分別為(A,B,E)、(F,B,E)及(B,C,E)；節點C有兩個，分別為(B,C,E)和(C,D,E)；節點D有一個，為(C,D,E)；節點E有4個，分別為(A,B,E)、(F,B,E)、(B,C,E)及(C,D,E)；節點F有1個，為(F,B,E)。

另外，該專利采用的蓄水池抽樣方法需提前知道整個數據流圖的規模，才能選擇合適的需在內存中維持的蓄水池空間大小。在未知數據圖流的規模的情況下，若蓄水池空間分配太小，會直接造成采樣率偏低，影響三角形數目評估的準確性；若蓄水池空間分配空間太大，會使該空間長時間處于未使用狀態，從而浪費了內存資源，降低了內存的有效使用率。

發明內容

為了解決上述問題，本發明提供一種基于大規模流圖中在線自適應采樣空間的三角形計數方法，通過自適應的增大采樣空間的方式，維持采樣率始終不低于用戶指定的采樣率閾值，且能夠同時評估全動態數據圖流中的全局和局部三角形的數目，用以實現在充分利用內存資源的同時，為全局和局部三角形數目評估結果提供更高的準確率。

為達到上述目的，本發明提供了一種大規模流圖在線自適應采樣空間的三角形計數方法，其包括以下步驟：

步驟1：檢測數據圖流是否有新邊到達，

若沒有新邊到達，結束處理流程；