A Study of Sort Algorithms for Multiprocessor Database Machines.

@inproceedings{DBLP:conf/vldb/Menon86,
  author    = {Jai Menon},
  editor    = {Wesley W. Chu and
               Georges Gardarin and
               Setsuo Ohsuga and
               Yahiko Kambayashi},
  title     = {A Study of Sort Algorithms for Multiprocessor Database Machines},
  booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
               August 25-28, 1986, Kyoto, Japan, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1986},
  isbn      = {0-934613-18-4},
  pages     = {197-206},
  ee        = {db/conf/vldb/Menon86.html},
  crossref  = {DBLP:conf/vldb/86},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1986 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb7588 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[BABBE79]

Edward Babb: Implementing a Relational Database by Means of Specialized Hardware. ACM Trans. Database Syst. 4(1): 1-29(1979) BibTeX

[BATCH68]

Kenneth E. Batcher: Sorting Networks and Their Applications. AFIPS Spring Joint Computing Conference 1968: 307-314 BibTeX

[BAUDE78]

...

[BITTO83]

Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983) BibTeX

[BITTO84]

Dina Bitton, David J. DeWitt, David K. Hsiao, Jai Menon: A Taxonomy of Parallel Sorting. ACM Comput. Surv. 16(3): 287-318(1984) BibTeX

[BRATS84]

Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX

[DEWIT79]

David J. DeWitt: Query Execution in DIRECT. SIGMOD Conference 1979: 13-22 BibTeX

[GARDA81]

...

[HIRSC78]

Daniel S. Hirschberg: Fast Parallel Sorting Algorithms. Commun. ACM 21(8): 657-661(1978) BibTeX

[HSIAO80]

...

[KNUTH73]

Donald E. Knuth: The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition. Addison-Wesley 1973
BibTeX

[MENON86]

...

[MULLE75]

David E. Muller, Franco P. Preparata: Bounds to Complexities of Networks for Sorting and for Switching. J. ACM 22(2): 195-201(1975) BibTeX

[NASSI78]

...

[PREPA78]

...

[STONE71]

...

[THOMP77]

Clark D. Thompson, H. T. Kung: Sorting on a Mesh-Connected Parallel Computer. Commun. ACM 20(4): 263-271(1977) BibTeX

[VALDU84]

Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) BibTeX

[VALIA75]

Leslie G. Valiant: Parallelism in Comparison Problems. SIAM J. Comput. 4(3): 348-355(1975) BibTeX

Referenced by

1. Sven Helmer, Till Westmann, Guido Moerkotte: Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships. VLDB 1998: 98-109
2. Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
3. Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994)
4. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)