Accelerating Graph Similarity Search via Efficient GED Computation

Lijun Chang; Xing Feng; Kai YaoLu QinWenjie Zhang

首页> 外文期刊>IEEE Transactions on Knowledge and Data Engineering >Accelerating Graph Similarity Search via Efficient GED Computation

【24h】

Accelerating Graph Similarity Search via Efficient GED Computation

机译：Accelerating Graph Similarity Search via Efficient GED Computation

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

Computing the graph edit distance (GED) between graphs is the core operation in graph similarity search. Recent studies suggest that the existing index structures are ineffective in reducing the overall processing time of graph similarity search, and that directly verifying the GED between the query graph and every data graph in the database is still the best option. The state-of-the-art algorithm for GED verification is the recently proposed ${{{mathsf {AStar}}} text{-}{mathtt {LSa}} }$. However, ${{{mathsf {AStar}}} text{-}{mathtt {LSa}} }$ may consume an extremely large amount of main memory or even run out-of-memory, when the graphs become larger and/or the GED threshold becomes larger. In this paper, we aim to improve the efficiency of GED verification and simultaneously lower the main memory consumption. To achieve that, we propose a new estimation for the lower bounds of partial mappings between graphs. We formally prove that our new lower bound is tighter than the one used in ${{{mathsf {AStar}}} text{-}{mathtt {LSa}} }$. Moreover, we also propose efficient algorithms to compute the lower bounds, as well as optimization techniques to improve the efficiency. Empirical studies on real datasets demonstrate that our newly proposed algorithm ${{{mathsf {AStar}}} text{-}{mathtt {BMao}} }$ runs faster, and at the same time consumes much less main memory, than ${{{mathsf {AStar}}} text{-}{mathtt {LSa}} }$.

著录项

来源
《IEEE Transactions on Knowledge and Data Engineering》 |2023年第5期|4485-4498|共14页
作者
Lijun Chang; Xing Feng; Kai YaoLu QinWenjie Zhang;
展开▼
作者单位

School of Computer Science, University of Sydney, Camperdown, NSW, Australia;

University of Technology Sydney, Ultimo, NSW, Australia;

University of New South Wales, Sydney, NSW, Australia;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类计算技术、计算机技术;
关键词
Indexes; Costs; Databases; Memory management; Estimation; Clustering algorithms; Classification algorithms;

Accelerating Graph Similarity Search via Efficient GED Computation

摘要

著录项

相关主题

期刊订阅