Symmetry breaking for suffix tree construction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Symmetry breaking for suffix tree construction

Full text

Pdf (958 KB)

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: 300 - 309

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Sühleyman Cenk Sahinalp	Department of Computer Science, University of Maryland, College Park, MD
Uzi Vishkin	Institute for Advanced Computer Studies and Department of Electrical Engineering, University of Maryland, College Park, MD

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	AILSV88	A. Apostolico, C. Iliopoulos, G. M. Landau, B. Schieber, and U. Vishkin, Parallel Construction of a Suffix Tree with Applications, In Algorithmica, 3: 347-365, 1988.
	BV88	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]
	BDHPRS89	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]
	BLMPSZ91	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
	CV86a	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]
	CV86b	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	Ga85	Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
	Ja92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	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]
	LZ77	J. Ziv, and A. Lempel, A Universal Algorithm for Sequential Data Compression In IEEE Transactions on Information Theory, 23: 337-343, 1977.
	MV91	Yossi Matias , Uzi Vishkin, Parallel hashing and integer sorting, Journal of Algorithms, v.12 n.4, p.573-606, Dec. 1991 [doi>10.1016/0196-6774(91)90034-V]
	Mc76	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]
	MSU94	K. Mehlhorn , R. Sundar , C. Uhrig, Maintaining dynamic sequences under equality-tests in polylogarithmic time, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.213-222, January 23-25, 1994, Arlington, Virginia, United States
	SV94	S. C..Sahinalp, and U. Vishkin, Symmetry Breaking in Suffix Tree Construction, In preparation
	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]
	Vi85	Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80028-0]
	Vi91	Uzi Vishkin, Deterministic sampling: a new technique for fast pattern matching, SIAM Journal on Computing, v.20 n.1, p.22-40, Feb. 1991 [doi>10.1137/0220002]
	We73	P. Weiner, Linear Pattern Matching Algorithm, In Proceedings o/the latexstoc, f inal.4.texl4th IEEE Symposium on Switching and Automata Theory, pages latex stoc.final.4.texl-ll, 1973.

CITED BY 8

	Pilu Crescenzi , Alberto Del Lungo , Roberto Grossi , Elena Lodi , Linda Pagli , Gianluca Rossi, Text sparsification via local maxima, Theoretical Computer Science, v.304 n.1-3, p.341-364, 28 July 2003
	Martin Farach-Colton , Paolo Ferragina , S. Muthukrishnan, On the sorting-complexity of suffix tree construction, Journal of the ACM (JACM), v.47 n.6, p.987-1011, Nov. 2000
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
	Zvi Galil , Jong Geun Park , Kunsoo Park, Three-dimensional pattern matching, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.53-62, June 23-25, 1997, Newport, Rhode Island, United States
	Ramesh Hariharan, Optimal parallel suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.290-299, May 23-25, 1994, Montreal, Quebec, Canada
	Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States
	Luc Devroye , Ralph Neininger, Random suffix search trees, Random Structures & Algorithms, v.23 n.4, p.357-396, December 2003
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005