Efficient Search in Graph Edit Distance: Metric Search Trees vs Brute Force Verification
<|reference_start|>Efficient Search in Graph Edit Distance: Metric Search Trees vs Brute Force Verification: 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.<|reference_end|>
@article{guo2024efficient,
    title={Efficient Search in Graph Edit Distance: Metric Search Trees vs. Brute
  Force Verification},
    author={Wenqi Marshall Guo and Jeffrey Uhlmann},
    journal={arXiv preprint arXiv:2405.17434},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.17434},
    primaryClass={cs.DB cs.IR}
}