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: he6ea089292413cbd
Venue: VLDB
Year: 2012
Pagerank: 5.5903532e-05
Overall Rank: 7,191 | 51.66%
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,485	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB	6.1100479e-05
12,588	RACE: A Scalable and Elastic Parallel System for Discovering Repeats in Very Long Sequences	2013	VLDB	4.9793485e-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,138	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	7.606774e-05
3,535	Practical Suffix Tree Construction	2004	VLDB	7.2241971e-05
5,364	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD	6.1608023e-05

Semantically Similar Papers

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