Serial and Parallel Methods for I/O Efficient Suffix Tree Construction

Summary: Suffix-tree construction re-architected as a tiled, constant-working-set workflow for I/O-efficient scaling beyond main memory. On massively parallel platforms (Blue Gene/L), locality-aware design and efficient communication yield major speedups, indexing the human genome on 1024 CPUs in under 15 minutes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6d687dfb8c0be430
Venue: SIGMOD
Year: 2009
Pagerank: 6.1608023e-05
Overall Rank: 5,364 | 63.94%
DOI: 10.1145/1559845.1559931

Incoming Non-self Citations Over Time

Authors

1. Amol Ghoting (IBM)
2. Konstantin Makarychev (IBM)

BibTeX Citation

@inproceedings{ghoting_sigmod09,
        title = {{Serial and Parallel Methods for I/O Efficient Suffix Tree Construction}},
        author = {Ghoting, Amol and Makarychev, Konstantin},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559931},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559931},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,191	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB	5.5903532e-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
2,059	A Database Index to Large Biological Sequences	2001	VLDB	9.1020248e-05
3,138	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	7.606774e-05
3,228	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.5077929e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,970	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB
2	7,815	Mining Tree-Structured Data on Multicore Systems	2009	VLDB
3	13,969	Memory Efficient Minimum Substring Partitioning	2013	VLDB
4	4,889	An Efficient Index Structure for String Databases	2001	VLDB
5	7,303	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	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	7,191	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB
10	3,138	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD