Practical Suffix Tree Construction

Summary: Practical suffix-tree construction for large data; yields persistent suffix-tree indexing for exact and approximate queries. O(n^2) in-memory construction beats O(n) Ukkonen; buffered disk approach scales suffix-tree construction to data far beyond prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9373
Venue: VLDB
Year: 2004
Pagerank: 7.3893019e-05
Overall Rank: 3,470 | 76.20%
DOI: 10.1016/B978-012088469-8.50007-3

Incoming Non-self Citations Over Time

Authors

1. Sandeep Tata (University of Michigan)
2. Richard A. Hankins (University of Michigan)
3. Jignesh M. Patel (University of Michigan)

BibTeX Citation

@article{tata_vldb04,
        title = {{Practical Suffix Tree Construction}},
        author = {Tata, Sandeep and Hankins, Richard A. and Patel, Jignesh M.},
        journal = {PVLDB},
        series = {{VLDB} '04},
        doi = {10.1016/B978-012088469-8.50007-3},
        url = {https://doi.org/10.1016/B978-012088469-8.50007-3},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,176	Effective Phrase Prediction	2007	VLDB	9.0172465e-05
3,077	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	7.7810685e-05
7,057	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB	5.7159515e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,008	A Database Index to Large Biological Sequences	2001	VLDB	9.310515e-05
3,164	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.6778551e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
2	1,112	Cache-Oblivious String B-trees	2006	PODS
3	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
4	9,861	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
5	2,008	A Database Index to Large Biological Sequences	2001	VLDB
6	4,776	An Efficient Index Structure for String Databases	2001	VLDB
7	7,057	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB
8	3,077	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD
9	5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD
10	12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD