Fall 2019 Finding Similar Sets Vassilis Christophides christop@csd.uoc.gr http://www.csd.uoc.gr/~hy562 University of Crete, Fall 2019 1 Fall 2019 Motivation  Many Web-mining problems can be expressed as finding “similar” sets: Pages with similar words, e.g., for classification by topic NetFlix users with similar tastes in movies for recommendation systems Dual: movies with similar sets of fans Images of related things  The best techniques depend on whether you are looking for items that are very similar or only somewhat similar Special cases are easy, e.g., identical documents, or one document contained character-by-character in another General case, where many small pieces of one document appear out of order in another, is very hard 2 1 1 Fall 2019 Comparing Documents for Near Duplicates  Applications: Given a body of documents, find pairs of documents with a lot of text in common, e.g.: Mirror Web sites, or approximate mirrors Application: Don’t want to show both in a search Plagiarism, including large quotations Similar news articles at many news sites Application: Cluster articles by “same story”  Simple IR approaches are not suited: Document = set of words appearing in document Document = set of “important” words Why? we need to account for ordering of words! 3 Fall 2019 Main Issues  What is the right representation of the document when we check for similarity? E.g., representing a document as a set of characters will not do (why?)  When we have billions of documents, keeping the full text in memory is not an option We need to find a shorter representation  How do we do pairwise comparisons of billions of documents? If exact match was the issue it would be ok, can we replicate this idea? 4 2 2 Fall 2019 Three Essential Techniques for Detecting Similar Documents Localitysensitive Hashing Document The set of strings of length k that appear in the document Signatures : short integer vectors that represent the sets,