4 ms·
Finding duplicate issues should be an O(N^2) problem, I wonder how they manage to do it with 5.3k issues (28 million pairs)?
by blackbear_ 6y ago
Finding duplicate issues should be an O(N^2) problem, I wonder how they manage to do it with 5.3k issues (28 million pairs)?
- DominikD 6y agoInstitutional memory. If you work on a project long enough, you tend to remember these things. You may not recall the exact issue id, obviously, but you know you've seen something like this and there's a limited number of keywords you have to search to get there.
- Cthulhu_ 6y agoHopefully they can edit or label issues in such a way that helps with searching for duplicates; older issues become a knowledge base / documentation. IIRC it's what Stack Overflow tried to do, turn questions into wiki pages / references.
- ThePadawan 6y agoYou're not finding duplicates within open issues, you must find them among ALL issues. There are 20 times more, making that 400 times more pairs (10 billion).
- DannyBee 6y agoNobody does this in an N^2 way. See simhash, minhash, etc Trivial faster-than-N^2 algorithm: 1. Compute simhash of each issue - O(1) in N, the number of issues. 2. Sort the issues by hamming distance of simhash (N log N in the number of issues) 3. Pick the K issues before or after the current issue in the results (O(1) in the number of issues) You can precompute/incrementally update any of these steps as issues are added. This would make find duplicates itself O(1) because it would just be step 3. If you put this in term of size of text in the issues instead of number (which is what you used) it changes the time bounds, but, for example, it's not any worse than sorting/comparing the issues as text strings.