Optimal parallel string algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel string algorithms: sorting, merging and computing the minimum

Full text

Pdf (1.26 MB)

Source

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

Montreal, Quebec, Canada

Pages: 382 - 391

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Torben Hagerup

Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 35, Citation Count: 2

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/195058.195202 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	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	2	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
	3	N. Alon and N. Megiddo. Parallel linear programming in fixed dimension almost surely in constant time. In Proc. 31st Ann. Syrup. on Foundatzons of Computer Science, pages 574-582, 1990.
	4	Yossi Azar , Uzi Vishkin, Tight comparison bounds on the complexity of parallel sorting, SIAM Journal on Computing, v.16 n.3, p.458-464, June 1987 [doi>10.1137/0216032]
	5	Holger Bast , Martin Dietzfelbinger , Torben Hagerup, A Perfect Parallel Dictionary, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.133-141, August 24-28, 1992
	6	Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989 [doi>10.1145/65950.65958]
	7	Omer Berkman , Baruch Schieber , Uzi Vishkin, Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values, Journal of Algorithms, v.14 n.3, p.344-370, May 1993 [doi>10.1006/jagm.1993.1018]
	8	Omer Berkman , Uzi Vishkin, Recursive star-tree parallel data structure, SIAM Journal on Computing, v.22 n.2, p.221-242, April 1993 [doi>10.1137/0222017]
	9	P. C. P. Bhatt , K. Diks , T. Hagerup , V. C. Prasad , T. Radzik , S. Saxena, Improved deterministic parallel integer sorting, Information and Computation, v.94 n.1, p.29-47, Sept. 1991 [doi>10.1016/0890-5401(91)90031-V]
	10	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	11	V. Chvgtal. Lecture notes on the new AKS sorting network. DIMACS Tech. Report 92-29, Rutgers University, New Brunswick, NJ, 1992.
	12	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]
	13	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	14	M. Dietzfelbinger , M. Kutylowski , R. Reischuk, Exact time bounds for computing boolean functions on PRAMs without simultaneous writes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.125-135, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97678]
	15	F E Fich , F Meyer auf der Heide , P Ragde , A Wigderson, One, two, three . . . infinity: lower bounds for parallel computation, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.48-58, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22151]
	16	Faith E. Fich , Prabhakar Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal on Computing, v.17 n.3, p.606-627, June 1988 [doi>10.1137/0217037]
	17	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
	18	Torben Hagerup , Ola Petersson, Merging and Sorting Strings in Parallel, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.298-306, August 24-28, 1992
	19	T. Hagerup and R. Raman. Waste makes haste: Tight bounds for loose parallel sorting. In Proc. 33rd Ann. Syrup. on Foundations o} Computer Science, pages 628-637, 1992.
	20	Torben Hagerup , Rajeev Raman, Fast deterministic approximate and exact parallel sorting, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.346-355, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.157380]
	21	Joseph F. JáJá , Kwan Woo Ryu, An efficient parallel algorithm for the single function coarsest partition problem, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.230-239, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165261]
	22	Joseph JáJá , Kwan Woo Ryu , Uzi Vishkin, Sorting strings and constructing digital search trees in parallel, University of Maryland at College Park, College Park, MD, 1993
	23	S.K. Kim. Optimal parallel algorithms on sorted intervals. Tech. Report 90-01-04, Dept. of Computer Science and Engineering, University of Washington, Seattle, WA, 1990.
	24	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
	25	C.P. Kruskal. Searching, merging, and sorting in parallel computation. IEEE Trans. Comput., C-32:942-946, 1983.
	26	Philip D. MacKenzie , Quentin F. Stout, Ultra-fast expected time parallel algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.414-423, January 28-30, 1991, San Francisco, California, United States
	27	K. Mehlhorn. Data Structures and Algorithms, Vol. 1: Sorting and Searching. Springer-Verlag, Berlin, Germany, 1984.
	28	M. S. Paterson. Improved sorting networks with O(logN) depth. Algorithm,ca, 5:75-92, 1990.
	29	Nicholas Pippenger, Communication networks, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	30	Prabhakar Ragde, The parallel simplicity of compaction and chaining, Journal of Algorithms, v.14 n.3, p.371-380, May 1993 [doi>10.1006/jagm.1993.1019]
	31	Y. Shiloach and U. Vishkin. Finding the maximum, merging, and sorting in a parallel computation model. }. Algorithms, 2:88-102, 1981.
	32	R.E. Tarjan and U. Vishkin. An efficient parallel biconncctivity algorithm. SIAM J. Comput., 14:862-874, 1985.
	33	R. Vaidyanathan, C. R. P. Hartmann, and P. K. Varslmey. Optimal parallel lexicographic sorting usiag a fine-grained decomposition. Tech. Report SU-CIS-91-01, School of Computer and Information Science, Syracuse University, Syracuse, NY, 1991.
	34	L.G. Valiant. Parallelism in comparison problems. SIAM }. Comput., 4:348-355, 1975.
	35	Jean Vuillemin, A unifying look at data structures, Communications of the ACM, v.23 n.4, p.229-239, April 1980 [doi>10.1145/358841.358852]
	36	H. Wagener, Triangulating a monotone polygon in parallel, Proceedings on International Workshop on Computational Geometry on Computational Geometry and its Applications, p.136-147, October 1988, Wu:9Airzburg, Germany
	37	H. Wagener. Personal commurScation, October 1990.
	38	R.A. Wagner and Y. Han. Parallel algorithms for bucket sortin$ and the data z#cpendent prc#x problem. In Proc. 1986 International Con}. on Parallel Processing, pages 924- 930, 1986.

CITED BY 2

	Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States