Fast parallel algorithms for processing of joins

Dennis Shasha; Paul Spirakis

doi:10.1007/3-540-18991-2_55

Fast parallel algorithms for processing of joins

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

Abstract

We present and analyze here some innovative techniques for processing a join (or a semi-join) in a parallel computing environment. Our algorithms employ perfect hashing and, in some cases, copying of data in a group of processors, or filtering the data as they move through the network. By using the combinatorial properties of hashing we are able to prove almost optimal speedup, with high probability, when some uniformity assumptions hold for the data. Even in the absense of these assumptions our techniques achieve sub-optimal speedup and can be used as practical heuristics.

Original language	English (US)
Title of host publication	Supercomputing - 1st International Conference, Proceedings
Editors	Theodore S. Papatheodorou, Constantine D. Polychronopoulos, Elias N. Houstis
Publisher	Springer Verlag
Pages	939-953
Number of pages	15
ISBN (Print)	9783540189916
DOIs	https://doi.org/10.1007/3-540-18991-2_55
State	Published - 1988
Event	1st International Conference on Supercomputing, 1987 - Athens, Greece Duration: Jun 8 1987 → Jun 12 1987

Publication series

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

Other

Other	1st International Conference on Supercomputing, 1987
Country/Territory	Greece
City	Athens
Period	6/8/87 → 6/12/87

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-18991-2_55

Cite this

Shasha, D., & Spirakis, P. (1988). Fast parallel algorithms for processing of joins. In T. S. Papatheodorou, C. D. Polychronopoulos, & E. N. Houstis (Eds.), Supercomputing - 1st International Conference, Proceedings (pp. 939-953). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 297 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-18991-2_55

Fast parallel algorithms for processing of joins. / Shasha, Dennis; Spirakis, Paul.
Supercomputing - 1st International Conference, Proceedings. ed. / Theodore S. Papatheodorou; Constantine D. Polychronopoulos; Elias N. Houstis. Springer Verlag, 1988. p. 939-953 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 297 LNCS).

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

Shasha, D & Spirakis, P 1988, Fast parallel algorithms for processing of joins. in TS Papatheodorou, CD Polychronopoulos & EN Houstis (eds), Supercomputing - 1st International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 297 LNCS, Springer Verlag, pp. 939-953, 1st International Conference on Supercomputing, 1987, Athens, Greece, 6/8/87. https://doi.org/10.1007/3-540-18991-2_55

Shasha D, Spirakis P. Fast parallel algorithms for processing of joins. In Papatheodorou TS, Polychronopoulos CD, Houstis EN, editors, Supercomputing - 1st International Conference, Proceedings. Springer Verlag. 1988. p. 939-953. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-18991-2_55

Shasha, Dennis ; Spirakis, Paul. / Fast parallel algorithms for processing of joins. Supercomputing - 1st International Conference, Proceedings. editor / Theodore S. Papatheodorou ; Constantine D. Polychronopoulos ; Elias N. Houstis. Springer Verlag, 1988. pp. 939-953 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9febcb9261d340089e63e35bc91bc48a,

title = "Fast parallel algorithms for processing of joins",

abstract = "We present and analyze here some innovative techniques for processing a join (or a semi-join) in a parallel computing environment. Our algorithms employ perfect hashing and, in some cases, copying of data in a group of processors, or filtering the data as they move through the network. By using the combinatorial properties of hashing we are able to prove almost optimal speedup, with high probability, when some uniformity assumptions hold for the data. Even in the absense of these assumptions our techniques achieve sub-optimal speedup and can be used as practical heuristics.",

author = "Dennis Shasha and Paul Spirakis",

note = "Funding Information: This research was supported in part by the NSF grant DCR 8503497 and by the Minis- Publisher Copyright: {\textcopyright} 1988, Springer-Verlag.; 1st International Conference on Supercomputing, 1987 ; Conference date: 08-06-1987 Through 12-06-1987",

year = "1988",

doi = "10.1007/3-540-18991-2_55",

language = "English (US)",

isbn = "9783540189916",

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

publisher = "Springer Verlag",

pages = "939--953",

editor = "Papatheodorou, {Theodore S.} and Polychronopoulos, {Constantine D.} and Houstis, {Elias N.}",

booktitle = "Supercomputing - 1st International Conference, Proceedings",

}

TY - GEN

T1 - Fast parallel algorithms for processing of joins

AU - Shasha, Dennis

AU - Spirakis, Paul

PY - 1988

Y1 - 1988

N2 - We present and analyze here some innovative techniques for processing a join (or a semi-join) in a parallel computing environment. Our algorithms employ perfect hashing and, in some cases, copying of data in a group of processors, or filtering the data as they move through the network. By using the combinatorial properties of hashing we are able to prove almost optimal speedup, with high probability, when some uniformity assumptions hold for the data. Even in the absense of these assumptions our techniques achieve sub-optimal speedup and can be used as practical heuristics.

AB - We present and analyze here some innovative techniques for processing a join (or a semi-join) in a parallel computing environment. Our algorithms employ perfect hashing and, in some cases, copying of data in a group of processors, or filtering the data as they move through the network. By using the combinatorial properties of hashing we are able to prove almost optimal speedup, with high probability, when some uniformity assumptions hold for the data. Even in the absense of these assumptions our techniques achieve sub-optimal speedup and can be used as practical heuristics.

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

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

U2 - 10.1007/3-540-18991-2_55

DO - 10.1007/3-540-18991-2_55

M3 - Conference contribution

AN - SCOPUS:85034817033

SN - 9783540189916

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

SP - 939

EP - 953

BT - Supercomputing - 1st International Conference, Proceedings

A2 - Papatheodorou, Theodore S.

A2 - Polychronopoulos, Constantine D.

A2 - Houstis, Elias N.

PB - Springer Verlag

T2 - 1st International Conference on Supercomputing, 1987

Y2 - 8 June 1987 through 12 June 1987

ER -

Fast parallel algorithms for processing of joins

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this