Genome-scale Disk-based Suffix Tree Indexing

Summary: Genome-scale disk-based suffix tree: Trellis preserves suffix links and enables external indexing for DNA sequences. Index the human genome in ~4h with 2GB RAM and ~2h suffix-link recovery, outpacing prior methods on index and query performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3966
Venue: SIGMOD
Year: 2007
Pagerank: 7.7810685e-05
Overall Rank: 3,077 | 78.90%
DOI: 10.1145/1247480.1247572

Incoming Non-self Citations Over Time

Authors

1. Benjarath Phoophakdee (Rensselaer Polytechnic Institute)
2. Mohammed J. Zaki (Rensselaer Polytechnic Institute)

BibTeX Citation

@inproceedings{phoophakdee_sigmod07,
        title = {{Genome-scale Disk-based Suffix Tree Indexing}},
        author = {Phoophakdee, Benjarath and Zaki, Mohammed J.},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247572},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247572},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD	6.3019356e-05
7,057	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB	5.7159515e-05
12,297	RACE: A Scalable and Elastic Parallel System for Discovering Repeats in Very Long Sequences	2013	VLDB	5.093636e-05
12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD	5.093636e-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,470	Practical Suffix Tree Construction	2004	VLDB	7.3893019e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
2	12,283	RCSI: Scalable similarity search in thousand(s) of genomes	2013	VLDB
3	13,656	Memory Efficient Minimum Substring Partitioning	2013	VLDB
4	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB
5	4,691	Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO)	2021	SIGMOD
6	12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD
7	3,470	Practical Suffix Tree Construction	2004	VLDB
8	7,057	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB
9	2,008	A Database Index to Large Biological Sequences	2001	VLDB
10	5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD