This project is now archived. It was merged with my cryptanalysislib
This repository contains a header only implementation of the paper A faster algorithm for finding closet pairs in hamming metric.
Arch Linux
sudo pacman -S gtest
Ubuntu: You need to follow this guide to install the googletest suite.
sudo apt install gtest
arch linux
git clone --recurse-submodules https://github.com/submission-nn/nn-algorithm
cd optimalnn
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make
If you use Ubuntu, you have to replace the two last lines with the following to ensure that you have a C++17 ready compiler.
cmake -DCMAKE_BUILD_TYPE=Release -D CMAKE_C_COMPILER=clang-11 -D CMAKE_CXX_COMPILER=clang++-11 ..
make
Currently we have 2 implementations:
- QUADRATIC naive quadratic search
- WINDOWED our new algorithm
You cann pass additional preprocessor flags to the cmake process:
#define LOGGING // upon definition A LOT of debug information will be printed
#define CSV_LOGGING // Same as 'LOGGING' but will print everything as a CSV file. DO NOT use TOGETHER WITH 'LOGGING'
#define SOLUTION_LOGGING // print additionally to the normal debug log every solution found.
#define PERFOMANCE_LOGGING // print some information about the max three depth,.... Extends the `LOGGING`
#define COMPRESS_OUTPUT // compresses some logging output
#define ALL_DELTA // Instead of filtering all elements which do not have weight wt(x+z) = \delta k, we allow each element to have weight wt(x+z) <= \delta k
For
cd build
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_64_10.Windowed:GoldenNearestNeighbor_64_10/*.Windowed:*/GoldenNearestNeighbor_64_10
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_64_15.Windowed:GoldenNearestNeighbor_64_15/*.Windowed:*/GoldenNearestNeighbor_64_15
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_64_20.Windowed:GoldenNearestNeighbor_64_20/*.Windowed:*/GoldenNearestNeighbor_64_20
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_64_10.WindowedWithEpsilon:GoldenNearestNeighbor_64_10/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_64_10
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_64_15.WindowedWithEpsilon:GoldenNearestNeighbor_64_15/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_64_15
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_64_20.WindowedWithEpsilon:GoldenNearestNeighbor_64_20/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_64_20
For
cd build
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_128_10.Windowed:GoldenNearestNeighbor_128_10/*.Windowed:*/GoldenNearestNeighbor_128_10
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_128_15.Windowed:GoldenNearestNeighbor_128_15/*.Windowed:*/GoldenNearestNeighbor_128_15
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_128_20.Windowed:GoldenNearestNeighbor_128_20/*.Windowed:*/GoldenNearestNeighbor_128_20
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_128_10.WindowedWithEpsilon:GoldenNearestNeighbor_128_10/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_128_10
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_128_15.WindowedWithEpsilon:GoldenNearestNeighbor_128_15/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_128_15
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_128_20.WindowedWithEpsilon:GoldenNearestNeighbor_128_20/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_128_20
For
cd build
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_256_10.Windowed:GoldenNearestNeighbor_256_10/*.Windowed:*/GoldenNearestNeighbor_256_10
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_256_15.Windowed:GoldenNearestNeighbor_256_15/*.Windowed:*/GoldenNearestNeighbor_256_15
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_256_20.Windowed:GoldenNearestNeighbor_256_20/*.Windowed:*/GoldenNearestNeighbor_256_20
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_256_10.WindowedWithEpsilon:GoldenNearestNeighbor_256_10/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_256_10
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_256_15.WindowedWithEpsilon:GoldenNearestNeighbor_256_15/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_256_15
./test/nn/nn_golden_64 --gtest_filter=GoldenNearestNeighbor_256_20.WindowedWithEpsilon:GoldenNearestNeighbor_256_20/*.WindowedWithEpsilon:*/GoldenNearestNeighbor_256_20
or see here for more Benchmarks
The code of our algorithm is in the directory src/*
.
All the fundamental data functionality, e.g. compare, xor, ... is implemented in container.h
In nn.h
is an implementation of the naive quadratic search and some helper functions. Our Algorithm is implemented in windowed_nn_v2.h
in the class WindowedNearestNeighbor2
which inherits from NearestNeighbor
which implements the quadratic search.