Hi, Can anyone please point me a good data set on which I might try SimHash clustering ? Thank you,
Cristi On Tue, Mar 23, 2010 at 10:35 AM, cristi prodan <prodan.crist...@gmail.com>wrote: > Hello again, > > First of all, thank you all for taking time to answer my ideas. Based on > your thoughts, I have been digging around, and the project I would very > much like to propose is a MapReduce implementation of the simhash algorithm. > Thank you Ted for the great idea! I'm keen on starting implementing a new > algorithm for Mahout, which seems manageable and doable during the summer > period and which has a clear scope. I have noticed quite a few comments, > advising about not taking a project which would be to big and I intend to > follow them. > > After taking a deep look at the article pointed out by Ted, as well as > other articles and simlar ideas (Charikar's algorithm, Ankur's patch for > Minhash), I've decided to write some notes on the algorithm and a schedule > for implemeting the idea during the competition. I kindly ask for your > feedback on this proposal. > > > 1. Problem and outline of simhash > --------------------------------------- > > Detecting similar files and cliassifying documents requires complex > heuristics and/or O(n^2) pair-wise computations [1]. The simhash algorithm > [1] relies on computing a hash function that hashes similar files to similar > values. The file similarities would then be determined by comparing the > pre-sorted hash key values (and reducing the complexity to O(n log n)). > In order to futher improve the detection mechanism, the algorithm will also > store some auxiliary data, used to compute the hash keys. This will be used > as a second filter, i.e. after the hash key comparison indicates that two > files are potentiallly similar. > > Properties for the similarity function and the algorithm: > - very similar files map to very similar or even the same hash key; > - distance between keys should be some measure of the difference between > files. This would lead to keys proportional to file sizes and this would > create false positives. Some auxiliary data will provide an easy and > efficient way of refining the similarity detection. > - the metric used will be a binary metric (simhash operats at byte level). > - given a similarity metric, there needs to be a threshold to determine how > close within the metric files need to be to count as similar. > > I would like my implementation of the simhash algorithm to answer two > questions: > - retrieving a set of files, similar to a given file; > - retrieving all pairs of similar files. > > > 2. simhash implementation > ------------------------------ > Chose 16, 8-bit tags - the bytes used for pattern matching. The idea is to > count the occurances of these tags within the file under processing. > > > 2.1 Computing the hash function for each file > ------------------------------------------------- > for each directory > for each file within directory > - scan through the file and look for matches for each tag; > - detection window is moved one bit at a time > - if a match if found > - set a skip_counter and then decrement it for the following bits; > - a count of matches is stored for each tag, and these are stored as > SUM_TABLE_ENTRIES > - the KEY for the current file is computed as a function of the > SUM_TABLE_ENTRIES (a linear combination of the sum) [#1] > - after this processing, we store: > | file_name | file_path | file_size | key | SUM_TABLE_ENTRIES | > > The key function could also be implemented to take into account file > extensions. > > > 2.2 Finding similarities > ---------------------------- > for each FILE > SIMILAR_FILES = files with keys within a tollerance range of KEY(FILE); > for each SIMILAR_FILE > if file_size(SIMILAR_FILE) differes a lot from file_size(FILE) > discard the query > else > compute the distance between SIMLAR_FILE and FILE ' s > SUM_TABLE_ENTRIES > (i.e. "the sum of the absolute values of the diffs between > their entries) > if the computed distance is within a tollerance or is equal to > 0 then > "The files are identical" > > > > 3. Distributing simhash on hadoop > ------------------------------------- > The algorithm above is very suited for a MapReduce implementation. > > 1. Map > In this phase we do the computation of the hash for a file. > It outputs (File, simhash_key). > > 2. Reduce > Once every item has a simhash, group everyfile with the same simhash into a > cluster, sorted by the simhashkey (the key is an integer [#1]) . > > QUESTIONS SO FAR: > 1. For the distributed version, I believe there should be a prepocessing > phase where data about files should be stored on HDFS, in a proper vector > format ? Would it be better to store this in HBase, Cassandra or something > similar ? > 2. Would it be better in the reduce phase to actually eliminate the > duplicates and create a single sorted-by-hash file ? > > > 4. Implementation schedule > ------------------------------ > > *** May 24 - Jul 12: > * Week 1: write documentation for the algorithm on the wiki and start > planning the objects would interact (classes, methods etc.). * Week 2,3,4: > write the algorithm for hashing of the files. > * Week 5: Thoroughly test > * Week 6: Document the MapReduce implementation - 2 days. Organize the data > structures 3 - days. > * Week 7,8,9: Write the distributed MapReduce Implementation of the > algorithm along with tests. Test as much as possible on different datasets. > > *** Jul 16 - Aug 9: > * Week 10, 11, 12, 13: Continue with tests on different datasets for the > distributed implementation. Also if time permits, I would like to make > graphs and publish results with the carried tests. > > I'm very open to suggestions regarding this plan, so any observation is > highly appreciated. > > Thank you again for taking time to read this. > > Regards, > Cristi. > > > [1] Caitlin Sadowski, Greg Levin - SimHash: Hash-based Similarity > Detection, December 13, 2007. > On Mar 19, 2010, at 7:47 PM, Ted Dunning wrote: > > > Minhash clustering is important for duplicate detection. You can also > > do simhash > > clustering< > http://simhash.googlecode.com/svn/trunk/paper/SimHashWithBib.pdf>which > > might be simpler to implement. I can imagine an implementation where > > the map generates the simhash and emits multiple copies keyed on part of > the > > hash. Near duplicates would thus be grouped together in the reduce where > an > > in-memory duplicate detection could be done. > > > > Sean's intuitions about project size are generally better than mine, but > if > > you limit you are strict about not increasing scope, I think you could > > succeed with this project. > > > > On Fri, Mar 19, 2010 at 6:34 AM, cristi prodan < > prodan.crist...@gmail.com>wrote: > > > >> IDEA 1 - MinHash clustering > >> --------------------------- > >> The first idea come after taking a look at Google 's paper on > collaborative > >> filtering for their news system[2]. In that paper, I looked at MinHash > >> clustering. > >> My first question is: is MinHash clustering considered cool ? If yes, > than > >> I would like to take a stab at implementing it. > >> The paper also describes the implementation in a MapReduce style. Since > >> this is only a suggestion I will not elaborate very much on the solution > >> now. I would like to ask you weather this might be considered a good > choice > >> (i.e. important for the framework to have something like this) and if > this > >> is a big enough project. > >> > >
