#include <lsh_util.hpp>

Collaboration diagram for jubatus::core::storage::lsh_probe_generator:

Public Member Functions
const lsh_vector &	base (size_t i) const

lsh_vector	base_all () const

std::pair< size_t, lsh_vector >	get_next_table_and_vector ()

void	init ()

	lsh_probe_generator (const std::vector< float > &hash, size_t num_hash_tables)

Private Types
typedef std::pair< float, std::pair< size_t, std::vector< int > > >	diff_type

typedef std::priority_queue< diff_type, std::vector< diff_type >, std::greater< diff_type > >	heap_type

Private Member Functions
void	next_perturbations ()

Private Attributes
std::vector< lsh_vector >	base_

std::vector< std::vector< float > >	hash_

heap_type	heap_

std::vector< std::vector< std::pair< float, int > > >	perturbation_sets_

Detailed Description

Definition at line 30 of file lsh_util.hpp.

Member Typedef Documentation

typedef std::pair<float, std::pair<size_t, std::vector<int> > > jubatus::core::storage::lsh_probe_generator::diff_type

private

Definition at line 43 of file lsh_util.hpp.

typedef std::priority_queue< diff_type, std::vector<diff_type>, std::greater<diff_type> > jubatus::core::storage::lsh_probe_generator::heap_type

private

Definition at line 47 of file lsh_util.hpp.

Constructor & Destructor Documentation

jubatus::core::storage::lsh_probe_generator::lsh_probe_generator	(	const std::vector< float > &	hash,
		size_t	num_hash_tables
	)

Definition at line 84 of file lsh_util.cpp.

References base_, and hash_.

                             {
   partition(hash, num_hash_tables, hash_);
   base_.resize(hash_.size());
   for (size_t i = 0; i < hash_.size(); ++i) {
     threshold(hash_[i], base_[i]);
   }
 }

Member Function Documentation

const lsh_vector& jubatus::core::storage::lsh_probe_generator::base ( size_t i ) const

inline

Definition at line 37 of file lsh_util.hpp.

References base_.

Referenced by jubatus::core::storage::lsh_index_storage::make_entry().

                                          {
     return base_[i];
   }

Here is the caller graph for this function:

lsh_vector jubatus::core::storage::lsh_probe_generator::base_all ( ) const

Definition at line 118 of file lsh_util.cpp.

References base_, and jubatus::core::storage::lsh_vector::set().

                                                {
   const size_t base_size = base_[0].size();
   lsh_vector lv(base_size * base_.size());
   for (size_t i = 0; i < base_.size(); ++i) {
     for (size_t j = 0; j < base_size; ++j) {
       lv.set(i * base_size + j, base_[i].get(j));
     }
   }
   return lv;
 }

Here is the call graph for this function:

pair< size_t, lsh_vector > jubatus::core::storage::lsh_probe_generator::get_next_table_and_vector ( )

Definition at line 129 of file lsh_util.cpp.

References base_, heap_, next_perturbations(), and perturbation_sets_.

                                                                         {
   if (heap_.empty()) {
     return make_pair(-1ul, lsh_vector());
   }
   const size_t i = heap_.top().second.first;
   pair<size_t, lsh_vector> ret(
       i,
       perturbe(base_[i], heap_.top().second.second, perturbation_sets_[i]));
   next_perturbations();
   return ret;
 }

Here is the call graph for this function:

void jubatus::core::storage::lsh_probe_generator::init ( )

Definition at line 94 of file lsh_util.cpp.

References base_, jubatus::core::clustering::dist(), hash_, heap_, and perturbation_sets_.

                                {
   const int base_size = base_[0].size();
 
   perturbation_sets_.resize(base_.size());
   for (size_t i = 0; i < base_.size(); ++i) {
     vector<pair<float, int> >& cands = perturbation_sets_[i];
     cands.resize(2 * base_size);
     for (int j = 0; j < base_size; ++j) {
       const float dist = hash_[i][j] - base_[i].get(j);
       cands[j * 2] = make_pair((1 - dist) * (1 - dist), j);
       cands[j * 2 + 1] = make_pair(dist * dist, ~j);
     }
     sort(cands.begin(), cands.end());
   }
 
   for (size_t i = 0; i < base_.size(); ++i) {
     if (!perturbation_sets_[i].empty()) {
       heap_.push(
           make_pair(perturbation_sets_[i][0].first,
                     make_pair(i, vector<int>(1))));
     }
   }
 }

Here is the call graph for this function:

void jubatus::core::storage::lsh_probe_generator::next_perturbations ( )

private

Definition at line 141 of file lsh_util.cpp.

References heap_, and perturbation_sets_.

Referenced by get_next_table_and_vector().

                                              {
   const int index = heap_.top().second.first;
   const vector<pair<float, int> >& cands = perturbation_sets_[index];
 
   vector<int> shifted = heap_.top().second.second;
   ++shifted.back();
 
   vector<int> expanded = heap_.top().second.second;
   expanded.push_back(expanded.back() + 1);
 
   const float score_base = heap_.top().first;
   heap_.pop();
 
   if ((size_t) shifted.back() < cands.size()) {
     const float score_diff = cands[shifted.back()].first
         - cands[shifted.back() - 1].first;
     heap_.push(make_pair(score_base + score_diff, make_pair(index, shifted)));
   }
 
   if ((size_t) expanded.back() < cands.size()) {
     const float score_diff = cands[expanded.back()].first;
     heap_.push(make_pair(score_base + score_diff, make_pair(index, expanded)));
   }
 }