References
| [AKL+00] | Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, and Michael Rodeh. Text indexing and dictionary matching with one error. Journal of Algorithms, 37(2):309-325, November 2000. |
| [AN07] | Abdullah Arslan and Johannes Nowak. Efficient approximate dictionary look-up for long words over small alphabets. Unpublished manuscript, 2007. |
| [AZS99] | Anurag Acharya, Huican Zhu, and Kai Shen. Adaptive algorithms for cache-efficient trie search. In Proceedings of the 1st International Workshop on Algorithm Engineering and Experimentation (ALENEX'99), volume 1619 of Lecture Notes in Computer Science, pages 296-311. Springer, January 1999. |
| [BGW00] | Adam L. Buchsbaum, Michael T. Goodrich, and Jeffery R. Westbrook. Range searching over tree cross products. In Proceedings of the 8th European Symposium on Algorithms (ESA'00), volume 1879 of Lecture Notes in Computer Science, pages 120-131. Springer, September 2000. |
| [BH04] | Srikanta J. Bedathur and Jayant R. Haritsa. Engineering a fast online persistent suffix tree construction. In Proceedings of the 20th International Conference on Data Engineering (ICDE'04), pages 720-731. IEEE, March/April 2004. |
| [BH05] | Srikanta J. Bedathur and Jayant R. Haritsa. Search-optimized suffix-tree storage for biological applications. In Proceedings of the 12th International Conference on High Performance Computing (HiPC'05), volume 3769 of Lecture Notes in Computer Science, pages 29-39, December 2005. |
| [CGL04] | Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. Dictionary matching and indexing with errors and don't cares. In Proceedings of the 36th Symposium on Theory of Computing (STOC'04), pages 91-100. ACM Press, June 2004. |
| [Cli05] | Raphaël Clifford. Distributed suffix trees. Journal of Discrete Algorithms, 3:176-197, June 2005. |
| [CLS+06] | Ho-Leung Chan, Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tam, and Swee-Seong Wong. A linear size index for approximate pattern matching. In CPM 2006 [CPM06], pages 49-59. |
| [CM96] | David R. Clark and J. Ian Munro. Efficient suffix trees on secondary storage. In SODA 1996 [SOD96], pages 383-391. |
| [CO06] | Luís Pedro Coelho and Arlindo L. Oliveira. Dotted suffix trees - A structure for approximate text indexing. In SPIRE 2006 [SPI06], pages 329-336. |
| [Cob95] | Archie L. Cobbs. Fast approximate matching using suffix trees. In Proceedings of the 6th Symposium on Combinatorial Pattern Matching (CPM'95), volume 937 of Lecture Notes in Computer Science, pages 41-54. Springer, July 1995. |
| [CPM04] | Proceedings of the 15th Symposium on Combinatorial Pattern Matching (CPM'04), volume 3109 of Lecture Notes in Computer Science. Springer, July 2004. |
| [CPM06] | Proceedings of the 17th Symposium on Combinatorial Pattern Matching (CPM'06), volume 4009 of Lecture Notes in Computer Science. Springer, July 2006. |
| [EGM05] | Chiara Epifanio, Alessandra Gabriele, and Filippo Mignosi. Languages with mismatches and an application to approximate indexing. In Proceedings of the 9th International Conference on Developments in Language Theory (DLT'05), volume 3572 of Lecture Notes in Computer Science, pages 224-235. Springer, July 2005. |
| [EKN07] | Stefan Eckhardt, Sven Kosub, and Johannes Nowak. Smoothed analysis of trie height. Unpublished manuscript, 2007. |
| [FCFM00] | Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan. On the sorting-complexity of suffix tree construction. Journal of the ACM, 47(6):987-1011, November 2000. |
| [FG96] | Paolo Ferragina and Roberto Grossi. Fast string searching in secondary storage: Theoretical developments and experimental results. In SODA 1996 [SOD96], pages 373-382. |
| [FG99] | Paolo Ferragina and Roberto Grossi. The string B-tree: A new data structure for string search in external memory and its applications. Journal of the ACM, 46(2):236-280, March 1999. |
| [GMRS03] | Alessandra Gabriele, Filippo Mignosi, Antonio Restivo, and Marinella Sciortino. Indexing structures for approximate string matching. In Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC'03), volume 2653 of Lecture Notes in Computer Science, pages 140-151. Springer, May 2003. |
| [HAI02] | Ela Hunt, Malcolm P. Atkinson, and Robert W. Irving. Database indexing for large DNA and protein sequence collections. The VLDB Journal, 11(3):256-271, November 2002. |
| [JTU96] | Petteri Jokinen, Jorma Tarhio, and Esko Ukkonen. A comparison of approximate string matching algorithms. Software: Practice and Experience, 26(12):1439-1458, December 1996. |
| [JU91] | Petteri Jokinen and Esko Ukkonen. Two algorithms for approximate string matching in static texts. In Proceedings of the 16th International Symposium on Mathematical Foundations of Computer Science (MFCS'91), volume 520 of Lecture Notes in Computer Science, pages 240-248. Springer, September 1991. |
| [KA06] | Pang Ko and Srinivas Aluru. Obtaining provably good performance from suffix trees in secondary storage. In CPM 2006 [CPM06], pages 72-83. |
| [Maa03] | Moritz G. Maass. Linear bidirectional on-line construction of affix trees. Algorithmica, 37(1):43-74, June 2003. |
| [Maa04] | Moritz G. Maass. Average-case analysis of approximate trie search. In CPM 2004 [CPM04], pages 472-483. |
| [Maa06] | Moritz G. Maass. Matching statistics: efficient computation and a new practical algorithm for the multiple common substring problem. Software: Practice and Experience, 36(3):305-331, March 2006. |
| [McC76] | Edward M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23(2):262-272, April 1976. |
| [MM93] | Udi Manber and Eugene W. Myers. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5):935-948, October 1993. |
| [MN05a] | Moritz G. Maass and Johannes Nowak. A new method for approximate indexing and dictionary lookup with one error. Information Processing Letters, 96(5):185- 191, December 2005. |
| [MN05b] | Moritz G. Maass and Johannes Nowak. Text indexing with errors. In Proceedings of the 16th Symposium on Combinatorial Pattern Matching (CPM'05), volume 3537 of Lecture Notes in Computer Science, pages 21-32. Springer, June 2005. |
| [MN07] | Moritz G. Maass and Johannes Nowak. Text indexing with errors. Journal of Discrete Algorithms, 2007. to appear. |
| [Mye94] | Eugene W. Myers. A sublinear algorithm for approximate keyword searching. Algorithmica, 12:345-374, October 1994. |
| [Nav01] | Gonzalo Navarro. A guided tour to approximate string matching. ACM Computing Surveys, 33(1):31-88, March 2001. |
| [NBY98] | Gonzalo Navarro and Ricardo Baeza-Yates. A practical q-gram index for text retrieval allowing errors. CLEI Electronic Journal, 1(2), December 1998. |
| [NBY00] | Gonzalo Navarro and Ricardo Baeza-Yates. A hybrid indexing method for approximate string matching. Journal of Discrete Algorithms, 1(1):205-239, 2000. |
| [NC06] | Gonzalo Navarro and Edgar Cha'vez. A metric index for approximate string matching. Theoretical Computer Science, 352:266-279, March 2006. |
| [Now04] | Johannes Nowak. A new indexing method for approximate pattern matching with one mismatch. Diploma thesis, Inst. f. Informatik, Technische Universita"t Mu"nchen, February 2004. |
| [SM96] | Heping Shang and Timothy H. Merrett. Tries for approximate string matching. IEEE Transactions on Knowledge and Data Engineering, 8(4):540-547, August 1996. |
| [SOD96] | ACM/SIAM. Proceedings of the 7th Symposium on Discrete Algorithms (SODA'96), January 1996. |
| [SPI06] | Proceedings of the 13th Symposium on String Processing and Information Retrieval (SPIRE'06), volume 4209 of Lecture Notes in Computer Science. Springer, October 2006. |
| [ST96] | Erkki Sutinen and Jorma Tarhio. Filtration with q-samples in approximate string matching. In Proceedings of the 7th Symposium on Combinatorial Pattern Matching (CPM'96), volume 1075 of Lecture Notes in Computer Science, pages 50-63. Springer, June 1996. |
| [ST04] | Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385-463, May 2004. |
| [Szp01] | Wojciech Szpankowski. Average Case Analysis of Algorithms on Sequences. Wiley, 2001. |
| [TBG04] | Hanjo Täubig, Arno Buchner, and Jan H. Griebsch. A method for fast approximate searching of polypeptide structures in the PDB. In Proceedings of the German Conference on Bioinformatics (GCB'04), volume P-53 of Lecture Notes in Informatics, pages 65-74. Ko"llen Verlag, October 2004. |
| [TBG06] | Hanjo Täubig, Arno Buchner, and Jan H. Griebsch. PAST: fast structure-based searching in the PDB. Nucleic Acids Research, 34(Web Server Issue):W20-W23, July 2006. |
| [TTHP05] | Yuanyuan Tian, Sandeep Tata, Richard A. Hankins, and Jignesh M. Patel. Practical methods for constructing suffix trees. The VLDB Journal, 14(3):281-299, September 2005. |
| [Ukk93] | Esko Ukkonen. Approximate string-matching over suffix trees. In Proceedings of the 4th Symposium on Combinatorial Pattern Matching (CPM'93), volume 684 of Lecture Notes in Computer Science, pages 228-242. Springer, June 1993. |
| [Ukk95] | Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249-260, September 1995. |
| [Wei73] | Peter Weiner. Linear pattern matching algorithms. In Proceedings of the 14th IEEE Annual Symposium on Switching and Automata Theory, pages 1-11. IEEE, 1973. |