基于分区过滤-增量验证的图编辑相似查询

图编辑相似查询问题是指从图集G中查询出所有与查询图q的图编辑距离(Graph Edit Distance,GED)在给定阈值τ内的数据图.由于GED计算是NP-Hard问题,现有的研究多采用过滤-验证框架进行查询,对未能过滤掉的图采用A*-GED算法验证.本文提出了分区过滤-增量验证框架PFIV来处理图相似查询问题,在增强过滤效果的同时,还能加快验证速度.首先,在过滤阶段提出了2种分区策略,用来加快分区速度.(1)映射顶点顺序策略:在分区过程中,基于图的特征信息和结构信息提出分区时顶点的映射顺序,尽快过滤掉不相似的图,减少计算量;(2)分区结束条件策略:在分区过程中,设置分区结束条件,加快不相似图的过滤速度.其次,在验证阶段提出了增量验证策略,利用过滤阶段保留的映射结果,设计状态空间树,进行增量验证,加快验证阶段的计算.最后,通过大量实验验证了PFIV能够高效地处理图编辑相似查询问题,对比原有算法,查询效率提高8%~17%,并证明了所提出策略的有效性.

异构网络中关联实体识别模型及增量式验证算法研究

利用关联实体识别技术可以对异构网络中主题相关的实体进行检测并整合,更好地帮助用户理解搜索目标.然而,目前关联实体识别技术考虑的因素较为单一、对识别结果缺乏验证而影响识别准确性.文中提出了一种两阶段的关联实体识别模型,充分考虑了实体的模式特征与属性特征.此外,提出了一种增量式验证算法,基于迭代对识别结果进行增量式的验证并修正,以保证结果的准确性.通过实验验证了文中所提出的关键技术的可行性和有效性.

基于层次状态机的方面化特征模块的增量式验证

方面化特征模块(AFM)是最新提出的软件产品线(SPL)编程范式,能解决现有SPL编程范式存在的问题,但由于AFM范式同时存在模块的并发组合和顺序组合,现有的组合验证技术和模块化模型检验技术并不适用于AFM程序的验证,且目前还未见到针对AFM的验证方法,这制约了AFM范式的应用.文中首次为AFM范式建立了形式化模型,并基于此模型提出一种AFM程序的增量式的验证方法.该方法可以从一个小规模的AFM程序的验证开始,以后每次只添加对新组合的AFM模块的验证,因此可避免直接验证大型AFM程序时可能由于模型的规模太大而无法验证的问题.

Native XML数据库的增量式验证

针对native XML数据库的更新操作,提出了一种增量式验证方法,确保更新后的XML数据仍然符合指定模式的约束.基于正则树文法理论,形式化地描述XML模式语言,给出DTD在native XML数据库中的表示与存储格式.在更新操作过程中,首先检验期望结果是否满足模式的约束;只有在更新操作通过验证的前提下,原始XML数据才允许被修改.由于增量式验证仅涉及到直接受更新操作影响的XML数据片段.因此,与完全重新验证相比,增量式验证可以极大地提高XML数据更新效率.

零知识证明递归与复合技术研究综述

零知识证明作为一种重要的密码学协议,是实现数据安全流通的关键技术之一.其允许证明者向验证者证明某个断言的正确性,而又不泄露任何额外信息.零知识证明所描述的断言可划分成代数断言、非代数断言和复合断言,而递归与复合技术可以极大地提高零知识证明协议的性能并深入拓展其功能,是当前的研究热点.本文系统且全面地研究了零知识证明的递归与复合技术.首先,在针对代数断言的递归零知识证明方面,全面研究了关于内积关系的递归零知识证明协议,并从证明复杂度、通信复杂度、验证复杂度等角度对比分析了基于Pedersen承诺方案的内积论证协议.其次,在针对非代数断言的递归零知识证明方面,全面梳理了增量可验证计算方案与基于电路的证明系统组合这两种主流应用的研究现状,并对比分析了增量可验证计算方案的复杂度、关键技术及实现方案等.然后,在针对复合断言的复合零知识证明方面,从复杂度、启动阶段、关键模块等角度对比分析了承诺并证明的零知识证明协议.最后,给出了零知识证明递归与复合技术的未来研究方向.

基于GrO¨bner基方法的乘法器等价性验证

乘法器的等价性验证目前仍是大规模算术集成电路设计领域内的一大难题。本文利用逻辑门与多项式之间的对应关系,构建了乘法器的代数模型,将乘法器等价性验证问题转化成理想成员判定问题,然后再用计算机代数系统中的Gröbner基方法进行求解。提出了一种对乘法器结构进行切片后再采用增量式验证的新方法。在Linux平台上的计算机代数系统Mathematica上所做的实验结果也表明了该方法的有效性。

XML数据索引技术

对XML数据建立有效的索引,是左右XML数据处理性能的重要因素.深入地讨论了目前XML索引技术的研究现状,将XML索引技术分为两大类:节点记录类索引(本身还可以分为3个小的类型)和结构摘要类索引.根据XML数据查询处理效率以及XML数据修改对XML索引的要求,讨论了相关XML索引方法的优点和不足,并归结出XML索引后续研究的3个方向:XML结构信息的获取,路径信息的多维处理,数据修改合法性的有效支持,以及涉及能够同时有效满足XML查询和信息获取的索引.