支持动态图数据的子图查询方法

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。     

基于自动机XML正则路径表达式查询研究

基于自动机正则路径表达式查询技术是半结构化数据模式下XML查询研究领域颇有价值的方法。许多研究方法对含有“//”操作符和“*”通配符复杂正则路径重写都会产生大量中间路径。设计了处理XML正则路径查询高效方法——CSAS,利用对象交换模型(OEM)作为XML数据模型,有限自动机作为查询模型,提出裁剪XMLSchema转化的自动机片断作为重写自动机来重写“//”和“*”符号的重写技术;利用剪枝技术、谓词处理后移策略实现查询优化。实验证明,CSAS方法是一种高效的XML正则路径表达式查询方法。     

基于视图的正则路径查询重写

正则路径查询的重写是实现XML查询重写优化的基础。通过比较正则路径视图和正则路径查询的结构信息,分析了两者之间进行映射应满足的条件,描述了正则路径视图到正则路径查询的映射和基于有穷自动机的映射过滤算法,并从理论上阐明了两个算法的重写等价性。借助于此两个算法,能够极大地减少需要求解的映射数目和提高正则路径查询处理的效率。     

结构化加密图的最短路径查询

随着云计算的快速发展, 数据用户将大量图数据外包给云以节约存储和管理成本。然而, 外包数据的安全隐私问题是云计算面临的一大挑战。由于云是半诚实的, 为保护敏感信息的隐私安全, 数据拥有者希望在将图数据外包给云服务器之前对其加密, 同时保留对加密的图数据进行查询和处理的能力。最短路径查询查找图中给定两节点之间的最短路径, 是图应用中最基础的查询类型之一。目前已有许多研究者提出一系列高效的方案, 以支持加密图上近似或精确最短距离查询、约束最短距离查询和 top-k 最近关键字查询, 但支持最短路径查询的方案较少, 且已有方案的存储与时间开销较大。本文提出一种支持在加密图上进行两节点间最短路径查询的结构化加密图方案。在本方案中, 我们基于 2-Hop 标签技术构造支持有向图上最短路径查询的标签索引并加密, 然后将加密的标签外包给云服务器。 利用改进的保序编码算法编码距离值, 实现加法运算和值的比较, 提高最短路径查询的效率。在查询阶段, 通过递归式地计算两节点间最短路径上的第一条边和最后一条边, 最终输出完整的最短路径。安全性和性能分析证明本文方案是安全有效的, 能以较小的存储和较高的查询效率实现两节点间的最短路径查询并保护图数据的隐私。     

基于正则路径表达式的XML查询优化技术研究

支持正则路径表达式的查询技术,被认为是半结构化数据模式下的XML查询研究领域中一种颇具有研究价值的XMI。查询计算方法。本文对基于正则路径表达式的XML查询计算方法及其特点进行了分析,在此基础上详尽地介绍了目前所提出的各种查询优化技术,最后讨论了XML查询优化技术研究中存在的问题以及今后的研究方向。     

基于路径索引的密集邻域图数据查询方法研究

随着社交网络、生物信息以及web挖掘等应用的不断发展,图结构数据的存储和查询处理越来越得到重视。但是,针对顶点邻域非常密集的场合,如何提高此类顶点的查询效率,现有的研究相对较少。论文在分析了顶点密集领域数据的特点后,提出了一种对顶点密集邻域建立路径索引的策略,有效地解决了此类查询的效率。首先分析顶点密集的邻域的查询模式,并在这些模式上建立路径索引,然后采用B 树方法,对路径索引的存储、更新和查找方法进行了设计实现,最后,采用图数据库NEO4J为基础,对路径索引存储空间和查询性能进行了测试,测试表明,虽然路径索引会占用存储空间,但是能够提高特定的查询处理的性能。     

面向大规模图数据的分布式可达性索引与查询策略

针对构建大规模图数据可达性索引时的构建时间长、存储代价高和响应时间长等问题,提出一种分布式可达性索引与查询策略(DRIQ)。在不破坏原图中节点可达性的前提下,将大规模图划分成若干小规模子图,并对每个子图分布式并行地创建可达性索引,从而提高可达性索引创建效率。给出保持图划分后各子图内节点间以及子图间节点可达性的方法,从而保证基于DRIQ进行可达性查询的正确性。实验结果表明,与传统可达性查询方法相比,该策略具有高效性和可扩展性。     

结构化加密图数据的Top-H跳节点查询

为了保护外包数据的隐私,用户通常需要对数据加密后再存储到云服务器.但数据加密后,对密文数据的查询与处理变得极为困难. 2010年, Kamara等提出结构化加密的概念,可以实现各种类型数据的高效查询,包括文本、矩阵及图数据等.利用结构化加密的思想,本文提出第一个结构化加密图数据的top-H跳节点查询方法.现有的H跳查询方案主要通过2-Hop索引计算查询节点之间的跳数来判断它们之间的可达性,当节点数达到十万或百万级时,构建2-Hop索引的计算和存储开销都非常大.本文提出的方案在满足可达性判断的同时极大地降低了存储开销,同时提高了查询效率,还实现了更加丰富的H跳范围查询.本方案采用了结构化加密中可链接(chainable)的思想,实现邻居节点的迭代查询.同时,根据用户指定的跳数(H)获取满足条件的top-H跳节点.安全性分析表明本方案满足CQA2安全.在真实数据集上的测试结果表明,本方案比已有方案更加高效.     

