Source-linked AI summary
Lightweight Data Indexing and Compression in External Memory
Paolo Ferragina, Travis Gagie, Giovanni Manzini
TL;DR
Large-scale indexing and compression can be bottlenecked by construction algorithms that require substantial working space. This paper presents lightweight algorithms that use sequential scans to build BWT-based indexes and invert the BWT; its one-disk scan algorithms are within an O(log n) factor of the stated lower bound.
Problem
External-memory construction algorithms for full-text indexes use Θ(n log n) bits of working space, a potentially large burden relative to compressed output.
Source: §1 · p. 1Method
The paper develops lightweight external-memory algorithms for BWT-based index construction and BWT inversion that access disk data only through sequential scans.
Source: §1 · p. 2Results
The BWT construction algorithm uses n bits of disk working space and O(n/M) passes, while one-disk scan-based construction and inversion are within an O(log n) factor of the stated lower bound.
Source: §1 · pp. 2–3Takeaways & Limitations
The paper establishes lightweight scan-based algorithms and space×passes bounds for external-memory BWT construction and inversion.
Source: §1 · pp. 2–3The analysis uses the classical I/O model with M-word internal memory and O(1) unbounded-capacity disks, and counts sequential disk passes.
Source: §1 · p. 2
Abstract
from arXiv · showhide
In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size $n$, they use only ${n}$ bits of disk working space while all previous approaches use $\Th{n \log n}$ bits of disk working space. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the BWT that uses $\Th{n}$ bits of working space, and a lightweight {\em internal-memory} algorithm for computing the BWT which is the fastest in the literature when the available working space is $\os{n}$ bits. Finally, we prove {\em lower} bounds on the complexity of computing and inverting the BWT via sequential scans in terms of the classic product: internal-memory space $\times$ number of passes over the disk data.
1 Introduction
Building indexes and compressed data can become a bottleneck for large datasets because existing external-memory construction algorithms use Θ(n log n) bits of working space. The paper develops lightweight, sequential-scan algorithms for index construction and BWT inversion, and analyzes their space–pass complexity.
1 Introduction
- The motivation is that existing external-memory construction algorithms use Θ(n log n) bits of working space, potentially up to 500 times the compressed output size.Typical compressed outputs are three to five times smaller than the input and are O(n) bits in the worst case.Source: §1 · pp. 1–2
- The algorithms target disk-based construction with minimal working space and access disk data only through sequential scans.The paper studies building compressed or uncompressed full-text indexes and compressing data through sequential scans.Source: §1 · p. 2
- The BWT construction algorithm uses n bits of disk working space and O(n/M) passes; tests report it as the fastest currently available external-memory BWT tool.Its total space is Θ(n) bits, proportional to the input size.Source: §1 · p. 2
- The paper derives a lightweight internal-memory BWT algorithm, fastest in the literature when working space is o(n) bits, and algorithms for the suffix array, Ψ array, and suffix-array samples.These arrays are identified as ingredients of compressed indexes.Source: §1 · p. 2
- The BWT inversion algorithm uses Θ(n) bits of disk working space and O(n/M) passes with one disk or O(log^2 n) passes with two disks.The inversion algorithm is based on techniques different from those used for construction.Source: §1 · p. 2
- For one-disk scan-based BWT construction and inversion, the space×passes product is O(n log n) bits, within an O(log n) factor of optimal.The paper proves that this product cannot be reduced to o(n) bits with a one-disk scan-based algorithm.Source: §1 · p. 3
2 Notation
The notation section defines suffix-array order and its inverse, then introduces the BWT, Ψ, and sampled suffix-position values used in compressed indexes.
2 Notation
- The suffix array orders text suffixes lexicographically, while pos gives each suffix’s rank and is its inverse permutation.The paper also defines pos_d as the ranks of suffixes starting at d-spaced text positions.Source: §2 · p. 3
- The BWT stores the character preceding each suffix in suffix-array order, and Ψ maps a suffix rank to the rank of the suffix one character shorter.The BWT and Ψ are basic ingredients of most compressed indexes.Source: §2 · p. 3
- Compressed indexes may combine the BWT or Ψ array with pos_d, the set of ranks for d-spaced suffixes, for d = Ω(log n).The paper considers external-memory algorithms for computing all three ingredients.Source: §2 · p. 3
3 Lightweight Scan-Based BWT construction
bwt-disk constructs the BWT block by block, using sequential scans and n bits of disk working space. Its prototype was faster than DC3 on the tested files while using substantially less working space, though the asymptotic analysis predicts it can eventually be slower when M ≪ n.
Algorithm
- The algorithm partitions T into blocks of size m = Θ(M) and incrementally inserts each new block’s characters into the BWT of the already processed text.The insertion preserves the relative order of old BWT characters.Source: §3 · pp. 3–4
- The gap array counts old suffixes between adjacent new suffixes, enabling bwt-disk to merge the new and existing BWTs using the n-bit gt array.The algorithm computes gap in O(n) time using the n extra bits of gt.Source: §3 · pp. 4–5
Implementation
- The prototype keeps a reduced gt representation in RAM using a length-ℓ prefix and the bits for suffixes sharing that prefix; with ℓ = 1024, it used 128KB.Suffixes that differ from the prefix can be compared directly; matching suffixes use their stored gt bit.Source: §3 · pp. 6–7
Experimental results
- For all tested files, bwt-disk’s working space was below the uncompressed input size, while DC3 used over 30× that size.For Html-4, DC3 working space exceeded 500× the compressed BWT size; bwt-disk working space was at most that size.Source: §3 · p. 7, Figure 2 · p. 8
- bwt-disk was faster than DC3 on every tested file and used less working space; its I/O volume was below 6× input size except for Random2, at 14.76×.The runtime comparison ignores the additional cost of computing the BWT from DC3’s suffix array.Source: §3 · p. 7
- The asymptotic analysis predicts bwt-disk may eventually run slower than DC3 when M ≪ n, despite its faster runtime on the tested real-world inputs.The prototype stores compressed input and partial BWTs; the paper attributes its practical speed to compression and avoiding suffix-array construction.Source: §3 · pp. 7–8
4 Other Lightweight Scan-Based Construction Algorithms
The paper adapts its scan-based framework to construct suffix arrays, Ψ arrays, and sampled suffix-array positions, and derives a low-space internal-memory BWT algorithm. The Ψ representation can reduce processed data to O(n) bits, with working space n + o(n) bits.
Internal-memory BWT
- The internal-memory variant computes the BWT in o(n) working bits and can store the result in the space originally occupied by the input.The paper describes a time-space tradeoff, including an O(n log n)-time setting using 2n working bits.Source: §4 · pp. 8–9
Lightweight SA construction
- The suffix array can be computed in O(n/M) passes over Θ(n log n) bits of disk data using n bits of working space.The algorithm replaces the partial BWT with suffix-array entries and updates them using the gap array.Source: §4 · p. 9
Comparison with prior work
- Compared with the similar algorithm in [5], the new proposal reduces working space, processed data, and CPU time by a logarithmic factor.The algorithms share a similar structure and features.Source: §4 · p. 10
Lightweight Ψ computation
- Encoding Ψ differences reduces its processed disk data to O(n) bits and its working space to n + o(n) bits.The algorithm uses O(n/M) passes.Source: §4 · pp. 8, 10
Lightweight pos_d computation
- The sampled suffix-array positions pos_d can be computed in O(n/M) passes over Θ(n) bits of disk data using n bits of working space.The sampling step is d = Ω(log n), so the stored set contains O(n/log n) pairs.Source: §4 · p. 10
5 Lightweight Scan-Based BWT Inversion
The BWT inversion algorithm grows non-overlapping text substrings over repeated rounds, using list ranking to merge adjacent substrings and recover their order. It uses Θ(n) total disk bits, with pass costs depending on the number of disks.
Algorithm
- The algorithm grows n/log n non-overlapping substrings over O(log n) rounds, appending characters and merging adjacent substrings.The BWT and an n-bit mark array track characters already appended to the substrings.Source: §5 · pp. 11–12
- List ranking detects adjacent substrings and orders them for merging; the algorithm adds new unmarked characters to keep the substring count at n/log n.Each round requires a constant number of sort/scan primitives over O(n) items.Source: §5 · pp. 11–12
Algorithm and bounds
- BWT inversion uses Θ(n) total disk bits, with O(n/M) passes on one disk and O(log^2 n) passes on two or more disks.The theorem also gives an I/O bound for random disk accesses, but the algorithm discussed here is scan-based.Source: §5 · p. 11
Recovering T
- Once the substrings cover T without overlap, list ranking orders them by their successor links so they can be sorted to recover T.The starting position of a substring in the BWT alone does not determine its position in T.Source: §5 · p. 12
6 Lower bounds
The section proves that, in the worst case, one-disk sequential-scan algorithms need a memory-bits × passes product of at least linear size to compute or invert the BWT. The paper's algorithms have an O(n log n)-bit product, within an O(log n) factor of this lower bound.
6 Lower bounds
- O(n log n) bits: the authors' scan-based algorithms have a memory-size × passes product within an O(log n) factor of the one-disk lower bound.The lower bound is best-possible: with Ω(n) bits of memory, the input can be read in one pass before computing the BWT.Source: §6 · p. 12
- Unlike the earlier result based on De Bruijn sequences, this lower bound targets BWT computation itself and gives a stronger bound with a direct proof.The earlier result ruled out entropy-only bounds with polylogarithmic memory and passes.Source: §6 · pp. 12–13
- The proof combines a disk-segment reconstruction lemma with the fact that periodic strings have BWTs consisting of relatively few runs.Memory configurations at each pass, together with the disk segment's initial or eventual contents, suffice to reconstruct that segment.Source: §6 · p. 13
- o(n) bits: no one-disk sequential-scan algorithm can compute or invert the BWT in the worst case when memory bits × passes stays below this threshold.Theorem 7 gives the linear lower bound for both operations.Source: §6 · p. 13
- For computation, a repeated substring of length r can be replaced by a BWT substring with o(r) runs, although storing the original substring takes Ω(r) bits.The reconstruction lemma then forces the memory-size × passes product to be at least linear in r.Source: §6 · p. 13
- The inversion argument similarly uses overwritten BWT substrings with o(r) runs to show that a one-disk algorithm cannot have an o(n) memory-size × passes product.The proof applies the same reconstruction reasoning to the repeated substrings of the text.Source: §6 · p. 13