0
$\begingroup$

I have two very large files with numbers seperated by commas. What is most efficient/fastest way to say with some confidence that these two files have same numbers.

The main rule if if two distributions are the same, also the order of data does matter for example:
A = {1 2 4 5 6}
B = {6 5 4 2 1}
C = {0.5 0.5 1 2 3 4 5 6}

in above case A and C are still similar but A and B are totally different

To be more clear lets split the question into 3 main tasks

  1. Given large lists A,B find if lets say 50% of A is contained in B (Most efficient technique without comparing all numbers from list)

  2. Given A,B match above condition check that the overlapping numbers have similar order as mentioned above i.e. if 2 in A is followed by 1 same should happen in B. The positions of 1,2 can be different in B.

  3. Select two independent batches from A and B and test if those are from Poission distribution, binomial distribution.

$\endgroup$
  • 1
    $\begingroup$ If you expect that the files are equal bit for bit, you can compute a hash, say SHA256. If the hash is equal you can be reasonably sure that the files are equal. Similarity as implied by your title is much more difficult. $\endgroup$ – adrianN May 23 '16 at 13:12
  • 1
    $\begingroup$ You need to specify more precisely what "similar" means. Community votes, please: unclear? $\endgroup$ – Raphael May 23 '16 at 14:26
  • 1
    $\begingroup$ There is a big problem, without definition of similarity, when you say that order does matter and at the same time you want answer with some confidence, there is no way to know how to handle [6,1,2,3,4,5], [1,2,3,4,5,6] - similar to me. To say similar with confidence - do you give e.g. 10% as input (this much it might deviate) or expect this as result - files are similar with 10% margin? $\endgroup$ – Evil May 23 '16 at 15:24
  • $\begingroup$ 1) is doable, 2) is vague but looks like some kind of predictive packing, 3) looks like different question unless you are sure that samples are only from two distributions given, the 50% overlap is the discarded part and this makes your similarity test working. Let me try to tell you possible outcome to see what part of question is missing. 1) the result says 64.6% overlap, 2) 39% of numbers successors from A match those of B. 3) for A both are YES, for B both are NO. Or perhaps you have some results from $\chi^2$? How do you merge results into one conclusive test? $\endgroup$ – Evil May 24 '16 at 3:41
  • $\begingroup$ The whole idea is give a weightage to these three tests (or any other in future). like score = c1*(test1 score)+c2*(test2 score) + c3*(test 3 score) and use supervised machine learning on calculating value of c1,c2,c3. I can take care of ml part but need some statistical/algorithms for the test computations. Some vague ideas also works, give me hints to jump on :) $\endgroup$ – rohit May 24 '16 at 7:40
1
$\begingroup$

Check out Jaccard Similarity, as it gives a measure of set similarity. See MinHash, locality sensitive hashing.

$\endgroup$
0
$\begingroup$

Anwser is hashing.

  • Lists are small enough to fit in memory, are unsorted and scanning through them completely with a single machine counts as quick, then the idea of building a hash set out of the smaller list and then scan the larger for matches.
  • One of the lists is small enough to fit in memory and you need to use more than one compute to make scanning the larger list fast enough, then scanning the small list on all machines or scanning on one and passing the hash set around will allow you some speedup.
  • If the small list is too large, then building partial hash sets on many machines can work. Distribute the hash sets according to some modulo method. Each machine would then read part of the bigger list and send the list element according to the same hash modulo method the first list hashes were distributed.

MapReduce will help you in this journey too.

Breakthrough achievements:

Google Teams With Prodigal Son to Bust Data Sort Record

Breaking the Minute Barrier for TeraSort

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.