扩展数据结构方法的研究

本文介绍了如何扩展数据结构来支持更多的应用操作。通过扩展红-黑树,分析了动态地维护集合中关键字的次序统计,同时,概括了扩展数据结构的方法和步骤。     

扩展数据结构方法的研究

本文介绍了如何扩展数据结构来支持更多的应用操作。通过扩展红-黑树,分析了动态地维护集合中关键字的次序统计,同时,概括了扩展数据结构的方法和步骤。     

An evaluation of self-adjusting binary search tree techniques

Much has been said in praise of self-adjusting data structures, particularly self-adjusting binary search trees. Self-adjusting trees are most suited to skewed key-access distributions as the techniques attempt to place the most commonly accessed keys near the root of the tree. Theoretical bounds on worst-case and amortized performance (i.e. performance over a sequence of operations) have been derived which compare well with those for optimal binary search trees. In this paper, we compare the performance of three different techniques for self-adjusting trees with that of AVL and random binary search trees. Comparisons are made for various tree sizes, levels of key-access-frequency skewness and ratios of insertions and deletions to searches. The results show that, because of the high cost of maintaining self-adjusting trees, in almost all cases the AVL tree outperforms all the self-adjusting trees and in many cases even a random binary search tree has better performance, in terms of CPU time, than any of the self-adjusting trees. Self-adjusting trees seem to perform best in a highly dynamic environment, contrary to intuition.     

Time- and Space-optimal height-balanced 2-3 brother trees

The node-visit optimal (NVO) and the space-cost optimal (SCO) height-balanced (HB) 2-3 brother trees are defined. The characterization of the NVO HB 2-3 brother trees is developed. This characterization leads to a linear-time algorithm for constructing an NVO HB 2-3 brother tree for an ordered set of keys. The minimum space-cost of an N-key NVO HB2-3 brother tree and the space-cost of an N-key SCO HB 2-3 brother tree is analysed. It is shown that the minimum space-cost of an NVO HB 2-3 brother tree is never more than one plus the space-cost of an SCO HB 2-3 brother tree. Further, the minimum node-visit cost of an SCO HB 2-3 brother tree is at most one plus the node-visit cost of an NVO HB 2-3 brother tree. It is also shown that there exists an HB 2-3 brother tree which is both SCO and NVO for just over half the possible values of keys. Finally, an outline for constructing an SCO HB 2-3 brother tree is presented.     

TinyDB数据库存储策略的分析与改进

TinyDB数据库是典型的无线传感器网络的数据库模型,它采用的是以数据为中心的语义路由树的存储方法,需要维持特定的路由结构。介绍一种基于红黑树TinyDB数据库的存储策略,并参照TinyDB数据库的数据存储策略对基于红黑树的存储进行了性能分析。通过理论分析和实验证明该应用方法对TinyDB数据库存储有很大的优势。     

Linux下一种高性能定时器池的实现

提出Linux用户空间下的一种高性能定时器池的实现方法。主要基于时间轮、红黑树及Linux内核提供了一种利于管理的定时器句柄Timerfd。结合红黑树、位图、时间轮等技术,设计一种高性能级定时器池。池中定时器的粒度可达到40 ms,满足用户空间低延时的应用需求,同时又可以方便地管理一定数量的定时器。     

Succinct representation of dynamic trees

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree.We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively.We demonstrate that to efficiently support more extended operations, such as determining the i-th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time.Previous work on dynamic succinct trees (Munro et al., 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al., 2001 [17]) or “poly-log-log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log-log” query time (Gupta et al., 2007 [11]). More recently, the update time has been improved to O(logn/loglogn) while queries can be performed in O(logn/loglogn) time (Sadakane and Navarro, 2010 [20]).     

Chromatic binary search trees

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions ofred-black trees. The relaxed red-black trees, calledchromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present.     

基于红黑树的堆内存泄漏动态检测技术

设计与实现一个轻量级的堆内存泄漏检测工具,针对使用C++编码的开源代码,通过重载new, delete运算符,动态跟踪程序在执行过程中堆内存块的分配释放情况,在程序运行结束时给出内存泄露的检测结果。实现时采用红黑树管理所分配的堆内存,理论推导和实验表明其具有较高的效率。     

Chromatic binary search trees

We propose a new rebalancing method for binary search trees that allows rebalancing and updating to be uncoupled. In this way we obtain fast updates and, whenever the search tree is accessed by multiple users, a high degree of concurrency. The trees we use are obtained by relaxing the balance conditions of red-black trees. The relaxed red-black trees, called chromatic trees, contain information of possible imbalance such that the rebalancing can be done gradually as a shadow process, or it can be performed separately when no urgent operations are present. Received December 5, 1991 / May 2, 1995     

二叉查找树的一种优化结构——Treap

二叉查找树是一种重要的数据结构,但它有一个致命的缺点,就是会退化成线性表,解决这一问题的常用方法是采用平衡树、红-黑树等复杂的数据结构,实现起来比较困难.本文提出一种较为简单的优化结构-Treap,它是采用随机化的思想,将二叉查找树和堆有效结合在一起,从而实现相对平衡的二叉树结构.     

一种新的删除红黑树的结点的算法

提出一种新的删除红黑树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退。证明新算法是正确的。设n是红黑树的内部结点的个数。执行新算法时进行O（1）次旋转。新算法的时间复杂性是O（log2n）。实验结果表明新算法的平均执行时间比Tarjan的算法和Guibas-Sedgewick算法的短。新算法的空间复杂性是O（1）。     

Concurrent processing of linearly ordered data structures onhypercube multicomputers

