RLPI索引:一种处理连续不确定XML索引

针对目前连续不确定XML数据的概率阈值范围查询,提出一种新的包含路径索引和值索引的RLPI(Reverse Label Probabilistic Index)索引。RLPI路径索引以逆序标签路径作为索引项,通过逆序标签路径可区分不同路径上的同名节点,更具针对性地定位所需节点。RLPI值索引借鉴U树的思想,通过提前计算并存储叶子节点的相关信息,以减少查询中需处理的元素数目,并且其对满足任意连续pdf(probability density function)的不确定数据均适用。理论分析和实验结果表明,RLPI索引技术有效地提高了查询处理的性能。     

连续不确定XML数据索引技术研究

针对连续不确定XML数据的概率阈值查询,提出CPTI(Continuous Probabilistic Threshold Index)索引技术,包括CPTI结构索引和CPTI值索引。CPTI结构索引扩展了结构索引F-index支持连续不确定XML数据,通过CPTI结构索引查询twig小枝,并确定小枝的路径概率;CPTI值索引是一个二维表,记录cont类节点的概率信息,通过CPTI值索引过滤与查询无关的元素以减少查询中需要处理的元素数目。实验表明,此索引技术可极大地提高查询处理的性能。     

使用DTD优化XML数据流上的XPath查询

如何在XML数据流上高效地执行XPath查询,是XML数据流管理的关键问题。DTD结构信息对提高XML查询效率有很大帮助,已有的大部分算法没有利用这一资源。提出了一种使用DTD进行XML数据流查询处理的方法,具有以下特征:利用树自动机表示XPath;通过XPath树自动机与DTD树匹配,预先标识不匹配查询结构的DTD节点;给出一种利用DTD的XML流索引方法DBXSI;执行查询时,根据流索引信息直接跳过某些与查询不匹配的节点及子树。实验结果表明:该方法可有效支持Xpath查询,效率优于传统算法。     

连续不确定XML的Top-k查询算法研究

为了解决连续不确定XML高效的top-k查询,提出CProTJFast算法.该算法基于P-文档模型,扩展PEDewey(probabilistic extended Dewey)编码支持连续分布类型节点的编码,采用路径概率下限值进行节点过滤,并针对连续概率密度函数制定过滤策略,从而在计算连续节点概率之前过滤掉不参与结果的节点.实验结果表明,采用连续节点过滤策略的CProTJFast算法有效地提高了连续不确定XML的top-k查询效率.     

基于优化过滤策略的XML数据查询处理

如何高效地处理XML查询，是目前研究的热点。由于当前方法存在过多扫描无用节点引起效率下降的问题，本文设计了一种XML数据的二级索引结构，基于该结构给出路径查询处理算法。首先，本文对XML模式中每个节点按路径类型进行分类编码，然后把每个节点按该编码进行聚类存储。在查询时，就可以先根据模式信息和查询信息得到目标节点的编码，然后只需将二级索引中这些编码对应的部分载入内存，进行过滤操作。这样就不必扫描整个索引，提高CPU和IO效率。本文还对二级索引结构进行扩展，使本文的过滤索引能方便应用在有分支结构的查询上。实验结果表明，本文的XML数据过滤算法效率优于基于Bit vector的过滤算法，并且索引结构所需要的存储空间也小于Bitvector索引。     

高效的连续不确定XML数据Top-k查询算法

目前,不确定XML数据的top-k查询算法中都没有处理连续不确定数据,本文提出SPCProTJFast算法,该算法改进了传统的归并算法,并结合连续不确定数据的过滤方法,实现了连续不确定XML的Top-k查询。为了避免概率下限值过小对过滤效果的影响,又提出HPCProTJFast算法,该算法推迟了对连续节点的处理,只有在获得满足概率条件的整枝路径时才对连续节点进行访问。实验表明,在执行时间以及过滤效率上,同直接处理连续不确定数据的ProTJFast算法相比,这两种算法都要更高效,并且HPCProTJFast算法的效率更高。     

结构编码与簇集索引相结合的XML混合索引*

提出了一种结构编码与簇集索引相结合的XML混合索引结构(H iSC)。引入簇集索引结构,将XML节点分类,尽量多地保存XML数据的结构信息,缩小查询范围,提高了查询效率并能支持关键字的查询。实验表明此索引结构可以高效并准确地查询XML数据中的结构信息。     

基于KD树和R树的多维云数据索引

针对云存储系统大多基于键值对模型存储数据,多维查询需要对整个数据集进行完全扫描,查询效率较低的问题,提出了一种基于KD树和R树的多维索引结构(简称KD-R索引)。KD-R索引采用双层索引模式,在全局服务器建立基于KD树的多维全局索引,在局部数据节点构建R树多维本地索引。基于性能损耗模型,选取索引代价较小的R树节点发布到全局KD树,从而优化多维查询性能。实验结果表明：与全局分布式R树索引相比,KD-R索引能够有效提高多维范围查询性能,并且在出现服务器节点失效的情况下,KD-R索引同样具有高可用性。     

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段.文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index.RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符" 和后代轴"//"的查询以及兄弟节点无序的模式树的查询.仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构.     

