# A Survey on Shortest Unique Substring Queries
## 8 Discussion and Future Work  
In this paper, we reviewed several types of shortest unique substring queries and their corresponding solutions. All the discussed problems in this manuscript are highly motivated topics in string processing and computational biology research areas. Although we discussed more than 10 approaches for variants of \(\mathsf{SUS}\) queries, there still exist related topics which have not been studied, or there is no efficient algorithm to solve them. In this section, we discuss some of such topics and open questions for future work:  
* We discussed all the solutions to solve approximate \(\mathsf{SUS}\) queries in Section 5. However, there is no efficient in-place algorithm which can find \(\mathsf{LSUS}\)s to get \(\mathsf{SUS}\)s afterward. Another technique that can be applied to solve approximate \(\mathsf{SUS}\) queries is considering the \(RLE\) representation of the input string. Section 4.2 shows this technique for solving interval-\(\mathsf{SUS}\) queries. To our knowledge, an \(RLE\) based approach for solving approximate \(\mathsf{SUS}\) queries has not been studied. In addition, there is no work considering the standard external memory model for solving an approximate \(\mathsf{SUS}\) problem. As the I/O-efficient construction of the suffix array and \(\mathsf{lcp}\) array exist ([PERSON], 2015; [PERSON], 2016; [PERSON], 2017; [PERSON], 2018), it seems to be possible to change the RAM model algorithm for the construction of these arrays to the external memory model. * In Section 4.2, the \(\tau_{q}(N,m)\) in the query time of Theorem 6 is \(\sqrt{\log m/\log\log m}\), which is actually the time for performing dynamic predecessor/successor queries using \(\mathcal{O}(|RLE(\mathcal{S}))\) space ([PERSON], 2016). In order to make the query time faster using the same space, the question is if there exists a data structure of size \(\mathcal{O}(|RLE(\mathcal{S})|)\) that can efficiently answer Problem 3 without using predecessor/successor. * As we discussed in Section 6, palindromic substrings have great motivations in computational biology. All the reviewed works are on finding the exact \(\mathsf{SUPS}\)s. Similar to the approximate \(\mathsf{SUS}\) problem, approximate \(\mathsf{SUPS}\) query is also important to be studied for considering errors and mutations. Besides the definition of Problem 5, the following definition has a great motivation in bioinformatics. A nucleotide sequence is considered as a palindrome if the reverse of its complementary strand is equal to the original sequence ([PERSON], 2016). The question is if the methods discussed in Section 6 can be applied to efficiently solve this problem. * The last topic that we discussed was the \(\mathsf{rSUS}\) problem. According to Theorem 12, \(\mathsf{rSUS}\) queries can be solved in \(\mathcal{O}(\log_{w}n)\) time using a data structure of size \(\mathcal{O}(n\log n)\) word. The questionis whether we can design an efficient \(\mathcal{O}(n)\)-word data structure for the \(r\)SUS problem. In addition, the approximate version of \(r\)SUS queries has not been studied. It is possible to combine the technique discussed in Section 7 and the framework of [PERSON] et al. [50] to provide an efficient algorithm for approximate \(r\)SUS problem. * Besides shortest unique substrings, _Maximal Unique Matches_ is an important concept in computational biology for aligning two long genome sequences [51]. [PERSON] et al. [18] applied a similar technique discussed in Section 3.4 to find maximal unique matches of two strings. As far as we are aware, the dynamic version (when mismatches are allowed) of this problem has not been studied yet. We believe that, by modifying the techniques on the dynamic longest common substring problem (LCS after \(k\) mismatches) [52; 53; 54], the approximate Maximal Unique Matches problem can be solved in subquadratic time. Methodology, writing--original draft, P.A. ; writing--review and editing, M.O.K. ; supervision, writing--review and editing, S.V.T.