<p>If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l_0$, when $S$ is drawn randomly from $D^n$.</p>

<p>For a simple example, consider the case where $B=2$ and $D$ is the uniform distribution on $\Sigma$.  Then</p>

<p>$$l_0 \approx {\lg(n^2/2) \over \lg |\Sigma|},$$</p>

<p>due to the birthday paradox.</p>

<p>Thus, an algorithm can ignore the input string $S$, look only at $B,n$, compute the appropriate $l_0$, and output that.  This will be approximately correct, almost all the time.</p>

<p>That's why I say this can be treated as purely a mathematical question, not an algorithmic one.</p>

CC BY-SA 3.0
2016-10-21T15:48:08.643Z
2016-10-21T15:48:08.643Z
D.W.
<p>Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal is to find the solution of following problem:
$$
\begin{align*}
\min_{l\in\mathbb{N}} &amp;\quad l \\
\text{s.t. }&amp; \max_{s\subset S, |s|=l} \ \text{freq}(s) &lt; B
\end{align*}
$$
i.e., I want to find a length $l_c$, such that for "any" substring $s\subset S$ with length $|s|&gt;l$, it occurs no more than $B$ times. </p>

<p>Assume every character in $S$ obeys the same known distribution $D$: $S[i]\sim D, \forall i\in[N]$. Here we can allow some violations in the constraint, only requiring 
$$
\Pr[\max_{s\subset S, |s|=l} \ \text{freq}(s) &lt; B] &gt; 1-\delta.
$$</p>

<p>Currently I'm using a brute force approach, testing each $l$ from small to large, where for each $l$ I scan through the whole string $S$ to determine if there is one substring occur too often. This is very inefficient since $|S|$ is huge. </p>

<p>So I want to know if there exists some <strong>sub-linear</strong> (w.r.t. $N$) algorithm that can estimate the maximum frequency of substrings with fixed length.</p>

<hr>

<p>Maybe I didn’t make it clear. Here is my problem:</p>

<ol>
<li><p>Given a constant $B$ and the length of the string $N$, I want to find the minimum length $l$, such that all $l$-long substrings occur no more than $B$ times. Is there a algorithm better than simply testing from small to large?</p></li>
<li><p>If it's expensive to determine the exact $l$, an approximated $l$ is also acceptable. Here "approximated" has two meanings: $l$ can be smaller than the true $l_c$ as long as there're not too many violating $l$-long substrings; or it can be larger that $l_c$, but not too far away.</p></li>
<li><p>Furthermore, if the distribution of input character is highly skewed (i.e., some characters occur far more often than others), can I find an approximate or exact $l$, such that all $l$-long substrings <strong>starting with some fixed character $s$</strong> occur no more than $B$ times? </p></li>
</ol>

CC BY-SA 3.0
2016-10-20T20:55:37.097Z
Welcome to TCS.SE!  I don't understand the probabilistic part of your question.  What's the random variable?  What is the probability taken over?  The random choices of the algorithm (which determine $l,B$)?  The random choice of the string $S$?  Both?  If $l,B$ are fixed and $S$ is random, then this is purely a mathematical question, not an algorithmic one.  Finally: What is your question?  In the last sentence you say you want an algorithm to do something.  What are the inputs, and what are the desired outputs?  $S,l$ are the inputs, and you want it to output a $B$ such that (..)?
D.W.
CC BY-SA 3.0
2016-10-20T20:59:04.323Z
Also, do you allow linear-time preprocessing that depends only on $S$ but not on $l$?  If you do, have you looked at suffix trees?  There is a deterministic $O(N)$ time algorithm that will find the exact answer to the problem in your first paragraph, by building a suffix tree and then labelling each node with the number of suffixes that pass through it.
D.W.
CC BY-SA 3.0
2016-10-21T14:01:34.150Z
@D.W. The budget $B$ is a given constant and $S$ is random. I stated the probabilistic part because: firstly, I can get distribution information of $S$ and want to exploit it; secondly, an randomized/approximated solution is acceptable. You can just view the probabilistic part as requiring "for all $l$-long substrings, no more than a small fraction of them have frequency exceeding $B$"
xyguo
CC BY-SA 3.0
2016-10-21T14:08:09.343Z
@D.W. As for the suffix tree you mentioned, actually I was building a suffix tree. But in my case, an $O(N)$ construction time is unacceptable because $N$ is just too large. I can't even afford to put the whole tree in main memory. So I turn to the [ERa](http://www.vldb.org/pvldb/vol5/p049_essammansour_vldb2012.pdf) algorithm which construct a suffix tree with limited memory. The "Virtual Partitioning" procedure of ERa helps, but I wonder whether there exists a better solution.
xyguo
<randomized-algorithms><streaming-algorithms>
Estimate the maximum frequency of substring with given length in a very long character stream
xyguo
# Estimate the maximum frequency of substring with given length in a very long character stream

