Communication efficient data structures on the BSP model with applications in computational geometry

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

The implementation of data structures on distributed memory models, like the Bulk-Synchronous Parallel (BSP), rather than shared memory ones, like the PRAM, offers a serious challenge. In this paper we undertake the architecture independent study of the communication and synchronization requirements of searching "ordered h-level graphs", which include most of the standard data structures. We propose n-way search as a general tool for the design, analysis, and implementation of BSP algorithms. This technique allows elegant high-level design and analysis of algorithms, using data structures similar to that of sequential models. Our methods are within a 1 + o(1) factor of the respective sequential methods. An application to computational geometry is also presented.

Original languageEnglish (US)
Title of host publicationEuro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings
EditorsLuc Bouge, Pierre Fraigniaud, Anne Mignotte, Yves Robert
PublisherSpringer Verlag
Pages348-351
Number of pages4
ISBN (Print)3540616276, 9783540616276
DOIs
StatePublished - 1996
Externally publishedYes
Event2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996 - Lyon, France
Duration: Aug 26 1996Aug 29 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1124
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996
CountryFrance
CityLyon
Period8/26/968/29/96

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Communication efficient data structures on the BSP model with applications in computational geometry'. Together they form a unique fingerprint.

Cite this