Timeline for Estimate the maximum frequency of substring with given length in a very long character stream
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 20, 2016 at 15:50 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 21, 2016 at 15:48 | answer | added | D.W. | timeline score: 1 | |
| Oct 21, 2016 at 14:26 | history | edited | xyguo | CC BY-SA 3.0 |
added 861 characters in body
|
| Oct 21, 2016 at 14:08 | comment | added | xyguo | @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 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. | |
| Oct 21, 2016 at 14:01 | comment | added | xyguo | @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$" | |
| Oct 20, 2016 at 21:13 | review | Close votes | |||
| Oct 29, 2016 at 15:49 | |||||
| Oct 20, 2016 at 20:59 | comment | added | D.W. | 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. | |
| Oct 20, 2016 at 20:55 | comment | added | D.W. | 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 (..)? | |
| Oct 19, 2016 at 14:56 | history | asked | xyguo | CC BY-SA 3.0 |