IRST(k,l)-Index:一种支持分支路径查询的高效XML结构索引

为快速准确地查询图结构XML文档,本文在互关联后继树(IRST)的基础上,引入结构索引的相似性归并思想,提出一种基于互关联后继树且支持分支路径查询的高效XML结构索引-IRST(k,l)-index,并给出该索引的快速创建和查询算法.经实验验证,与国际上同类索引相比,该索引的创建速度更快、查询效率更高、空间开销更小.     

一种基于同心圆切割的XML编码方案

在可扩展标记语言(XML)文档的查询过程中,为快速判断任意两节点关系,提出一种基于同心圆切割的编码方案.将一棵n层的XML树看作由n个不同半径的同心圆组成,圆心代表根节点,根据兄弟节点等分切割给定区域的思想,将圆半径、角度与标识相结合进行编码.实验结果表明,与DietZ和StratE编码方法相比,该方案可加快节点间关系判断及任一节点在文档中具体定位的速度,时空效率较高.     

基于EXN-Tree编码的XML结构连接算法研究

提出了EXN-Tree的概念，将XML文档树的节点映射到EXN-Tree，依据EXN-Tree的节点编码生成XML文档树节点数据结构。基于此新型的节点编码结构，就无序无索引节点集和有序有索引节点集两种情况下的XML结构连接算法展开研究，提出了一系列的结构连接算法，解决了无序无索引节点集和有序有索引节点集两种情况下的XML结构连接。分析表明该算法的I/O复杂性优于已有算法，具有良好的性能。     

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

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

加密XML数据结构索引方案研究

充分利用XML数据库文档的树形结构特性,结合Dewey编码原理和B+树的索引特性,提出了一种基于B+树的加密XML结构索引和查询模型.在XML文档加密过程中,将XML加密数据与基于加密数据的B+树索引一起存储在服务器端,以便在服务器端完成对加密数据的结构索引.实验结果表明,此法提高了查询的效率,无需解密无关的加密数据,有效地实现了对加密XML数据的结构索引.     

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

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

一种支持动态插入的XML文档树编码IFED

XML文档树编码用来标识节点在文档树中的位置,XML文档查询算法通常通过编码来判断节点的祖先后代和兄弟关系,编码的好坏对查询效率影响很大.目前提出的编码主要分为两大类:区间编码和前缀编码,最近提出的扩展的前缀编码-Extended Dewey,由于通过单个节点的编码能够得到节点对应的路径,所以它支持有效的查询,但不支持动态插入.提出了一种新的XML文档树编码-IFED,它由Extended Dewey编码改进而来,既支持高效地查询,又支持动态插入.     

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

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

基于Schema的XML混合编码索引查询技术

Web中存在着越来越多的XML的文档,如何高效地从XML文档查询出有效信息已经成为当前在半结构化数据研究领域中的热点问题。针对XML文档节点进行编码和建立索引结构可以有效地提高查询速度,提出一种SBXHCI(Schema-Based XML Hybrid Coding Indexing)查询技术,该方法充分利用Schema信息对XML文档进行编码和构建索引。对创建索引所花费的时间和空间,查询响应的时间进行大量的实验分析,结果表明SBXHCI方法的编码机制降低了索引结构在时间和空间的资源消耗,并且在路径查询的响应速度有着显著的提高。     

优化索引XML数据研究

介绍了文档树中嵌入编码机制的思想和扩展编码方法，提出了采用改进的扩展编码方式来对XML文档进行编码，并使用改进的B 树构造算法构建索引树，以期提高存储空间利用率并减少B 树节点分裂次数；最后，在理论和实验的基础上分析了数据查询的执行效率。     

一种新的基于区域的动态编码方案

为了提高查询效率，许多XML文档编码方案相继被提出。目前大部分编码方案并不能很好地支持文档更新。在分析比较现有编码方案的基础上，提出了一种新的动态编码方案(DNS)。该方案用实数表示XML文档树中的节点编码，能够利用连续数值间的区域为新插入的节点或子树编码，并能够根据文档的更新情况动态调整部分节点的编码。     

Compact Labeling Scheme for XML Ancestor Queries

