2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27287 2026-08-25T13:18:21Z ddc:004 open_access

Indexing Integer Strings Using Local Difference Bounds Gibney, Daniel Kaka, Kaamil Thankachan, Sharma V. String Algorithms Pattern Matching Suffix Trees Compact Data Structures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Gibney and Kaamil Kaka and Sharma V. Thankachan 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.151 urn:nbn:de:0030-drops-272870 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.151 eng https://creativecommons.org/licenses/by/4.0/legalcode