ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
A Space-Economical Suffix Tree Construction Algorithm
Full text PdfPdf (790 KB)
Source Journal of the ACM (JACM) archive
Volume 23 ,  Issue 2  (April 1976) table of contents
Pages: 262 - 272  
Year of Publication: 1976
ISSN:0004-5411
Author
Edward M. McCreight  Xerox Palo Alto Research Center, 3333 Coyote Hill Road, Palo Alto, CA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 51,   Downloads (12 Months): 482,   Citation Count: 179
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: 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/321941.321946
What is a DOI?

ABSTRACT

A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.


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
Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
 
2
KIMBALL, R B. A rapid substring searching algorithm in speech recognition Abstracted in Conf Record, IEEE Syrup on Speech Recognition, Pittsburgh, Pa., April 1974.
 
3
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
 
4
KSUTH, D.E Pattern matching in strings. Unpub. lecture notes, Trondheim, Norway, May 1973.
 
5
KNUTH, D.E., MORRIS, J.H. JR., AND PRATT, V.R. Fast pattern matching in strings. Comput. Sei. Rep. STAN-CS-74-440, Stanford U., Stanford, Calif., Aug. 1974.
 
6
PRATT, V R. Applications of the Weiner repetition finder. Unpub. paper, Cambridge, Mass., May 1973; rev Oct. 1973
7
Robert A. Wagner, Order-n correction for regular languages, Communications of the ACM, v.17 n.5, p.265-268, May 1974  [doi>10.1145/360980.360995]
 
8
WEINER, P. Linear pattern matching algorlthms. Conf. Record, IEEE 14th Annual Symposium on Switching and Automata Theory, pp. 1-11.

CITED BY  179
 