基于关键词的RDF数据图查询模型研究

随着语义网数据的海量涌现,人们更加关注RDF图的数据查询效率,通过关键词匹配直接查询RDF数据图成为一个研究热点。针对关键词查询中普遍存在的结果冗余与偏离等问题,提出了一种基于关键词的RDF数据图查询模型。该模型首先采用提出的基于迭代的图查询算法(ISGR)对所查询关键词进行子图匹配,得到唯一且最大的结果子图集合;然后根据关键词图与结果子图之间的结构信息,利用统计语言模型,给出了一种结果子图排序方法(SimLM)。对比实验表明,提出的查询模型及排序方法在一致性和相关性方面的性能优于传统模型。     

基于信息熵的子图匹配算法

子图查询是指输入一个图数据库和查询子图,输出图数据库中包含查询子图的图集合,它广泛应用于社会网、生物网和信息网的查询应用中。目前的子图查询算法大多采用静态消耗测算模式,此类测算模式在图中点数和连接边数呈指数分布时,会在少数节点上花费较多时间遍历其邻节点,导致查询算法效率低下。根据信息熵在信息度量中的作用,将条件信息熵作为启发式匹配的依据,提出了基于信息熵的子图匹配算法。实验表明,基于信息熵的子图匹配算法具有更高的查询效率,且在指数分布的数据集上效果更明显。     

高性能正则表达式匹配算法评估

为对现有的高性能正则表达式匹配算法进行综合比较与分析,实现诸如DFA、D2FA、CD2FA、mDFA及XFA等最新算法,采用Snort规则集综合评估这些算法的存储空间和匹配时间。实验结果表明,在存储空间方面,与mDFA相比,XFA的存储空间减少84.9%~89.9%;在匹配效率方面,与mDFA相比,XFA的匹配时间增加了38.9%~174.6%;XFA在存储空间和匹配效率上具有良好的可伸缩性,即当规则数增加到8倍时,mDFA的存储空间增长了64倍,而XFA的存储空间仅增加了16倍,匹配时间仅增加了61.3%。     

基于双索引的子图查询算法

传统的子图查询算法大多只在图数据库上进行一次挖掘算法,即在图数据库上建立稳定的数据库索引后将不再对索引进行更新.随着查询兴趣的改变或数据库的频繁更新,原有的数据库索引将不再能提供有用的信息来减少查询过程中候选图的数量.为此,提出一种双索引的子图查询算法,同时在数据库和查询流上挖掘频繁子图并建立索引.子图查询和查询流索引的建立同步进行,即使查询兴趣改变,查询流索引也能自适应地更新索引信息来优化查询效率.针对数据库的频繁更新,查询流索引已提供实时的有效信息,数据库索引无需重新建立.实验结果表明,双索引的结合能有效提高查询子图的处理效率.     

融合启发式和Boosting的子图匹配基数估计方法

由于在建模关联信息方面具备天然优势,图数据已在社交网络、知识表示等方面被广泛运用.但是相较于传统的关系型数据库系统,图数据管理中的以子图匹配为代表的一系列基础操作仍有进一步优化的空间.在一个完善的图数据库系统中,为实现多个子图匹配任务的优化调度,往往需要对每个任务的代价,尤其是匹配结果的基数进行准确预估.然而,现有的子...     

自动机算法在文本不精确匹配中的应用

论文从实用的角度,着重研究了有限自动机算法在文本的不精确匹配中的应用,提出了一种用于中文精确匹配的自动机的构建思想,两种用于中文同音字匹配的自动机的构建思想,以及利用自动机的原理去除无用字符对文本匹配的干扰的方法。编程实现了上述三种自动机算法并对其作了测试,给出了三种算法各自的性能测试数据。     

基于最小生成树的图数据库索引算法

对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.     

动态图模式匹配技术综述

随着大数据时代的到来,多源异构数据的快速增长已经成为了一个开放性问题,这些数据之间的内在关联通常可以用图数据的形式来表现.然而在实际应用中,例如网络安全分析和社交网络舆情分析,描述实体对象之间关系的图数据的结构和内容往往不是固定不变的,图数据的结构以及节点和边的属性会随着时间的推移发生更新变化.因此,如何在动态更新的图数据中进行高效的查询、匹配是目前研究的热点问题,也涌现了许多优秀的研究工作.本文从关键技术、代表性算法和性能评价方面对动态图匹配技术的研究进展进行了综述.最后对动态图匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望.