include/lshkit/lsh-index.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_FLAT__
#define __LSHKIT_FLAT__

#include <stdexcept>
#include <algorithm>
#include <lshkit/common.h>
#include <lshkit/topk.h>
#include <lshkit/archive.h>

namespace lshkit {


template <typename LSH, typename KEY>
class LshIndex
{

    BOOST_CONCEPT_ASSERT((LshConcept<LSH>));
public:
    typedef typename LSH::Parameter Parameter;
    typedef typename LSH::Domain Domain;
    typedef KEY Key;

protected:
    typedef std::vector<Key> Bin;

    std::vector<LSH> lshs_;
    std::vector<std::vector<Bin> > tables_;

public:
    LshIndex() {
    }


    template <typename Engine>
    void init (const Parameter &param, Engine &engine, unsigned L)
    {
        verify(lshs_.size() == 0);
        verify(tables_.size() == 0);
        lshs_.resize(L);
        tables_.resize(L);

        for (unsigned i = 0; i < L; ++i) {
            lshs_[i].reset(param, engine);
            if (lshs_[i].getRange() == 0) {
                throw std::logic_error("LSH with unlimited range should not be used to construct an LSH index.  Use lshkit::Tail<> to wrapp the LSH.");
            }
            tables_[i].resize(lshs_[i].getRange());
        }
    }


    void load (std::istream &ar)
    {
        unsigned L;
        ar & L;
        lshs_.resize(L);
        tables_.resize(L);
        for (unsigned i = 0; i < L; ++i) {
            lshs_[i].serialize(ar, 0);
            unsigned l;
            ar & l;
            std::vector<Bin> &table = tables_[i];
            table.resize(l);
            for (;;) {
                unsigned idx, ll;
                ar & idx;
                ar & ll;
                if (ll == 0) break;
                table[idx].resize(ll);
                ar.read((char *)&table[idx][0], ll * sizeof(Key));
            }
        }
    }

    void save (std::ostream &ar)
    {
        unsigned L;
        L = lshs_.size();
        ar & L;
        for (unsigned i = 0; i < L; ++i) {
            lshs_[i].serialize(ar, 0);
            std::vector<Bin> &table = tables_[i];
            unsigned l = table.size();
            ar & l;
            unsigned idx, ll;
            for (unsigned j = 0; j < l; ++j) {
                if (table[j].empty()) continue;
                idx = j;
                ll = table[j].size();
                ar & idx;
                ar & ll;
                ar.write((char *)&table[j][0], ll * sizeof(Key));
            }
            idx = ll = 0;
            ar & idx;
            ar & ll;
        }
    }


    void insert (Key key, Domain value)
    {
        for (unsigned i = 0; i < lshs_.size(); ++i) {
            unsigned index = lshs_[i](value);
            tables_[i][index].push_back(key);
        }
    }


    template <typename SCANNER>
    void query (Domain obj, SCANNER &scanner) const
    {
        for (unsigned i = 0; i < lshs_.size(); ++i) {
            unsigned index = lshs_[i](obj);
            BOOST_FOREACH(Key key, tables_[i][index]) {
                scanner(key);
            }
        }
    }
};


}

#endif

---