Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

Full text

Pdf (1.11 MB)

Source

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

Portland, Oregon, United States

Pages: 397 - 406

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Roberto Grossi	Dipartimento di Informatica, Università di Pisa, 56125 Pisa, Italy
Jeffrey Scott Vitter	Department of Computer Science, Duke University, Durham, NC and I.N.R.I.A. in Sophia Antipolia, France

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 139, Citation Count: 33

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/335305.335351 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	Amihood Amir , Dmitry Keselman , Gad M. Landau , Moshe Lewenstein , Noa Lewenstein , Michael Rodeh, Indexing and Dictionary Matching with One Error, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.181-192, August 11-14, 1999
	2	A. Andersson, N. J. Larsson, and K. Swanson. Suffix trees on words. Algorithmica, 23(3):246-260, 1999.
	3	Arne Andersson , Stefan Nilsson, Efficient implementation of suffix trees, Software—Practice & Experience, v.25 n.2, p.129-141, Feb. 1995 [doi>10.1002/spe.4380250203]
	4	A. Apostolico. The myriad virtues of suffix trees. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume 12 of NATO Advanced Scieace Institutes, Series F, pages 85-96, Springer-Verlag, berlin, 1985.
	5	A. Apostolico, C. Iliopoulos, G. M. Landau, B. Schieber, and U. Vishkin. Parallel construction of a suffix tree with applications. Algorithmica, 3:347-365, 1988.
	6	J. L. Bentley and H. A. Maurer. Efficient worst-case data structures for range searching. Acta Informatica, 13:155-168, 1980.
	7	A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, and J. Seiferas. The smallest automaton recognizing the subwords of a text. Theoretical Computer Science, 40(1):31-55, Sept. 1985.
	8	A. Blumer , J. Blumer , D. Haussler , R. McConnell , A. Ehrenfeucht, Complete inverted files for efficient text retrieval and analysis, Journal of the ACM (JACM), v.34 n.3, p.578-595, July 1987 [doi>10.1145/28869.28873]
	9	Gerth Stølting Brodal , Leszek Gasieniec, Approximate Dictionary Queries, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.65-74, June 10-12, 1996
	10	David Richard Clark, Compact pat trees, University of Waterloo, Waterloo, Ont., Canada, 1998
	11	David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
	12	L. Colussi and A. De Col. A time and space efficient data structure for string searching on large texts. Information Processing Letters, 58(5):217-222, Oct. 1996.
	13	Maxime Crochemore, Transducers and repetitions, Theoretical Computer Science, v.45 n.1, p.63-86, Sept. 1986
	14	Maxime Crochemore , Dominique Perrin, Two-way string-matching, Journal of the ACM (JACM), v.38 n.3, p.650-674, July 1991 [doi>10.1145/116825.116845]
	15	Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
	16	M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.137, October 19-22, 1997
	17	Martin Farach , Paolo Ferragina , S. Muthukrishnan, Overcoming the Memory Bottleneck in Suffix Tree Construction, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.174, November 08-11, 1998
	18	Martin Farach , S. Muthukrishnan, Optimal Logarithmic Time Randomized Suffix Tree Construction, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.550-561, July 08-12, 1996
	19	Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
	20	P. Ferragina and G. Manzini. Personal communication, 2OOO.
	21	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]
	22	Z. Galil and J. Seiferas. Time-space-optimal string matching. Journal of Computer and System Sciences, 26:280-294, 1983.
	23	Robert Giegerich , Stefan Kurtz , Jens Stoye, Efficient Implementation of Lazy Suffix Trees, Proceedings of the 3rd International Workshop on Algorithm Engineering, p.30-42, July 19-21, 1999
	24	Gaston H. Gonnet , Ricardo A. Baeza-Yates , Tim Snider, New indices for text: PAT Trees and PAT arrays, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	25	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	26	R. W. Irving. Suffix binary search trees. Technical Report TR-1995-7, Computing Science Department, University of Glasgow, 1995.
	27	G. Jacobson. Space-efficient static trees and graphs. In IEEE Symposium on Foundations of Computer Science, pages 549-554, 1989.
	28	G. Jacobson. Succinct static data structures. Technical Report CMU-CS-89-112, Dept. of Computer Science, Carnegie-Mellon University, Jan. 1989.
	29	J. KSrkk~inen. Suffix cactus: A cross between suffix tree and suffix array. In Combinatorial Pattern Matching, volume 937 of Lecture Notes in Computer Science, pages 191-204. Springer, 1995.
	30	J. K~rkk~inen and E. Sutinen. Lempel-Ziv index for q-grams. Algorithmica, 21(1):137-154, 1998.
	31	J. K&rkk//inen and E. Ukkonen. Lempel-Ziv parsing and sublinear-size index structures for string matching. In N. Ziviani, R. Baeza-Yates, and K. Guimar&es, editors, Proceedings of the 3rd South American Workshop on String Processing, pages 141-155, Recife, Brazil, 1996. Carleton University Press.
	32	Juha Kärkkäinen , Esko Ukkonen, Sparse Suffix Trees, Proceedings of the Second Annual International Conference on Computing and Combinatorics, p.219-230, June 17-19, 1996
	33	D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:323-350, 1977.
	34	S. Kurtz. Reducing the space requirement of suffix trees. Technical Report 98-03, Universit/~t Bielefeld, 1998.
	35	Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
	36	U. Manber and S. Wu. GLIMPSE: A tool to search through entire file systems. In Proceedings of the USENIX Winter 199~ Technical Conference, pages 23- 32, 1994.
	37	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]
	38	Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
	39	Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
	40	J. Ian Munro, Tables, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.37-42, December 18-20, 1996
	41	J. I. Munro , V. Raman, Succinct representation of balanced parentheses, static trees and planar graphs, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.118, October 19-22, 1997
	42	J. Ian Munro , Venkatesh Raman , S. Srinivasa Rao, Space Efficient Suffix Trees, Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science, p.186-196, December 17-19, 1998
	43	Mark H. Overmars, Efficient data structures for range searching on a grid, Journal of Algorithms, v.9 n.2, p.254-275, June 1988 [doi>10.1016/0196-6774(88)90041-7]
	44	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]
	45	E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, Sept. 1995.
	46	P. Weiner. Linear pattern matching algorithm. Proc. l~th IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973.
	47	D E Willard, On the application of sheared retrieval to orthogonal range queries, Proceedings of the second annual symposium on Computational geometry, p.80-89, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10524]
	48	A. C. Yao and F. F. Yao. Dictionary look-up with small errors. Lecture Notes in Computer Science, 937:387- 394, 1995.
	49	Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998 [doi>10.1145/296854.277632]