(Asked by: username_0 on 2016-10-19)

Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal is to find the solution of following problem:
$$
\begin{align\*}
\min\_{l\in\mathbb{N}} &\quad l \\
\text{s.t. }& \max\_{s\subset S, |s|=l} \ \text{freq}(s) < B
\end{align\*}
$$
i.e., I want to find a length $l\_c$, such that for "any" substring $s\subset S$ with length $|s|>l$, it occurs no more than $B$ times.

Assume every character in $S$ obeys the same known distribution $D$: $S[i]\sim D, \forall i\in[N]$. Here we can allow some violations in the constraint, only requiring
$$
\Pr[\max\_{s\subset S, |s|=l} \ \text{freq}(s) < B] > 1-\delta.
$$

Currently I'm using a brute force approach, testing each $l$ from small to large, where for each $l$ I scan through the whole string $S$ to determine if there is one substring occur too often. This is very inefficient since $|S|$ is huge.

So I want to know if there exists some **sub-linear** (w.r.t. $N$) algorithm that can estimate the maximum frequency of substrings with fixed length.

---

Maybe I didn’t make it clear. Here is my problem:

1. Given a constant $B$ and the length of the string $N$, I want to find the minimum length $l$, such that all $l$-long substrings occur no more than $B$ times. Is there a algorithm better than simply testing from small to large?
2. If it's expensive to determine the exact $l$, an approximated $l$ is also acceptable. Here "approximated" has two meanings: $l$ can be smaller than the true $l\_c$ as long as there're not too many violating $l$-long substrings; or it can be larger that $l\_c$, but not too far away.
3. Furthermore, if the distribution of input character is highly skewed (i.e., some characters occur far more often than others), can I find an approximate or exact $l$, such that all $l$-long substrings **starting with some fixed character $s$** occur no more than $B$ times?

**Tags:** randomized-algorithms, streaming-algorithms

> **Comments:**
> **username_1**: Welcome to TCS.SE!  I don't understand the probabilistic part of your question.  What's the random variable?  What is the probability taken over?  The random choices of the algorithm (which determine $l,B$)?  The random choice of the string $S$?  Both?  If $l,B$ are fixed and $S$ is random, then this is purely a mathematical question, not an algorithmic one.  Finally: What is your question?  In the last sentence you say you want an algorithm to do something.  What are the inputs, and what are the desired outputs?  $S,l$ are the inputs, and you want it to output a $B$ such that (..)?  
> **username_1**: Also, do you allow linear-time preprocessing that depends only on $S$ but not on $l$?  If you do, have you looked at suffix trees?  There is a deterministic $O(N)$ time algorithm that will find the exact answer to the problem in your first paragraph, by building a suffix tree and then labelling each node with the number of suffixes that pass through it.  
> **username_0**: @username_1 The budget $B$ is a given constant and $S$ is random. I stated the probabilistic part because: firstly, I can get distribution information of $S$ and want to exploit it; secondly, an randomized/approximated solution is acceptable. You can just view the probabilistic part as requiring "for all $l$-long substrings, no more than a small fraction of them have frequency exceeding $B$"  
> **username_0**: @username_1 As for the suffix tree you mentioned, actually I was building a suffix tree. But in my case, an $O(N)$ construction time is unacceptable because $N$ is just too large. I can't even afford to put the whole tree in main memory. So I turn to the [ERa](http://www.vldb.org/pvldb/vol5/p049_essammansour_vldb2012.pdf) algorithm which construct a suffix tree with limited memory. The "Virtual Partitioning" procedure of ERa helps, but I wonder whether there exists a better solution.  

---

## 1 answers

### Answer by username_1 on 2016-10-21. Score: 1

If $D$ has high min-entropy, then there's a "sharp cut-off" phenomenom: there's a value $l\_0$ depending only on $n,B$ such that the value of $l$ is almost always very close to $l\_0$, when $S$ is drawn randomly from $D^n$.

For a simple example, consider the case where $B=2$ and $D$ is the uniform distribution on $\Sigma$. Then

$$l\_0 \approx {\lg(n^2/2) \over \lg |\Sigma|},$$

due to the birthday paradox.

Thus, an algorithm can ignore the input string $S$, look only at $B,n$, compute the appropriate $l\_0$, and output that. This will be approximately correct, almost all the time.

That's why I say this can be treated as purely a mathematical question, not an algorithmic one.


---

