Memory Efficient Minimum Substring Partitioning

Summary: Disk-based Minimum Substring Partitioning (MSP) enables memory-efficient de Bruijn graph construction for large genomes. Partitions reads into small in-memory chunks, processes them independently, and merges using k-mer overlaps to compress from Theta(kn) to Theta(n), enabling assembly on commodity hardware. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10844
Venue: VLDB
Year: 2013
Pagerank: -
Overall Rank: 13,707 | 6.28%
DOI: 10.14778/2535569.2448951

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yang Li (University of California Santa Barbara)
2. Pegah Kamousi (University of California Santa Barbara)
3. Fangqiu Han (University of California Santa Barbara)
4. Shengqi Yang (University of California Santa Barbara)
5. Xifeng Yan (University of California Santa Barbara)
6. Subhash Suri (University of California Santa Barbara)

BibTeX Citation

@article{li_vldb13,
        title = {{Memory Efficient Minimum Substring Partitioning}},
        author = {Li, Yang and Kamousi, Pegah and Han, Fangqiu and Yang, Shengqi and Yan, Xifeng and Suri, Subhash},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {3},
        pages = {169},
        doi = {10.14778/2535569.2448951},
        url = {https://doi.org/10.14778/2535569.2448951},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,093	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB
2	8,062	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD
3	3,484	Practical Suffix Tree Construction	2004	VLDB
4	12,611	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD
5	4,793	An Efficient Index Structure for String Databases	2001	VLDB
6	4,704	Fast Processing and Querying of 170TB of Genomics Data via a Repeated And Merged BloOm Filter (RAMBO)	2021	SIGMOD
7	13,525	On the String Matching with k Differences in DNA Databases	2021	VLDB
8	3,091	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD
9	3,518	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
10	5,265	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD