文献

J-GLOBAL ID：200902234792356373   整理番号：08A1059445

リンク構造解析アルゴリズム高速化のための縮小Webの構築

著者 (6件)： 片瀬弘晶 (早稲田大 大学院基幹理工学研究科) ,  松永拓 (早稲田大 大学院基幹理工学研究科) ,  上田高徳 (早稲田大 大学院基幹理工学研究科) ,  田代崇 (早稲田大 大学院基幹理工学研究科) ,  平手勇宇 (早稲田大 メディアネットワークセ) ,  山名早人 (早稲田大 理工学術院)
資料名： 日本データベース学会論文誌  (Journal of the DBSJ)
巻： 7  号： 1  ページ： 245-250  発行年： 2008年06月27日 
JST資料番号： L5754A  ISSN： 1883-1060  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 筆者らはリンク構造解析アルゴリズムの多くがグラフ構造のノード数・エッジ数に依存して計算量が増加するという事実に注目し,Webグラフのリンク構造を圧縮することでノード数・エッジ数を減らし,計算量の軽減とグラフ構造の保存に必要な記憶領域の削減が可能になるのではないかと考えた.そして本稿では,実際に既存のリンク構造解析アルゴリズムの高速化とグラフ構造データの削減を目的とするWebグラフのノード数とエッジ数を削減したグラフ構造(以降,縮小Web)の構築手法を提案した.提案手法では,HITSアルゴリズムのよって得られるWebページのAuthority値とHub値をもとにWebリンク構造上の隣接ノード類似度を判定し,類似ノードをクラスタリングすることで,グラフ構造を縮小化する。実際に,クローリングによって収集したWebデータに対して提案手法を適用し実験を行ったところ,PageRankアルゴリズムの実行時間を36%削減することに成功した.一方で,縮小WebはPageRank値の計算において局所的に誤差の大きくなるノードが発生するという性質があり,本来重要度の高いページがランキング上位から欠落してしまうという欠点を抱えている.

シソーラス用語： Web【情報システム】 ,  *Webページ ,  *リンク ,  グラフ ,  *構造解析 ,  縮小 ,  類似性 ,  クラスタ化 ,  高速アルゴリズム ,  計算量 ,  記憶容量 ,  高速化 ,  インターネット ,  Webグラフ ,  改変

分類 (1件)： 計算機網  (JC03000K)

引用文献 (14件)：

• J. Kleinberg, “Authority sources in a hyperlinked environ ment”, the 9th ACM-SIAM Symp. on Discrete Algorithms, pp. 668-677, 1998.
• L. Page, S. Brin, R. Motowani and T. Winograd: “The Page Rank Ciation Ranking: Bringing Order to the Web”, Tech. Rep., Stanford Digital Libraries, 1998.
• Taher H. Haveliwala, “Efficient computation of PageRank”, Tech. Rep., Computer Science Department, Stanford University, 1999.
• Y-Y Chen, Q. Gan, and T. Suel, “I/O-Efficient Techniques for Computing PageRank”, Proc. ACM Conf. on Information and Knowledge Management, pp. 549-557, 2002.
• Sepandar D. Kamvar, Taher H. Haveliwala, C. Manning and G. Golub, “Adaptive methods for the computation of Page Rank”, Tech, Rep., Stanford University, 2003.

タイトルに関連する用語 (6件)： リンク構造 ,  解析アルゴリズム ,  高速化 ,  縮小 ,  Web ,  構築