include/lshkit/composite.h

Go to the documentation of this file.

/* 
    Copyright (C) 2008 Wei Dong <wdong@princeton.edu>. All Rights Reserved.
  
    This file is part of LSHKIT.
  
    LSHKIT is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    LSHKIT is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with LSHKIT.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef __LSHKIT_COMPOSITE__
#define __LSHKIT_COMPOSITE__

namespace lshkit {


template <typename LSH>
class Tail
{
    BOOST_CONCEPT_ASSERT((LshConcept<LSH>));
protected:
    LSH lsh_;
    unsigned range_;
public:
    typedef LSH Super;
    struct Parameter: public Super::Parameter {
        unsigned range;
    };

    typedef typename Super::Domain Domain;

    Tail() {
    }

    template <typename RNG>
    void reset(const Parameter &param, RNG &rng) {
        range_ = param.range;
        lsh_.reset(param, rng);
    }

    template <typename RNG>
    Tail(const Parameter &param, RNG &rng) {
        reset(param, rng);
    }

    unsigned getRange () const {
        return range_;
    }

    unsigned operator () (Domain obj) const {
        return lsh_(obj) % range_;
    }

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


template <typename LSH, unsigned range>
class FixedTail
{
    BOOST_CONCEPT_ASSERT((LshConcept<LSH>));
protected:
    LSH lsh_;
public:
    typedef LSH Super;

    struct Parameter: public Super::Parameter {
    };

    typedef typename Super::Domain Domain;

    FixedTail()
    {
    }

    template <typename RNG>
    void reset(const Parameter &param, RNG &rng)
    {
        lsh_.reset(param, rng);
    }

    template <typename RNG>
    FixedTail(const Parameter &param, RNG &rng)
    {
        reset(param, rng);
    }

    unsigned getRange () const
    {
        return range;
    }

    unsigned operator () (Domain obj) const
    {
        return lsh_(obj) % range;
    }

    const LSH &getLsh () const
    {
        return lsh_;
    }

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


template <typename LSH>
class LSB: public FixedTail<LSH, 2>
{
public:
    typedef FixedTail<LSH,2> Super;
    struct Parameter: public Super::Parameter {
    };

    typedef typename Super::Domain Domain;

    LSB () {}

    template <typename RNG>
    LSB(const Parameter &param, RNG &rng)
        : FixedTail<LSH, 2>(param, rng)
    {
    }
};


template <typename LSH>
class DeltaLSB: public FixedTail<LSH, 2>
{
    BOOST_CONCEPT_ASSERT((DeltaLshConcept<LSH>));

public:
    typedef FixedTail<LSH, 2> Super;
    struct Parameter: public Super::Parameter {
    };

    typedef typename Super::Domain Domain;

    DeltaLSB() {}

    template <typename RNG>
    DeltaLSB(const Parameter &param, RNG &rng)
        : Super(param, rng)
    {
    }

    unsigned operator () (Domain obj) const
    {
        return Super::operator () (obj);
    }

    unsigned operator () (Domain obj, float *delta) const
    {
        float d;
        unsigned r = Super::getLsh()(obj, &d);
        *delta = min(d, 1.0F - d);
        return r % Super::getRange();
    }
};


template <typename LSH>
class Repeat
{
    BOOST_CONCEPT_ASSERT((LshConcept<LSH>));

public:
    typedef LSH Super;
    struct Parameter: public Super::Parameter {
        unsigned repeat;
    };

    typedef typename Super::Domain Domain;

    Repeat ()
    {
    }

    template <typename RNG>
    void reset(const Parameter &param, RNG &rng)
    {
        dup_ = param.repeat;
        assert(dup_ > 0);
        lsh_.resize(dup_);
        lsh_[0].reset(param, rng);
        range_ = unit_ = lsh_[0].getRange();
        assert(unit_ > 0);
        assert( (unsigned)(1 << (sizeof(unsigned) * 8 / dup_)) >= unit_);
        for (unsigned i = 1; i < dup_; ++i)
        {
            lsh_[i].reset(param, rng);
            assert(unit_ == lsh_[i].getRange());
            range_ *= unit_;
        }
    }

    template <typename RNG>
    Repeat(const Parameter &param, RNG &rng)
    {
        reset(param, rng);
    }

    unsigned getRange () const
    {
        return range_;
    }

    unsigned operator () (Domain obj) const
    {
        unsigned ret = 0;
        for (unsigned i = 0; i < dup_; ++i)
        {
            ret *= unit_;
            ret += lsh_[i](obj);
        }
        return ret;
    }

    template<class Archive>
    void serialize(Archive & ar, const unsigned int version)
    {
        ar & dup_;
        ar & range_;
        ar & unit_;
        ar & lsh_;
    }

protected:
    std::vector<Super> lsh_;
    unsigned dup_;
    unsigned range_;
    unsigned unit_;

};



template <typename LSH>
class RepeatHash
{
    BOOST_CONCEPT_ASSERT((LshConcept<LSH>));

public:
    typedef LSH Super;
    struct Parameter: public Super::Parameter {
        unsigned repeat;
    };

    typedef typename LSH::Domain Domain;

    RepeatHash ()
    {
    }

    template <typename RNG>
    void reset(const Parameter &param, RNG &rng)
    {
        assert(param.repeat > 0);
        lsh_.resize(param.repeat);
        for (unsigned i = 0; i < param.repeat; ++i)
        {
            lsh_[i].reset(param, rng);
        }
        a_.resize(param.repeat);

        for (unsigned i = 0; i < param.repeat; ++i) a_[i] = rng();
    }

    template <typename RNG>
    RepeatHash(const Parameter &param, RNG &rng)
    {
        reset(param, rng);
    }

    unsigned getRange () const
    {
        return 0;
    }

    unsigned operator () (Domain obj) const
    {
        unsigned ret = 0;
        for (unsigned i = 0; i < lsh_.size(); ++i)
        {
            ret += lsh_[i](obj) * a_[i];
        }
        return ret;
    }

    template<class Archive>
    void serialize(Archive & ar, const unsigned int version)
    {
        ar & lsh_;
        ar & a_;
        assert(a_.size() == lsh_.size());
    }
protected:
    std::vector<Super> lsh_;
    std::vector<unsigned> a_;

};


/*
 * The XOR of a number of 1-bit LSHes has higher locality sensitivity than
 * the original LSH.  This serves a similar purpose as RepeatHash.
 *
 * The new parameter is defined as:
 *      \code
 *      struct Parameter {
 *          unsigned xor_;     // # of LSHes to XOR
 *          ...                  // all parameters of the base LSH are inherited.
 *      };
 *      \endcode
 */