Moritz G. Maaß, Computing suffix links for suffix trees and arrays, Information Processing Letters, v.101 n.6, p.250-254, March, 2007
S. Rao Kosaraju, Real-time pattern matching and quasi-real-time construction of suffix trees (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.310-316, May 23-25, 1994, Montreal, Quebec, Canada
Alejandro López-Ortiz, Linear pattern matching of repeated substrings, ACM SIGACT News, v.25 n.3, p.114-121, Sept. 1994
 
Y. Panagis , E. Theodoridis , K. Tsichlas, Data structuring application for string problems in biological sequences, Proceedings of the international conference on Computational methods in sciences and engineering, p.479-483, September 12-16, 2003, Kastoria, Greece
Haixun Wang , Jian Pei , Philip S. Yu, Pattern-based similarity search for microarray data, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
 
Hubert Ka Yau Leung, Subject space: a state-persistent model for publish/subscribe systems, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.7, September 30-October 03, 2002, Toronto, Ontario, Canada
Mirella M. Moro , Zografoula Vagena , Vassilis J. Tsotras, Evaluating structural summaries as access methods for XML, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, ACM SIGPLAN Notices, v.19 n.6, p.117-121, June 1984
Zvi Galil, On improving the worst case running time of the Boyer-Moore string matching algorithm, Communications of the ACM, v.22 n.9, p.505-508, Sept. 1979
James J. Hunt , Kiem-Phong Vo , Walter F. Tichy, Delta algorithms: an empirical analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.192-214, April 1998
 
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
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
 
D. P. Mehta , S. Sahni, Computing Display Conflicts in String Visualization, IEEE Transactions on Computers, v.43 n.3, p.350-361, March 1994
 
Richard Cole , Ramesh Hariharan, Dynamic LCA queries on trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.235-244, January 17-19, 1999, Baltimore, Maryland, United States
 
Alberto Apostolico , Stefano Lonardi, A speed-up for the commute between subword trees and DAWGs, Information Processing Letters, v.83 n.3, p.159-161, 16 August 2002
Alberto Apostolico , Gill Bejerano, Optimal amnesic probabilistic automata or how to learn and classify proteins in linear time and space, Proceedings of the fourth annual international conference on Computational molecular biology, p.25-32, April 2000, Tokyo, Japan
R. Ramesh , I. V. Ramakrishnan , D. S. Warren, Automata-driven indexing of Prolog clauses, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.281-291, December 1989, San Francisco, California, United States
 
Shlomo Argamon , Ido Dagan , Yuval Krymolowski, A memory-based approach to learning shallow natural language patterns, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
 
Giorgio Satta , John C. Henderson, String transformation learning, Proceedings of the eighth conference on European chapter of the Association for Computational Linguistics, p.444-451, July 07-12, 1997, Madrid, Spain
 
Robert W. Irving , Lorna Love, The suffix binary search tree and suffix AVL tree, Journal of Discrete Algorithms, v.1 n.5-6, p.387-408, October 2003
H. V. Jagadish , Raymond T. Ng , Divesh Srivastava, Substring selectivity estimation, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.249-260, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
 
Amihood Amir , Igor Nor, Real-time indexing over fixed finite alphabets, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1086-1095, January 20-22, 2008, San Francisco, California
 
Gad M. Landau , Uzi Vishkin, Pattern matching in a digitized image, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.453-462, September 1992, Orlando, Florida, United States
 
David G. Korn , Kiem-Phong Vo, Engineering a Differencing and Compression Data Format, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.219-228, June 10-15, 2002
 
A. L. Brown, Constructing chromosome scale suffix trees, Proceedings of the second conference on Asia-Pacific bioinformatics, p.105-112, January 01, 2004, Dunedin, New Zealand
Christian Kreibich , Jon Crowcroft, Honeycomb: creating intrusion detection signatures using honeypots, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004
Tuğkan Batu , Funda Ergun , Cenk Sahinalp, Oblivious string embeddings and edit distance approximations, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.792-801, January 22-26, 2006, Miami, Florida
 
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
 
D. P. Mehta , S. Sahni, A Data Structure for Circular String Analysis and Visualization, IEEE Transactions on Computers, v.42 n.8, p.992-997, August 1993
Richard Cole , Ramesh Hariharan, Faster suffix tree construction with missing suffix links, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.407-415, May 21-23, 2000, Portland, Oregon, 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
 
Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.705-714, January 23-25, 1994, Arlington, Virginia, United States
Jisheng Wang , lhab Hamadeh , George Kesidis , David J. Miller, Polymorphic worm detection and defense: system design, experimental methodology, and data resources, Proceedings of the 2006 SIGCOMM workshop on Large-scale attack defense, p.169-176, September 11-15, 2006, Pisa, Italy
 
Dirk Strothmann, The affix array data structure and its applications to RNA secondary structure analysis, Theoretical Computer Science, v.389 n.1-2, p.278-294, December, 2007
Gianni Franceschini , S. Muthukrishnan, Optimal suffix selection, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
 
Krisztián Monostori , Arkady Zaslavsky , Heinz Schmidt, Suffix vector: space- and time-efficient alternative to suffix trees, Australian Computer Science Communications, v.24 n.1, p.157-165, January-February 2002
 
Muhammad Abulaish , Lipika Dey, Biological relation extraction and query answering from MEDLINE abstracts using ontology-based text mining, Data & Knowledge Engineering, v.61 n.2, p.228-262, May, 2007
Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984
Ning-Han Liu , Yi-Hung Wu , Arbee L. P. Chen, Efficient K-NN search in polyphonic music databases using a lower bounding mechanism, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
 
Paolo Ferragina , Giovanni Manzini, Compression boosting in optimal linear time using the Burrows-Wheeler Transform, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
 
Mikio Yamamoto , Kenneth W. Church, Using suffix arrays to compute term frequency and document frequency for all substrings in a corpus, Computational Linguistics, v.27 n.1, p.1-30, March 2001
 
Christophe Hohlweg , Christophe Reutenauer, Lyndon words, permutations and trees, Theoretical Computer Science, v.307 n.1, p.173-178, 26 September 2003
 
Peter Johansen, Adaptive Pattern Recognition, Journal of Mathematical Imaging and Vision, v.7 n.4, p.325-339, Oct. 1997
A. Blumer , J. Blumer , A. Ehrenfeucht , D. Haussler , R. McConnell, Building a complete inverted file for a set of text files in linear time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.349-358, December 1984
Arnd Christian König , Eric Brill, Reducing the human overhead in text categorization, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
 
Inbok Lee , Costas S. Iliopoulos , Kunsoo Park, Linear time algorithm for the longest common repeat problem, Journal of Discrete Algorithms, v.5 n.2, p.243-249, June, 2007
 
C. Iliopoulos , K. Perdikuri , E. Theodoridis , A. Tsakalidis , K. Tsichlas, Algorithms for extracting motifs from biological weighted sequences, Journal of Discrete Algorithms, v.5 n.2, p.229-242, June, 2007
 
H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, Multi-Dimensional Substring Selectivity Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.387-398, September 07-10, 1999
Stefan Burkhardt , Andreas Crauser , Paolo Ferragina , Hans-Peter Lenhof , Eric Rivals , Martin Vingron, q-gram based database searching using a suffix array (QUASAR), Proceedings of the third annual international conference on Computational molecular biology, p.77-83, April 11-14, 1999, Lyon, France
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
 
Ming Gu , Martin Farach , Richard Beigel, An efficient algorithm for dynamic text indexing, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 23-25, 1994, Arlington, Virginia, United States
Alexandra M. Carvalho , Arlindo L. Oliveira , Ana T. Freitas , Marie-France Sagot, A parallel algorithm for the extraction of structured motifs, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
 
Park Sang Hyun , Chu Wesley W., Discovering and Matching Elastic Rules from Sequence Databases, Fundamenta Informaticae, v.47 n.1-2, p.75-90, January 2001
Ross A. Lippert , Xiaoyue Zhao , Liliana Florea , Clark Mobarry , Sorin Istrail, Finding anchors for genomic sequence comparison, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.233-241, March 27-31, 2004, San Diego, California, USA
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
 
Richard Cole , Moshe Lewenstein, Multidimensional matching and fast search in suffix trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
 
H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, One-dimensional and multi-dimensional substring selectivity estimation, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.214-230, December 2000
 
H. J. Wolfson, On curve matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.5, p.483-489, May 1990
 
Bernhard Balkenhol , Stefan Kurtz, Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice, IEEE Transactions on Computers, v.49 n.10, p.1043-1053, October 2000
 
Satoru Miyamoto , Shunsuke Inenaga , Masayuki Takeda , Ayumi Shinohara, Ternary directed acyclic word graphs, Theoretical Computer Science, v.328 n.1-2, p.97-111, 29 November 2004
 
Justin Zobel , Alistair Moffat , Ron Sacks-Davis, Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files, Proceedings of the 19th International Conference on Very Large Data Bases, p.290-301, August 24-27, 1993
 
Frantisek Franěk , William F. Smyth , Yudong Tang, Computing all repeats using suffix arrays, Journal of Automata, Languages and Combinatorics, v.8 n.4, p.579-591, April 2003
Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States
 
Tae-Yeong Kwak , Yoon-Joon Lee, A filtering method for searching similar multidimensional sequences under the time-warping distance, Information Systems, v.28 n.7, p.791-813, 1 October 2003
 
Paolo Ferragina , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Two-dimensional substring indexing, Journal of Computer and System Sciences, v.66 n.4, p.763-774, 1 June 2003
Yun-Wu Huang , Philip S. Yu, Adaptive query processing for time-series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.282-286, August 15-18, 1999, San Diego, California, United States
 
Marcel H. Schulz , Sebastian Bauer , Peter N. Robinson, The generalised k-Truncated Suffix Tree for time-and space-efficient searches in multiple DNA or protein sequences, International Journal of Bioinformatics Research and Applications, v.4 n.1, p.81-95, February 2008
 
Shiri Dori , Gad M. Landau, Construction of Aho Corasick automaton in linear time for integer alphabets, Information Processing Letters, v.98 n.2, p.66-72, 30 April 2006
Laurent Marsan , Marie-France Sagot, Extracting structured motifs using a suffix tree—algorithms and application to promoter consensus identification, Proceedings of the fourth annual international conference on Computational molecular biology, p.210-219, April 2000, Tokyo, Japan
 
Costas S. Iliopoulos , M. Sohel Rahman, Faster index for property matching, Information Processing Letters, v.105 n.6, p.218-223, March, 2008
 
Claudio Mattiussi , Markus Waibel , Dario Floreano, Measures of Diversity for Populations and Distances Between Individuals with Highly Reorganizable Genomes, Evolutionary Computation, v.12 n.4, p.495-515, December 2004
Youfeng Wu , Mauricio Breternitz, Jr. , Herbert Hum , Ramesh Peri , Jay Pickett, Enhanced code density of embedded CISC processors with echo technology, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA
 
Ke Wang, Discovering Patterns from Large and Dynamic Sequential Data, Journal of Intelligent Information Systems, v.9 n.1, p.33-56, July/Aug. 1997
 
Joong Chae Na , Alberto Apostolico , Costas S. Iliopoulos , Kunsoo Park, Truncated suffix trees and their application to data compression, Theoretical Computer Science, v.304 n.1-3, p.87-101, 28 July 2003
James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982
 
Paolo Ferragina , Roberto Grossi, Fast string searching in secondary storage: theoretical developments and experimental results, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.373-382, January 28-30, 1996, Atlanta, Georgia, United States
H. V. Jagadish , Nick Koudas , Divesh Srivastava, On effective multi-dimensional indexing for strings, ACM SIGMOD Record, v.29 n.2, p.403-414, June 2000
 
H. Shang , T. h. Merrettal, Tries for Approximate String Matching, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.540-547, August 1996
Mihail Halachev , Nematollaah Shiri , Anand Thamildurai, Exact match search in sequence data using suffix trees, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Paolo Ferragina , Nick Koudas , Divesh Srivastava , S. Muthukrishnan, Two-dimensional substring indexing, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.282-288, May 2001, Santa Barbara, California, United States
 
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
S. Rao Kosaraju , Arthur L. Delcher, Large-scale assembly of DNA strings and space-efficient construction of suffix trees, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.169-177, May 29-June 01, 1995, Las Vegas, Nevada, United States
P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, ACM SIGMOD Record, v.25 n.2, p.282-293, June 1996
 
Jesper Jansson , Kunihiko Sadakane , Wing-Kin Sung, Ultra-succinct representation of ordered trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.575-584, January 07-09, 2007, New Orleans, Louisiana
 
Dan Gusfield , Jens Stoye, Linear time algorithms for finding and representing all the tandem repeats in a string, Journal of Computer and System Sciences, v.69 n.4, p.525-546, December 2004
 
John S. Gero , Vladimir S. Kazakov, A Genetic Engineering Approach to Genetic Algorithms, Evolutionary Computation, v.9 n.1, p.71-92, January 2001
Bin Cui , H. V. Jagadish , Beng Chin Ooi , Kian-Lee Tan, Compacting music signatures for efficient music retrieval, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
 
Paolo Ferragina , Roberto Grossi, Fast incremental text editing, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.531-540, January 22-24, 1995, San Francisco, California, United States
Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
 
Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
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
 
Zhiyuan Chen , Flip Korn , Nick Koudas , S. Muthukrishnan, Generalized substring selectivity estimation, Journal of Computer and System Sciences, v.66 n.1, p.98-132, 01 February 2003
 
Shunsuke Inenaga , Ayumi Shinohara , Masayuki Takeda , Setsuo Arikawa, Compact directed acyclic word graphs for a sliding window, Journal of Discrete Algorithms, v.2 n.1, p.33-51, March 2004
David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming I: linear cost functions, Journal of the ACM (JACM), v.39 n.3, p.519-545, July 1992
 
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
 
Alexandra M. Carvalho , Ana T. Freitas , Arlindo L. Oliveira , Marie-France Sagot, An Efficient Algorithm for the Identification of Structured Motifs in DNA Promoter Sequences, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.3 n.2, p.126-140, April 2006
Amihood Amir , Gary Benson , Martin Farach, Alphabet independent two dimensional matching, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.59-68, May 04-06, 1992, Victoria, British Columbia, Canada
Raffaele Giancarlo , Roberto Grossi, Parallel construction and query of suffix trees for two-dimensional matrices, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.86-97, June 30-July 02, 1993, Velen, Germany
 
Kunihiko Sadakane, New text indexing functionalities of the compressed suffix arrays, Journal of Algorithms, v.48 n.2, p.294-313, September 2003
 
Rafaele Giancarlo, The Suffix of a square matrix, with applications, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.402-411, January 25-27, 1993, Austin, Texas, United States
Jia-Lien Hsu , Arbee L. P. Chen , Hung-Chen Chen , Ning-Han Liu, The effectiveness study of various music information retrieval approaches, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
 
František Franěk , Jan Holub , William F. Smyth , Xiangdong Xiao, Computing quasi suffix arrays, Journal of Automata, Languages and Combinatorics, v.8 n.4, p.593-606, April 2003
Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
 
Amihood Amir , Gad M. Landau , Usi Vishkin, Efficient pattern matching with scaling, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.344-357, January 22-24, 1990, San Francisco, California, United States
 
Veli Mäkinen, Compact suffix array: a space-efficient full-text index, Fundamenta Informaticae, v.56 n.1,2, p.191-210, July 2003
Yangjun Chen , Duren Che , Karl Aberer, On the efficient evaluation of relaxed queries in biological databases, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
 
Ching-Fung Cheung , Jeffrey Xu Yu , Hongjun Lu, Constructing Suffix Tree for Gigabyte Sequences with Megabyte Memory, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.90-105, January 2005
 
Biing-Feng Wang , Jyh-Jye Lin , Shan-Chyun Ku, Efficient algorithms for the scaled indexing problem, Journal of Algorithms, v.52 n.1, p.82-100, July 2004
 
Shunsuke Inenaga, Bidirectional construction of suffix trees, Nordic Journal of Computing, v.10 n.1, p.52-67, Spring 2003
 
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
 
Stephen Alstrup , Gerth Stølting Brodal , Theis Rauhe, Pattern matching in dynamic texts, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.819-828, January 09-11, 2000, San Francisco, California, United States
 
Svante Janson , Stefano Lonardi , Wojciech Szpankowski, On average sequence complexity, Theoretical Computer Science, v.326 n.1-3, p.213-227, 20 October 2004
Hamid Abdul Basit , Simon J. Puglisi , William F. Smyth , Andrew Turpin , Stan Jarzabek, Efficient token based clone detection with flexible tokenization, The 6th Joint Meeting on European software engineering conference and the ACM SIGSOFT symposium on the foundations of software engineering: companion papers, September 03-07, 2007, Dubrovnik, Croatia
Paolo Ferragina , Raffaele Giancarlo , Giovanni Manzini , Marinella Sciortino, Boosting textual compression in optimal linear time, Journal of the ACM (JACM), v.52 n.4, p.688-713, July 2005
 
Emilios Cambouropoulos , Maxime Crochemore , Costas S. Iliopoulos , Manal Mohamed , Marie-France Sagot, All maximal-pairs in step-leap representation of melodic sequence, Information Sciences: an International Journal, v.177 n.9, p.1954-1962, May, 2007
Hamid Abdul Basit , Stan Jarzabek, Efficient token based clone detection with flexible tokenization, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia
 
Ai-Bo Song , Mao-Xian Zhao , Zuo-Peng Liang , Yi-Sheng Dong , Jun-Zhou Luo, Discovering user profiles for web personalized recommendation, Journal of Computer Science and Technology, v.19 n.3, p.320-328, May 2004
 
Frédéric Guyon , Alain Guénoche, Comparing bacterial genomes from linear orders of patterns, Discrete Applied Mathematics, v.156 n.8, p.1251-1262, April, 2008
 
Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.794-803, January 09-11, 2000, San Francisco, California, United States
H. V. Jagadish , Laks V. S. Lakshmanan , Tova Milo , Divesh Srivastava , Dimitra Vista, Querying network directories, ACM SIGMOD Record, v.28 n.2, p.133-144, June 1999
Eamonn Keogh , Stefano Lonardi , Bill 'Yuan-chi' Chiu, Finding surprising patterns in a time series database in linear time and space, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Amihood Amir , Gad M. Landau , Moshe Lewenstein , Dina Sokol, Dynamic text and static pattern matching, ACM Transactions on Algorithms (TALG), v.3 n.2, p.19-es, May 2007
Bijit Hore , Hakan Hacigumus , Bala Iyer , Sharad Mehrotra, Indexing text data under space constraints, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
 
Jayendra Venkateswaran , Deepak Lachwani , Tamer Kahveci , Christopher Jermaine, Reference-based indexing of sequence databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
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
 
Dror Baron , Yoram Bresler, Antisequential Suffix Sorting for BWT-Based Data Compression, IEEE Transactions on Computers, v.54 n.4, p.385-397, April 2005
 
Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Journal of Algorithms, v.50 n.2, p.257-275, February 2004
 
Wojciech Szpankowski, (Un)expected behavior of typical suffix trees, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.422-431, September 1992, Orlando, Florida, United States
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
Elizabeth Shoop , Jaideep Srivastava , Paul Bieganski , John Riedl , Ernest Retzel, An object-oriented genetics information system, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.641-651, February 14-16, 1993, Indianapolis, Indiana, United States
Paolo Ferragina , Roberto Grossi, A fully-dynamic data structure for external substring search, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.693-702, May 29-June 01, 1995, Las Vegas, Nevada, United States
Brenda S. Baker, A theory of parameterized pattern matching: algorithms and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.71-80, May 16-18, 1993, San Diego, California, United States
 
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
 
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
Jason Tsong-Li Wang , Gung-Wei Chirn , Thomas G. Marr , Bruce Shapiro , Dennis Shasha , Kaizhong Zhang, Combinatorial pattern discovery for scientific data: some preliminary results, ACM SIGMOD Record, v.23 n.2, p.115-125, June 1994
 
Sandeep Tata , Richard A. Hankins , Jignesh M. Patel, Practical suffix tree construction, Proceedings of the Thirtieth international conference on Very large data bases, p.36-47, August 31-September 03, 2004, Toronto, Canada
Benjarath Phoophakdee , Mohammed J. Zaki, Genome-scale disk-based suffix tree indexing, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Adam L. Buchsbaum , Glenn S. Fowler , Balachannder Kirishnamurthy , Kiem-Phong Vo , Jia Wang, Fast prefix matching of bounded strings, Journal of Experimental Algorithmics (JEA), 8, 2003
 
Maxime Crochemore, Reducing space for index implementation, Theoretical Computer Science, v.292 n.1, p.185-197, January 2003
Maxime Crochemore , Dominique Perrin, Two-way string-matching, Journal of the ACM (JACM), v.38 n.3, p.650-674, July 1991
 
Colin Meek , Jignesh M. Patel , Shruti Kasetty, OASIS: an online and accurate technique for local-alignment searches on biological sequences, Proceedings of the 29th international conference on Very large data bases, p.910-921, September 09-12, 2003, Berlin, Germany
 
Costas S. Iliopoulos , Christos Makris , Yannis Panagis , Katerina Perdikuri , Evangelos Theodoridis , Athanasios Tsakalidis, The Weighted Suffix Tree: An Efficient Data Structure for Handling Molecular Weighted Sequences and its Applications, Fundamenta Informaticae, v.71 n.2,3, p.259-277, August 2006
 
Yanjun Li , Soon M. Chung , John D. Holt, Text document clustering based on frequent word meaning sequences, Data & Knowledge Engineering, v.64 n.1, p.381-404, January, 2008
 
Dong Kyue Kim , Yoo Ah Kim , Kunsoo Park, Generalizations of suffix arrays to multi-dimensional matrices, Theoretical Computer Science, v.302 n.1-3, p.223-238, 13 June 2003
 
Dong Kyue Kim , Yoo Ah Kim , Kunsoo Park, Generalizations of suffix arrays to multi-dimensional matrices, Theoretical Computer Science, v.302 n.1-3, p.401-416, 13 June 2003
 
Feng Gao , Mohammed J. Zaki, PSIST: A scalable approach to indexing protein structures using suffix trees, Journal of Parallel and Distributed Computing, v.68 n.1, p.54-63, January, 2008
 
Arnab Nandi , H. V. Jagadish, Effective phrase prediction, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
 
Mikhail Atallah , Yann Génin , Wojciech Szpankowski, Pattern Matching Image Compression: Algorithmic and Empirical Results, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.7, p.614-627, July 1999
 
Luc Devroye , Ralph Neininger, Random suffix search trees, Random Structures & Algorithms, v.23 n.4, p.357-396, December 2003
 
Jens Stoye , Dan Gusfield, Simple and flexible detection of contiguous repeats using a suffix tree, Theoretical Computer Science, v.270 n.1-2, p.843-850, January
 
Shein-Yung Cheng , Chia-Sheng Lin , Hsien-Hsun Chen , Jia-Sheng Heh, Learning and diagnosis of individual and class conceptual perspectives: an intelligent systems approach using clustering techniques, Computers & Education, v.44 n.3, p.257-283, April 2005
E. R. Fiala , D. H. Greene, Data compression with finite windows, Communications of the ACM, v.32 n.4, p.490-505, April 1989
Luca Foschini , Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: Experiments with compressing suffix arrays and applications, ACM Transactions on Algorithms (TALG), v.2 n.4, p.611-639, October 2006
 
F. Blanchet-Sadri , Nathan D. Wetzler, Partial words and the critical factorization theorem revisited, Theoretical Computer Science, v.385 n.1-3, p.179-192, October, 2007
 
Moritz G. Maaí , Johannes Nowak, Text indexing with errors, Journal of Discrete Algorithms, v.5 n.4, p.662-681, December, 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
 
Yu-Lung Lo , Wen-Ling Lee , Lin-Huang Chang, True suffix tree approach for discovering non-trivial repeating patterns in a music object, Multimedia Tools and Applications, v.37 n.2, p.169-187, April 2008
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
 
R. W. P. Luk , D. S. Yeung , Q. Lu , H. L. Leung , S. Y. Li , F. Leung, ASAB: a Chinese screen reader, Software—Practice & Experience, v.33 n.3, p.201-219, March 2003
Steffen Heinz , Justin Zobel , Hugh E. Williams, Burst tries: a fast, efficient data structure for string keys, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.192-223, April 2002
 
F. Blanchet-Sadri , S. Duncan, Partial words and the critical factorization theorem, Journal of Combinatorial Theory Series A, v.109 n.2, p.221-245, February 2005
Mohamed Y. Eltabakh , Wing-Kai Hon , Rahul Shah , Walid G. Aref , Jeffrey S. Vitter, The SBC-tree: an index for run-length compressed sequences, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
 
Gonzalo Navarro , Edgar Chávez, A metric index for approximate string matching, Theoretical Computer Science, v.352 n.1, p.266-279, 7 March 2006
Paolo Ferragina , Giovanni Manzini, Indexing compressed text, Journal of the ACM (JACM), v.52 n.4, p.552-581, July 2005
 
Alberto Apostolico , Fang-Cheng Gong , Stefano Lonardi, Verbumculus and the discovery of unusual words, Journal of Computer Science and Technology, v.19 n.1, p.22-41, January 2004
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
 
Nikolas Askitis , Ranjan Sinha, HAT-trie: a cache-conscious trie-based data structure for strings, Proceedings of the thirtieth Australasian conference on Computer science, p.97-105, January 30-February 02, 2007, Ballarat, Victoria, Australia
 
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
 
Aleksandar Stojmirović , Vladimir Pestov, Indexing schemes for similarity search in datasets of short protein fragments, Information Systems, v.32 n.8, p.1145-1165, December, 2007
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
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
 
Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, A Database Index to Large Biological Sequences, Proceedings of the 27th International Conference on Very Large Data Bases, p.139-148, September 11-14, 2001
 
Yuanyuan Tian , Sandeep Tata , Richard A. Hankins , Jignesh M. Patel, Practical methods for constructing suffix trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.3, p.281-299, September 2005
R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989
Juha Kärkkäinen , Peter Sanders , Stefan Burkhardt, Linear work suffix array construction, Journal of the ACM (JACM), v.53 n.6, p.918-936, November 2006
 
Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, Database indexing for large DNA and protein sequence collections, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.3, p.256-271, November 2002
Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001
 
Jeffrey Scott Vitter, Algorithms and data structures for external memory, Foundations and Trends® in Theoretical Computer Science, v.2 n.4, p.305-474, January 2008

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS


General Terms:
Algorithms, Performance, Theory, Verification

Collaborative Colleagues:
Edward M. McCreight: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
Terms of Usage   Privacy Policy