Timeline for Probabilistic Substring Match
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7, 2017 at 5:50 | vote | accept | Scovetta | ||
| Feb 24, 2017 at 11:01 | history | tweeted | twitter.com/StackCompSci/status/835082248747696128 | ||
| Feb 21, 2017 at 6:32 | comment | added | KWillets | The average LCP between consecutive strings in a sorted list is a measure of how many characters need to be compared to get a unique match -- in your case you need at least log2(100M) = ~27 bits, but I'm guessing it's much more. | |
| Feb 21, 2017 at 4:56 | comment | added | Scovetta | Not sure about average, but the needles could be tokenized, with each token either coming from a set of size perhaps 300. They aren't at all random, so exploiting the structure would be very reasonable. | |
| Feb 21, 2017 at 4:50 | comment | added | KWillets | What's the average longest common prefix between the needles? | |
| Feb 21, 2017 at 3:35 | comment | added | Scovetta | Typical length of needles is less than 500 characters. Thoughts on approaches (not algorithms per se) were: DBMS "LIKE" query, DBMS full text search, pre-processing and then using straight 'grep'. I didn't see a way of getting the performance where I want it, hence I'm exploring here. I suppose LCS would work, but the complexity seems like it wouldn't work for this scale. On the other hand, the streaming case is similar to a search engine, so an inverted index might be the way to go. I also took a look at some of the code-search tools, but performance wasn't very good there either. | |
| Feb 21, 2017 at 3:35 | answer | added | D.W.♦ | timeline score: 2 | |
| Feb 21, 2017 at 3:17 | comment | added | D.W.♦ | What algorithms have you looked at so far? What's the range of typical lengths of the needles? | |
| Feb 21, 2017 at 1:20 | review | First posts | |||
| Feb 21, 2017 at 2:53 | |||||
| Feb 21, 2017 at 1:17 | history | asked | Scovetta | CC BY-SA 3.0 |