大規模グラフに対するObjectRankの高速な近似Top-k検索

• 佐藤, 朋紀

• 塩川, 浩昭

• 山口, 祐人

• 北川, 博之

書誌事項

タイトル別名

• Fast Approximate Top-k Search of ObjectRank for Large Graphs

抄録

データベースに対するキーワード検索を実現する手法にObjectRankがある．ObjectRankは，データベース内のオブジェクトをグラフによって表現することでPageRankを拡張したリンク解析手法を適用し，キーワードに対する各オブジェクトの重要度を評価する．しかし，ObjectRankは重要度評価時に行列とベクトルの積を繰り返し計算する必要があるため，大規模なグラフへの適用が難しいという問題がある．そこで本稿では，ObjectRankのtop-k検索の近似解を高速に計算する手法を提案する．提案手法は，重要度の計算過程でtop-k検索の解に影響を与えにくいノードを特定し枝刈りすることで，計算対象のノード数を削減する．本稿では，実データを用いた評価実験により提案手法の有効性を評価する．

ObjectRank performs keyword search on databases. ObjectRank represents objects as a graph and evaluates the importance of each node with respect to the keyword based on link analysis method which extends PageRank. However, it is infeasible for ObjectRank to evaluate large graphs in a practical time since it needs to iteratively calculate the product of matrix and vector during importance evaluation. In order to address this problem, we propose a fast algorithm that efficiently approximates top-k search results obtained by ObjectRank. Our proposed algorithm reduces the number of nodes to be calculated by identifying and prunes nodes that have low influence on the top-k search results during the computation. In this paper, we evaluate the performance of our proposed algorithm by experiments using real-world data.

収録刊行物

• 情報処理学会論文誌データベース（TOD）

  情報処理学会論文誌データベース（TOD） 10 (4), 11-15, 2017-12-13

キーワード

• [テクニカルノート] ObjectRank，グラフマイニング，グラフデータベース

詳細情報

• CRID: 1050001337908514560
• NII論文ID: 170000149098
• NII書誌ID: AA11464847
• ISSN: 18827799
• Web Site: http://id.nii.ac.jp/1001/00184836/
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN