基于k-自同构的图模拟方法研究

发布时间：2024-02-15 16:19

　　子图模式匹配是图数据管理和计算中的一项基本操作,它主要包括子图同构和图模拟。子图同构要求子图与查询图有完全相同的结构特征和标签特征,因此它的计算复杂度很高。图模拟是针对子图同构的高时间复杂度所提出的一种新的子图模式匹配模型,国内外学者在图模拟的基础上又提出了多种图模拟扩展模型,包括双重模拟(Dual Simulation)、强模拟(Strong Simulation)、严格模拟(Strict Simulation)和严密模拟(Tight Simulation)等,以适应不同应用场景下的匹配查询。随着图数据规模的增大和云端平台管理技术的日益成熟,用户也愈加倾向于将大量图数据存储于云平台上。虽然当前的云服务平台可以提供数据存储平台和基础数据管理服务,但是云平台的安全性并不能得到保证,因此将重要图数据存储于云平台上会面临隐私泄露的安全隐患。本文对云端图数据匹配查询所面临的隐私泄露问题进行研究,提出了基于k-自同构的隐私保护基础框架。针对图数据的标签隐私,本文采用了标签泛化的方法,对数据图和模式图的顶点标签进行匿名化处理;针对图数据的结构隐私,本文采用了基于k-自同构模型的保护方法,利用k-自...

【文章页数】：68 页

【学位级别】：硕士

【部分图文】：

图２－１数据图和匹配图样例??

第二ｆ：相关理论及问题定义?基于自同构的图模拟方法研究??定义２．１．??路径：在图中，一条有向路径由一组顶点的集合（１，１，匕．．．，％，）表示，其中〇，．＾，．＋?１）（／’￡??丨ｌ，ｎ－?１］）表示图Ｇ中的一条边。一条路径中顶点的个数就是该条路径的长度，??用／ｅｖ；（ｐ....

图２－２自同构图样例??２．１．２子图模式匹配糢型理论介绍??

基于Ｉ自同构的图模拟方法研究?第二章相关理论及问题定义??如图２－２所示的图Ｒ是一个典型的自同构图，它关于图中的虚线是对称的。??在Ｇ中存在自同构函数／，使得／（Ａ，）?＝?Ａ３，?／（取）＝馬，且／（（Ａ，，取ｊＸ／ＸＡａ／ＯＢ，））：??（Ａ３，８２）０??＠?＼??／？??....

图２－３不同匹配模型对比样例??

第二章相关理论及问题定义?基于ｈ自同构的图模拟方法研究??＆?（ｓ）??（ａ＞模式图Ｑ?（ｂ）数据图Ｇ??图２－３不同匹配模型对比样例??别以丨氏，的，知队，出，５６｝作为球心，以模式图！２中ｆｉ与其它顶点的最长距离１为半径作??球，最终产生与子图同构相同的匹配结果。??２．２问....

图２－５强模拟匹配子图??当用户发现数据图Ｇ的规模很大时，就会考虑利用云服务平台来存储数据图??并通过该平台进行简笮的匹配查询操作，此时用户就需要考虑到一个数据安全性??的问题

基于ｆｃ－自同构的图模拟方法研究?第二章相关理论及问题定义??

本文编号：3899984