Converting high probability into nearly-constant time—with applications to parallel hashing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Converting high probability into nearly-constant time—with applications to parallel hashing

Full text

Pdf (1.05 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 307 - 316

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Yossi Matias	Univ. of Maryland, College Park
Uzi Vishkin	Univ. of Maryland, College Park

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 16, Citation Count: 26

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/103418.103453 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	R. Anderson, Parallel algorithms for generating random permutations on a shared memory machine, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.95-102, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97674]
	2	P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States [doi>10.1145/28395.28405]
	3	O.Berkman, J. JdJd, S. Krishnamurthy, R. Thurimella, and U. Vishkin. Some triply-logarithmic parallel algorithms. In Proc. of the 31st IEEE Annual Syrup. on Foundation of Computer Science, pages 871-881, 1990. Also in Fast Routing around a rectangle- in preparation.
	4	O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In Proc. of the 30th IEEE Annual Syrup. on Foundation of Computer Science, pages 196-202, 1989.
	5	J.L. Carter and M.N. Wegman. Universal classes of hash functions. J. Computer and System Sciences, 18:143-154, 1979.
	6	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	7	Richard Cole , Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation, v.81 n.3, p.334-352, June 1989 [doi>10.1016/0890-5401(89)90036-9]
	8	M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R.E. Tarjan. Dynamic perfect hashing: upper and lower bounds. In Proc. of the 29th IEEE Annual Syrup. on Foundation of Computer Science, pages 524- 531, 1988.
	9	M. Dietzfelbinger , F. Meyer auf der Heide, An optimal parallel dictionary, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.360-368, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72974]
	10	M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
	11	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]
	12	J. Gil. Fast load balancing on PRAM. Manuscript, 1990.
	13	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
	14	J. Gil, Y. Matias, and U. Vishkin. A fast parallel dictionary. In preparation, 1990.
	15	J. Gil , F. Meyer auf der Heide , A. Wigderson, Not all keys can be hashed in constant time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.244-253, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100247]
	16	J. Gil and L. Rudolph. Counting and packing in parallel. In Proc. 1986 International Conference on Parallel Processing, pages 1000-1002, 1986.
	17	Torben Hagerup, Constant-time parallel integer sorting, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.299-306, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103452]
	18	Torben Hagerup, Fast parallel generation of random permutations, Proceedings of the 18th international colloquium on Automata, languages and programming, p.405-416, June 1991, Madrid, Spain
	19	Torben Hagerup , Manfred Nowak, Parallel Retrieval of Scattered Information, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.439-450, July 11-15, 1989
	20	Y. Han, Matching partition a linked list and its optimization, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.246-253, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72961]
	21	J. J~J#. Introduction to Parallel Algorithms. Addison-Wesley, Reading, MA, 1991.
	22	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	23	C.P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. on Computers, C-32:942-946, 1983.
	24	Yossi Matias , Uzi Vishkin, On parallel hashing and integer sorting, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.729-743, July 1990, Warwick University, England
	25	G.L. Miller and J.H. Reif. Parallel tree contraction and its application. In Proc. of the 26th IEEE Annual Syrup. on Foundation of Computer Science, pages 478-489, 1985.
	26	P. Ragde, The parallel simplicity of compaction and chaining, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.744-751, July 1990, Warwick University, England
	27	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	28	Rajeev Raman, The power of Collision: randomized parallel algorithms for chaining and integer sorting, Proceedings of the tenth conference on Foundations of software technology and theoretical computer science, p.161-175, November 1990, Bangalore, India
	29	R. Raman. Optimal sub-logarithmic time integer sorting on a CRCW P RAM (note). Submitted for publication, 1991.
	30	j.H. Reif. An optimal parallel algorithm for integer sorting. In Proc. of the 26th IEEE Annual Symp. on Foundation of Computer Science, pages 496- 503, 1985.
	31	G. E. Shannon, Optimal on-line load balancing, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.235-245, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72960]
	32	Uzi Vishkin, Randomized speed-ups in parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.230-239, December 1984 [doi>10.1145/800057.808686]

CITED BY 26

	Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States
	Artur Czumaj , Przemka Kanarek , Mirosław Kutyłowski , Krzyztof Loryś, Delayed path coupling and generating random permutations via distributed stochastic processes, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 17-19, 1999, Baltimore, Maryland, United States
	Philip D. MacKenzie, Load balancing requires &OHgr;(log*n) expected time, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.94-99, September 1992, Orlando, Florida, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	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
	Susanne Albers , Torben Hagerup, Improved parallel integer sorting without concurrent writing, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.463-472, September 1992, Orlando, Florida, United States
	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada
	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Efficient low-contention parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.236-247, June 27-29, 1994, Cape May, New Jersey, United States
	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	Philip D. MacKenzie , Quentin F. Stout, Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.224-229, June 30-July 02, 1993, Velen, Germany
	Torben Hagerup, Constant-time parallel integer sorting, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.299-306, May 05-08, 1991, New Orleans, Louisiana, United States
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999
	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, United States
	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany
	Yossi Matias , Jeffrey Scott Vitter , Wen-Chun Ni, Dynamic generation of discrete random variates, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.361-370, January 25-27, 1993, Austin, Texas, United States
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel convex hulls for d≤3: optimal sublogarithmic algorithms for small outputs, Proceedings of the twelfth annual symposium on Computational geometry, p.176-185, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	Bogdan S. Chlebus , Dariusz R. Kowalski, Randomization helps to perform independent tasks reliably, Random Structures & Algorithms, v.24 n.1, p.11-41, January 2004
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States
	Michael T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.767-776, January 05-07, 1997, New Orleans, Louisiana, United States
	Torben Hagerup, Fast deterministic processor allocation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.1-10, January 25-27, 1993, Austin, Texas, United States
	Leslie Ann Goldberg , Mark Jerrum , Tom Leighton , Satish Rao, A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.300-309, June 30-July 02, 1993, Velen, Germany
	Stefano Leonardi , Alberto Marchetti-Spaccamela , Friedhelm Meyer auf der Heide, Scheduling against an adversarial network, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain