-
题名面向图相似性搜索的高效图编辑距离算法
- 1
-
-
作者
邱珍
郑朝晖
-
机构
苏州大学计算机科学与技术学院
苏州大学江苏省网络空间安全工程实验室
-
出处
《计算机应用研究》
CSCD
北大核心
2023年第2期371-377,共7页
-
基金
江苏省高校自然科学研究项目(19KJA550002)
江苏省高校优势学科建设工程资助项目。
-
文摘
在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。
-
关键词
图编辑距离
等价映射
映射编码
下界计算
图相似性搜索
-
Keywords
graph edit distance
equivalent mapping
mapping encoding
lower bound computation
graph similarity search
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名高效低索引的图相似性搜索算法
- 2
-
-
作者
邱珍
郑朝晖
-
机构
苏州大学计算机科学与技术学院
江苏省网络空间安全工程实验室
-
出处
《计算机科学》
CSCD
北大核心
2023年第9期130-138,共9页
-
基金
江苏省高校自然科学研究项目(19KJA550002)。
-
文摘
图相似性搜索是在给定的度量标准下查找与查询图相似的图集合,目前大多采用“过滤-验证”的计算框架。针对现有方法中过滤下界不紧密和索引空间占用较大等问题,提出了一种基于查询图分区的多层级过滤、低索引空间占用的图相似性搜索算法Z-Index。该算法首先通过全局粗粒度过滤得到预候选集;然后提出基于扩展概率的查询图分区算法,并采用层级过滤机制进一步精简候选集,增强下界紧密性;最后引入序列相似性差值计算序列中数据分布的稀疏度,提出分区压缩和差值压缩两种编码压缩算法,并据此构建“零”索引结构,降低索引空间开销。实验结果表明,Z-Index算法所得下界更加紧密,产生的候选集大小可减少50%左右,算法执行时间大大缩短,且该算法在索引空间占用极小的情况下仍具有可扩展性。
-
关键词
图相似性搜索
层级过滤
扩展概率
编码压缩
查询图分区
-
Keywords
Graph similarity search
Hierarchical filtering
Extension probability
Coding compression
Query graph partitioning
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名基于拓扑子图与编辑距离的距离测量方法
- 3
-
-
作者
程树明
古天龙
-
机构
桂林电子科技大学计算机与控制学院
-
出处
《桂林电子科技大学学报》
2009年第1期35-40,共6页
-
文摘
图结构数据搜索的核心是为图的匹配寻找一个好的相似性测量方法。图编辑距离法和最大公共子图法是现有的两种较成熟的测量方法。图编辑距离法善于描述细小的距离差距,但缺乏结构上的描述;最大公共子图法与之相反,在结构描述上很有优势,但是在细节的描述上很弱。鉴于这种情况,将最大拓扑公共子图法与编辑距离测量法相结合,提出了一种新的相似性测量方法。这种方法先用拓扑公共子图进行结构性描述,然后利用编辑距离的细节描述能力对最大拓扑公共子图内部的相似性距离进行调整,从而有效地发挥了最大公共子图法和编辑距离法各自的优点,使得图之间的相似性衡量更加有效、精确;同时在图的相似性搜索、图像检索、对象识别等领域也更有相容力和理解力。
-
关键词
图结构数据
拓扑公共子图
图相似性搜索
编辑距离
距离测量
-
Keywords
graph-structured data
topological common subgraph
graph similarity searching
edit distance
distance measure
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
