Efficient selection on a binary tree

Given a sequence of n ordered but not sorted b-bit integers, an algorithm is described to select the kth smallest by reducing the length of the original sequence until only the required kth value or those equal to the kth remain. Using the time to add two bits as the unit, a running time of O(b log n) is obtained by employing O(n) simple processors arranged in a binary tree. The algorithm is then adapted to run on a binary tree of processors with N leaves, where N log N ⩽ n, in O(bn/N) time for an optimal cost of O(bn).     

Acquisition of a symbolic manipulation task model by attention point analysis

As a way of automatic programming of robot behavior, a method for building a symbolic manipulation task model from a demonstration is proposed. The feature of this model is that it explicitly stores the information about the essential parts of a task, i.e. interaction between a hand and an environmental object, or interaction between a grasped object and a target object. Thus, even in different environments, this method reproduces robot motion as similar as possible to that of humans to complete the task while changing the motion during non-essential parts to adapt to the current environment. To automatically determine the essential parts, a method called attention point analysis is proposed; this method searches for the nature of a task using multiple sensors and estimates the parameters to represent the task. A humanoid robot is used to verify the reproduced robot motion based on the generated task model.     

A binary tree feature selection technique for limited training sample size

In cases where there are larger numbers of features available than should be used for a given classification task, current practice is to arbitrarily pick the number of features to be used and then to use a feature selection algorithm to determine the specific feature subset to be used. An algorithm is presented that predicts the best feature dimensionality, taking into account the number of training samples. It is demonstrated that rather small training set sizes are still practical using these techniques. Several experiments are presented to assess the algorithm's performance, and a binary tree classification procedure with two examples that utilize the algorithm is shown to demonstrate its usefulness.     

网格环境中基于二叉树模型的资源监控方法

针对虚拟共享平台（VSP）对资源监控和用户任务计费的需求,设计实现了VSP的网格资源监控模块VSPMonitor。VSPMonitor中资源消耗的计算采用二叉树对系统进程树进行存储。通过对二叉树的非递归遍历统计出用户任务的资源消耗量。实验表明这种基于二叉树模型的方法可以高效计算出用户任务的资源消耗量,满足VSP对资源监控和任务计费的需求。     

A combined nonparametric approach to feature selection and binary decision tree design

An efficient procedure which integrates feature selection and binary decision tree construction is presented. The nonparametric approach is based on the Kolmogorov-Smirnov criterion which yields an optimal classification decision at each node. By combining the feature selection with the design of the classifier, only the most informative features are retained for classification.     

A note on searching in a binary search tree

An algorithm for searching in a binary search tree using two-way comparisons is presented. The number of comparisons required by this algorithm is only one more than when using three-way comparisons. Since most high-level programming languages do not supply three-way comparisons, the number of comparisons used de facto is reduced by a factor of two. We give experimental results to indicate the speed-up that may be achieved by the presented algorithm.     

A Markov chain model for dynamic binary search tree behaviour

We present a Markov chain model for the analysis of the behaviour of binary search trees (BSTs) under the dynamic conditions of insertions and deletions. The model is based on a data structure called a lineage tree, which provides a compact representation of different BST structures while still retaining enough information to model the effect of insertions and deletions and to compute average path length and tree height. Different lineages in the lineage tree correspond to states in the Markov chain. Transition probabilities are based on the number of BST structures corresponding to each lineage. The model is based on a similar lineage tree model developed for B-trees. The BST model is not intended for practical computations, but rather as a demonstration of the generalizability of the lineage tree approach for modeling data structures such as B-trees, B*-trees, B⁺-trees, BSTs, etc.     

Probabilistic word classification based on a context-sensitive binary tree method

A corpus-based statistical-oriented Chinese word classification can be regarded as a fundamental step for automatic or non-automatic, monolingual natural processing systems. Word classification can solve the problems of data sparseness and have far fewer parameters. So far, much relative work about word classification has been done. All the work is based on some similarity metrics. We use average mutual information as the global similarity metric to do classification. The clustering process is top-down splitting and the binary tree is growing with splitting. In natural language, the effect of left neighbours and right neighbours of a word are asymmetric. To utilize this directional information, we induce the left–right binary and the right–left binary tree to represent this property. The probability is also introduced in our algorithm to merge the resulting classes from the left–right and the right–left binary tree. Also, we use the resulting classes to do experiments on a word class-based language model. Some classes' results and the perplexity of a word class-based language model are presented.     

网络信息自适应发布的PLCH二叉树模型

针对网络信息的(硬件)自适应发布问题进行研究，建立了信息结构体的PLCH二叉树模型，并根据简化模型最优方案求解，得出网络信息自适应发布的最优算法。     

Constructing a binary tree efficiently from its traversals

In this note we streamline an earlier algorithm for constructing a binary tree from its inorder and preorder traversals. The new algorithm is conceptually simpler than the earlier algorithms and its time complexity has a smaller constant facto.     

Embedding a complete binary tree into the supercube

