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: 4023
Venue: SIGMOD
Year: 2008
Pagerank: 4.1945683e-05
Overall Rank: 12,365 | 13.98%
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,250	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	9.2009942e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,724	Text Indexing for Long Patterns: Anchors are All you Need	2023	VLDB	4.295436e-05
5,813	Space-efficient Substring Occurrence Estimation	2011	PODS	5.3170565e-05
5,404	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB	5.5267144e-05
13,272	On the String Matching with k Differences in DNA Databases	2021	VLDB	-
1,118	A Database Index to Large Biological Sequences	2001	VLDB	0.00013879121
4,333	An Efficient Index Structure for String Databases	2001	VLDB	6.2805237e-05
6,319	ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings	2012	VLDB	5.1132714e-05
2,250	Genome-scale Disk-based Suffix Tree Indexing	2007	SIGMOD	9.2009942e-05
4,550	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD	6.0924864e-05
2,583	Practical Suffix Tree Construction	2004	VLDB	8.497732e-05