ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings

Summary: ERa constructs suffix trees for strings far exceeding memory via adaptive horizontal/vertical partitioning that minimizes I/O as tree shape and memory change. It supports serial, shared-memory/shared-disk, and shared-nothing parallelism, indexing the human genome in 19 minutes on a desktop. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10523
Venue: VLDB
Year: 2012
Pagerank: 5.7159515e-05
Overall Rank: 7,057 | 51.59%
DOI: 10.14778/2047485.2047490

Incoming Non-self Citations Over Time

Authors

1. Essam Mansour (King Abdullah University of Science and Technology)
2. Amin Allam (King Abdullah University of Science and Technology)
3. Spiros Skiadopoulos (University of Peloponnese)
4. Panos Kalnis (King Abdullah University of Science and Technology)

BibTeX Citation

@article{mansour_vldb12,
        title = {{ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings}},
        author = {Mansour, Essam and Allam, Amin and Skiadopoulos, Spiros and Kalnis, Panos},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {1},
        pages = {49--60},
        doi = {10.14778/2047485.2047490},
        url = {https://doi.org/10.14778/2047485.2047490},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,426	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB	6.2231556e-05
12,297	RACE: A Scalable and Elastic Parallel System for Discovering Repeats in Very Long Sequences	2013	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3,077	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	7.7810685e-05
3,470	Practical Suffix Tree Construction	2004	VLDB	7.3893019e-05
5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD	6.3019356e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,691	Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO)	2021	SIGMOD
2	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB
3	13,656	Memory Efficient Minimum Substring Partitioning	2013	VLDB
4	12,297	RACE: A Scalable and Elastic Parallel System for Discovering Repeats in Very Long Sequences	2013	VLDB
5	4,776	An Efficient Index Structure for String Databases	2001	VLDB
6	2,008	A Database Index to Large Biological Sequences	2001	VLDB
7	12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD
8	3,470	Practical Suffix Tree Construction	2004	VLDB
9	3,077	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD
10	5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD