没有合适的资源?快使用搜索试试~ 我知道了~
https://theses.hal.science/tel-01781831Chems Eddine Nabti0HAL编号:tel-017818310提交日期:2018年4月30日0HAL是一个多学科开放存取档案,用于存储和传播科学研究文献,无论其是否发表。这些文献可以来自法国或国外的教育和研究机构,也可以来自公共或私人研究中心0HAL多学科开放存取档案,旨在存储和传播法国或国外教育和研究机构、公共或私人实验室发表或未发表的研究级科学文献0在大规模图数据中的子图同构搜索0引用此版本:0Chems Eddine Nabti. 在大规模图数据中的子图同构搜索. 数据库 [cs.DB]. 里昂大学, 2017. 英文. �NNT :2017LYSE1293�. �tel-01781831�No d’ordre NNT : xxxLIETARD Ludovic, Maitre de Conférences, HDR, Université de Rennes1RapporteurTAMINE-LECHANI Lynda, Professeure des Universités, UPS ToulouseRapporteur(e)TERMIER Alexandre, Professeur des Universités, Université de Rennes1ExaminateurSEBA Hamida, Maitre de conférences, HDR, Université Claude Bernard Lyon1Directrice dethèse0里昂大学博士论文,由里昂第一大学操作0博士学位授予学校:ED512学校:计算机科学和数学学院0博士专业:学科:计算机科学0公开答辩日期:,候选人:Chemseddine NABTI0在大规模图数据中的子图同构搜索0评审委员会:� � � �� � ��� � � � � �� �� � � � � � � �� � � �� � � � � � � � ��� � � � � � � � � � �� � � � � � � � � � � ���� � � � � � � �� ��� � � � � � �� �� � ��� � � � � � � � �0Avis du directeur de thèse, des rapporteurs et des membres du jury0关键词0Titre0学科分类0Résumé0导师0Abstract0摘要0Author0目录0Title0致谢0Doctoral Thesis0Discipline0Keywords0摘要0Abstract0目录0附录0致谢0参考文献0参考文献0致谢0附录0目录0摘要0目录0导师0致谢0学科分类0参考文献0关键词0附录0论文摘要0摘要0��������������� ���������������������������0��������������0������������������������������������������0������������������������������������������0�������������������������������������� ����0������������������������������������������0����������������������������0�������������������������������������������0��������������������������0�������������������������������0�����������������������������������������0����������������������������� ���������� �0������������������������������������������0������������������������������������������0����������������� ���������� ��0������������������������������0��������������������������������������0���������������������������0��������������������������������������0�������������������������������������������0���������������������������0�0摘要0查询图数据是一个基本问题,它在不断增长的情况下见证了0特别适用于大规模结构化数据,其中图形作为一种有前景的0关系数据库的替代方案,用于大数据建模。然而,查询0图数据与查询关系表格数据的查询方式不同且更加复杂0数据。查询图数据涉及的主要任务是子图同构0子图同构搜索是一个NP完全问题。子图同构搜索是0这是一个重要的问题,涉及到各个领域,如模式0识别、社交网络分析、生物学等领域中的一个重要问题,它的目标是枚举0数据图中与查询图匹配的子图。最为人所知的解决方案0这个问题的大多数解决方案都是基于回溯的。它们探索了一个庞大的搜索空间,这0当我们处理大规模图数据时,结果会导致计算成本很高。0为了降低子图同构问题的时间和内存空间复杂度0搜索。我们提出使用压缩图。在我们的方法中,子图同构0在压缩表示的图上实现了对同构搜索的加速,而无需0解压缩它们。图形压缩是通过将顶点分组成0超级顶点。在图论中,这个概念被称为模块分解。0tion。它用于生成图的树形表示,突出显示了组0具有相同邻居的顶点的压缩。通过这种压缩,我们获得了0搜索空间的大幅减少,从而节省了大量的时间。0在处理时间上获得了显著的改善。0Chemseddine Nabti Liris实验室 iii0我们还提出了一种新颖的顶点编码方法,简化了过滤0搜索空间。这种新机制被称为紧凑邻域索引0(CNI)。CNI将一个顶点周围的所有信息压缩成一个整数。这0简单的邻域编码减少了顶点过滤的时间复杂度0从立方体到二次方程,这对于大型图形来说是相当可观的。我们还提出了0一种迭代的全局过滤算法,依赖于CNI的特性来0确保对搜索空间进行全局剪枝。0我们在几个真实数据集上评估了我们的方法,并进行了比较0使用最先进的算法对其进行处理。0iv Liris实验室Chemseddine Nabti0摘要0数据图的查询是一个基本问题,0尤其是对于大规模结构化数据0其中图形是数据库的有希望的替代品0关系模型用于建模大量数据。0数据图的查询与关系数据的查询不同0关系数据查询与关系表的查询不同。主要任务0数据图的查询的主要任务是搜索0子图同构是一个NP完全问题。0子图同构搜索是一个非常重要的问题0涉及各个领域,如形状识别,分析0如社交网络,生物学等。它涉及到枚举0数据图形与查询图形相对应。最佳解决方案0这个问题的已知解决方案基于回溯。它们0探索大量的搜索空间,导致了处理成本的增加0尤其是在大规模数据的情况下。0为了减少搜索时间和空间复杂度,0子图同构搜索,我们提出使用压缩图0压缩。在我们的方法中,子图同构搜索是0在不解压缩的情况下进行搜索。0图的压缩是通过将顶点分组成超级0Chemseddine Nabti Liris实验室v0顶点。这个概念在图论中被称为0模块化。它用于生成图的树形表示,该表示0突出显示具有相同邻居的节点组。通过这种0通过压缩,我们可以大大减少搜索空间0从而节省了大量的处理时间。0我们还提出了一种新的顶点表示方法0图形,简化了搜索空间的过滤。这种新机制0称为“紧凑邻域索引(CNI)”,它编码了邻居信息0围绕一个顶点的整数。这种邻居编码简化了0时间复杂度从立方到平方。这是相当大的0用于大规模数据的0我们还提出了一种迭代过滤算法,它基于0为了确保对CNI的全局剪枝0搜索。0我们在多个数据集上评估了我们的方法,并对其进行了0与现有算法进行了比较。0vi Liris实验室Chemseddine Nabti0图表清单01.1 分层模型 . . . . . . . . . . . . . . . . . . . . . . . . . . 201.2 网络模型[39] . . . . . . . . . . . . . . . . . . . . . . . . . . 201.3 查询数据图 . . . . . . . . . . . . . . . . . . . . . . . . 301.4 图同构问题[54]。02.1 图的示例。02.2 引出和部分子图的示例。02.3 子图同构搜索。02.4 搜索树的部分构造。02.5 最先进的方法。02.6 NDS距离[55]的示例。02.7 核心-森林-叶子分解[6]。02.8 CPI的示例[6]。02.9 运行示例[6]。02.10 Trinity上的子图同构搜索。03.1 使用[12]进行图压缩。03.2使用模块化分解进行压缩步骤。S:串行模块。P:并行模块。N:邻域模块[31]。03.3 图及其压缩的示例[44]。03.4 提出框架的架构。03.5 运行示例的压缩步骤。03.6 第1步(超顶点选择)的流程图。03.7 第2步(子图搜索)的流程图。03.8 运行示例的超顶点选择阶段。0Chemseddine Nabti Liris实验室第七页4.8Time performance on the small dataset DANIO-RERIO (varying|Σ| and the label distribution). . . . . . . . . . . . . . . . . . . . .1054.9Scalability testing (varying |V (Q)|). . . . . . . . . . . . . . . . . .1064.10 Scalability testing on large graphs (varying |V (Q)|). . . . . . . . .1074.11 Scalability testing (varying |V (G)|).. . . . . . . . . . . . . . . . .107viiiLiris laboratoryChemseddine Nabti0图表清单03.9 模块的树表示[31]。03.10 运行示例的子图搜索阶段。03.11 AIDS数据集。03.12 NASA数据集。03.13 人类数据集。03.14 路径和团查询。03.15 WebGoogle数据集。03.16 Wiki-talk数据集。03.17 专利引用数据集。03.18 LiveJournal数据集。03.19 Pokec数据集。03.20 Orkut数据集。04.1 运行示例。04.2 运行示例上的MND过滤(修剪不匹配查询标签的顶点)。04.3 不必要的NLF过滤。04.4 使用两种不同的顶点解析顺序进行NLF过滤。04.5 查询图和数据图的CNIs。04.6 运行示例的过滤迭代。04.7 小数据集上的时间性能(变化 | V(Q)|)。结果以对数刻度表示。List of Tables3.1Graph Dataset Characteristics. avg|V |: average number of vertices.avg|E|: average number of edges.. . . . . . . . . . . . . . . . . .633.2width=17cm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .644.1Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .854.2Graph Dataset Characteristics.. . . . . . . . . . . . . . . . . . .101Chemseddine NabtiLiris laboratoryixContentsAbstractiiiR´esum´evList of FiguresviiList of Tablesix1Introduction11.1Thesis Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61.2Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . .72Subgraph Isomorphism search92.1Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.2Querying graph data. . . . . . . . . . . . . . . . . . . . . . . . .142.3Subgraph isomorphism search over a single large data graph. .172.4Existing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . .202.4.1Ullmann’s algorithm. . . . . . . . . . . . . . . . . . . . .222.4.2VF2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .232.4.3SPath and GraphQL . . . . . . . . . . . . . . . . . . . . . .242.4.4GADDI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.4.5QuickSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .272.4.6Turbo-iso . . . . . . . . . . . . . . . . . . . . . . . . . . . .292.4.7CFL-match . . . . . . . . . . . . . . . . . . . . . . . . . . .302.4.8Other Methods and techniques. . . . . . . . . . . . . . .332.5Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35Chemseddine NabtiLiris laboratoryxiCONTENTS2.6Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .393SUBGRAPH ISOMORPHISM SEARCH ON COMPRESSED GRAPHS413.1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .433.2Graph Compression . . . . . . . . . . . . . . . . . . . . . . . . . .433.3Compress and Search . . . . . . . . . . . . . . . . . . . . . . . . .513.3.1Candidate Supervertex Selection. . . . . . . . . . . . . .533.3.2Subgraph Search. . . . . . . . . . . . . . . . . . . . . . .573.4Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . .603.4.1Datasets. . . . . . . . . . . . . . . . . . . . . . . . . . . .613.4.2Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .653.4.3Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . .663.5Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7304紧凑的邻域索引用于大规模图中的子图查询7504.1动机...7704.2我们的方法...8404.2.1紧凑的邻域索引(CNI)...8504.2.2定理1的证明...8704.3引理3的证明概述...8904.3.1迭代局部全局过滤算法(ILGF)...8904.3.2子图搜索...9404.3.3扩展到更大的图...9504.4实验...9704.4.1数据集...9704.4.2结果...10104.5 cni ( v ) at ( k > 1)-hops邻域...10304.6结论...10805结论和展望11105.1结论...11105.2展望...1140出版物列表1170xii Liris实验室Chemseddine Nabti0目录0参考文献1190Chemseddine Nabti Liris实验室xiii0第1章:引言0目录01.1论文范围...601.2论文组织...70图是由一组顶点和一组边组成的数据结构0其中一条边连接两个顶点。图是一种形式化的有效方式0用于解决问题和表示对象。它们用于表示复杂和0在各个领域中的异构链接数据。使用图,顶点表示0对象和边表示这些对象之间的关系。0图非常灵活,它们允许添加新的关系类型,新的0现有结构中添加新的顶点而不干扰现有查询和应用程序0功能。这就是为什么图在数据建模中被广泛使用的原因0特别是对于大规模数据而言。然而,这并不是新的,第一个数据建模工具0是基于图的。分层数据模型是第一个数据建模工具0可以创建。首次出现于1966年,作为一种改进的通用文件处理0系统。主要的改进是可以创建关系0数据模型中的信息之间的联系是由图形保证的。主要的0分层数据模型的特点是树状结构。它由0由链接连接在一起的记录集合组成的模型。0父子关系。图1.1显示了分层数据的一个示例0模型。0Chemseddine Nabti Liris实验室10介绍0图1.1:分层模型0图1.2:网络模型[39]0作为分层模型的扩展,引入了网络模型。070年代由Charles Bachman最初发明,它作为一种新的数据模型出现。0它被构思为一种灵活的表示对象及其关系的方式。0它允许横向连接,并使用图结构。基本上,当0分层数据库模型将数据结构化为记录树,每个记录都有一个0记录具有一个父记录和多个子记录,网络模型允许0每个记录都有多个父记录和子记录,形成一个广义的02 Liris实验室Chemseddine Nabti
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 探索AVL树算法:以Faculdade Senac Porto Alegre实践为例
- 小学语文教学新工具:创新黑板设计解析
- Minecraft服务器管理新插件ServerForms发布
- MATLAB基因网络模型代码实现及开源分享
- 全方位技术项目源码合集:***报名系统
- Phalcon框架实战案例分析
- MATLAB与Python结合实现短期电力负荷预测的DAT300项目解析
- 市场营销教学专用查询装置设计方案
- 随身WiFi高通210 MS8909设备的Root引导文件破解攻略
- 实现服务器端级联:modella与leveldb适配器的应用
- Oracle Linux安装必备依赖包清单与步骤
- Shyer项目:寻找喜欢的聊天伙伴
- MEAN堆栈入门项目: postings-app
- 在线WPS办公功能全接触及应用示例
- 新型带储订盒订书机设计文档
- VB多媒体教学演示系统源代码及技术项目资源大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功