It is shown that structural similarity between proteins can be decided well with much less information than what is used in common similarity measures. The full Cα representation contains redundant information because of the inherent chain topology of proteins and a limit on their compactness due to excluded volume. A wavelet analysis on random chains and proteins justifies approximating subchains by their centers of mass. For not too compact chain-like structures in general, and proteins in particular, similarity measures that use this approximation are highly correlated to the exact similarity measures and are therefore useful, e.g., as fast filters. Experimental results with such simplified similarity measures in two applications, nearest neighbor search and automatic structural classification show a significant speed up.

The kinematic chain is a ubiquitous and extensively studied representation in robotics as well as a useful model for studying the motion of biological macro-molecules. Both fields stand to benefit from algorithms for efficient maintenance and collision detection in such chains. This paper introduces a novel hierarchical representation of a kinematic chain allowing for efficient incremental updates and relative position calculation. A hierarchy of oriented bounding boxes is superimposed on this representation, enabling high performance collision detection, self-collision testing, and distance computation. This representation has immediate applications in the field of molecular biology, for speeding up molecular simulations and studies of folding paths of proteins. It could be instrumental in path planning applications for robots with many degrees of freedom, also known as hyper-redundant robots. A comparison of the performance of the algorithm with the current state of the art in collision detection is presented for a number of benchmarks.

This paper addresses the problem of designing scalable concurrent priority queues for large scale multiprocessors machines with up to several hundred processors. Priority queues are fundamental in the design of modern multiprocessor algorithms, with many classical applications ranging from numerical algorithms through discrete event simulation and expert systems. While highly scalable approaches have been introduced for the special case of queues with a fixed set of priorities, the most efficient designs for the general case are based on the parallelization of the heap data structure. Though numerous intricate heap-based schemes have been suggested in the literature, their scalability seems to be limited to small machines in the range of ten to twenty processors. This paper proposes an alternative approach: to base the design of concurrent priority queues on the probabilistic skiplist data structure, rather than on a heap. To this end, we show that a concurrent skiplist structure, following a simple set of modifications, provides a concurrent priority queue with a higher level of parallelism and significantly less contention than the fastest known heap-based algorithms. Our initial empirical evidence, collected on a simulated 256 node shared memory multiprocessor architecture similar to the MIT Alewife, suggests that the new skiplist based priority queue algorithm scales significantly better than heap based schemes throughout most of the concurrency range. With 256 processors, they are about twice as fast in performing deletions and up to 8 times faster in performing insertions.