Parallel construction of multidimensional binary search trees

Multidimensional binary search tree (abbreviated k-d tree) is a popular data structure for the organization and manipulation of spatial data. The data structure is useful in several applications including graph partitioning, hierarchical applications such as molecular dynamics and n-body simulations, and databases. In this paper, we study efficient parallel construction of k-d trees on coarse-grained distributed memory parallel computers. We consider several algorithms for parallel k-d tree construction and analyze them theoretically and experimentally, with a view towards identifying the algorithms that are practically efficient. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on experimental results     

Parallel game-tree search

The design issues affecting a parallel implementation of the alpha-beta search algorithm are discussed with emphasis on a tree decomposition scheme that is intended for use on well ordered trees. In particular, the principal variation splitting method has been implemented, and experimental results are presented which show how such refinements as progressive deepening, narrow window searching, and the use of memory tables affect the performance of multiprocessor based chess playing programs. When dealing with parallel processing systems, communication delays are perhaps the greatest source of lost time. Therefore, an implementation of our tree decomposition based algorithm is presented, one that operates with a modest amount of message passing within a network of processors. Since our system has low search overhead, the principal basis for comparison is the communication overhead, which in turn is shown to have two components.     

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     

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.     

Dynamic weighted binary search trees

Summary We present an algorithm which optimizes a weighted binary tree after an insertion or deletion. The resulting tree is nearly optimal. The algorithm needs O(n) space. In the case of an insertion the expected number of operations is equal to or less than the height of the tree. All results presented in this paper can also be found in [15].     

Reductions in binary search trees

We analyze two bottom-up reduction algorithms over binary trees that represent replaceable data within a certain system, assuming the binary search tree (BST) probabilistic model. These reductions are based on idempotent and nilpotent operators, respectively. In both cases, the average size of the reduced tree, as well as the cost to obtain it, is asymptotically linear with respect to the size of the original tree. Additionally, the limiting distributions of the size of the trees obtained by means of these reductions satisfy a central limit law of Gaussian type.     

Nearly optimal binary search trees

Summary We discuss two simple strategies for constructing binary search trees: Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees and choose the root so as to equalize the total weight of the left and right subtrees as much as possible, then proceed similarly on the subtres. While the former rule may yield extremely inefficient search trees, the latter rule always produces nearly optimal trees.     

The optimal binary search tree for Andersson's search algorithm

Andersson [1] presented a search algorithm for binary search trees that uses only two-way key comparisons by deferring equality comparisons until the leaves are reached. The use of a different search algorithm means that the optimal tree for the traditional search algorithm, which has been shown to be computable inO(n ²) time by Knuth [3], is not optimal with respect to the different search algorithm. This paper shows that the optimal binary search tree for Andersson's search algorithm can be computed inO(nlogn) time using existing algorithms for the special case of zero successful access frequencies, such as the Hu-Tucker algorithm [2].     

Parallel search for LTL violations

Recent advances in parallel model checking for liveness properties achieve significant capacity increases over sequential model checkers. However, the capacity of parallel model checkers is in turn limited by available aggregate memory and network bandwidth. We propose a new parallel algorithm that sacrifices complete coverage for increased capacity to find errors. The algorithm, called BEE (for bee-based error exploration), uses coordinated depth-bounded random walks to reduce memory and bandwidth demands. A unique advantage of BEE is that it is well suited for use on clusters of nondedicated workstations.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

Smoothed analysis of binary search trees

Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity.     

The algebra of binary search trees

We introduce a monoid structure on the set of binary search trees, by a process very similar to the construction of the plactic monoid, the Robinson–Schensted insertion being replaced by the binary search tree insertion. This leads to a new construction of the algebra of planar binary trees of Loday–Ronco, defining it in the same way as non-commutative symmetric functions and free symmetric functions. We briefly explain how the main known properties of the Loday–Ronco algebra can be described and proved with this combinatorial point of view, and then discuss it from a representation theoretical point of view, which in turns leads to new combinatorial properties of binary trees.     

Widening with thresholds via binary search

In this paper, we present a useful technique for implementing practical static program analyzers that use widening. Our technique aims to improve the efficiency of the conventional widening‐with‐thresholds technique at a small precision compromise. In static analysis, widening is used to accelerate (or converge) fixed point iterations. Unfortunately, this acceleration often comes with a significant loss in analysis precision. A standard method to improve the precision is to apply the widening with a set of thresholds. However, this technique may significantly slow down the analysis, because in practice it is commonplace to use a large set of thresholds. In worst case, the technique increases the analysis cost by the size N of the threshold set. In this paper, we propose a technique to reduce the worst case by , by employing a binary search in the process of applying threshold values. We formalize the technique in the abstract interpretation framework and show that, by experiments with a realistic static analyzer for C, our technique considerably improves the efficiency (by 81.5%) of the existing method with a small compromise (20.9%) on the analysis precision. Copyright © 2015 John Wiley & Sons, Ltd.     

改进的RFID二进制搜索防碰撞算法

标签冲突是射频识别技术（RFID）不可避免的问题,在ABS算法和动态调整二进制搜索算法的基础上提出了一种改进的二进制搜索算法,该算法简化了阅读器发送的指令和冲突检测过程,并采用动态方式传输EPC数据。仿真结果表明,相比于目前的二进制搜索算法,这种算法能极大地减少阅读器与标签之间的通信量,有效地提高标签的识别速度,具有良好的应用前景。