Parallel priority queue and list contraction: The BSP approach

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis, Alexandre Tiskin

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


In this work we present efficient and practical randomized data structures on the Bulk-Synchronous Parallel (BSP) model of computation along with an experimental study of their performance. In particular, we study data structures for the realization of Parallel Priority Queues (PPQs). We show that our algorithms are communication efficient and achieve optimality to within small multiplicative constant factors for a wide range of parallel machines. We also present an experimental study of our PPQ algorithms on a Cray T3D. Finally, we present new randomized and deterministic BSP algorithms for list and tree contraction.

Original languageEnglish (US)
Pages (from-to)59-90
Number of pages32
JournalComputing and Informatics
Issue number1
StatePublished - 2002

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics


  • BSP model
  • Hashing
  • List contraction
  • List ranking
  • Parallel priority queues
  • Randomized algorithms
  • Randomized data structures
  • Tree contraction


Dive into the research topics of 'Parallel priority queue and list contraction: The BSP approach'. Together they form a unique fingerprint.

Cite this