# Sliding Suffix Tree
## 4 Conclusions and Open Problems  
In this paper, we presented a sliding suffix tree for performing online substring queries on a stream of characters from the alphabet of constant size. By extending previous work by [PERSON], [PERSON], [PERSON], and [PERSON] [14; 16; 18], we designed a novel data structure, the use of which can find all positions of the given substring inside the window in optimal \(\Theta(m+occ)\) time, where \(m\) is the length of the query and \(occ\) the number of its occurrences. Furthermore, the updates are done in amortized \(O(1)\) time.  
An open question remains whether the data structure can be updated in the worst case \(O(1)\) time. There is a well known linear-time suffix-sorting lower bound [25], but to our knowledge, no per-character lower bound has been explored. [PERSON]'s algorithm requires, by design, an amortized \(O(1)\) time for updates, due to the implicit buffer of un-finalized nodes. To the best of our knowledge, no other online suffix tree construction algorithms have been developed without such an implicit buffer.  
As stated, we assume the alphabet \(\Sigma\) of constant size. For \(\Sigma\) of arbitrary size, the current implementation of the suffix tree requires an additional factor of \(\lg|\Sigma|\) time to determine a child in a tree, but keeping the same space complexity. An interesting question is whether the same asymptotic times can be achieved for integer alphabets as was done in [25] for texts of fixed length. In our case \(|\Sigma|=O(|W|)\), but the alphabet can change in time.  
Streaming algorithms are common in heavy throughput environments and therefore it is desirable to involve parallelism, including distributed processing. Most of the research involving parallelism assumes either a static text (parallel construction of a suffix tree, e.g., [26; 27; 28; 29]) or a static data structure (parallelization of a query, e.g., [30; 31]). On the other hand, because the data structure between updates does not change, individual queries can generally be done in parallel. In our case, the updates are coming sequentially, which raises the question of whether the presented data structure can be adjusted to support shifts in a pipeline fashion. Moreover, going to the underlying [PERSON]'s algorithm, it is not known whether it is possible to parallelize an update itself. Finally, coming back to our case, it is an open question of how to process interleaving queries and updates in parallel.  
The presented data structure, while theoretically feasible, should also be competitive in practice. [PERSON] already provided code for maintaining the indexed sliding window ([16], Appendix A), but without reporting all substring positions. However, the code can be extended to report them. In general, the main practical concern of tree-based data structures is space consumption and cache inefficiency. To alleviate this, the data structure should be implemented succinctly (e.g., [32]), with an appropriate cache-efficient scheme (e.g., [33]).  
**Author Contributions:** The authors contribute equally to this work.  
**Funding:** The work is partially supported by the Slovenian Research Agency (research core funding No. P2-0359 and N2-0053).  
**Acknowledgments:** We would like to thank anonymous reviewers of Combinatorial Pattern Matching 2018 for valuable references to the related work and their ideas for simplifying the queries without using the lowest common ancestor auxiliary data structures used in the previous version of this paper [34].  
**Conflicts of Interest:** The authors declare no conflicts of interest.