检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

基于代数决策图的路由查找算法

计算机工程 2017年第3期34卷 99-104页

作者：徐周波胡魁常亮古天龙桂林电子科技大学广西可信软件重点实验室广西桂林541004

为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于AD... 详细信息

为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。

关键词：路由表路由查找代数决策图符号算法最长前缀匹配伪布尔函数

基于符号ADD和线性多分支程序的分类算法安全评估

在线全文

学校读者我要写书评

暂无评论

电子学报 2014年第5期42卷 940-947页

作者：古天龙何仲春常亮徐周波桂林电子科技大学广西可信软件重点实验室

分类算法是机器学习和数据分析中重要的算法.当需要对分类算法本身以及算法的输入数据进行隐私保护时,就出现了分类算法安全评估问题.针对现有的分类算法安全评估协议效率较低的问题,文章给出了一种基于代数决策图和线性多分支程序的解... 详细信息

分类算法是机器学习和数据分析中重要的算法.当需要对分类算法本身以及算法的输入数据进行隐私保护时,就出现了分类算法安全评估问题.针对现有的分类算法安全评估协议效率较低的问题,文章给出了一种基于代数决策图和线性多分支程序的解决方案.首先,设计了基于代数决策图的安全函数评估协议,用以安全评估决策函数;其次,引入了线性多分支程序的概念,用其对分类算法进行表示.最后,借助线性多分支程序和基于代数决策图的安全函数评估协议,给出了一个私有线性多分支程序的安全评估协议.对新的协议的正确性和安全性进行了分析和证明.实验数据表明,与原有的解决方案相比,新的协议在效率上有明显的提高.

关键词：安全评估分类算法代数决策图线性多分支程序

在线全文

学校读者我要写书评

暂无评论

基于概率转移矩阵的电路可靠性并行计算方法

小型微型计算机系统 2008年第2期29卷 357-360页

作者：王真江建慧沈君华史哲文同济大学嵌入式系统与服务计算教育部重点实验室上海201804 同济大学计算机科学与技术系上海201804

随着电路集成度的提高,软差错已经成为影响可靠性的关键因素.概率转移矩阵是一种用于估计软差错对电路影响的有效方法,它通过对门级电路建立概率模型来计算电路的可靠性.本文基于概率转移矩阵研究计算电路可靠性的并行方法,提出了一种... 详细信息

随着电路集成度的提高,软差错已经成为影响可靠性的关键因素.概率转移矩阵是一种用于估计软差错对电路影响的有效方法,它通过对门级电路建立概率模型来计算电路的可靠性.本文基于概率转移矩阵研究计算电路可靠性的并行方法,提出了一种电路分割算法,在对电路进行划分后,并行地计算各个模块的概率转移矩阵,再合成对应于整个电路的概率转移矩阵.其中,引入了代数决策图压缩矩阵存储空间.初步的实验结果表明,该并行算法可以有效地减少21.46%的平均时间开销.

关键词：转移矩阵代数决策图电路分割

WDM光网络中一种改进的波长转换器配置算法

在线全文

学校读者我要写书评

暂无评论

光通信研究 2009年第1期 15-17页

作者：仲留成蔡祥宝南京邮电大学光电工程学院江苏南京210003

文章在一种已有的"子图+ADD(代数决策图)"的波长转换器配置算法的基础上,提出了用优先配置最大度节点的启发式思想对该算法进行改进,得到了新的"子图+BDF(大度节点优先分配)"算法。通过对两种算法进行计算机仿真,得到的模拟结果显示新... 详细信息

文章在一种已有的"子图+ADD(代数决策图)"的波长转换器配置算法的基础上,提出了用优先配置最大度节点的启发式思想对该算法进行改进,得到了新的"子图+BDF(大度节点优先分配)"算法。通过对两种算法进行计算机仿真,得到的模拟结果显示新算法在保持结果准确的同时,有效降低了运算的时间复杂度。

关键词：波分复用波长转换器子图代数决策图

在线全文

学校读者我要写书评

暂无评论

基于属性基加密的电子病历隐私保护研究

基于属性基加密的电子病历隐私保护研究

作者：方颖桂林电子科技大学

学位级别：硕士

在智慧医疗中,电子病历(EMRs)会被频繁共享及使用,存在较大的数据窃取及隐私泄露风险。因此,EMRs的隐私保护是当下迫切需要解决的问题。密文策略属性基加密(CP-ABE)方案虽然可以同步实现EMRs的加密及访问控制,但大多数现存方案具有灵活... 详细信息

