Optimal parallel suffix tree construction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel suffix tree construction

Full text

Pdf (1.09 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: 290 - 299

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Ramesh Hariharan

Courant Institute, New York University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 50, Citation Count: 1

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.195162 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.

	A85	A. Apostolico. The myriad virtues of subword trees. Combinatorial Algorithms on Words, Editors: A. Apostilico and Z. Galil, NATO-ASI series F: Computer and System Sciences, Vol. 12, Springer-Verlag, 1985, pp. 85-96.
	AILSV86	A. Apostolico, C. Iliopoulos, G. Landau, B. Schieber, U. Vishkin. Parallel construction of a suffix tree with applications. Algomthmica, 3, 1988, pp. 347-365.
	AP83	A. Apostolico, F. Preparata. Optimal offline detection of repetitions in a string. Theoretical Computer Science, 22, 1983, pp. 297-315.
	AP85	A Apostolico , F P Preparata, Structural properties of the string statistics problem, Journal of Computer and System Sciences, v.31 n.3, p.394-411, December 1985 [doi>10.1016/0022-0000(85)90060-1]
	CHM86	B. Clift, D. Haussler, R. McConnell, T.D. Schneider, G.D. Stormo. Sequence Landscapes. Nucleic Acids Researc#5 4, 1, 1986, pp. 141-158.
	C88	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	FHM93	M. Farach, R. Hariharan, S. Muthukrishnan. Optimal parallel randomized suffix tree construction, Work in progress.
	KLP89	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72977]
	KMR72	Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
	LV86	G M Landau , U Vishkin, Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.220-230, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12152]
	M76	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	MP93	S. Muthukrishnan , K. Palem, Highly efficient dictionary matching in parallel, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.69-78, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165239]
	RPE81	Michael Rodeh , Vaughan R. Pratt , Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM (JACM), v.28 n.1, p.16-24, Jan. 1981 [doi>10.1145/322234.322237]
	SV88	Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
	SV93	Sühleyman Cenk Sahinalp , Uzi Vishkin, Symmetry breaking for suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.300-309, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195164]
	W73	P. Weiner. Linear pattern matching algorithm. Proc. of the 14th IEEE Symposium on Switching and Automata Theory, 1973, pp. 1-11.