A database for enthalpies of formation of binary transition metal alloys

Experimental values of the enthalpy of formation are listed for the 61 of the 276 binary alloys formed from pairs of Sc to Ni, Y to Pd and Lu to Pt for which data are available.     

Matching graphs with unique node labels

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification and detection of abnormal events in computer networks.     

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).     

Random binary search tree with equal elements

We consider random binary search trees when the input consists of a multiset, i.e. a set with multiple occurrences of equal elements, and prove that the randomized insertion and deletion algorithms given by Martínez and Roura (1998) [4] produce random search trees regardless of multiplicities; even if all the elements are equal during the tree updates, a search tree will maintain its randomness. Thus, equal elements do not degenerate a random search tree and they need not to be handled in any special way. We consider also stability of a search tree with respect to its inorder traversal and prove that the algorithms used produce stable trees. This implies an implicit indexing of equal elements giving another proof that multiplicities do not pose problems when maintaining random binary search trees.     

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.     

On-line motion synthesis and adaptation using a trajectory database

Autonomous robots cannot be programmed in advance for all possible situations. Instead, they should be able to generalize the previously acquired knowledge to operate in new situations as they arise. A possible solution to the problem of generalization is to apply statistical methods that can generate useful robot responses in situations for which the robot has not been specifically instructed how to respond. In this paper we propose a methodology for the statistical generalization of the available sensorimotor knowledge in real-time. Example trajectories are generalized by applying Gaussian process regression, using the parameters describing a task as query points into the trajectory database. We show on real-world tasks that the proposed methodology can be integrated into a sensory feedback loop, where the generalization algorithm is applied in real-time to adapt robot motion to the perceived changes of the external world.     

Combining path planners and motion graphs

Natural locomotion of virtual characters is very important in games and simulations. The naturalness of the total motion strongly depends on both the path the character chooses and the animation of the walking character. Therefore, much work has been done on path planning and generating walking animations. However, the combination of both fields has received less attention. Combining path planning and motion synthesis introduces several problems. In this paper, we will identify two problems and propose possible solutions. The first problem is selecting an appropriate distance metric for locomotion synthesis. When concatenating clips of locomotion, a distance metric is required to detect good transition points. We have evaluated three common distance metrics both quantitatively (in terms of footskating, path deviation and online running time) and qualitatively (user study). Based on our observations, we propose a set of guidelines when using these metrics in a motion synthesizer. The second problem is the fact that there is no single point on the body that can follow the path generated by the path planner without causing unnatural animations. This raises the question how the character should follow the path. We will show that enforcing the pelvis to follow the path will lead to unnatural animations and that our proposed solution, which uses path abstractions, generates significantly better animations. Copyright © 2011 John Wiley & Sons, Ltd.     

A characterization of database graphs admitting a simple locking protocol

Summary A simple locking protocol is presented for transactions executing concurrently in a database. The locking protocol is not two-phase, but each entity in the database may be locked at most once by any transaction. The database is modeled by a directed graph whose vertices correspond to the entities, and whose arcs correspond to certain locking restrictions. Necessary and sufficient conditions which assure serializability and deadlock-freedom in the absence of a concurrency control are derived.     

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.     

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.     

An RFID anti-collision algorithm with dynamic condensation and ordering binary tree

In many RFID applications, the reader repeatedly identifies the same staying tags. Existing anti-collision protocols can rapidly identify the staying tags by remembering the order in which the tags were recognized in the previous identification process. This paper proposes a novel protocol, dynamic blocking adaptive binary splitting (DBA), based on the blocking mechanism, which prevents the newly-arriving tags from colliding with the staying tags. Moreover, DBA utilizes a dynamic condensation technique to reduce the number of idle slots produced when recognized tags leave. Following the condensation process, multiple staying tags may be required to share the same slot, and thus may cause collisions among them. Accordingly, an efficient ordering binary tree mechanism is proposed to split the collided tags deterministically according to the order in which they were recognized. The analytical and simulation results show that DBA consistently outperforms previous algorithms in all of the considered environments.     

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.     

A hybrid dynamic motion prediction method for multibody digital human models based on a motion database and motion knowledge

In this paper, we present a novel method to predict human motion, seeking to combine the advantages of both data-based and knowledge-based motion prediction methods. Our method relies on a database of captured motions for reference and introduces knowledge in the prediction in the form of a motion control law, which is followed while resembling the actually performed reference motion. The prediction is carried out by solving an optimization problem in which the following conditions are imposed to the motion: must fulfill the goals of the task; resemble the reference motion selected from the database; follow a knowledge-based dynamic motion control law; and ensure the dynamic equilibrium of the human model, considering its interactions with the environment. In this work, we apply the proposed method to a database of clutch pedal depression motions, and we present the results for three predictions. The method is validated by comparing the results of the prediction to motions actually performed in similar conditions. The predicted motions closely resemble the motions in the validation database and no significant differences have been noted either in the motion’s kinematics or in the motion’s dynamics.     

Recovery point selection on a reverse binary tree task model

An analysis is conducted of the complexity of placing recovery points where the computation is modeled as a reverse binary tree task model. The objective is to minimize the expected computation time of a program in the presence of faults. The method can be extended to an arbitrary reverse tree model. For uniprocessor systems, an optimal placement algorithm is proposed. For multiprocessor systems, a procedure for computing their performance is described. Since no closed form solution is available, an alternative measurement is proposed that has a closed form formula. On the basis of this formula, algorithms are devised for solving the recovery point placement problem. The estimated formula can be extended to include communication delays where the algorithm devised still applies