Speed up duplication detection process

[MrOrz]

Currently it's O(n^2) scan for all rumor entries.

https://github.com/MrOrz/rumors-db/blob/master/scripts/csvToElasticSearch.js#L108

Locality sensitive hashing should help, but requires effective design for the hashing bins.

[AnshulMalik]

How come is it O(n^2) ?

[MrOrz]

Given a document, findDuplication scans through each processed document to calculate similarity between them (O(n)).

If we process n documents, findDuplication is invoked 1+2+...+n times, which derives O(n^2).

I think hashing (more specifically, LSH) can help reduce the complexity of findDuplication to constant. But I have no idea how to implement LSH now.

[AnshulMalik]

Ok.

I'll try to find some solution, also, can you tell me where is this findDuplication function is called?

[MrOrz]

Thanks. Call path:

npm run seed in CLI
--> aggregateRowsToDocs() in csvToElasticSearch.js
--> https://github.com/MrOrz/rumors-db/blob/master/scripts/csvToElasticSearch.js#L43 and https://github.com/MrOrz/rumors-db/blob/master/scripts/csvToElasticSearch.js#L64.

[MrOrz]

It is said that Levenshtein Automata is useful when the character distribution is poor.

Not sure if it works, I just note it here: https://www.npmjs.com/package/node-levenshtein-automata

[MrOrz]

Please note that we are moving away from Airtable very soon. This issue will be trivial after the shift.

After that, in the seed script we no longer need to ask for similarities -- we can just provide static set of seed data, in which all rumors and answers are already unique.

See https://www.facebook.com/groups/1847232902175197/1896817880550032/ for the shift, and the derivative issues are #2 , #3 and #4 .

[MrOrz]

We have shifted to elastic search and this is no longer required.