Thanks Robin, I will try have a look at that. Cristi.
On Thu, Apr 1, 2010 at 9:36 AM, Robin Anil <robin.a...@gmail.com> wrote: > Why dont you try it on 20 newsgroups. There are about 17-18 unique topics > and couple of overlapping ones. You can easily find issues with the > clustering code with that dataset. Once its done you can try bigger > datasets > like wikipedia > > Robin > > On Thu, Apr 1, 2010 at 12:02 PM, Cristian Prodan > <prodan.crist...@gmail.com>wrote: > > > 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. > > > >> > > > > > > > > >
