[1]刘哲峰,梁 平,顾进广.基于坐标映射及多重图划分的图相似查询研究[J].计算机技术与发展,2023,33(12):58-64.[doi:10. 3969 / j. issn. 1673-629X. 2023. 12. 008]
　LIU Zhe-feng,LIANG Ping,GU Jin-guang.Research on Graph Similarity Query Based on Coordinate Mapping and Multigraph Partition[J].,2023,33(12):58-64.[doi:10. 3969 / j. issn. 1673-629X. 2023. 12. 008]

点击复制

基于坐标映射及多重图划分的图相似查询研究()

分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

33

期数:

2023年12期

页码:

58-64

栏目:

媒体计算

出版日期:

2023-12-10

文章信息/Info

Title:

Research on Graph Similarity Query Based on Coordinate Mapping and Multigraph Partition

文章编号:

1673-629X(2023)12-0058-07

作者:

刘哲峰¹; 2 ; 梁 平¹; 2 ; 顾进广¹; 2

1. 武汉科技大学 计算机科学与技术学院,湖北 武汉 430065;

2. 智能信息处理与实时工业系统湖北省重点实验室,湖北 武汉 430065

Author(s):

LIU Zhe-feng1; 2 ; LIANG Ping1; 2 ; GU Jin-guang1; 2

1. School of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China;

2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan 430065,China

关键词:

图数据库; 图相似查询; 坐标映射; 选择性图划分; 多层索引结构

Keywords:

graph database; graph similarity search; coordinate mapping; selective map partitioning; multilayer index structure

分类号:

TP311

DOI:

10. 3969 / j. issn. 1673-629X. 2023. 12. 008

摘要:

图相似查询是图数据库资源管理最重要的操作之一。 目前的相似性查询算法几乎都是采用对整个图数据库进行过滤得到候选集的方式,没有考虑在实际图数据库中各数据图规模之间存在着一定的差距,没有必要对整个图数据库进行计算。 因此,提出了一种基于坐标映射的批量处理方式,从规模上对数据图进行剔除,使得后续需要计算的数据图数量大大减少。 同时给出了一个参数化的、基于选择性划分的 GED 下界,使得图划分方式具有约束性,而不是随机的,并在此基础上给出了一个多层索引结构,用于 GED 下限交叉检查。 模拟实验结果表明,所提出的处理方法在通过坐标映射来尽量缩减计算时间的同时,较好地提升了过滤精度,甚至能在过滤阶段就得到相似查询的结果。

Abstract:

Graph similarity search is one of the most important operations in graph database resource management. Currently, mostsimilarity search algorithms filter the entire graph database?

to obtain a candidate set,without considering the significant differences in thesize of the data graphs of the actual graph database, so it is not necessary to calculate the entire graph database. A batch processingmethod based on coordinate mapping is proposed to remove data graphs from the graph database,which greatly reduces the number ofdata graphs that need to be calculated subsequently. Moreover,a parameterized and selective partition-based GED lower bound is givento make the graph partitioning method constrained rather than random. Based on this,a multi-level index structure is provided for GEDlower bound cross - checking. Simulation results show that the proposed processing method not only minimizes the calculation timethrough coordinate mapping but also improves filtering accuracy. Furthermore,it can even obtain the results of similarity queries in thefiltering stage.

常用功能