Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/98213

Fringe analysis of synchronized parallel algorithms on 2--3 trees
Baeza-Yates, R.; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals; Universitat Politècnica de Catalunya. CEBIM - Centre de Biotecnologia Molecular
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.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Bougé, Luc; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Schabanel, Nicolas
Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Daniel, Riu
Baeza-Yates, Ricardo; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier
Bouge, L; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Schabanel, N