在智慧医疗中,电子病历(EMRs)会被频繁共享及使用,存在较大的数据窃取及隐私泄露风险。因此,EMRs的隐私保护是当下迫切需要解决的问题。密文策略属性基加密(CP-ABE)方案虽然可以同步实现EMRs的加密及访问控制,但大多数现存方案具有灵活性较差、仅支持布尔函数形式下的访问策略、用户一经授权便可解密获取文件的全部信息、只有加密方具备写入权限、解密方只具备读取权限等突出缺陷。因此,为了在共享EMRs时遵循“最小泄露原则”和“最小特权原则”,本文基于可搜索加密技术、代数决策图(ADD)和CP-ABE技术对EMRs的数据安全及隐私保护展开研究,提出了两种CP-ABE方案,主要的工作内容如下:(1)提出了基于密文策略属性基可搜索加密(CP-ABSE)的EMRs分类访问控制方案。首先,按照内容对EMRs进行分类,提出了一种面向EMRs的分类访问控制框架,支持数据使用者按需检索并访问EMRs中的信息,减轻信息检索的负担、降低系统开销。其次,基于分类访问控制框架,提出了新型ADD访问结构。同一个ADD访问结构可以表示多个访问策略,协助对多个共享文件进行加密和访问控制。第三,构造了基于CP-ABSE的EMRs分类访问控制算法,其密钥生成、陷门生成、搜索和解密阶段的时间复杂度为O(1)。最后,借助于理论分析证明了方案在抵抗选择明文攻击(CPA)、选择关键字攻击(CKA)和串谋攻击方面的安全性以及访问控制的灵活性,同时借助于对比实验证明了方案的高效性。(2)提出了读写可控的EMRs细粒度共享方案。首先,面向EMRs共享中的细粒度操作(只读、只写和读写)需求,提出了读写可控的新颖的访问控制系统框架。其次,改进了ADD访问结构,以支持细粒度访问控制的实现。第三,针对EMRs细粒度操作的需求,基于新型ADD访问结构提出了具备访问冲突解决能力且运算高效的CP-ABE方案。新方案能够避免多用户同步访问EMRs时的冲突,并且所含密钥生成算法、读操作算法、写操作算法的计算复杂度为O(1),均不受属性数量等因素制约。最后,结合理论分析与仿真实验,对方案的安全性、功能实现及性能表现进行了剖析,验证了方案设计的合理性和可行性。

关键词：电子病历访问控制可搜索加密代数决策图密文策略属性基加密

基于RDS技术的加权约束满足问题的符号算法研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于RDS技术的加权约束满足问题的符号算法研究

作者：杨新亮桂林电子科技大学

学位级别：硕士

计算机科学和人工智能领域中的许多问题都可以形式化为加权约束满足问题(WCSP),如地图着色、生产调度、产品配置、路由选择、物流规划、资源分配等问题。WCSP的求解目标是寻找一个使得违反约束总代价值最小的完全赋值。WCSP最基本的求... 详细信息

计算机科学和人工智能领域中的许多问题都可以形式化为加权约束满足问题(WCSP),如地图着色、生产调度、产品配置、路由选择、物流规划、资源分配等问题。WCSP的求解目标是寻找一个使得违反约束总代价值最小的完全赋值。WCSP最基本的求解方法是深度优先分支定界(DFBB)算法,Russian Doll Search(RDS)算法是通过修改DFBB算法框架得到的,其能有效提高搜索中的上下界,但RDS算法的求解效率取决于分解后得到的各个子问题的求解效率。结构化记录是避免重复搜索的有效技术之一,通过存储已求解信息,在搜索过程中判断是否可以重用已存储的求解信息,从而提高求解效率。由于在RDS算法求解中,一次只能处理一个约束值对,不能同时处理多个约束值对,而代数决策图(ADD)能高效的表示和以集合方式处理数据,且能减缓因问题规模过大造成的组合状态爆炸问题。因此本文对加权约束满足问题的RDS符号求解算法做了相关研究,主要工作包括:(1)给出改进RDS符号ADD求解算法。基于RDS算法思想,将DFBB算法中的一次搜索用m个子问题的相继搜索来替代。通过改进最多约束变量(MCV)的变量选择法,引入RDS变量来引导原问题的子问题分解,进而减少RDS算法中分解的子问题个数。为提高各个子问题的求解效率,用桶消元算法求解非RDS变量,减少DFBB算法处理的变量个数。为了进一步提高算法的效率,借助WCSP的符号ADD表示,给出WCSP的改进RDS符号ADD求解算法。(2)给出混合RDS符号ADD求解算法。通过研究RDS变量之间的约束关系,给出RDSV-T子问题分解方法;在子问题求解中,基于子问题之间的结构关系,存储当前子问题的结构化记录,便于在后续子问题求解中重用此结构化记录。借助WCSP的符号ADD表示,给出WCSP的混合RDS符号求解算法。(3)以随机生成的WCSP问题作为测试用例,结果表明,本文给出的符号算法优于RDS算法、EDAC-FC-DFBB算法和DFBB-ADD算法。

