I would like to make a program which finds similar packets (there might be more then one class of similarity) in packet list (which is updated all the time). Are there any efficient algorithems to find these similarities?

By similarities I mean that they have the same size, type and payload.

I thought about using tree(with conditions on the branches just like decision tree) or vector support machine with k classes (k>2), but it means that it should have a lot of classes/nodes. Say there are 10 different packets and 2 kinds of similar packets (3 packets in each group). Then there will be 10 classes with single packet, 2 classes with 3 packets - So its size depends on the amount of packets which can be really big.

thank you

  • $\begingroup$ Can you clarify what you mean by similarity? How would you like to measure similarity? There are many possible ways one could do it. Small edit distance? Contains a large byte sequence in common? Something else? $\endgroup$ – D.W. Mar 28 '17 at 23:14
  • $\begingroup$ edited the question. $\endgroup$ – Adi Ml Mar 29 '17 at 14:32

There are many possible approaches for measuring document similarity:

I suggest you think more about what metric makes sense for you, and review the literature on information retrieval and natural language processing to see what metrics have been used in other contexts.

  • $\begingroup$ I read about these algorithems, but is not them slow algorithems (for example, it is expensive to create the shingles in the w-shingles algorithem). and I have to find all the similarities in the list $\endgroup$ – Adi Ml Mar 29 '17 at 14:36
  • $\begingroup$ @AdiMl, if you knew about an approach and had rejected it for some reason, it would be good to mention it in the question, so we don't waste our time telling you something you already know; and to make sure to state the explicit requirement that the approach you rejected violates. See cs.stackexchange.com/help/how-to-ask. But I don't follow you; w-shingling is very fast. If you're finding it slow, maybe you haven't quite understood how to implement it (?), or maybe you have a different definition of slow. Either way, I encourage you to edit the question to clear this up. $\endgroup$ – D.W. Mar 29 '17 at 15:06
  • $\begingroup$ I already mentioned in the question what I rejected. I am sorry, this algorithem looked slow to me, but I don't quite know this algorithem, so I believe to you saying it is fast and will try it myself. thanks again. $\endgroup$ – Adi Ml Mar 29 '17 at 17:03

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.