# Sliding Suffix Tree
## 1 Introduction and Related Work  
Text indexing, pattern matching, and big data in general is a well studied field of computer science and engineering. An especially intriguing area is (infinite) streams of data, which are too big to fit onto disk and cannot be indexed in the traditional way, regardless of the data compression or succinct representation used (e.g., [1; 2; 3]). In practice, stream processing is usually done so that queries are defined in advance, and data streams are processed by efficient, carefully engineered filters. One way of implementing string matching including regular expressions is by using finite automata [4; 5]. This approach is used by the well-known grep command. Instead of matching the pattern characters with the text, we could use a rolling hash and compare the pattern's _fingerprint_ with the fingerprint of the current sliding window [6; 7; 8]. String matching is also used in digital forensics, where we typically match multiple regular expressions on massive amounts of data, which involves multiple streams and parallelism [9; 10; 11]. In intrusion detection systems, finite automata are replaced with neural networks, and by unsupervised machine learning we can avoid hard-coding malicious patterns [12; 13]. In our research, we consider a slightly different setup. There is an infinite stream of characters, where the main memory holds the most recent characters in terms of a big sliding window. At any moment, a user wants to find all positions of the given substring in the current window. The stream processing filters described in the previous paragraph could easily solve this issue, if the queries were known in advance. However, since the queries are provided on-the-fly, the filters would need to re-scan the sliding window, which requires at least linear work in terms of the size of the window. The only way to speed up the query for the order of magnitude is to _index_ the sliding window. [PERSON] and [PERSON] [14] defined an indexed sliding window based on a suffix tree, and they based their work on [PERSON]'s suffix tree construction algorithm [15]. Their primary application was data compression, and the main contribution was the maintenance of the indexed sliding window. However, the query operation was different from ours. For data compression, they wanted to determine _the length and the position of the longest prefix_ of the given pattern in the sliding window. [PERSON] revised work of [PERSON] and [PERSON] in his PhD thesis [16], and presented it in a new light using the primitives from [PERSON]'s more recent suffix tree construction algorithm [17]. [PERSON] also provided a referenceimplementation of his data structure. Furthermore, [PERSON] revisited both works by [PERSON], [PERSON], and [PERSON] and noticed a flaw in the window maintenance proof [18]. Fortunately, the underlying data structure was designed correctly and he only needed to correct the proof. Another approach for indexing the sliding window is by using the compact directed acyclic word graph, also known as the suffix automaton [19]. The suffix automaton can be constructed on-line for the whole text [20] or maintained as a sliding window [21]. Both approaches use [PERSON]'s suffix tree construction algorithm as a base. Originally, the suffix automaton was developed to efficiently decide whether the query string is included in the text. However, obtaining _all positions_ of the query in the text requires performing depth first traversals over the automaton and takes linear time in terms of the size of the sliding window. For our application, we cannot afford this time. Recently, a practical suffix array based a sliding window was proposed by [PERSON] et al. [22; 23], with speed improvements by [PERSON] et al. [24]. Their approach supports efficient substring query operations, but updating the suffix array requires at least linear time due to the nature of the array, i.e., insertion and/or removal of an element requires the other elements to shift by one slot.