An Empirical Evaluation of Set Similarity Join Techniques - Compilation Instructions

W. Mann, N. Augsten, P. Bouros. An Empirical Evaluation of Set Similarity Join Techniques. In The Proceedings of the VLDB Endowment (PVLDB 2016)

Go back to paper's main page

Pre-Requisites

Source Code (License: GPL-3)
Cmake
A recent version of a C++ compiler (e.g., GCC, CLANG)
Boost (for Boost Program Options and Boost::MPL)
Sparsehash Package. On Debian-based systems (Debian, Ubuntu,...), you should find package libsparsehash-dev (APT link) in your distribution's repository. Otherwise, download this tarball and unpack it in the same directory as the source code package.

Compiling

These instructions have been tested on Debian jessie (Debian 8). They should work on most UNIX-like systems.

```
tar xavf ssjoin-0.1.tar.xz
COMPILE_IN=bin
mkdir $COMPILE_IN
cd $COMPILE_IN
cmake -DCMAKE_BUILD_TYPE=Release ../ssjoin-0.1
make -j2
```
Note: the -j2 lets make compile two files in parallel. You might adjust this number according the number of cores and the available main memory on your system. The code may take some minutes to compile.
If you do not have sparsehash in your system includes, you will have to download (see above) and unpack the sparsehash headers. This requires some changes to the instructions given above:
- after tar:
```
tar xavf ssjoin-0.1-sparsehash.tar.xz
```
- instead of cmake
```
export CXXFLAGS="-I../ssjoin-0.1"
cmake -DCMAKE_BUILD_TYPE=Release ../ssjoin-0.1
```

Execution

The set_sim_join binary by default expects fully preprocessed input, i.e.:

one set by line
The collection of sets is sorted by set size. For groupjoin, sets with the same size need to be sorted lexicographically. This is is also recommended for the other algorithms (see paper for details)
The integer tokens need to sorted.
The integers should be chosen according to token frequency - the larger the integer, the more frequent the corresponding token.

If your input does not fulfill these conditions, you can request preprocessing by --whitespace (every consecutive sequence of non-whitespace characters is a token) or --qgram N ( to build q-grams). Again, one set per line.

Available algorithms

Algorithm

cmd-line algorithm string

Required Options

AllPairs

allpairs

PPJoin

ppjoin

PPJoinPlus

ppjoin

--suffixfilter

MPJoin

ppjoin

---mpjoin

PEL

ppjoin

--mpjoin --pljoin

GroupJoin

groupjoin

AdaptJoin

adaptjoin

Example execution

./set_sim_join --statistics --timings flickr-dedup-raw.txt  ppjoin --mpjoin --pljoin 0.75

This executes the PEL algorithm with Jaccard threshold 0.75 on pre-processed input file flickr-dedup-raw.txt and outputs algorithm-specific statistics and timing information. Further options are documented in the command-line output:

./set_sim_join --help

Contact

Willi Mann (wmann AT cosy.sbg.ac.at)