基于节点位置信息的降低更新代价前缀编码方案研究

Novel Position-based Prefix Encoding Approach to Reduce Update Cost for Dynamic XML Data

分析了现有的几种XML文档前缀编码[1-4]方法,研究了在XML文档树不同位置插入节点时的更新代价,提出了一种基于位置信息的前缀编码方案,对更新代价较大的节点预留较大的空间。设计了更新算法,在产生新插入节点的编码的同时,为今后插入节点也预留空间,且采用"借"空间算法,减小插入操作造成重新编码的数量。充分的试验结果证明,采用提出的编码方法,具有相对较小的平均编码长度和编码时间,查询速度很快,更重要的是能够有效降低更新操作引起的编码长度增加、重新编码节点数以及更新时间。

Prefix scheme is popular to label XML tree. Inserting nodes or sub-tree in XML tree will cause abundances of nodes renumbering. Nodes inserted in different positions cause different update cost. We proposed a novel position-based prefix encoding approach to reduce update cost for dynamic XML data,which preserves bigger coding space for the higher update cost nodes. In our update algorithm, coding space was preserved when the nodes were inserted. And we proposed ＂borrow＂ space algorithm, which can decrease the number of nodes renumbering by inserted operation. Extensive experimental results show that the new position-based prefix encoding approach has relatively smaller mean coding length and encoding time, higher query response time. And the method can effectively decrease the increasing code length, renumbering nodes number and update time causing by update