Search Results

Time series data can often be represented as a string T[1..n] over an integer alphabet Σ. A standard approach for indexing such strings is the compressed suffix tree, which supports efficient exact pattern matching using 𝒪(n log |Σ|) bits of space. However, when |Σ| is close to n, as is often the case for time-series data, this yields little to no space savings over the classical Θ(n log n)-bit suffix tree. In this work, we study a different parameter that is often much smaller than |Σ|: the maximum absolute difference between consecutive values in T, denoted by Δ. Although representing T in 𝒪(n log Δ) bits is straightforward, supporting efficient pattern matching within this space bound remains challenging. By leveraging succinct data structure techniques, particularly the FM-index, we obtain a compressed index occupying n log Δ + 𝒪(n) bits. Given a query pattern P[1..m], the index answers counting queries in 𝒪(m log Δ) time and reporting queries in 𝒪(m log Δ + occ ⋅ log n ⋅ log Δ) time, where occ denotes the number of occurrences of P in T. In addition, the structure supports suffix array and inverse suffix array queries in 𝒪(log n ⋅ log Δ) time. Our construction is conceptually simple. We show that the local-difference bound induces a strong form of locality in the Burrows-Wheeler Transform (BWT), allowing the transformed text to be decomposed into regions that each use only a small local alphabet of size 𝒪(Δ). This makes it possible to adapt the classical FM-index so that its space usage depends on Δ rather than the overall alphabet size, while still supporting efficient pattern matching queries.