The paper presents a simple and effective method for the concurrent manipulation of linearly ordered data structures on hypercube systems. The method Is based on the existence of an augmented binomial search tree, called the pruned binomial tree, rooted at any arbitrary processor node of the hypercube such that; every edge of the tree corresponds to a direct link between a pair of hypercube nodes; and the tree spans any arbitrary sequence of n consecutive nodes containing the root, using a fanout of at most [log₂ n] and a depth of at most [log₂ n]+1. Search trees spanning nonoverlapping processor lists are formed using only local information, and can be used concurrently without contention problems. Thus, they can be used for performing operations such as broadcast and merge simultaneously on sets with nonuniform sizes. Extensions of the tree to k-ary n-cubes and faulty hypercubes are presented. Applications of this concurrent data structure to low- and intermediate-level image processing algorithms, and for dictionary operations involving multiple keys, are also outlined     

Faster entropy-bounded compressed suffix trees

Suffix trees are among the most important data structures in stringology, with a number of applications in flourishing areas like bioinformatics. Their main problem is space usage, which has triggered much research striving for compressed representations that are still functional. A smaller suffix tree representation could fit in a faster memory, outweighing by far the theoretical slowdown brought by the space reduction. We present a novel compressed suffix tree, which is the first achieving at the same time sublogarithmic complexity for the operations, and space usage that asymptotically goes to zero as the entropy of the text does. The main ideas in our development are compressing the longest common prefix information, totally getting rid of the suffix tree topology, and expressing all the suffix tree operations using range minimum queries and a novel primitive called next/previous smaller value in a sequence. Our solutions to those operations are of independent interest.     

一种新的组密钥管理方案

给出了一种新的组密钥管理方案,该方案是基于密钥树、异或运算以及单向函数链,能保证前向以及后向安全性：新加入的组成员不能获得以前的组播报文,而且即使任意多个退出组播组的组成员进行合谋也不能获得以后的组播报文。就通信、计算以及存储开销而言,该方案比现有其他基于密钥树的方案有所提高。     

Representing Trees of Higher Degree

This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (or k-ary tries), where each node has k slots, labelled {1,...,k}, each of which may have a reference to a child, and ordinal trees, where the children of each node are simply ordered. Our representations use a number of bits close to the information theoretic lower bound and support operations in constant time. For ordinal trees we support the operations of finding the degree, parent, ith child, and subtree size. For cardinal trees the structure also supports finding the child labelled i of a given node apart from the ordinal tree operations. These representations also provide a mapping from the n nodes of the tree onto the integers {1, ..., n}, giving unique labels to the nodes of the tree. This labelling can be used to store satellite information with the nodes efficiently.     

基于二叉树相似性检测的变形文字识别研究

文字在经过一系列艺术处理后,许多现有的识别特征会产生歧义而导致识别准确率下降。文章讨论了在文字的变形处理不会改变文字内在的框架情况下的识别特征检测。首先利用最小生成树获取文字图像所对应的树型结构,然后约简非分叉节点(即节点的邻接节点数为2的中间节点),提出一个实用的无序无标签二叉树之间的相似测度计算算法,与原文字图像所对应的约简树进行相关度分析检测,最后获得文字相似性度量结果。这种算法着重分析图像中的分枝特征,因此对于不会改变文字内在框架的艺术处理来说,文字本身的分枝特征能够很好地被检测出来,从而实现艺术文字的识别。     

Mining manufacturing databases to discover the effect of operation sequence on the product quality

Data mining techniques can be used for discovering interesting patterns in complicated manufacturing processes. These patterns are used to improve manufacturing quality. Classical representations of quality data mining problems usually refer to the operations settings and not to their sequence. This paper examines the effect of the operation sequence on the quality of the product using data mining techniques. For this purpose a novel decision tree framework for extracting sequence patterns is developed. The proposed method is capable to mine sequence patterns of any length with operations that are not necessarily immediate precedents. The core induction algorithmic framework consists of four main steps. In the first step, all manufacturing sequences are represented as string of tokens. In the second step a large set of regular expression-based patterns are induced by employing a sequence patterns. In the third step we use feature selection methods to filter out the initial set, and leave only the most useful patterns. In the last stage, we transform the quality problem into a classification problem and employ a decision tree induction algorithm. A comparative study performed on benchmark databases illustrates the capabilities of the proposed framework.     

一种支持快速加密的基于属性加密方案

基于属性加密算法因含有大量耗时的指数运算和双线性对运算,一些方案提出将加密外包给云服务器.然而这些方案并没有给出外包加密在云服务器中的并行计算方法,而且还存在用户保管私钥过多、授权中心生成用户私钥成本过大的问题.针对这些问题,提出一种基于Spark大数据平台的快速加密与共享方案.在该方案中,根据共享访问树的特点设计加密并行化算法,该算法将共享访问树的秘密值分发和叶子节点加密并行化之后交给Spark集群处理,而用户客户端对每个叶子节点仅需要一次指数运算;此外,用户私钥的属性计算也外包给Spark集群,授权中心生成一个用户私钥仅需要4次指数运算,并且用户仅需要保存一个占用空间很小的密钥子项.     

基于Merkle哈希树的云存储加密数据去重复研究

收敛加密可以有效地解决数据加密和去重的矛盾,实现安全去重复,但是收敛加密仍然面临许多安全问题。针对传统的收敛加密容易遭受字典攻击的问题,提出基于Merkle哈希树的收敛加密方案实现数据去重复,通过执行额外的加密操作,加强数据的机密性,有效地避免字典攻击。为了克服传统的收敛加密方案的收敛密钥随着用户数量线性增长的问题,设计收敛密钥共享机制,进一步节省了收敛密钥的存储空间。