| Presentation | 2012-08-02 A Study on Graph Similarity Search Haichuan Shang, Masaru Kitsuregawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | DE2012-25 |
| Date of Issue |
| Conference Information | |
| Committee | DE |
|---|---|
| Conference Date | 2012/7/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Data Engineering (DE) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Study on Graph Similarity Search |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Haichuan Shang |
| 1st Author's Affiliation | Institute of Industrial Science University of Tokyo() |
| 2nd Author's Name | Masaru Kitsuregawa |
| 2nd Author's Affiliation | Institute of Industrial Science University of Tokyo |
| Date | 2012-08-02 |
| Paper # | DE2012-25 |
| Volume (vol) | vol.112 |
| Number (no) | 172 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |