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: 4024
Venue: SIGMOD
Year: 2008
Pagerank: 4.1905499e-05
Overall Rank: 12,373 | 14.01%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

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
2,251	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	9.1921005e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,723	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB	4.2913201e-05
5,825	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3119504e-05
5,410	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB	5.5214688e-05
13,285	On the String Matching with k Differences in DNA Databases	2021	VLDB	-
1,115	A Database Index to Large Biological Sequences	2001	VLDB	0.00013865352
4,330	An Efficient Index Structure for String Databases	2001	VLDB	6.2745131e-05
6,319	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB	5.1083749e-05
2,251	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	9.1921005e-05
4,550	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD	6.0866239e-05
2,586	Practical Suffix Tree Construction	2004	VLDB	8.4894627e-05