| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 5A |
| セッション名 |
| 情報検索・論理・オートマトン |
| 講演日 |
| 2009/09/03 |
| 講演場所(会議室等) |
| A会場（9号館1F 911教室） |
| 講演番号 |
| A-020 |
| タイトル |
| グラフデータベースにおけるキーワード検索方式の改良 |
| 著者名 |
| 岡谷 昌史, 大森 匡, 星 守, |
| キーワード |
| グラフデータベース, キーワード検索, 最小コストグループシュタイナー木 |
| 抄録 |
| 本稿では、グラフとして表現されたデータベースを対象に、入力された複数キーワードを満たす部分グラフを最小コスト順に上位k個（top-k）検索する問題を扱う。この問題は、2007年に、B.Dingらによって最小コストグループシュタイナー木の計算問題として扱われ、最短経路法の戦略に基づいたコスト昇順の連結木計算法DPBF-kが提案されている。しかし、DPBF-kは、top-1解の他は近似解になる。本稿は、DPBF-kに基づいて、計算過程でのグラフのノードに上位k個の根つき木候補を保存することにより、top-k個の厳密解を計算するようDPBFを修正した改良DPBF法を提案する。本稿は、改良DPBF法を述べた後、冗長な解の回避にナイーブな戦略だけを用いた状況下で実装を行った結果を報告する。 |
| 本文pdf |
| PDF download (823KB) |