关键词：加权约束满足问题 RDS(Russian Doll Search) 桶消元算法结构化记录代数决策图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向图相似性搜索的图编辑距离算法研究

面向图相似性搜索的图编辑距离算法研究

作者：张军伟桂林电子科技大学

学位级别：硕士

图编辑距离（Graph Edit Distance,GED）是衡量两个图之间相似度的常用方法之一,且被广泛应用于图相似性搜索问题中。图编辑距离算法根据求得的代价值是否精确,主要分为两类:精确图编辑距离算法和近似图编辑距离算法。其中,精确图编辑... 详细信息

图编辑距离（Graph Edit Distance,GED）是衡量两个图之间相似度的常用方法之一,且被广泛应用于图相似性搜索问题中。图编辑距离算法根据求得的代价值是否精确,主要分为两类:精确图编辑距离算法和近似图编辑距离算法。其中,精确图编辑距离算法具有高时空复杂度的特点,主要用于图相似性搜索的验证阶段,以及作为判断近似图编辑距离算法求解精度的评价指标。然而,近似图编辑距离算法则可以在多项式时间内求得相应的解,且基于代价矩阵的近似图编辑距离算法具有较高的求解精度,并受到广泛研究。如何在保证高精确度的情况下提高代价矩阵的求解速度是研究者致力解决的问题。为了能够在多项式时间内求得图编辑距离,且保证近似算法求解的高精确度。因此,本文针对基于代价矩阵的近似图编辑距离算法进行研究,并将其应用到精确图编辑距离求解算法,以及图相似性搜索问题中,具体研究内容及成果如下所示:（1）针对现有的代价矩阵求解算法求解复杂度高,且无法直接对非方阵求解这一问题,本文提出了基于最小费用最大流问题的代价矩阵求解模型MCMF（Minimum Cost and Maximum Flow）,并在此基础上提出了一种简化的求解模型SMCMF（Simplified Minimum Cost and Maximum Flow）,且SMCMF模型具有通用性,尤其在求解非方阵的代价矩阵时性能优越。（2）针对SMCMF模型求解过程中,需要多次查找最短路径这一问题,本文提出一种预处理算法,该算法可在O（n）时间复杂度内求得一组最优匹配,对SMCMF模型进行预处理,以此减少最短路径的查找次数。同时,考虑到代数决策图（Algebraic Decision Diagram,ADD）可以有效改善伪布尔函数的表述能力,本文通过对SMCMF模型的伪布尔函数表述,提出了一种求解图编辑距离的符号ADD算法,称为ADD＿SMCMF算法。实验结果表明,在AIDS和Pub Chem数据集下,该算法在求解规模和时空性能上均优于AStar-BMao算法和FBP（Fast Bipartite）算法。（3）针对图相似性搜索问题中的验证算法AStar-BMao的下界求解复杂度高,以及其在图相似性搜索验证阶段需要对候选集中的每个图进行精确验证这一问题,本文引入ADD＿SMCMF求解思想,提出了一个新的下界求解算法BP-lb ,在此基础上结合改进的上下界求解方法,设计了一个用于图相似性搜索验证阶段的混合算法,称为BP-AStar算法。实验结果表明,该算法可以有效提升图相似性搜索验证阶段的验证效率。

关键词：图编辑距离最佳优先搜索代价矩阵最小费用最大流图相似性搜索下界代数决策图

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于增量的动态图模式匹配符号算法研究

基于增量的动态图模式匹配符号算法研究

作者：许昌胜桂林电子科技大学

学位级别：硕士

图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要... 详细信息

