Fringe analysis of synchronized parallel algorithms on 2-3 trees

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Baeza Yates, Ricardo
• dc.contributor.author Gabarró Vallès, Joaquim
• dc.contributor.author Messeguer, Xavier
• dc.date.accessioned 2021-02-08T09:31:11Z
• dc.date.available 2021-02-08T09:31:11Z
• dc.date.issued 1998
• dc.description Comunicació presentada a: International Workshop on Randomization and Approximation Techniques in Computer Science celebrat del 8 al 10 d'octubre de 1998 a Barcelona.
• dc.description.abstract We are interested in the fringe analysis of synchronized parallel insertion algorithms on 2–3 trees, namely the algorithm of W. Paul, U. Vishkin and H. Wagener (PVW). This algorithm inserts keys into a tree of size n with parallel time O(log n + log k). Fringe analysis studies the distribution of the bottom subtrees and it is still an open problem for parallel algorithms on search trees. To tackle this problem we introduce a new kind of algorithms whose two extreme cases seems to upper and lower bounds the performance of the PVW algorithm. We extend the fringe analysis to parallel algorithms and we get a rich mathematical structure giving new interpretations even in the sequential case. The process of insertions is modeled by a Markov chain and the coefficients of the transition matrix are related with the expected local behavior of our algorithm. Finally, we show that this matrix has a power expansion over (n+1) -1 where the coefficients are the binomial transform of the expected local behavior. This expansion shows that the parallel case can be approximated by iterating the sequential case.en
• dc.description.sponsorship Partially supported by ACI-CONICYT through Catalunya-Chile Cooperation Program (DOG 2320-30.1.1997) and RITOS network (CYTED) and ESPRIT Long Term Research Project no. 20244-ALCOM IT and DGICYT under grant PB95-0787 (project KOALA) and CICIT TIC97-1475-CE and CIRIT 1997SGR-00366.
• dc.format.mimetype application/pdf
• dc.identifier.citation Baeza-Yates R, Gabarró Vallès J, Messeguer Peypoch X. Fringe analysis of synchronized parallel algorithms on 2-3 trees. In: Luby M, Rolim J, Serna M, editors. Randomization and Approximation Techniques in Computer Science. International Workshop on Randomization and Approximation Techniques in Computer Science; 1998 Oct 8-10; Barcelona, Spain. Berlin: Springer; 1998. p 131-44. DOI: 10.1007/3-540-49543-6_11
• dc.identifier.doi http://dx.doi.org/10.1007/3-540-49543-6_11
• dc.identifier.uri http://hdl.handle.net/10230/46377
• dc.language.iso eng
• dc.publisher Springer
• dc.relation.ispartof Luby M, Rolim J, Serna M, editors. Randomization and Approximation Techniques in Computer Science. International Workshop on Randomization and Approximation Techniques in Computer Science; 1998 Oct 8-10; Barcelona, Spain. Berlin: Springer; 1998. p 131-44
• dc.rights © Springer The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-49543-6_11
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.keyword Fringe analysisen
• dc.subject.keyword Parallel algorithmsen
• dc.subject.keyword 2–3 treesen
• dc.subject.keyword Binomial transformen
• dc.title Fringe analysis of synchronized parallel algorithms on 2-3 treesen
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/acceptedVersion