dc.contributor |
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
dc.contributor |
Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
dc.contributor |
Universitat Politècnica de Catalunya. CEBIM - Centre de Biotecnologia Molecular |
dc.contributor.author |
Baeza-Yates, R. |
dc.contributor.author |
Gabarró Vallès, Joaquim |
dc.contributor.author |
Messeguer Peypoch, Xavier |
dc.date |
1998-06-02 |
dc.identifier.uri |
http://hdl.handle.net/2117/98213 |
dc.language.iso |
eng |
dc.relation |
LSI-98-37-R |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
dc.title |
Fringe analysis of synchronized parallel algorithms on 2--3 trees |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
We are interested in the fringe analysis of synchronizedparallel insertion algorithms on 2--3 trees, namely the algorithm ofW. Paul, U. Vishkin and H. Wagener~(PVW). This algorithminserts k keys into a tree of size n with parallel time O(logn+log k).Fringe analysis studies the distribution of the bottom subtreesand it is still an open problem for parallel algorithms on searchtrees. To tackle this problem we introduce a new kind of algorithmswhose two extreme cases upper and lower bounds the performanceof the PVW algorithm.We extend the fringe analysis to parallel algorithms and we get a richmathematical structure giving new interpretations even in thesequential case. The process of insertions is modeled by a Markovchain and the coefficients of the transition matrix are related withthe expected local behavior of our algorithm.Finally, we show that this matrix has a powerexpansion over (n+1)^{-1} where the coefficients are the binomialtransform of the expected local behavior. This expansion shows thatthe parallelcase can be approximated by iterating the sequential case. |