An optimal parallel dictionary

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An optimal parallel dictionary

Full text

Pdf (892 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the first annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Fe, New Mexico, United States

Pages: 360 - 368

Year of Publication: 1989

ISBN:0-89791-323-X

Authors

M. Dietzfelbinger	Fachbereich 17 - Mathematik - Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of Germany
F. Meyer auf der Heide	Fachbereich 17 - Mathematik - Informatik, Universität-GH Paderborn, D-4790 Paderborn, Fed. Rep. of Germany

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 19, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/72935.72974 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	[AV] Angluin, D., and Valiant, L. G., Fast probabilistic algorithms for Hamiltonian circuits and matchings, JCSS 18, 1979, 155-193.
	2	[DKM] Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., Tarjan, R. E., Dynamic perfect hashing: Upper and lower bounds, Proceedings of the 29th IEEE FOCS, 1988, pp. 524-531.
	3	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	4	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
	5	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A Complexity Theory of Efficient Parallel Algorithms (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.333-346, July 11-15, 1988
	6	Wolfgang J. Paul , Uzi Vishkin , Hubert Wagener, Parallel Dictionaries in 2-3 Trees, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.597-609, July 18-22, 1983
	7	[R] Ranade, A. G., How to emulate shared memory, Proceedings of the 28th IEEE FOCS, 1987, pp. 185-194.
	8	Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]

CITED BY 5

	Holger Bast , Torben Hagerup, Fast and reliable parallel hashing, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.50-61, July 21-24, 1991, Hilton Head, South Carolina, United States
	M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States
	Abhiram Ranade, Maintaining dynamic ordered sets on processor networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 29-July 01, 1992, San Diego, California, United States
	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States
	Joseph Gil , Yossi Matias, Fast hashing on a PRAM—designing by expectation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 28-30, 1991, San Francisco, California, United States