多重图查询和挖掘的关键问题

多重图的查询与挖掘信息是解放。知识就是力量.由蒙彼利埃大学颁发研究生院编写信息，结构和系统（I2S），LIRMM研究单位，ADVANSE团队。专业： 计算机科学维贾伊·英加拉利辩护vijay@lirmm.fr于2017年2月27日在陪审团面前辩护，陪审团由以下人员组成BrunoCremilleux教授卡昂大学总统CélineRobardet教授里昂大学审稿AndreaTagarelli二当家教授卡拉布里亚大学审稿先生克里斯托夫·保罗博士法国国家科学研究中心，蒙彼利埃考官PascalPoncelet教授蒙彼利埃大学主任DinoIencoCRIRSTEA，蒙彼利埃联合主任摘要随着数据和信息的不断增长，提取正确的知识已成为一个真正的挑战。此外，高级应用程序需要分析复杂和相互关联的数据，这些数据无法使用命题表示进行充分描述。 图表示是知识提取社区的极大兴趣，因为图是通用的数据结构，是最通用的数据表示形式之一。在几类图中，多重图最近一直吸引着人们的注意力，这要归功于它们的固有属性，即通过允许实体之间的丰富而复杂的关系来简洁地表示实体本论文的重点是精简为两个主题的知识提取：一个是知识检索，其中的重点是在多图的子图查询匹配方面，另一个是知识发现，其中的重点是在多图的频繁模式挖掘问题。本文在查询匹配和数据挖掘领域做出了三个主要贡献第一个贡献涉及在多重图中查询子图以产生同构匹配，并且这个问题在遥感、社交网络、生物信息学和化学信息学领域中找到潜在的应用。 第二个贡献，它集中在知识图，处理查询子图的RDF多重图，产生同态匹配。在这两个贡献，有效的索引结构，捕获多边缘信息。所提出的查询匹配过程已经过仔细优化，以提高时间性能，所提出的算法保证了鲁棒的性能。第三个贡献是在数据挖掘领域，提出了一个有效的多重图频繁模式挖掘算法我们观察到多重图在探索搜索空间时带来了挑战，因此引入了新的优化技术和启发式搜索方法来快速遍历搜索空间。对于每一种方法，通过与现有的最先进的方法进行比较，以验证所提出的方法的性能和正确性进行了广泛的实验分析最后，对一个遥感数据集进行了案例分析，将数据集建模为一个多重图，并采用挖掘和查询匹配过程来发现一些有用的知识。我ii简历由于大量的数据和重要的数据，以及复杂的数据和可靠的内部数据，因此，对相关 数 据 的 提 取 仍 然 是 一 种 可靠 的方 法 Les graphes offrent actuellement unsupport de représentation efficace pour représenter ces données.Parmi lesapprochesexistantes，lesmulti-graphesontmontréquepouvoird'expressionétaitparticulièrementadapt épourmanipulations des données complex possédant de nombreuxtypes de relations entre elles.这是多重图的两个主要方面：对多重图中的子图的她提出三个建议在le domaines du requêtage et de la fouille de données.第一个贡献这种方法可以应用于卫星图像分析或社会网络等众多应用领域在第二部分中，我们研究了连通图，并解决了多重图RDF中图的同态问题。在这两篇文章中，我们提出了新的索引技术，以有效地表示多重图中的信息。La rescherche des sousgraphestire avantage de ces nouveaux index et différentes explanistiques etoptimisations sont également proposées pour garantir de bonnes performanceslors de第二个贡献是然而，从研究的角度来看，图形中的图案研究是一个困难的问题。 Pour parcourir effi- cacement l'espacederechercheencoreplusvolumineuxpourlesmultigraphes ， nous proposons de nouvelles techniques et methodes pour le extensierefficement notam- ment en éliminant des candidats ointectant à l'avance les motifs nonféquents.Pourchacunedecesproposalsdenombreusesexperimentationssontréaliséespour valider à la fois leurs performance et exactudes en les comparantavec les approaches existantes.最后，我们提出了一项关于卫星成像问题的研究，该研究采用了多功能和多功能的形式，以应用新的实用知识所允许的测量方法IIIiv确认首先，我要感谢我的导师教授。Pascal Poncelet和共同主管Dr.感谢迪诺·伊恩科给我提供了一个机会，让我和他们一起完成这项博士研究正是他们对我的巨大支持和信任使我的论文成为可能。攻读博士学位是一场研究的奥德赛，有几个波峰和波谷，希望看到隧道尽头的光明。“我们几乎看到了光明，Vijay”，每当我们即将完成一项特定的任务时，迪诺都会每当我陷入问题的细节而迷失方向时，帕斯卡为我提供了正确的方向，揭开了隐藏的一般问题。每当我陷入问题的细节时，与帕斯卡和迪诺的会议室讨论都会及时产生见解Pascal和Dino在整个博士期间都我很感激能成为LIRMM充满活力的Advanse团队的一员，在那里我遇到了一些很棒的人。我从同事那里得到的宝贵建议在很多方面塑造了我我与他们进行的讨论和辩论几乎不会像我们分享的幽默时刻一样消失我也感谢在我读博士期间与我交朋友的LIRMM的许多人;我真的和他们一起度过了许多难忘的时刻，我将珍惜很长一段时间。我还要感谢MTD实验室的工作人员和同事，我有时也在那里工作。我要感谢所有负责我在LIRMM，MTD和蒙彼利埃大学博士学位的行政方面的人我特别感谢尼古拉斯·塞鲁里耶先生和盖莱恩·马蒂诺蒂女士，他们为我克服所有官僚主义我还对NUMEV1项目表示感谢，该项目使我能够以慷慨资助的形式进行这项研究，并为我参加各种会议以及几个夏季/冬季学校提供了急需的支持我也很荣幸在实验室外结交了许多朋友，并感谢他们与我同甘共苦。我的许多朋友住在世界各地，他们一直以来都很支持我，我感谢他们对我的信任，我很高兴能和他们保持联系。1个Labex NUMEV（NUMEV，ANR-10-LABX-20）。vvi最后但并非最不重要的是，我非常感谢我的家人，虽然他们住在遥远的印度，但一直以来都把我关在身边尤其是我的父亲，对我的博士研究感到非常兴奋作为一名哲学教授，他对计算机科学领域的浓厚兴趣为我在博士期间进行的许多有趣的讨论铺平了道路我欠我的父亲，在论文中的任何哲学语气另一方面，我妈妈是个很好的人。我从来没有觉得远离她，因为她总是拥抱我，通过所有的情况下，我不得不面对这里。我们频繁的谈话使我感到温暖，足以使我坚持下去。我的哥哥和他的妻子是一对可爱的夫妇，我欠他们很多，因为他们让我在博士期间保持理智。很多时候，我们谈论工作，很多时候，我们谈论生活。我很高兴有一个兄弟，他是我的好朋友，我可以和他分享一切我还要感谢所有在不同时期直接或间接参与这一旅程的人Vijay IngalalliMontpellier，2017年内容摘要i鸣谢iv图表. ix表xii上下文11介绍31.1知识提取原则31.1.1知识检索41.1.2知识发现51.2管理和挖掘图形数据71.3捐款101.4第11章组织结构2基金会152.1图，多重图152.2图形匹配172.3图形数据库，索引192.4关于查询图202.5图形数据挖掘212.5.1FSM22的基础知识2.5.2密克罗尼西亚联邦办法23VIIviii我在多重图中查询匹配27第一部分概述283Multigraphs中的子图查询匹配313.1一.导言. 313.2相关工作323.3问题定义343.4SuMGra36的概述3.5索引373.5.1离线索引构建383.6子图查询处理413.6.1查询顶点排序423.6.2选择初始查询顶点433.6.3子图搜索433.7实验评价473.7.1数据集描述473.7.2SuMGra50的性能3.8摘要574查询RDF数据594.1导言. 594.2相关工作614.3背景和资料624.3.1RDF数据624.3.2SPARQL查询644.3.3采用多重图同态的SPARQL查询。674.4AMBER：一个SPARQL查询引擎684.5指数建筑694.5.1属性索引694.5.2顶点签名索引704.5.3顶点邻域指数724.6查询匹配程序734.6.1顶点级处理754.6.2处理附属顶点764.6.3任意查询处理784.7实验评价814.7.1实验装置824.7.2第82代4.7.3与RDF引擎的834.8摘要88第一部分结论. 90目录.ixII挖掘多重图93第一部分概述945Multigraphs中的频繁模式挖掘5.1一、导言. 975.2相关工作985.3问题和定义995.4MuGRAM：一个频繁模式挖掘算法5.4.1多边缘表示和模式枚举1015.4.2MuGraM102概述5.4.3DFS遍历跨越的搜索空间1035.4.4发现频繁模式1045.4.5图案延伸1055.4.6支持多重图的计算1075.5实验评价1145.5.1定量分析：时间绩效评估1145.5.2定性分析1185.6摘要121第一部分结论122案例研究1246遥感数据的知识提取摘要1317总结和未来方向133论文摘要133未来工程135参考书目139x内容图目录1.1数据库中的知识发现（KDD）61.2一个多重图9的实例3.1子图嵌入的示例353.2多重图36的等价表示3.3数据顶点的邻域索引423.4数据集的特征473.5查询DBLP数据集523.6查询BIOGRID数据集3.7查询FLICKR数据集543.8查询YOUTUBE数据集553.9查询DBPEDIA数据集553.10 通过改变概要字段查询DBLP数据集的时间563.11 查询合成数据集574.1n-triple和multigraph representation中的RDF数据634.2在n-triple和multigraph representation中的SPARQL查询664.3AMB ER框架684.4邻域索引结构724.5查询分解744.6多重图中的星结构764.7DBPEDIA数据集的星形查询评估844.8DBPEDIA数据集的复杂形状查询评估854.9YAGO数据集86的星形查询评估4.10 YAGO数据集86的复杂形状查询评估4.11 LUBM 100数据集的星形查询评估874.12 LUBM 100数据集的复杂形状查询评估875.1数据多重图的多重图模式985.2图案的嵌入1005.3用于频繁种子集合的搜索空间1035.4模式和自守分组的各种可能的扩展。1065.5Amazon和DBLP数据集的时间性能1165.6Citeseer和Microsoft数据集的时间性能117XiXII图目录5.7时间性能与DBLP数据集的输出模式数。. 1185.8AUCS数据集的一些有趣模式1195.9ATN数据集119的一些有趣模式5.10 MRM数据集120的一些有趣模式6.1Basse Plaine de l'Aude（BPA）128的卫星图像6.2BPA数据集的两种常见模式1296.3在原始BPA图像130中嵌入频繁模式6.4缩放原始图像以研究所提取的知识130表的列表1.1数据、信息和知识检索的比较53.1数据图的顶点签名383.2数据顶点概要393.3数据集统计483.4索引构造的执行时间和内存使用514.1字典查找表674.2顶点签名和相应的概要704.3RDF数据集统计824.4索引建设时间835.1图形数据集的属性115XIIIXIV表的列表上下文我们在生活中失去的生命在哪里我们在知识中失去的智慧在哪里我们在信息中丢失的内识在哪里- T.S.艾略特，《岩石》，1934年2表格清单CH aPTE r介绍在这一章中，我们简要介绍了知识检索和发现的概念。然后，我们讨论了管理图数据以及挖掘操作和探索多重图的重要性-一类通用的图。最后，我们讨论了论文的贡献和组织。11.1知识抽取知识提取处理从结构化（关系数据库）、半结构化（图、树、XML）或非结构化（文本、文档、图像）数据源中发现知识所发现的知识需要是机器可读和机器可解释的格式，并且必须以明确定义其含义的方式表示知识，并便于推理[Un-10 uen等人， 2012年]。首先，必须理解数据、信息和知识含义的微妙之处，如[Bellinger et al.，2004年]。数据是某些变量的一组值，可以是定性的或定量的。从各个领域收集的数据通常是原始的，未经处理的，本身可能没有意义。信息是经过处理后变得有用的数据，它通过一种关系联系的方式被赋予意义，并能提供问题的答案一个简单的例子是关系数据库或图形数据库。知识1这项工作由Labex NUMEV（NUMEV，ANR-10-LABX-20）资助。314第1章介绍是对信息的理解，通过经验或发现获得，以便可以使用其意图由于知识抽取的概念是非常通用的，本文集中在两个广泛研究的知识抽取过程的主题：（i）知识检索，从数据中检索特定的知识，其中的数据往往可能被组织成一个数据库的领域;（ii）知识发现，从数据中发现的知识，迄今未知的1.1.1知识检索知识检索（KR）系统是一种先进的系统，能够检索知识，而不仅仅是信息检索（IR）系统中观察到的信息在IR系统中，一旦信息被检索，就必须经历从检索到的信息中找到意义或知识的艰苦工作知识检索系统的目标是通过改进搜索和表示来减轻这些过程的负担 KR系统关注于知识层面，因此，我们需要研究如何提取、表示和使用数据和信息中的知识[Bellinger等人，2004年]。信息检索系统通过索引来组织数据和文档，而知识检索系统通过指示这些文档中的元素之间的连接来组织信息此外，知识检索系统以结构化的方式向用户提供知识，因为它们关注语义和更好的信息组织 这种KR系统将被高级和专家用户用于解决知识寻求的挑战性问题[Yao等人， 2007年]。Web的发展和演变带来了大量的机会，使知识检索系统成为支持未来Web的必要条件。随着时间的推移，其他领域，如遥感，生物信息学，化学，也成为知识检索系统感兴趣的领域许多研究工作已经提出[Kamel和Quintana，1990，Martin和Eklund，2000，Yao，2002]，涵盖了不同的方面，并为我们提供了深入的知识检索的发展。由于知识检索的任务不仅涉及收集有用的信息，而且还需要用其他信息来丰富它以获得知识，因此这个过程是相当具有挑战性的。在表1.1中，知识检索的显著特征与数据和信息检索进行了比较 从检索模型的角度来看，知识检索系统主要关注语义和知识组织。此外，知识检索系统通过允许知识结构之间的连接来组织知识，而信息检索系统通过索引来组织数据。知识检索也是基于部分匹配（近似匹配）和最佳匹配（精确匹配）。