Abstract
Fringe analysis uses the distribution of bottom subtrees or fringe
of search trees under the assumption of random insertion of keys,
yielding an average case analysis of the fringe. The results in the
fringe give upper and lower bounds for several measures for the whole
tree. We are interested in the fringe analysis of the synchronized
parallel insertion algorithms of Paul, Vishkin, and Wagener (PVW)
on 2–3 trees. This algorithm inserts k keys with k processors into
a tree of size n with time O(log n+log k). As the direct analysis
of this algorithm is very difficult we tackle this problem by introducing
a new family of algorithms, denoted by MacroSplit algorithms, and
our main theorem proves that two algorithms of this family, denoted
MaxMacroSplit and MinMacroSplit, bound the behavior of the fringe
in the \PVW\ algorithm. Previous work deals with the fringe analysis
of sequential algorithms, but this type of analysis was still an
open problem for parallel algorithms on search trees. We extend fringe
analysis to parallel algorithms and we get a rich mathematical structure
giving new interpretations even in the sequential case. We prove
that random insertion of keys generates a binomial distribution,
that the synchronized insertion of keys can be modeled by a Markov
chain, and that the coefficients of the transition matrix of the
Markov chain are related to the expected local behavior of our algorithm.
Finally, we show that the coefficients of the power expansion of
this matrix over (n+1)−1 are the binomial transform of the expected
local behavior of the algorithm. We finally show that the fringe
of the \PVW\ algorithm asymptotically converges to the sequential
case.
Users
Please
log in to take part in the discussion (add own reviews or comments).