XML documents are often viewed as trees (basically the parse tree of the document), and queries over such documents typically test for ancestor relationships among tree nodes. Search engines process such queries using an index structure summarizing the ancestor relations. In the index, each document item (tree node) is identified using some logical id (node label), such that, given two labels, the engine can determine the ancestor relationship between the corresponding nodes. The length of the labels is a main factor of the index size. Therefore, reducing this length, even by a constant factor, is a critical issue. In this work we consider the following problem. Given a rooted XML tree T, label the nodes of T in the most compact way such that given the labels of two nodes, one can determine in constant time, by looking at the labels only, whether one node is an ancestor of the other. Labelings currently being used are all variants of the following interval scheme. Number the leaves say from left to right and label each node with a pair consisting of the numbers of its smallest and largest leaf descendants. An ancestor query then amounts to an interval containment test on the labels. The maximum label length using this scheme is 2 log n, where n is the number of nodes in the tree. (All logarithms in this paper are to base 2.) The focus of this work is finding a scheme that works best in practice on real XML data. We suggest an orthogonal prefix-based approach, where the labeling is such that an ancestor query roughly amounts to testing whether one label is a prefix of the other. We present several new labeling schemes based on this approach and analyze their performance both theoretically and empirically.     

深度优先算法在创建树形结构中的应用研究

为了让软件系统可以对树结构进行灵活管理,对相关学者提出的生成动态树结构的方案进行改进,给出了以数据表自关联的方式对节点信息进行存储,提出了在存储状态下的父节点、兄弟节点、叶子节点等节点类型的定义。使用深度优先非递归算法抽取节点信息,并按照树结构方式对节点进行排序,依据排序结果以及节点类型生成树结构,实现了一种具有很好可移植性、可扩充性和可维护性的无限级动态树。最后,将动态树植入学校管理系统,通过实验证明,植入该树结构之后系统具有界面结构性强、信息层次清晰、用户操作简单等优点。     

基于节点多样性的域内路由保护算法

已有的路由保护方案都没有考虑网络中节点的重要程度,然而在实际网络中不同节点在网络中的重要程度是不相同的。针对该问题,提出一种基于节点多样性的域内路由保护算法（intra-domain routing protection algorithm based on node diversity,RPBND）。计算节点构造以目的为根的最短路径树（shortest path tree,SPT）,从而保证RPBND算法和目前互联网部署的路由算法的兼容性;在该最短路径树的基础上构造特定结构的有向无环图（directed acyclic graph,DAG）,从而最大化路由可用性。实验结果表明,RPBND极大地提高了路由可用性,降低了故障造成的网络中断时间,为ISP部署域内路由保护方案提供了充分的依据。     

一种XML文档索引及查询处理方式

本文首先论述了传统XML路径模式索引方式，在此基础上提出面向元素的XML文档索引方式和相关算法，以及使用扩展的后序遍历序号进行元素节点标识的方案，并给出了该索引方式和元素节点标识方案下规则路径表达式查询和树型模式查询处理的方法，最后说明该方式在效率上优于传统索引方式下规则路径表达式查询和树型模式查询处理。     

XML数据扩展前序编码的更新方法

大部分XML查询技术都是基于某种对XML树的编码方法.对XML树的编码,是指按照某种规则对XML树的每一个结点分配唯一的编码,目的是通过任意两个结点的编码,能够直接判断两个结点之间是否具有祖先后代关系.最常用的编码方法是区域编码方法(region based numbering scheme).然而,XML数据也会面临插入删除等更新问题.数据一旦更新,区域编码也要作相应的调整,才能保证基于这个编码的各种索引和查询算法的正确性.在编码的更新方面,目前研究得还不多.主要研究区域编码的更新问题,采用预留编码空间的方法,针对不同特征的XML数据和应用环境提出了一整套预留算法和编码更新算法,并做了大量的实验,检验这些算法的有效性.     

SLS: A numbering scheme for large XML documents

In view of the efficiency requirements for query and update processing in XML databases, implementation of the robust node labeling (numbering) scheme becomes an increasingly important research issue. In order to process XML queries efficiently, it is necessary to detect the ancestor-descendant relationship between the nodes and restore the sequence order of nodes in the document. To solve this problem, the technique of labeling the document nodes is used. As a result, the so-called numbering scheme is created. The nodes of the documents are labeled with certain unique identifiers. Comparing these identifiers, one can restore the sequence order of the nodes and to establish the hierarchical relationships. In this paper, we give a survey of the most efficient numbering schemes and introduce a numbering scheme proposed by the authors and employed in the Sedna DBMS [1].     

多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较：（1）解的质量;（2）计算时间;（3）算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。