lsh_functions.hpp

Go to the documentation of this file.

//=======================================================================
// Copyright (c) 2014 Andrzej Pacuk, Piotr Wygocki
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#ifndef PAAL_LSH_FUNCTIONS_HPP
#define PAAL_LSH_FUNCTIONS_HPP

#include "paal/data_structures/ublas_traits.hpp"
#include "paal/utils/functors.hpp"
#include "paal/utils/type_functions.hpp"

#include <boost/range/algorithm/equal.hpp>
#include <boost/range/algorithm/generate.hpp>
#include <boost/range/algorithm/min_element.hpp>
#include <boost/range/algorithm_ext/iota.hpp>
#include <boost/range/counting_range.hpp>
#include <boost/range/empty.hpp>
#include <boost/range/iterator.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/size.hpp>
#include <boost/range/adaptor/transformed.hpp>
#include <boost/numeric/ublas/vector.hpp>
#include <boost/numeric/ublas/vector_sparse.hpp>
#include <boost/numeric/ublas/vector_expression.hpp>

#include <cassert>
#include <cmath>
#include <cstddef>
#include <random>
#include <type_traits>
#include <utility>

namespace paal {

namespace lsh {

template <typename IntType = std::size_t>
class projection_hash_function {
    IntType m_chosen_position;

public:
    template<class Archive>
    void serialize(Archive & ar, const unsigned int version) {
        ar & m_chosen_position;
    }

    projection_hash_function() = default;

    projection_hash_function(IntType chosen_position) :
            m_chosen_position(chosen_position) {
    }

    bool operator==(projection_hash_function const & other) const {
        return m_chosen_position == other.m_chosen_position;
    }

    template <typename Range>
    //TODO change to decltype(auto), when it starts working
    auto operator()(Range &&range) const ->
            range_to_elem_t<decltype(range)> {
        //TODO takes to long, use boost assert
        //assert(m_chosen_position < boost::size(range));
        return range[m_chosen_position];
    }
};

template <typename RandomEngine = std::default_random_engine,
          typename IntType = std::size_t>
class random_projection_hash_function_generator {
    mutable RandomEngine m_generator;
    using distribution_t = std::uniform_int_distribution<IntType>;
    mutable distribution_t m_distribution;

    static IntType convert_to_inclusive(IntType upper_bound) {
        assert(upper_bound > 0);
        return upper_bound - 1;
    }

public:
    random_projection_hash_function_generator(IntType range_size,
            RandomEngine random_engine = RandomEngine{}) :
            m_generator(std::move(random_engine)),
            m_distribution(0, convert_to_inclusive(range_size)) {
    }

    //TODO change to auto, when it starts working
    projection_hash_function<IntType> operator()() const {
        return projection_hash_function<IntType>(m_distribution(m_generator));
    }
};

using hamming_hash_function_generator =
    random_projection_hash_function_generator<>;

template <typename FloatType = double>
class l_p_hash_function {
public:
    using r_param_t = boost::numeric::ublas::vector<FloatType>;

private:
    r_param_t m_r;
    FloatType m_b;
    FloatType m_w;

public:

    template<class Archive>
    void serialize(Archive & ar, const unsigned int version) {
        ar & m_r;
        ar & m_b;
        ar & m_w;
    }

    l_p_hash_function(r_param_t r,
                      FloatType b, FloatType w) :
            m_r(std::move(r)), m_b(b), m_w(w) {
    }

    l_p_hash_function() = default;

    bool operator==(l_p_hash_function const & other) const {
        return boost::equal(m_r, other.m_r) &&
               m_b == other.m_b &&
               m_w == other.m_w;
    }

    template <typename Range>
    auto operator()(Range &&range) const {
        //TODO use concept check with VectorExpressionConcept<Range>,
        //when it works

        //TODO takes to long, use boost assert
        //assert(boost::size(m_r) == boost::size(range));

        using boost::numeric::ublas::inner_prod;
        auto inner_product = inner_prod(m_r, range);
        return std::floor((m_b + inner_product) / m_w);
    }

};

template <typename FloatType = double,
          typename RandomEngine = std::default_random_engine,
          typename Distribution = std::normal_distribution<FloatType>>
class l_p_hash_function_generator {
    std::size_t m_range_size;
    FloatType m_w;
    mutable RandomEngine m_generator;
    mutable Distribution m_r_distribution;
    mutable std::uniform_real_distribution<FloatType> m_b_distribution;

public:
    l_p_hash_function_generator(std::size_t range_size,
                                FloatType w,
                                RandomEngine random_engine = RandomEngine{}) :
            m_range_size(range_size),
            m_w(w),
            m_generator(std::move(random_engine)),
            m_b_distribution(FloatType{}, w) {
    }

    l_p_hash_function<FloatType> operator()() const {
        typename l_p_hash_function<FloatType>::r_param_t r(m_range_size);
        boost::generate(r, [&]() {
            return m_r_distribution(m_generator);
        });

        FloatType b = m_b_distribution(m_generator);
        return l_p_hash_function<FloatType>(std::move(r), b, m_w);
    }
};

template <typename FloatType = double,
          typename RandomEngine = std::default_random_engine>
using l_1_hash_function_generator =
    l_p_hash_function_generator<FloatType, RandomEngine,
                                std::cauchy_distribution<FloatType>>;

template <typename FloatType = double,
          typename RandomEngine = std::default_random_engine>
using l_2_hash_function_generator =
    l_p_hash_function_generator<FloatType, RandomEngine>;

class min_hash_function {
    //permutation
    std::vector<std::size_t> m_perm;

public:

    template<class Archive>
    void serialize(Archive & ar, const unsigned int version) {
        ar & m_perm;
    }

    template <typename RandomEngine>
    min_hash_function(std::size_t set_element_upper_bound, RandomEngine && rng)
            : m_perm(set_element_upper_bound)  {
        boost::iota(m_perm, 0);
        std::shuffle(m_perm.begin(), m_perm.end(), rng);
    }

    min_hash_function() = default;

    bool operator==(min_hash_function const & other) const {
        return boost::equal(m_perm, other.m_perm);
    }

    template <typename Range>
    auto operator()(Range &&range) const {
        static_assert(data_structures::is_sparse_row<Range>::value, "vector must be sparse");
        using iter_t = typename boost::range_iterator<Range>::type;

        auto perm_function = [&](iter_t it) {
            auto set_elem = it.index();
            assert(set_elem < m_perm.size());
            return m_perm[set_elem];
        };
        auto perm_range =
                boost::counting_range(range)
                | boost::adaptors::transformed(utils::make_assignable_functor(perm_function));

        assert(!boost::empty(perm_range));
        return *boost::min_element(perm_range);
    }
};

template <typename RandomEngine = std::default_random_engine>
class min_hash_function_generator {
    std::size_t m_range_size;
    mutable RandomEngine m_generator;

public:
    min_hash_function_generator(std::size_t range_size,
                                RandomEngine random_engine = RandomEngine{}) :
            m_range_size(range_size),
            m_generator(std::move(random_engine)) { }

    min_hash_function operator()() const {
        return min_hash_function(m_range_size, m_generator);
    }
};
using jaccard_hash_function_generator =
    min_hash_function_generator<>;

} 

} 

#endif // PAAL_LSH_FUNCTIONS_HPP