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

IPSJ

Bibliographic Information

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

Search this article

Abstract

データベースに対するキーワード検索を実現する手法に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.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top