CITED BY 33

	Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
	Miklos Ajtai , Randal Burns , Ronald Fagin , Darrell D. E. Long , Larry Stockmeyer, Compactly encoding unstructured inputs with differential compression, Journal of the ACM (JACM), v.49 n.3, p.318-367, May 2002
	Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Veli Mäkinen, Compact suffix array: a space-efficient full-text index, Fundamenta Informaticae, v.56 n.1,2, p.191-210, July 2003
	Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.289-294, January 07-09, 2001, Washington, D.C., United States
	Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003
	Kunihiko Sadakane, New text indexing functionalities of the compressed suffix arrays, Journal of Algorithms, v.48 n.2, p.294-313, September 2003
	Richard Cole , Lee-Ad Gottlieb , Moshe Lewenstein, Dictionary matching and indexing with errors and don't cares, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Gonzalo Navarro, Indexing text using the Ziv-Lempel trie, Journal of Discrete Algorithms, v.2 n.1, p.87-114, March 2004
	Kunihiko Sadakane, Succinct representations of lcp information and improvements in the compressed suffix arrays, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.225-232, January 06-08, 2002, San Francisco, California
	Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, v.2 n.1, p.53-86, March 2004
	Meng He , J. Ian Munro , S. Srinivasa Rao, A categorization theorem on suffix arrays with applications to space efficient text indexes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Daniel K. Blandford , Guy E. Blelloch, Dictionaries using variable-length keys and data, with applications, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: experiments with compressing suffix arrays and applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Graham Cormode , S. Muthukrishnan, Substring compression problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Paolo Ferragina , Giovanni Manzini, Indexing compressed text, Journal of the ACM (JACM), v.52 n.4, p.552-581, July 2005
	Alejandro López-Ortiz, Algorithmic foundations of the internet, ACM SIGACT News, v.36 n.2, June 2005
	Kunihiko Sadakane , Roberto Grossi, Squeezing succinct data structures into entropy bounds, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1230-1239, January 22-26, 2006, Miami, Florida
	Ho-Leung Chan , Wing-Kai Hon , Tak-Wah Lam , Kunihiko Sadakane, Dynamic dictionary matching and compressed suffix trees, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Moritz G. Maaß, Matching statistics: efficient computation and a new practical algorithm for the multiple common substring problem, Software—Practice & Experience, v.36 n.3, p.305-331, March 2006
	Trinh N. D. Huynh , Wing-Kai Hon , Tak-Wah Lam , Wing-Kin Sung, Approximate string matching using compressed suffix arrays, Theoretical Computer Science, v.352 n.1, p.240-249, 7 March 2006
	Veli Mäkinen , Gonzalo Navarro, Succinct suffix arrays based on run-length encoding, Nordic Journal of Computing, v.12 n.1, p.40-66, March 2005
	Ho-Leung Chan , Wing-Kai Hon , Tak-Wah Lam , Kunihiko Sadakane, Compressed indexes for dynamic text collections, ACM Transactions on Algorithms (TALG), v.3 n.2, p.21-es, May 2007
	Shunsuke Inenaga , Hiromasa Hoshino , Ayumi Shinohara , Masayuki Takeda , Setsuo Arikawa , Giancarlo Mauri , Giulio Pavesi, On-line construction of compact directed acyclic word graphs, Discrete Applied Mathematics, v.146 n.2, p.156-179, 1 March 2005
	Anna Gál , Peter Bro Miltersen, The cell probe complexity of succinct data structures, Theoretical Computer Science, v.379 n.3, p.405-417, June, 2007
	Moritz G. Maaí , Johannes Nowak, Text indexing with errors, Journal of Discrete Algorithms, v.5 n.4, p.662-681, December, 2007
	M. Ganapathiraju , D. Weisser , R. Rosenfeld , J. Carbonell , R. Reddy , J. Klein-Seetharaman, Comparative n-gram analysis of whole-genome protein sequences, Proceedings of the second international conference on Human Language Technology Research, March 24-27, 2002, San Diego, California
	Klaus-Bernd Schürmann , Jens Stoye, Counting suffix arrays and strings, Theoretical Computer Science, v.395 n.2-3, p.220-234, May, 2008
	Min-Soo Kim , Kyu-Young Whang , Jae-Gil Lee , Min-Jae Lee, Structural optimization of a full-text n-gram index using relational normalization, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1485-1507, November 2008
	Ankur Gupta , Wing-Kai Hon , Rahul Shah , Jeffrey Scott Vitter, Compressed data structures: Dictionaries and data-aware measures, Theoretical Computer Science, v.387 n.3, p.313-331, November, 2007
	Holger Bast , Christian W. Mortensen , Ingmar Weber, Output-sensitive autocompletion search, Information Retrieval, v.11 n.4, p.269-286, August 2008
	Alexander Golynski, Cell probe lower bounds for succinct data structures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.625-634, January 04-06, 2009, New York, New York
	Nikolas Askitis , Justin Zobel, B-tries for disk-based string management, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.157-179, January 2009