一种改进XML模式树查询最小化算法

对XML模式树查询进行最小化查询优化,是左右XML数据查询处理性能的关键因素。对模式树查询最小化技术进行了研究,结合XML结构索引提出了一种改进的XML模式树查询最小化算法。该算法有效地解决了普遍意义上的语法层次优化中不能有效删除冗余节点的缺陷,从而提高了查询效率。实验结果表明该算法是正确的和有效的。     

基于扩展前缀编码的左孩子右兄弟结构连接算法

为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法.该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置.该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表.算法时间复杂度分析表明了该算法比现有算法的性能更好.     

一种高效的连续不确定XML小枝模式匹配算法

针对目前不确定XML小枝模式匹配算法均基于归并,易造成很大的空间和时间浪费问题,提出基于P-文档模型的连续不确定XML的非归并的小枝模式匹配算法.算法在节点入队列和出队列时分别进行过滤剪枝操作,减少待处理节点的个数,匹配过程使用相互关联的链表存储中间结果,不需要归并.理论分析与实验结果表明,该算法是一种高效的连续不确定XML查询算法.     

VEMBP:支持更新的XML树编码方法

对有序XML文档树进行编码,不需要访问XML原始文件就能够实现对XML数据的管理,提高了XML管理系统的效率。针对查询提出的编码方案具有很高的查询性能,但更新效率很低。为提高更新性能而设计的方案存在查询效率低或者编码空间大等问题。为了在提高更新XML文档效率的同时不对查询性能和编码空间产生负面影响,提出了一种新的编码方法VEMBP(Vector Encoding Method Based of Prime),该方法利用向量表示有序XML节点之间的顺序关系,采用素数表示有序XML文档节点之间的结构信息;并设计了一种算法来实现在没有牺牲查询性能的前提下完全避免更新过程中的二次编码和重新计算,降低了更新代价,同时编码空间也得到了控制。实验结果显示,VEMBP具有较好的查询和更新性能。     

概率XML文件树结点概率的查询算法

概率XML文件是概率数据的网络数据交换和表示标准,元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型,定义了概率XML文件树的基本路径和扩展路径,提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法,根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法,并通过实验进行了比较分析.实验结果表明:这两种方法是有效的;与前一种方法比较,后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询,计算过程较简单.     

匹配预处理对XML查询的优化

在基于匹配预处理的XML查询算法中,利用现有的三种树匹配模型,按照匹配代价高低得出数据集匹配结果。并在此基础上对现有算法加以改进,引入"匹配预处理"功能,进行一系列的实验。结果表明,当数据规模庞大时,该算法去除树中的无用结点,提高了数据集的查询效率,特别是查全率、查准率以及平均响应时间均令人满意。该算法应用于科技资源数据库的统一检索系统中,实现了资源导航,缩小了查找范围,提高系统的易用度。     

基于特征路径的XML文档变化检测算法

由于在线信息变化频繁,XML文档变化快速检测成为Internet查询系统、搜索引擎以及连续查询系统的关键技术。目前国际上的研究主要集中于有序模式的XML文档比较,针对有序模式最好的算法复杂度为O(nkgn),其中n为文档的长度,而针对无序模式为多项式时间复杂度,为提高处理效率,提出一种基于特征路径的变化检测算法,将传统标号树匹配问题转换为基于特征路径的无重复路径标号树的匹配问题,同时适于有序和无序两种模式,复杂度为O(n),其中n为文档结点的个数．实验证明KF-Diff 能够非常高效地比较XML文档。     

XML数据流中的后兄弟查询算法

针对在XML文档树模型中进行后兄弟节点查询时内存消耗大、匹配效率低等缺陷,提出一种基于XML数据流与栈的后兄弟查询算法。采用SAX解析器与结构连接方法,对XML文档中所有已知节点与后兄弟节点进行精确匹配并输出。结果表明,该算法具有适用范围广、占用系统资源少、匹配效率高等优势。     

RTC树的构建与不确定近邻关系查询方法

空间索引结构和查询技术在空间数据库中具有重要的作用,针对已有的方法在复杂空间数据对象的近似和组织方面的局限性,提出了一种基于最小外接矩形(MBR)、梯形和圆的新的索引结构(RTC树).为了有效处理复杂空间数据对象的最近邻(NN)关系查询问题,提出了基于RTC树的最近邻查询(NNRTC)算法,NNRTC算法利用剪枝规则可减少节点遍历和距离计算.针对障碍物对数据集中最近邻的影响问题,提出了障碍物环境下的基于RTC树的最近邻查询(BNNRTC)算法,BNNRTC算法先在理想空间进行查询,再对查询结果进行判断.为了有效处理动态单纯型连续近邻链查询问题,进一步给出了基于RTC树的动态单纯型连续近邻链查询(SCNNCRTC)算法.实验结果表明,相对基于R树的查询方法,所提的方法在处理数据量较大的复杂空间对象的数据集时可提高60%~80%的效率.     

基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。