基于物化视图的查询重写系统设计与实现

随着XML文档大量涌现,如何有效地管理和查询XML数据已经成为亟待解决的问题。结合数据库发展的需要,研究了在关系数据库中利用物化视图和查询重写技术存储和查询XML文档。基于视图的查询重写技术是查询优化的一个重要技术,利用缓存的视图结果回答新查询不需要访问源数据库进行查询,能够节省查询处理时间。通过对物化视图、视图缓存、查询重写等技术进行研究,讨论如何利用关系数据库中缓存的物化视图来回答查询的问题,并实现了基于物化视图的XML数据查询系统原型。系统中使用扩展的模式匹配算法实现对多分支路径的模式匹配,解决了重写是否存在的问题,并通过模式匹配算法的匹配结果,来判断是否可以构造补偿表达式。通过构造补偿表达式算法得到重写结果,进而通过数据库中缓存的视图完成查询。     

基于查询优化策略的语义缓存谓词化简

语义缓存技术可以有效地支持移动计算应用。现有的语义缓存查询处理算法在时空效率和裁剪的复杂度上较高,限制了语义缓存的实用性。为此,本文提出20条逻辑规则和语义缓存动态合并策略,来降低查询裁剪的复杂性。在Android系统上的实验表明,在简单查询下,采用全合并的缓存管理策略和谓词析取式优化算法相结合的方法,能较好地优化查询处理。在复杂查询方面,基于谓词复杂度的语义缓存动态合并策略能很好地平衡缓存与查询两端的谓词复杂度,有效地提高语义缓存的查询处理效率。     

高效的top-k相似字符串查询算法

研究基于编辑距离的top-k相似字符串查询处理方法,即对于给定的字符串集合S和查询串σ,返回S中前k个与σ编辑距离最小的字符串。首先提出了基于长度跳跃索引的2种自适应过滤策略来减少字符串之间编辑距离的计算次数;其次提出了查询字符串与不匹配字符串集合的编辑距离下界,以便在处理和σ无公共特征的字符串时,进一步减少编辑距离的计算次数;最后给出了基于上述过滤策略的高效top-k相似字符串查询算法,并在3个真实的数据集上进行了实验,实验结果验证了所提算法的高效性。     

基于父节点的XML查询优化算法

本文提出了基于父节点的XML查询优化算法,它主要利用关键词的顺序循环查找父节点,把查找出来的父节点集合求交集,所得的父节点交集集合中的元素即为最小子树根节点,最后根据所得出的最小子树根节点得到用户所需的最紧致片段。通过选取经典的INEX数据集算法进行测试。实验结果表明,与传统的XML查询优化算法相比,基于父节点的XML查询优化算法有较高的准确率,更能满足用户需求。     

一种基于并行Bloom Filter的高速URL查找算法

URL查找是众多网络系统中重要的组成部分,如URL过滤系统、Web缓存等.随着互联网的迅速发展,URL查找面临的主要挑战是实现大规模URL集合下的高速查找,同时保证低存储和低功耗.本文提出了一种基于并行Bloom Filter的URL查找算法,CaBF.该算法高度并行化,提供大规模URL集合下的高速最长前缀匹配,并很好地适应集合中不同数量的URL组件.理论分析和真实网络数据集上的实验表明,该算法相比现有算法可以降低假阳性概率达一个数量级(或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗).此外,该方法的体系结构很容易映射到FPGA等硬件器件上,提供每秒超过150M次的URL查找速度.     

面向大数据处理的高精度多维计数布鲁姆过滤器

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法.AMD-CBF中元素表示和查找分两步进行,第1步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第2步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息,然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF),完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,AMD-CBF能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高.     

应用程序、专用程序、实用程序

0633957 3ds Max选择集合的应用[刊,中]／焦飞／／电视字幕·特技与动画．-2006,12(9)．-39-42(L) 0633958 XML,Schema设计方法研究[刊,中]／刘洪星／／交通与计算机．-2006,24(4)．-123-126(D) 0633959基于语义缓存技术的Hibernate查询缓存机制研究[刊,中]／徐凯声／／交通与计算机．-2006,24(4)．- 120-122(D)语义缓存技术是优化数据库性能的有效方法。为优化查询性能,Hibernate引入了查询缓存机制。在深入研究基于语义缓存技术的Hibernate缓存机制同时,提出了在不同进程中利用JMS技术与手工刷新查询结果,从而实现了一个查询应用进程与一个更新应用进程间的相互通信,并根据后一进程的状态判定是否需要查询缓存。参6     

UN-GRAIL算法——基于逆向双区间标签解决k步可达性查询问题

随着大数据时代的来临,越来越多的复杂结构数据需要用图数据结构模型来表示,因此图数据模型有着十分广泛的应用前景。高效地处理图数据模型顶点之间的查询问题变得至关重要,GRAIL算法为传统的可达性查询算法,基于GRAIL算法文章提出了一种新的算法——UN-GRAIL,该算法的特点是基于逆向双区间标签来解决k步可达性查询问题,并最终基于相同的实验环境,相同的数据集进行实验,最后统计对顶点对的查询时间,查询时间越少,说明查询效率越高,最终得出结论,UN-GRAIL算法在处理位于两个不同分支上的k步可达性查询问题时会有比较高的查询效率。     

基于查询树的防碰撞算法性能分析与研究

多标签碰撞问题严重影响射频识别系统的性能.基于查询树的防碰撞算法作为一种确定性算法被广泛的应用于各类射频识别场景中.本文分析了主流查询树防碰撞算法的性能与不足,并基于查询树方法提出了一种时间有效的防碰撞算法.该算法基于传统查询树识别模型,实施了一种双查询前缀匹配方法,可以消除传统查询树方法中的空闲时隙.此外,提出的算法可以充分利用碰撞时隙来提高识别效率.理论分析和仿真结果表明该算法优于现有的查询树防碰撞算法.     

基于聚类分析的内核恶意软件特征选择

针对现有基于数据特征的内核恶意软件检测方法存在随特征的增多效率较低的问题,该文提出一种基于层次聚类的特征选择方法。首先,分析相似度计算方法应用于数据特征相似度计算时存在的困难,提出最长公共子集并设计两轮Hash求解法计算最长公共子集;其次,设计基于最长公共子集的层次聚类算法,有效地将相似特征聚类成簇;在此基础上,设计基于不一致系数的内核恶意软件特征选择算法,大大减少特征数,提高检测效率。实验结果验证了方法的有效性,且时间开销在可接受的范围内。