文献

J-GLOBAL ID：201202236740174658   整理番号：12A1377723

グラフ相似性探索に関する研究

A Study on Graph Similarity Search

著者 (2件)： SHANG Haichuan (Univ. Tokyo) ,  KITSUREGAWA Masaru (Univ. Tokyo)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 172(DE2012 16-26)  ページ： 53-58  発行年： 2012年07月25日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフ相似性探索は与えられた質問グラフを近似的に含むグラフを取り出すことである。これは,例えば,化合物間の類似機能の検出などの多くの応用がある。この問題は,NP完全な2つのグラフ間に閉じ込められたサブグラフの検査としてまさに挑戦的である。従って,非期待グラフを除去するための効果的で有効な技術の開発に焦点を当てて,既存の技術をフィルタリングと検証フレームワークに採用した。とは言っても,既存のフィルタリング技術は,未だに,多くの「低」品質の候補を効率よく除去することはできない。本稿では,これを解決するために,特徴への「距離」に従ってグラフを索引する,新しい索引技術を提案した。次に,(1)非期待グラフ刈り取り,および(2)その相似性が与えられた相似性閾値を超えることを保証されているグラフの包含への索引を,利用する下界および上界技術を開発した。この検証フェーズは満足いく研究がされておらず,しかも全体のプロセスの中で主要な役割を果たしていることを考慮して,候補を検証するための効果的なアルゴリズムを考案した。現実のデータベースを用いた包括的な実験により,提案した手法が既存の手法より,著しく優れている事を実証した。(翻訳著者抄録)

シソーラス用語： *グラフ ,  索引 ,  NP完全問題 ,  フィルタリング ,  閾値 ,  検証 ,  捜索 ,  類似性
準シソーラス用語： *相似性 ,  探索

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (9件)：

• CHENG, J. Fg-index : towards verification-free query processing on graph databases. SIGMOD, 2007. 2007, 857-872
• GAREY, M. R. Computers and Intractability : A Guide to the Theory of NP-Completeness. 1979
• GIUGNO, R. Graphgrep : A fast and universal method for querying graphs. ICPR, 2002. 2002, volume 2, 112-115
• HE, H. Closure-tree : An index structure for graph queries. ICDE, 2006. 2006, 38-39
• SHANG, H. Taming verification hardness : an efficient algorithm for testing subgraph isomorphism. VLDB,2008. 2008, 364-375

タイトルに関連する用語 (4件)： グラフ ,  相似性 ,  探索 ,  研究