Improving Suffix Array Locality for Fast Pattern Matching on Disk

Summary: Disk-aware suffix array layout using a small trie plus a blocked SA-like structure; improves locality for on-disk pattern matching. Queries run up to 3x faster than the best disk-based SA arrangements, with modest extra processing beyond suffix-tree build and negligible extra memory. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4085
Venue: SIGMOD
Year: 2008
Pagerank: 5.093636e-05
Overall Rank: 12,558 | 13.85%
DOI: 10.1145/1376616.1376683

Incoming Non-self Citations Over Time

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

Authors

1. Ranjan Sinha (University of Melbourne)
2. Simon J. Puglisi (RMIT University)
3. Alistair Moffat (University of Melbourne)
4. Andrew Turpin (RMIT University)

BibTeX Citation

@inproceedings{sinha_sigmod08,
        title = {{Improving Suffix Array Locality for Fast Pattern Matching on Disk}},
        author = {Sinha, Ranjan and Puglisi, Simon J. and Moffat, Alistair and Turpin, Andrew},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376683},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376683},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,861	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB
2	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
3	5,426	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB
4	13,474	On the String Matching with k Differences in DNA Databases	2021	VLDB
5	2,008	A Database Index to Large Biological Sequences	2001	VLDB
6	4,776	An Efficient Index Structure for String Databases	2001	VLDB
7	7,057	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB
8	3,077	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD
9	5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD
10	3,470	Practical Suffix Tree Construction	2004	VLDB