Fast parallel algorithms for processing of joins

Dennis Shasha, Paul Spirakis

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationSupercomputing - 1st International Conference, Proceedings
EditorsTheodore S. Papatheodorou, Constantine D. Polychronopoulos, Elias N. Houstis
PublisherSpringer Verlag
Pages939-953
Number of pages15
ISBN (Print)9783540189916
DOIs
StatePublished - 1988
Event1st International Conference on Supercomputing, 1987 - Athens, Greece
Duration: Jun 8 1987Jun 12 1987

Publication series

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

Other

Other1st International Conference on Supercomputing, 1987
CountryGreece
CityAthens
Period6/8/876/12/87

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Fast parallel algorithms for processing of joins'. Together they form a unique fingerprint.

Cite this