シソーラスブラウザxthesにおけるDAG構造の描画アルゴリズムとその評価

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we present a method to plot a directed acyclic graph (DAG) which represents a hierarchical structure with multiple inheritances. This method is used in the thesaurus browser 'xthes' to display 'is-a' relationship between nodes in a thesaurus or ontology. Because it is noted that the problem of minimizing arc crossings in a DAG is NP-hard, we need a fast heuristic algorithm. 'xthes' draws a DAG as follows. At first, it splits a DAG into a tree and other non-tree arcs. Then, it rearranges the order of children nodes by clustering subtrees, and reverses the order of subtrees in the clusters, to make the length of inter-subtree links as short as possible. Finally, it minimizes the distance between subtrees in bottom-up manner, and decides the position of the nodes and arcs. By the experiment, it was confirmed that our node-exchanging method saves about 50% of the total length of the crossing arcs. It seems that our method can display a DAG in a comprehensible form, and that it is fast enough to update the diagram interactively.

• 九州大学の論文

著者

• 市丸 夏樹

  九州大学大学院システム情報科学研究院知能システム学部門

関連論文

• シソーラスと確率文法による派生語解析
• 要約文の話題の流れの最大化による自動要約
• 常識推論における推論の選択と文脈処理への応用
• PCFGによる派生語処理手法の比較と検討
• Stolcke, A. : An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities, Computational Linguistics, Vol.21, No.2, pp.165-201 (1995)
• 意味的結束性に基づく文脈処理
• 常識推論における推論の選択
• シソーラスブラウザxthesにおけるDAG構造の描画アルゴリズムとその評価

スポンサーリンク