Timeline for How fast can we identifiy almost-duplicates in a list of strings?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2014 at 18:49 | comment | added | Eran Medan | @Raphael thanks for the comments! I guess I shouldn't have used "expected values" since it has a statistical meaning, I meant more of "assumed values" e.g. an upper bound. | |
| Jun 11, 2014 at 16:09 | comment | added | D.W.♦ | @Raphael, 1) That's why I asked for the context and whether this is a practical situation. Based upon the 2nd comment, the answer appears to be yes, it's a practical situation (in which case typical values are relevant for choosing which algorithms are likely to be most suitable in his context). Probably the question should be edited to ask for a good algorithm for his situation rather than the best possible big-O bounds. | |
| Jun 11, 2014 at 6:19 | comment | added | Raphael | 1) The "expected values" are utterly irrelevant for O-bounds. 2) There is no single upper O-bound. Do you mean $\Theta$? 3) Optimal algorithms are notoriously hard to find. Are you satisfied with any "good" one? How good is good enough for you? 4) What FrankW said. If you don't fix one element, the problem is not well-defined. | |
| Jun 11, 2014 at 6:16 | history | edited | Raphael | CC BY-SA 3.0 |
edited tags
|
| Jun 11, 2014 at 1:51 | history | edited | Eran Medan | CC BY-SA 3.0 |
added some clarifications and expected values
|
| Jun 10, 2014 at 15:41 | comment | added | Eran Medan | @D.W. sorry, I edited the comment, T is probably between 1 and 3. | |
| Jun 10, 2014 at 10:24 | history | tweeted | twitter.com/#!/StackCompSci/status/476308966302289920 | ||
| Jun 9, 2014 at 22:21 | answer | added | D.W.♦ | timeline score: 3 | |
| Jun 9, 2014 at 21:38 | comment | added | FrankW | Note that "edit distance < $T$" is not transitive, i.e. you might have words $u$, $v$, and $w$, where $u$ and $v$ resp. $v$ and $w$ are duplicates of each other by your definition, but $u$ and $w$ are not. How do you want to deal with such cases? Also, the info from your previous comment should be incorporated into the question, in order to make it self contained. | |
| Jun 9, 2014 at 20:32 | comment | added | D.W.♦ | Great, and what's $T$? There are some algorithms that are much more efficient than pairwise edit distances, but they depend heavily on $T$. | |
| Jun 9, 2014 at 20:26 | comment | added | Eran Medan | @D.W. Thanks! it's for finding duplicate addresses, N can be very large, M is the maximum length of a possible address (any address in the world) I would assume the maximum longest address possible (longest street name + place name) is still below 200 chars. for simplicity we can assume even smaller M, e.g. 50 will most likely be covering 99% of the cases. N can be in the range of several millions. let's say 1 million for simplicity. {T} is probably 2-3 max, although some address variations are swapping whole worlds, not just chars. (e.g. Foo avenue / Avenu of Foo). but let's ignore this :) | |
| Jun 9, 2014 at 20:11 | answer | added | Ari Trachtenberg | timeline score: 1 | |
| Jun 9, 2014 at 19:17 | comment | added | D.W.♦ | It depends. What is the context in which you have run across this question? If it is a practical situation, there are potentially better algorithms than computing the edit distance $N^2$ times. If it is practical, can you give us a sense of the rough size of $N$, $M$, and $T$? Also, what research have you done? We expect you to do a significant amount of research before asking. There are lots of resources on how to compute the edit distance and the asymptotic running time of doing so. | |
| Jun 9, 2014 at 16:27 | review | First posts | |||
| Jun 9, 2014 at 21:38 | |||||
| Jun 9, 2014 at 16:18 | history | edited | Eran Medan | CC BY-SA 3.0 |
edited body
|
| Jun 9, 2014 at 16:10 | history | asked | Eran Medan | CC BY-SA 3.0 |