Standard

Parallel priority queue and list contraction: The BSP approach. / Gerbessiotis, Alexandros V.; Siniolakis, Constantinos J.; Tiskin, Alexandre.

In: Computing and Informatics, Vol. 21, No. 1, 01.01.2002, p. 59-90.

Research output: Contribution to journal › Article › peer-review

Harvard

Gerbessiotis, AV, Siniolakis, CJ & Tiskin, A 2002, 'Parallel priority queue and list contraction: The BSP approach', Computing and Informatics, vol. 21, no. 1, pp. 59-90.

APA

Gerbessiotis, A. V., Siniolakis, C. J., & Tiskin, A. (2002). Parallel priority queue and list contraction: The BSP approach. Computing and Informatics, 21(1), 59-90.

Vancouver

Gerbessiotis AV, Siniolakis CJ, Tiskin A. Parallel priority queue and list contraction: The BSP approach. Computing and Informatics. 2002 Jan 1;21(1):59-90.

Author

Gerbessiotis, Alexandros V. ; Siniolakis, Constantinos J. ; Tiskin, Alexandre. / Parallel priority queue and list contraction: The BSP approach. In: Computing and Informatics. 2002 ; Vol. 21, No. 1. pp. 59-90.

BibTeX

@article{346018c71a734ded9643124aa694a7f6,
title = "Parallel priority queue and list contraction: The BSP approach",
abstract = "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.",
keywords = "BSP model, Hashing, List contraction, List ranking, Parallel priority queues, Randomized algorithms, Randomized data structures, Tree contraction",
author = "Gerbessiotis, {Alexandros V.} and Siniolakis, {Constantinos J.} and Alexandre Tiskin",
year = "2002",
month = jan,
day = "1",
language = "English",
volume = "21",
pages = "59--90",
journal = "Computing and Informatics",
issn = "1335-9150",
publisher = "Slovak Academy of Sciences",
number = "1",

}

RIS

TY - JOUR

T1 - Parallel priority queue and list contraction: The BSP approach

AU - Gerbessiotis, Alexandros V.

AU - Siniolakis, Constantinos J.

AU - Tiskin, Alexandre

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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.

AB - 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.

KW - BSP model

KW - Hashing

KW - List contraction

KW - List ranking

KW - Parallel priority queues

KW - Randomized algorithms

KW - Randomized data structures

KW - Tree contraction

UR - http://www.scopus.com/inward/record.url?scp=0346677541&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0346677541

VL - 21

SP - 59

EP - 90

JO - Computing and Informatics

JF - Computing and Informatics

SN - 1335-9150

IS - 1

ER -

ID: 127712638