template <typename LSH>
class Xor
{
    BOOST_CONCEPT_ASSERT((LshConcept<LSH>));
public:

    typedef LSH Super;
    struct Parameter: public Super::Parameter {
        unsigned xor_; // xor is a keyword
    };

    typedef typename Super::Domain Domain;

    Xor ()
    {
    }

    template <typename RNG>
    void reset(const Parameter &param, RNG &rng)
    {
        lsh_.resize(param.xor_);
        for (unsigned i = 0; i < lsh_.size(); ++i)
        {
            lsh_[i].reset(param, rng);
            assert(lsh_[i].getRange() == 2);
        }
    }

    template <typename RNG>
    Xor(const Parameter &param, RNG &rng)
    {
        reset(param, rng);
    }

    unsigned getRange () const
    {
        return 2;
    }

    unsigned operator () (Domain obj) const
    {
        unsigned ret = 0;
        for (unsigned i = 0; i < lsh_.size(); ++i)
        {
            ret = ret ^ lsh_[i](obj);
        }
        return ret;
    }

    template<class Archive>
    void serialize(Archive & ar, const unsigned int version)
    {
        ar & lsh_;
    }
protected:
    std::vector<Super> lsh_;
};

/*
 * This is essentially the same as XOR.  The delta of XOR is the
 * minimum of the deltas of all the original LSHes.
 */
template <typename LSH>
class DeltaXor: public Xor<LSH>
{
public:
    typedef Xor<LSH> Super;
    struct Parameter: public Super::Parameter  {
    };

    typedef typename Super::Domain Domain;

    DeltaXor ()
    {
    }

    template <typename RNG>
    DeltaXor(const Parameter &param, RNG &rng): Xor<LSH>(param, rng)
    {
    }

    unsigned operator () (Domain obj) const {
        return Super::operator () (obj);
    }

    unsigned operator () (Domain obj, float *delta) const
    {
        unsigned ret = 0;
        float m = std::numeric_limits<float>::max(), d;
        for (unsigned i = 0; i < Xor<LSH>::lsh_.size(); ++i)
        {
            ret = ret ^ Xor<LSH>::lsh_[i](obj, &d);
            m = min(m, d);
        }
        *delta = m;
        return ret;
    }
};

}

#endif

---