[發明專利]基于Greedy啟發式策略降低隨機訪問開銷的方法

在審

• 申請號: 201811237816.0
• 申請日: 2018-10-23
• 公開（公告）號: CN109857676A
• 公開（公告）日: 2019-06-07
• 發明（設計）人: 韋鵬程;李莉;段昂
• 申請（專利權）人: 重慶第二師范學院
• 主分類號: G06F12/02
• 分類號: G06F12/02;G06F16/901
• 代理公司: 重慶市信立達專利代理事務所(普通合伙) 50230
• 代理人: 包曉靜

本發明屬于大圖數據處理技術領域；公開了一種基于Greedy啟發式策略降低隨機訪問開銷的方法；內存中設置一個state數組，對算法中圖節點的狀態信息進行記錄；通過第一行和第二行對內存中的state數組進行初始化操作；算法的主體部分，當訪問的當前的節點的狀態為初始狀態的時候，則該點添加到最大獨立集當中，同時將其周圍的點的狀態修改為非獨立集的狀態；依次遍歷圖中的所有的點，最終得到這個圖的最大獨立集。本發明提供的算法在時間和空間上都是非常高效的，而且對其中的大多數數據來說，本發明的算法所得到的最大獨立集可達到其理論上界的96％以上。

技術領域

本發明屬于大圖數據處理技術領域；尤其涉及一種基于Greedy啟發式策略降低隨機訪問開銷的方法。

背景技術

目前，業內常用的現有技術是這樣的：最大獨立集求解是圖論研究領域的基本問題，其在社交網絡分析、編碼理論、無線傳感器網絡調度等領域都有著非常重要的應用。最大獨立集的求解也是一個著名的組合優化的NP-Hard問題。大量的研究工作對近似求解最大獨立集的問題進行了研究，提出了很多近似求解算法。這些算法大多數在理論上是可行的，但若將其應用在大圖數據的環境下，則因算法隨機訪問外存的開銷過大而無法運行。此外，雖然一些計算最大獨立集的外存算法，也因為其隨機性而不能有很好的理論保證。所以，在當前這個許多領域都需要涉及圖數據處理的時代，設計和開發高效的具有實際應用意義的最大獨立集求解算法顯得格外重要。

最大獨立集問題，作為圖論領域的基本問題之一，許多傳統的求解算法都假設圖數據可以直接放在內存中處理，但這對于大規模圖數據來說，是不可能完成的(例如，僅包含節點信息的clueweb數據占用磁盤空間170GB，一般的機器無法直接放入內存中)。如果直接將這些算法以外存的方式實現并應用在大規模圖數據的處理當中，則會因為隨機磁盤訪問數量太高而導致大多數算法不能在合理的時間內運行結束。所以按照傳統思路去設計大圖數據處理算法將變得不再可行。此外，現有一些外存算法的研究，多數集中在理論層面，很少涉及到數據庫層面的研究。

綜上所述，現有技術存在的問題是：

(1)現有技術的求解算法都假設圖數據可以直接放在內存中處理，但這對于大規模圖數據來說，是不可能完成的，一般的機器無法直接放入內存中；目前的計算機內存有限，不能把大圖數據直接從外部設備載入內存。

(2)現有技術中的這些算法中，因為隨機磁盤訪問數量太高而導致大多數算法不能在合理的時間內運行結束；算法時間復雜度過高，計算機不能在有限時間內求解。

解決上述技術問題的難度和意義：：設計算法的時候所采取的降低內存開銷的方法的有效性，同時有效避免了大量隨機訪問產生的開銷，算法是空間高效的。

發明內容

針對現有技術存在的問題，本發明提供了一種基于Greedy啟發式策略降低隨機訪問開銷的方法。

本發明是這樣實現的，一種基于Greedy啟發式策略降低隨機訪問開銷的方法，所述基于Greedy啟發式策略降低隨機訪問開銷的方法包括：

步驟一：內存中設置一個state數組，對算法中圖節點的狀態信息進行記錄；

步驟二：通過第一行和第二行對內存中的state數組進行初始化操作；

步驟三：算法的主體部分，當訪問的當前的節點的狀態為初始狀態的時候，則該點添加到最大獨立集當中，同時將其周圍的點的狀態修改為非獨立集的狀態；

步驟四：依次遍歷圖中的所有的點，最終得到這個圖的最大獨立集。

進一步，所述于Greedy啟發式策略的降低大量隨機訪問產生的開銷的方法具體包括：

步驟一：在內存中設置一個state數組，對算法中圖節點的狀態信息進行記錄；

步驟二：對內存中的state數組進行初始化操作；