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

Alexandros V. Gerbessiotis; Constantinos J. Siniolakis

doi:10.1007/bfb0024722

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 proceeding › Conference contribution

3 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 language	English (US)
Title of host publication	Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings
Editors	Luc Bouge, Pierre Fraigniaud, Anne Mignotte, Yves Robert
Publisher	Springer Verlag
Pages	348-351
Number of pages	4
ISBN (Print)	3540616276, 9783540616276
DOIs	https://doi.org/10.1007/bfb0024722
State	Published - 1996
Externally published	Yes
Event	2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996 - Lyon, France Duration: Aug 26 1996 → Aug 29 1996

Publication series

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

Other

Other	2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996
Country/Territory	France
City	Lyon
Period	8/26/96 → 8/29/96

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0024722

Cite this

Gerbessiotis, A. V., & Siniolakis, C. J. (1996). Communication efficient data structures on the BSP model with applications in computational geometry. In L. Bouge, P. Fraigniaud, A. Mignotte, & Y. Robert (Eds.), Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings (pp. 348-351). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1124). Springer Verlag. https://doi.org/10.1007/bfb0024722

Gerbessiotis, Alexandros V. ; Siniolakis, Constantinos J. / Communication efficient data structures on the BSP model with applications in computational geometry. Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings. editor / Luc Bouge ; Pierre Fraigniaud ; Anne Mignotte ; Yves Robert. Springer Verlag, 1996. pp. 348-351 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6270dc1363424146bb2463400521f38c,

title = "Communication efficient data structures on the BSP model with applications in computational geometry",

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.",

author = "Gerbessiotis, {Alexandros V.} and Siniolakis, {Constantinos J.}",

note = "Publisher Copyright: {\textcopyright} 1996, Springer Verlag. All rights reserved.; 2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996 ; Conference date: 26-08-1996 Through 29-08-1996",

year = "1996",

doi = "10.1007/bfb0024722",

language = "English (US)",

isbn = "3540616276",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "348--351",

editor = "Luc Bouge and Pierre Fraigniaud and Anne Mignotte and Yves Robert",

booktitle = "Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings",

address = "Germany",

}

Gerbessiotis, AV & Siniolakis, CJ 1996, Communication efficient data structures on the BSP model with applications in computational geometry. in L Bouge, P Fraigniaud, A Mignotte & Y Robert (eds), Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1124, Springer Verlag, pp. 348-351, 2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996, Lyon, France, 8/26/96. https://doi.org/10.1007/bfb0024722

Communication efficient data structures on the BSP model with applications in computational geometry. / Gerbessiotis, Alexandros V.; Siniolakis, Constantinos J.
Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings. ed. / Luc Bouge; Pierre Fraigniaud; Anne Mignotte; Yves Robert. Springer Verlag, 1996. p. 348-351 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1124).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Gerbessiotis, Alexandros V.

AU - Siniolakis, Constantinos J.

PY - 1996

Y1 - 1996

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

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

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

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

U2 - 10.1007/bfb0024722

DO - 10.1007/bfb0024722

M3 - Conference contribution

AN - SCOPUS:84947918727

SN - 3540616276

SN - 9783540616276

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 348

EP - 351

BT - Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings

A2 - Bouge, Luc

A2 - Fraigniaud, Pierre

A2 - Mignotte, Anne

A2 - Robert, Yves

PB - Springer Verlag

T2 - 2nd International Euro-Par Conference on Parallel Processing, Euro-Par 1996

Y2 - 26 August 1996 through 29 August 1996

ER -

Gerbessiotis AV, Siniolakis CJ. Communication efficient data structures on the BSP model with applications in computational geometry. In Bouge L, Fraigniaud P, Mignotte A, Robert Y, editors, Euro-Par 1996 Parallel Processing - 2nd International Euro-Par Conference, Proceedings. Springer Verlag. 1996. p. 348-351. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0024722

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this