The continuous and dynamic nature of data streams may lead a query execution plan (QEP) of a long-running continuous query to become suboptimal during execution, and hence will need to be al-tered. The ability to perform an efficient and flawless transition to an equivalent, yet optimal QEP is essential for a data stream query processor. Such transition is challenging for plans with stateful bi-nary operators, such as joins, where the states of the QEP have to be maintained during query transition without compromising the correctness of the query output. This paper presents Just-In-Time State Completion (JISC); a new technique for query plan migration. JISC does not cause any halt to the query execution, and thus allows the query to maintain steady output. JISC is applicable to pipelined as well as eddy-based query evaluation frameworks. Probabilistic analysis of the cost and experimental studies show that JISC in-creases the execution throughput during the plan migration stage by up to an order of magnitude compared to existing solutions. 1.

We study the variety of subtrees lying on the fringe of recursive trees and binary search trees by analyzing the distributional behavior of $X_{n,k}$, which counts the number of subtrees of size k in a random tree of size n, with $k = k(n)$ dependent on n. Using analytic methods we can characterize for both tree families the phase change behavior of $X_{n,k}$ as follows. In the subcritical case, when $k(n)/\sqrt{n} \to 0$, we show that $X_{n,k}$ is (after normalization) asymptotically normally distributed, whereas in the supercritical case, when $k(n)/\sqrt n \to \infty$, $X_{n,k}$ converges to 0. In the critical case, when $k(n) = \Theta(\sqrt{n}\,)$, we show that if $k/\sqrt{n}$ approaches a limit, then $X_{n,k}$ converges in distribution to a Poisson random variable, whereas if $k/\sqrt{n}$ does not approach a finite nonzero limit, the size oscillates and does not converge in distribution to any random variable. In regard to recursive trees and binary search trees, this provides an understanding of the complete spectrum of phases of $X_{n,k}$ and the gradual change from the subcritical to the supercritical phase.

Random search trees are studied when they grow under a general computer memory management scheme. In a general scheme, the space is released in buckets of certain predesignated sizes. For a search tree with branch factor m, the nodes may hold up to $m - 1$ keys. Suppose the buckets of the memory management scheme that can hold less than m keys have key capacities $c_1 , \ldots ,c_r $. The search tree must then be implemented with multitype nodes of these capacities. After n insertions, let $X_n^{(i)} $ be the number of buckets of type i (i.e., of capacity $c_i $,$1 \leqslant i \leqslant p$. The multivariate structure of the tree is investigated. For the vector ${\bf X}_n = ( \leqslant X_n^{(1)} , \ldots ,X_n^{(p)} )^T $, the asymptotic mean and covariance matrix are determined. Under practical memory management schemes, all variances and covariances experience a phase transition: For $3 \leqslant m \leqslant 26$, all variances and covariances are asymptotically linear in n; for higher branch factors the variances and covariances become a superlinear (but ubquadratic) function of n. The joint distribution of ${\bf X}_n $ is shown to be multivariate normal in a range of m. While the tree is growing, conversions between types are necessary. A multivariate problem concerning these conversions with an asymptotic multivariate normal distribution is also studied. The fixed bucket, exact fit, and buddy system allocation schemes will serve as illustrating examples.

Let Vi be the set of vertices of degree, i, i=1,2,3, in a random binary search tree. We prove that E(|Vi|)=n∣3+0(1), for i=1,2,3. This result tells us that the expected tree shape does not contain very long path subgraphs; thus in a sense the expected shape tends to be balanced.