图作为一种可以描述事物之间关系的数据结构,在现实生活中应用广泛。子图匹配问题是图数据分析研究中的基本课题,有着十分重要的研究价值。但随着数据规模越来越大并且伴随实时变化,基于快照模式的动态图匹配算法无法满足实时响应的要求。基于辅助索引结构的动态图匹配算法能够在数据图发生变化时基于辅助结构的信息进行局部更新,获得比快照模式更快的求解效率。我们从两个方面对现有的动态图匹配技术进行优化,一方面优化辅助结构的候选集存储,通过为辅助结构添加更多的约束来优化辅助结构的存储空间,另一方面引入新的压缩技术,其中代数决策图是一种存储紧凑且易于操作的隐式存储结构,可以在相对较小的存储空间内实现大规模图的运算。本文引入代数决策图技术研究了动态图匹配符号算法以及考虑邻域约束解决现有算法中存在的信息冗余问题。主要研究成果和结论如下:(1)针对现有的动态图匹配算法数据图规模庞大,求解过程产生大量的内存消耗的问题,本文引入了代数决策图(Algebraic decision diagram,ADD)结构作为数据的表示方式,实现数据查询与更新的并行运算以及公共子图的共享存储,有效平衡了算法的空间和时间效率。(2)针对(1)中随着数据规模的快速增长,基于增量的有界模拟图匹配算法在更新过程中存在大量的重复计算,以及通过逐点扩展的方式确认受影响区域时的算法效率低下问题,本文基于ADD提出了一种新的编码方式来构建辅助索引结构ADD Index(AIndex),该辅助结构不仅可以压缩存储节点间的路径信息,同时可以利用ADD并行操作的特性,实现快速查找和维护;其次为了增量维护辅助结构和匹配结果,提出了适用于AIndex的增量更新算法。实验表明,与经典算法相比,优化了存储空间,求解性能有了明显提升。(3)为了降低动态子图匹配候选集空间和提高算法效率,针对目前最先进的增量子图同构匹配算法Symbi中的索引结构动态候选空间(Dynamic Candidate Space,DCS)中存在的信息冗余问题,引入邻域信息约束,提出了一种新的索引结构ZDCS,并提出了ZDCS的更新算法INCZDCS来动态维护ZDCS索引结构和匹配结果,进一步提出了动态图的增量子图匹配算法ZSymbi。最后,在真实数据集上与Symbi算法进行实验对比,结果表明ZSymbi有效缩减了计算空间并提高了算法的求解效率。

关键词：动态图匹配代数决策图符号技术邻域约束 ZSymbi

基于树分解技术的子图同构约束求解符号算法研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于树分解技术的子图同构约束求解符号算法研究

作者：吴量桂林电子科技大学

学位级别：硕士

子图同构作为图数据库中的一种查询技术,广泛应用于计算机视觉、社交网络分析及生物化学分析等领域。子图同构是NP完全问题,随着图规模的增大,算法的时间和空间复杂度呈指数增长。提升候选集的过滤技术、减少计算消耗的内存空间及降低... 详细信息

子图同构作为图数据库中的一种查询技术,广泛应用于计算机视觉、社交网络分析及生物化学分析等领域。子图同构是NP完全问题,随着图规模的增大,算法的时间和空间复杂度呈指数增长。提升候选集的过滤技术、减少计算消耗的内存空间及降低问题的求解规模是提高子图同构求解效率的有效途径。约束满足问题是求解组合优化问题的通用框架,利用约束传播和分解技术,能够起到删减匹配候选集和降低问题求解规模的作用,通过结合符号技术,利用代数决策图紧凑和易操作的优点,达到减少内存消耗和缓解组合爆炸的目的,同时符号操作具有并行性,能够有效加快计算速度。鉴于此,本文结合约束求解技术和符号技术对子图同构问题进行了研究,主要研究内容和结论如下:(1)为了描述子图同构问题,本文结合约束求解技术和符号技术给出了子图同构问题的一种新的约束符号模型,首先使用伪布尔函数对新模型的各要素进行形式化描述,然后使用ADD数据结构对模型进行压缩存储。与传统约束模型相比,该模型具有更好的适用性和紧凑性。(2)为了提高候选集的过滤效果,在子图同构的约束符号模型基础上,研究了全不同约束,给出了全不同约束的广义弧一致性符号算法,对值域进行了初步删减,并对算法进行了优化,提出了冗余边过滤算法和平凡SCC剪枝来加快计算速度。同时通过挖掘图的结构和属性信息,提出了邻域标签约束过滤算法,有效删减了值域。之后结合全不同约束的传播算法,进一步过滤了变量的值域。(3)为了缓解状态的组合爆炸,采取分治的思想,结合树分解算法对原CSP问题进行分解,得到多个子问题,限制了问题的求解规模,降低了求解难度。并对符号树分解算法进行了改进,通过引入优先函数提高了并行性,加快了计算速度,最后使用无回溯的树搜索算法求解和组合子问题以得到原问题的解。(4)为了验证算法的有效性,通过CUDD软件包实现了所有符号算法,并在随机测试实例和公开基准数据集上进行了广泛的实验对比,实验结果表明本文算法提高了子图同构求解的时间和空间效率。

关键词：图匹配子图同构约束满足问题全不同约束树分解技术符号算法代数决策图