Consider a complete binary tree with 2ⁿ − 1 nodes and a supercube with the same number of nodes. We present a new embedding method to map the complete binary tree into the supercube with dilation 1. Our simple mapping method is quite competitive with the previous result.     

Wireless sensor network minimum beacon set selection algorithm based on tree model

Wireless sensor networks (WSNs) are highly attractive both in academia and in practice as a wholly new platform for information transmission. Localization technology is a key technology of WSNs. The structure of the beacon node set is very important to the positioning of the nodes. A method for constructing a minimum beacon set is proposed in this thesis based on the tree model, in which unimportant nodes are identified as early as possible and then pruned. Thus, we avoid unnecessary calculations when establishing the minimum beacon set. This method can provide a reliable guarantee for the unknown node localization. According to our experiment, this algorithm is rapid and stable.

     

Database reverse engineering: From the relational to the binary relationship model

This paper describes an algorithmic method for transforming a relational database schema to a binary-relationship one. The source schema may consist of relations that are at any level of normalization, and the designer may add semantic information on the source schema, such as the definition of candidate keys, foreign keys, functional dependencies of various types, multi-valued dependencies, many-to-many constraints, inclusion dependencies, and others. Based on this information, the multi-stage transformation algorithm applies mapping rules to generate object-types, binary-relationships and constraints in the target conceptual schema. The method is implemented as a PC-based tool, utilizing Ingres, SQL and C, and is part of a comprehensive database design tool for both forward and reverse engineering.     

Optimal computation of prefix sums on a binary tree of processors

Givenn numbersa ₀,a ₁,...,a _n –1, it is required to compute all sums of the forma ₀+a ₁+...+a _i , fori=0, 1,...,n–1. This problem arises in many applications and is trivial to solve sequentially in O(n) time. Besides its practical importance, the problem gains an additional theoretical interest in parallel computation. A technique known asrecursive doubling allows all sums to be computed in O(logn) time on a model of computation wheren processors communicate through aninverse perfect suffle interconnection network. In this paper we show how the problem can be solved on a simple network, namely abinary tree of processors. In addition, we show how to extend our solution to obtain an optimal-cost algorithm. The algorithm usesp processors and runs in O((n/p)+logp) time, for a cost of O(n+p logp). This cost is optimal whenp logp=O(n). Finally, two applications of our results are illustrated, namely job scheduling with deadlines and the knapsack problem.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A0282 and A3336.     

基于知识的协同设计任务分配双向选择模型

针对协同设计任务分配中忽略设计人员自我发展需求的问题,在对设计人员知识作业过程进行分析的基础上,提出显性知识的学习模型和知识集合的概念,并构建了一个能实现任务与设计人员之间双向选择的优化模型,从而实现任务的合理分配,达到任务完成时间最短和设计人员知识学习最大化之间的平衡。最后,通过算例分析验证了模型的有效性：模型的使用有利于设计人员知识扩容;模型的循环使用对完成任务时间的缩短有利。     

应用最小生成树实现点云分割

点云分割是点云参数化、形状识别、编辑造型等领域的关键基础算法。提出一种基于最小生成树的点云模型分割算法,包括生成带状分割边界、区域增长、拆分带状分割边界以及生成最终区域4个步骤。算法采用Snake模型提取分割曲线并向两侧扩展形成带状分割边,利用最小生成树实现区域增长来提取区域内部点,最后拆分带状分割边界并与已有区域合并形成最终区域。实验结果表明,该算法能够有效避免过分割和欠分割,能够生成光顺分割边界,与Level Set分割算法相比具有较高的效率。     

On the max-entropy rule for a binary search tree

Summary A modified max-entropy rule is proposed for constructing nearly optimum binary search tree in the case of ordered keys with given probabilities. The average cost of the trees obtained by this rule is shown to be bounded by the entropy of the probability distribution plus a constant not larger than one. An algorithm for implementing this rule is then suggested and its complexity is investigated in a probabilistic setting.     

Word prediction using a clustered optimal binary search tree

Word prediction methodologies depend heavily on the statistical approach that uses the unigram, bigram, and the trigram of words. However, the construction of the N-gram model requires a very large size of memory, which is beyond the capability of many existing computers. Beside this, the approximation reduces the accuracy of word prediction. In this paper, we suggest to use a cluster of computers to build an Optimal Binary Search Tree (OBST) that will be used for the statistical approach in word prediction. The OBST will contain extra links so that the bigram and the trigram of the language will be presented. In addition, we suggest the incorporation of other enhancements to achieve optimal performance of word prediction. Our experimental results showed that the suggested approach improves the keystroke saving.     

基于EREW的后序遍历二叉树算法

针对单处理器后序遍历二叉树的时间复杂度为O（n）问题,提出了在EREW PRAM并行计算模型下一种后序遍历二叉树的算法。将后序遍历二叉树的边构造一个单链表,使用指针跳越技术对单链表进行表序问题求解,从而得到后序遍历二叉树结点的顺序。得出了运用该算法将时间复杂度从O（n）减少到O（logn）的结论。