請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37134
標題: | 巨圖中三角子圖數的快速計算及其應用 Triangle Counting in Large Sparse Graph |
作者: | Meng-Tsung Tsai 蔡孟宗 |
指導教授: | 劉邦鋒(Pangfeng Liu) |
關鍵字: | 三角子圖計算,稀疏圖,高效演算法,群聚指令,除頻原則, triangle counting,sparse graph,efficient algorithm,population counting,frequency division principle, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 在論文中,
我們發展了新的演算法來計算給定圖的三角子圖數。 目前已知最有效率的撥結點演算法需要$O(m^{3/2})$ 基本指令的計算時間及$Theta(m)$記憶體空間。 結合廣為人知的四蘇聯人演算法, 可以得到稍微進一步的演算法需要$O(m^{3/2}/log^{1/2}m)$ 群聚指令的計算時間及$Theta(m)$記憶體空間。 然而僅有部份的中央處理器支援群聚指令, 在有支援的情況下, 群聚指令被視為基本指令, 在不支援的情況下, 群聚指令可以用$O(log^{(2)}g)$個基本指令完成。 在這論文提到的計算三角子圖中, 並不需要知道每個群聚指令的執行結果。 利用這個特性, 我們發展了攤還式演算法, 它能進一步改善了在不支援的情況下, 群聚指令所需的基本指令僅須$o(log^{(3)}g)$個指令完成。 不管在理論分析或是實驗數據上, 我們的攤還式演算法均勝出, 快的幅度是$omega(log^{1/2}m/log^{(4)}m)$。 In this paper, we develop a new algorithm to count the number of triangles in a graph $G(n, m)$. The latest efficient algorithm, Forward Algorithm, needs $O(m^{3/2})$ basic instructions' execution time and $Theta(m)$ memory space. With the combination of the well-known Four-Russians' Algorithm, we obtain an algorithm that requires $O(m^{3/2}/log^{1/2} m)$ execution of the population count procedure using $Theta(m)$ memory space. Some CPUs support population count directly. In such cases, the population count can be executed with one instruction; otherwise, an alternative method should be employed. The known best one is named as extit{bitwise twiddling} method, which can be executed with $Theta(log^{(2)}g)$ basic instructions. Owing to it is not necessary to exactly know the result of each population count, we can replace each population count with an amortized population count. Therefore, we also develop an efficient algorithm to fast execute the amortized population count. Based on the theoretic analysis, we conclude that the amortized population count can be executed with $o(log^{(3)}g)$ basic instructions. Besides, the experiment result also shows the performance of our amortized population count is better than others. As a result, our triangle counting algorithm is faster than the previous known best one by a factor $omega(g^{1/2} / log^{(3)} g)$ where $g = Omega(log m)$. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37134 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 742.41 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。