講演名	2012-08-02 A Study on Graph Similarity Search ,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)
抄録(英)	Graph similarity search is to retrieve graphs that approximately contain a given query graph. It has many applications, e.g., detecting similar functions among chemical compounds. The problem is challenging as even testing subgraph containment between two graphs is NP-complete. Hence, existing techniques adopt the filtering-and-verification framework with the focus on developing effective and efficient techniques to remove non-promising graphs. Nevertheless, existing filtering techniques may be still unable to effectively remove many "low" quality candidates. To resolve this, in this paper we propose a novel indexing technique to index graphs according to their "distances" to features. We then develop lower and upper bounding techniques that exploit the index to (1) prune non-promising graphs and (2) include graphs whose similarities are guaranteed to exceed the given similarity threshold. Considering that the verification phase is not well studied and plays the dominant role in the whole process, we devise efficient algorithms to verify candidates. A comprehensive experiment using real datasets demonstrates that our proposed methods significantly outperform existing methods.
キーワード(和)
キーワード(英)
資料番号	DE2012-25
発行日

研究会情報
研究会	DE
開催期間	2012/7/25(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Data Engineering (DE)
本文の言語	ENG
タイトル（和）
サブタイトル（和）
タイトル（英）	A Study on Graph Similarity Search
サブタイトル（和）
キーワード(1)（和/英）
第 1 著者 氏名（和/英）	/ Haichuan Shang
第 1 著者 所属（和/英）	Institute of Industrial Science University of Tokyo
発表年月日	2012-08-02
資料番号	DE2012-25
巻番号（vol）	vol.112
号番号（no）	172
ページ範囲	pp.-
ページ数	6
発行日