minhash

• group.py helper module
• seqmatch.py uses sequence matching to find similar text files
  • seqmatch_m.py is the multithreaded version
• minhash.py uses MinHash and Jaccard similarity estimation algorithms, based on http://mccormickml.com/2015/06/12/minhash-tutorial-with-python-code/
  • minhash_m.py is the multiprocessing version, with shared memory access and simplified data structures (Unix only)
    • minhash_m_init.py is Windows-compatible; uses an initializer to preserve global variable states https://medium.com/@rvprasad/data-and-chunk-sizes-matter-when-using-multiprocessing-pool-map-in-python-5023c96875ef
    • minhash_dss.py uses delimited search space
    • minhash_v.py is the vectorized version; the use of an initializer avoids synchronization stalls and memory bubbles with large inputs. Unix only, as changes to the NumPy array do not get carried back to the main process in Windows

lessons learned

• a simple heuristic can significantly decrease running time while still finding a large majority of similar files
• if the input iterator is very large, using map will lead to a segmentation fault
• if a function returns results faster than they can be consumed, using it with imap and imap_unordered will cause a memory bubble
  • https://stackoverflow.com/questions/40922526/memory-usage-steadily-growing-for-multiprocessing-pool-imap-unordered
  • https://stackoverflow.com/questions/9862091/iteration-over-pool-imap-unordered
• pypy3 is significantly faster than python3, but it did not support Numba
• minimize your inputs before passing them off to a function (e.g. grouping results uses connected_components from networkx which had high space complexity)
• vectorize, if possible

measurements

a random selection of non-duplicate text files of varying sizes (0-1767kb):

script	interpreter	1500	5000	10000	20000	50000
seqmatch.py	python3	2503.13s
seqmatch_m.py	python3	658.70s
minhash.py	pypy3	10.52s	67.52s	266.74s	1060.77s	8278.96s
minhash_m.py	pypy3	7.87s	51.07s	190.73s	859.66s	4094.37s
minhash_m_init.py	pypy3	7.56s	52.22s	191.57s	680.1s	5070.27s
minhash_dss.py	pypy3	5.33s	22.19s	75.49s	189.22s	1019.88s
minhash_v.py	python3	3.06s	4.19s	6.19s	13.51s	59.42s