Winnowing: Local Algorithms for Document Fingerprinting (2003) [pdf]
theory.stanford.edu
theory.stanford.edu
There are also interesting references at http://en.wikipedia.org/wiki/Plagiarism_detection#Fingerprin....
Edit: Thank you all for the excellent comments.
What do you mean by blogspam?
If you had pure article text, you can do a pretty good job. An obvious technique is to build a histogram over 1,2,3 grams then do something like cos_sim. This sounds very slow but you don't have that much content and can be easily sped up via lsh. That doesn't solve your containment problem, but it helps w/ dups. Containment could potentially be done via windowing.
edit -- i'm sure you've reached out, but there's a yc founder with a lot of experience doing both of these.
edit2 -- of the two challenges: 1 - turning url into extracted text, and 2 - fingerprint matching, #1 strikes me as much harder
edit3 -- I'm going to suggest the plagiarism detection is probably misleading because they're working with already clean text, eg word or txt representations. If you want fingerprinting to work, you need to test it with all the page cruft or your best attempt at quickly cleaning page cruft. Again, I think you'll find this harder.
I'm definitely not an expert in this area, but I know coworkers have used MinHash for similarity detection.
Alternatively (and more simply if you already have a search index), Lucene has a 'more like this' feature that also works pretty well in practice. It takes a document's tokens and submits them all to the search index in one query.
For when you've got a really big pool of documents to look through, simhash tends to be higher-performance because of the tiny fingerprints it uses. It also tends to force you into making stark decisions about precision vs. recall, though. Depending on your needs you might be able to make up for less-than-stellar precision by cleaning up false positives after the fact.
Sort the two lists of sha1 block hashes. Then do a merge-compare of the two lists of hash. Blocks of same content have the same hash. See how many blocks are the same out of the two lists. Compute a percentage of similarity. Have some threshold to declare the two files are similar or not.
Rolling Hash is good in finding dynamic boundaries of similar blocks, gracefully handling addition, deletion, and movement of content. Once the block boundaries are known, use sha1 to strongly find equivalence. Sorting the two lists allows comparing out-of-order blocks.
[1] Content based slicing using rolling hash. http://en.wikipedia.org/wiki/Rolling_hash#Content_based_slic...
One of the nice things about locality-sensitive hashing algorithms for less-than-pristine data is that you can instead tune it to construct the fingerprint from a larger number of smaller samples, which makes it more likely that you'll get at least some samples which represent all signal and no noise.
Research in this area could trace back to the early days of information retrieval (such as tf-idf, http://en.wikipedia.org/wiki/Tf%E2%80%93idf). I am not quite familiar with the recent progress in this area, perhaps anyone could provide some pointers?
An interesting use case for the NCD is authorship attribution and plagiarism detection[3]. At one point during my project, while I was collecting documents for the corpus we used - I noticed very low NCD scores between some of the documents.
Sure enough, all of the documents with a compression distance between ~0.01 and 0.1 were either complete or heavy plagiarizations of each other! We lost around 15 documents, but at least we knew the NCD functionality was working! :)
if you think including NCD measurements in your system could be helpful, be sure to check out the findings from [4] if you'll be working with any larger documents.
[1] - http://en.wikipedia.org/wiki/Normalized_compression_distance
[2] - http://homepages.cwi.nl/~paulv/papers/cluster.pdf
[3] - http://www.inf.ufpr.br/lesoliveira/download/FSI2013.pdf
For blogspam detection can't PG whip up a nice Bayesian model for that ;) ? Again if you want fast and large scale spam filters see Vowpal Wabbit: http://hunch.net/~vw/ . For something more advanced see scikit-learn: http://scikit-learn.org/ which has many algo's up for this task.
A new option you may not have considered yet, is to crowdsource this task. Just offer a labelled dataset and let the HN and ML community have a go at it. I'd love to do content and URL-based spam modelling.
Also another thing to consider is the visiting traffic on HN is much much less than either google or yahoo (HN currently ranked as #3100+, while as a comparison slashdot ranked #1700+, according to the alexa)...And there seems to be heavy skew in the geological distribution of the originators' IP...Perhaps a carefully tailored system would outperform the existing framework here...
Vowpal Wabbit is made to scale. You set a fixed bitsize and words and n-grams are hashed. So if you expect 2^32 unique words you set the bitsize to around 32. More data is usually better. Linear speed-ups by adding parallel machines.
I too think that HN's user patterns could be different than other web estates. With large scale spam filters like at Yahoo mail, I believe they employ two (or more) models: One fitted on your inbox, and one fitted on everyone's inbox. That ensemble model should be able to specialize on your behavior, yet still be able to detect general spam that it has already seen in other boxes.
>Is this the basic assumption that close documents also have close information entropy?
Yes, that is the gist of it. The better the compressor, the closer NCD will approximate NID.
A simple principle: Compressors do a better job on repeating data patterns. If two files or documents share data patterns, then adding these together and compressing, will result in a smaller filesize, than if you concatenate and compress two files that don't share any data patterns.
NCD works on text, but not as good as other algo's for NLP. Sometimes PAQ (very slow, but efficient compressor) is used on genome data, or bzip on binary files like virusses. I don't think it will be practical here, since for a comparison every other file would need to be concatenated and compressed. If not using a fast compressor like Snappy or Gzip this would take a while, over a simple cosine distance between tokens.
Slightly worse? because it has to go to different nodes to do the match, and hence incurs a slight delay which then incurs a bit inconsistency of the sample base?
> I too think that HN's user patterns could be different than other web estates.
That's a better generalization...
perhaps some more mining could be done based on this, such as the social clustering ; and also perhaps construct different language/wording models for the different interest/area groups (by posts) -- after all, there is no language model that fits them all...
And as in terms of spam detection, I assume if an ID, or originating IP, replies to almost every post, then it's unlikely the quality of his post would be high...Well, this returns to that fundamental question, how do you define "spam" in the space of HN?
> With large scale spam filters like at Yahoo mail, I believe they employ two (or more) models: One fitted on your inbox, and one fitted on everyone's inbox. That ensemble model should be able to specialize on your behavior, yet still be able to detect general spam that it has already seen in other boxes.
Interesting...It would be interesting to see how often the two models produce inconsistent results...Then if you biased towards one, then what's the use of the other one? Or perhaps they devised some strategy to combine the two models...
>NCD works on text, but not as good as other algo's for NLP. Sometimes PAQ (very slow, but efficient compressor) is used on genome data, or bzip on binary files like virusses. I don't think it will be practical here, since for a comparison every other file would need to be concatenated and compressed... perhaps
NCD and NID are theoretically charming...but perhaps they are only good for pure coding without much context to depend on...there are just tons of information outside the analysis target, especially a natural language, that would be hard to take into the calculation of the entropy model...By the way, in terms of the similarity analysis based on compressed binary, there was a paper (peHash) published a few years ago that was interesting.... https://www.usenix.org/legacy/event/leet09/tech/full_papers/...
Another issue with the entropy is, it's easy to inject some tokens to manipulate the frequency...In this case, some preprocessing should be in place...
VW is the (open-source) state of the art. If you want a linear learner, use it.