Suffix arrays use less memory for faster text search queries
Tiny Suffix Arrays
Data Structures and AlgorithmsInformation Retrieval
Summary
Suffix arrays help computers find patterns in text quickly but usually need a lot of memory. The authors show a way to use smaller extra data structures to answer queries with only a small slowdown in speed. Their method lets you balance memory use and query time based on available resources. This means searching in texts can be more memory-efficient without a big drop in performance.
What this means in practice
- •For database engineers: Build indexes for large text datasets that use less memory while keeping query times reasonable.
- •For compression software developers: Use smaller suffix arrays to speed up pattern detection during data compression with limited memory.
A theory result. No direct application yet.
Authors
Sharma V. Thankachan
Abstract
Suffix array and inverse suffix array queries on a text of length $n$ can be answered in $\widetilde{O}(τ^3)$ time using an auxiliary data structure occupying $O(n/τ)$ words, for any $τ\in [1,n]$.