Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.17434 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916262584516608 |
|---|---|
| author | Guo, Wenqi Marshall Uhlmann, Jeffrey |
| author_facet | Guo, Wenqi Marshall Uhlmann, Jeffrey |
| contents | This report evaluates the efficiency of Graph Edit Distance (GED) computation for graph similarity search, comparing Cascading Metric Trees (CMT) with brute-force verification. Despite the anticipated advantages of CMT, our findings indicate it does not consistently outperform brute-force methods in speed. The study, based on graph data from PubChem, suggests that the computational complexity of GED-based GSS remains a challenge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17434 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Search in Graph Edit Distance: Metric Search Trees vs. Brute Force Verification Guo, Wenqi Marshall Uhlmann, Jeffrey Databases Information Retrieval This report evaluates the efficiency of Graph Edit Distance (GED) computation for graph similarity search, comparing Cascading Metric Trees (CMT) with brute-force verification. Despite the anticipated advantages of CMT, our findings indicate it does not consistently outperform brute-force methods in speed. The study, based on graph data from PubChem, suggests that the computational complexity of GED-based GSS remains a challenge. |
| title | Efficient Search in Graph Edit Distance: Metric Search Trees vs. Brute Force Verification |
| topic | Databases Information Retrieval |
| url | https://arxiv.org/abs/2405.17434 |