-
题名高效低索引的图相似性搜索算法
- 1
-
-
作者
邱珍
郑朝晖
-
机构
苏州大学计算机科学与技术学院
江苏省网络空间安全工程实验室
-
出处
《计算机科学》
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
[自动化与计算机技术—计算机应用技术]
-
-
题名基于坐标映射及多重图划分的图相似查询研究
- 2
-
-
作者
刘哲峰
梁平
顾进广
-
机构
武汉科技大学计算机科学与技术学院
智能信息处理与实时工业系统湖北省重点实验室
-
出处
《计算机技术与发展》
2023年第12期58-64,共7页
-
基金
国家社会科学基金重大项目(11&ZD189)。
-
文摘
图相似查询是图数据库资源管理最重要的操作之一。目前的相似性查询算法几乎都是采用对整个图数据库进行过滤得到候选集的方式,没有考虑在实际图数据库中各数据图规模之间存在着一定的差距,没有必要对整个图数据库进行计算。因此,提出了一种基于坐标映射的批量处理方式,从规模上对数据图进行剔除,使得后续需要计算的数据图数量大大减少。同时给出了一个参数化的、基于选择性划分的GED下界,使得图划分方式具有约束性,而不是随机的,并在此基础上给出了一个多层索引结构,用于GED下限交叉检查。模拟实验结果表明,所提出的处理方法在通过坐标映射来尽量缩减计算时间的同时,较好地提升了过滤精度,甚至能在过滤阶段就得到相似查询的结果。
-
关键词
图数据库
图相似查询
坐标映射
选择性图划分
多层索引结构
-
Keywords
graph database
graph similarity search
coordinate mapping
selective map partitioning
multilayer index structure
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名面向图相似性搜索的高效图编辑距离算法
- 3
-
-
作者
邱珍
郑朝晖
-
机构
苏州大学计算机科学与技术学院
苏州大学江苏省网络空间安全工程实验室
-
出处
《计算机应用研究》
CSCD
北大核心
2023年第2期371-377,共7页
-
基金
江苏省高校自然科学研究项目(19KJA550002)
江苏省高校优势学科建设工程资助项目。
-
文摘
在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。
-
关键词
图编辑距离
等价映射
映射编码
下界计算
图相似性搜索
-
Keywords
graph edit distance
equivalent mapping
mapping encoding
lower bound computation
graph similarity search
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名基于SQL的图相似性查询方法
被引量：4
- 4
-
-
作者
赵展浩
黄斐然
王晓黎
卢卫
杜小勇
-
机构
中国人民大学信息学院
数据工程与知识工程教育部重点实验室(中国人民大学)
厦门大学软件学院
-
出处
《软件学报》
EI
CSCD
北大核心
2018年第3期689-702,共14页
-
基金
国家自然科学基金(61502504
61702432)
+1 种基金
中国人民大学科学研究基金(中央高校基本科研业务费专项资金)(15XNLF09)
福建省中青年教师教育科研项目(JAT160003)~~
-
文摘
图作为一种表示复杂信息的数据结构,被广泛应用于社交网络、知识图谱、语义网、生物信息学和化学信息学等领域.随着各领域应用的普及和深入开展,如何管理这些复杂图数据,是目前图数据库技术面临的巨大挑战.图的相似性查询是图数据管理中的热点问题之一,对图查询问题的研究主要包括图的相似性查询等.重点研究基于编辑距离(graph edit distance)的图相似性查询处理问题.首先,通过对目前代表性的问题求解算法分析发现,目前已提出的过滤规则都具有自己的优缺点和适用性.其次,针对已有方法在过滤阶段自身存在的优缺点和适用性的问题,提出一种面向关系型数据库的过滤框架,新的过滤框架可以支持所有已有的过滤规则,从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率.该方法可以最大程度地保留不同过滤规则的优点并克服其缺点,从而对不同查询具有普遍适用性.最后,基于PubChem数据集,通过比较算法在求解查询结果的时间消耗,验证所提出算法的高效性及可扩展性.实验结果表明,所提出的方法优于现有算法.
-
关键词
图编辑距离
图相似查询
POSTGRESQL
过滤和验证
-
Keywords
graph edit distance
graph similarity search
PostgreSQL
filter-and-verification
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
