The Horton–Strahler ordering method, originating in hydrology, formulates the hierarchical structure of branching patterns using a quantity called the bifurcation ratio. The main result of this paper is the central limit theorem for the bifurcation ratio of a general branch order. This is a generalized form of the central limit theorem for the lowest bifurcation ratio, which was previously proved. Some useful relations regarding the Horton–Strahler analysis are also derived in the proofs of the main theorems.

Considering a random binary tree with n labelled leaves, we use a pruning procedure on this tree in order to construct a β(3/2,1/2)-coalescent process. We also use the continuous analogue of this construction, i.e. a pruning procedure on Aldous's continuum random tree, to construct a continuous state space process that has the same structure as the β-coalescent process up to some time change. These two constructions enable us to obtain results on the coalescent process, such as the asymptotics on the number of coalescent events or the law of the blocks involved in the last coalescent event.

Map matching is an important algorithm for any location-based service, especially in navigation and tracking systems and services. Identifying the relevant road segments accurately and efficiently, given positioning data, is the first and most important step in any map matching algorithm. This paper proposes a new approach to searching for road candidates by clustering and then searching road segments through a constructed hierarchical clustering tree, rather than using indexing techniques to query segments within a fixed search window. A binary tree is created based on the hierarchical clustering tree and adaptive searches are conducted to identify candidate road segments given GPS positions. The approach was validated using road maps with different scales and various scenarios in which moving vehicles were located. Both theoretical analysis and experimental results confirm that the proposed approach can efficiently find candidate road segments for map matching.

An open ended list is a well known data structure in Prolog programs. It is frequently used to represent a value changing over time, while this value is referred to from several places in the data structure of the application. A weak point in this technique is that the time complexity is linear in the number of updates to the value represented by the open ended list. In this programming pearl we present a variant of the open ended list, namely an open ended tree, with an update and access time complexity logarithmic in the number of updates to the value.

A partially ordered set P is said to have the n-cutset property if for every element x of P, there is a subset S of P all of whose elements are noncomparable to x, with |S| ≤ n, and such that every maximal chain in P meets {x} ∪ S. It is known that if P has the n-cutset property then P has at most 2n maximal elements. Here we are concerned with the extremal case. We let Max P denote the set of maximal elements of P. We establish the following result. THEOREM: Let n be a positive integer. Suppose P has the n-cutset property and that |Max P| = 2n. Then P contains a complete binary tree T of height n with Max T = Max P and such that C ∩ T is a maximal chain in T for every maximal chain C of P. Two examples are given to show that this result does not extend to the case when n is infinite. However the following is shown. THEOREM: Suppose that P has the ω-cutset property and that |Max P| = 2ω. If P — Max P is countable then P contains a complete binary tree of height ω