crawljax/crawljax — pull request #432 by erwinvaneyk (2014-07-08 11:25:24+00:00)
Title: Near duplicate detection

Hi all,

Last 2 months we, @wilcovl and I, have been working on improving the near-duplicate detection of Crawljax in a project for @alexnederlof and @avandeursen. After a lot of research and coding we like to present our results.

For the purpose of the near-duplicate detection we have implemented a subpackage in the state-package for this sole task. To keep everything as backward compatible as possible the only thing this implementation overrides is the equals method in the StateVertex; no changes to any interface.

### Proces
The idea is that every StateVertex has a unique fingerprint, which can essentially be seen as a bloated hashcode. The general process of creating such a Fingerprint is:
1. We still use the *DOM strippers*. The stripped DOM is used in the fingerprint-generation. It essentially determines which parts of the content should be included in the fingerprint.
2. The stripped DOM is used in so-called *FeatureTypes*. These feature-types turn the stripped dom into small strings which can be hashed to integers. This step essentially determines how the content should be hashed.
3. The *NearDuplicateDetection*-implementations generate a Fingerprints from the set of features. This step essentially determines how the features are transformed into a Fingerprint. We have included two implementations: Crawlhash en Broder. Simply put, Crawlhash is incredibly fast and has small overhead, while Broder is more accurate.

To determine if two StateVertexes are duplicates you know simply compare the fingerprints with a given threshold using one of the methods defined in the fingerprint-API.

### Default: duplicates in terms of textual content
The current implementation is tuned to find near-duplicates in terms of content. This was a choice we had to make early on. We found that optimal values, one of which we have made as a default, reduce the number of mistaken states the current duplicate detections makes by about 50%. As @amesbah suggested to us, users might want to find duplicates in terms of near-duplicate DOM-structures or something other than the content. This is entirely possible with the current implementation. All a user or developer needs to do is to use different DOM Strippers and different features. Some fine-tuning might be needed to get the best results.

### Slider
Additionally for the visual aspect of the duplicate detection process, we have included a so-called threshold-slider in the crawloverview-plugin. This slider shows which states are present in the graph when a certain threshold for the duplicate detection is used. It only does, however, give an indication of what would happen. The threshold-slider will automatically show up when the new near-duplicate detection is used.

### Usage:
1. Use/checkout the example DuplicateDetectionExample in Crawljax.examples
2. Otherwise make sure to set the stateVertexFactory to NDDStateVertexFactory and set a ndd using setNearDuplicateDetectionFactory() in the Crawljax-builder.
3. Use the CLI:

### CLI:
We have build several options in the CLI to use the new duplicate-detection.
--useBroder --useCrawlhash: specifies the type of fingerprint to be used
--threshold : defines the threshold value for deciding on duplicates.
--featureType : defines the shingle-feature to be used (in the CLI only 1 feature can be used)
--featureSize : defines the size of the shingle-feature.
Only the first needs to be set to enable the new duplicate-detection. Others can be set or will use default values. So an example would be:
```shell
java -jar crawljax-cli-4.0.jar http://demo.crawljax.com test/ -featureType words -featureSize 2 -threshold 0.2 -useBroder
```

### Some notable design issues:
- Currently we have implemented this subsystem to be optional. It uses a separate StateVertex from the default StateVertexImpl, so the old duplicate-detection is still the default option. This might be confusing.
- The near-duplicate detection is focused on comparing the textual content. As explained above, this can be changed with some modifications and fine-tuning. Fine-tuning can be done using our [calibration tool](https://github.com/erwinvaneyk/crawljax-calibration-tool).

We hope this addition contributes to the Crawljax-project. If you have any question, remark or feedback of any sort please feel free to tell us.