#include <lsh_index_storage.hpp>

Collaboration diagram for jubatus::core::storage::lsh_index_storage:

Public Member Functions
size_t	all_lsh_num () const

void	clear ()

void	get_all_row_ids (std::vector< std::string > &ids) const

void	get_diff (lsh_master_table_t &diff) const

storage::version	get_version () const

	lsh_index_storage ()

	lsh_index_storage (size_t lsh_num, size_t table_num, uint32_t seed)

	lsh_index_storage (size_t table_num, const std::vector< float > &shift)

void	mix (const lsh_master_table_t &lhs, lsh_master_table_t &rhs) const

	MSGPACK_DEFINE (master_table_, master_table_diff_, lsh_table_, lsh_table_diff_, shift_, table_num_, key_manager_)

std::string	name () const

void	pack (framework::packer &packer) const

bool	put_diff (const lsh_master_table_t &mixed_diff)

void	remove_row (const std::string &row)

void	set_row (const std::string &row, const std::vector< float > &hash, float norm)

void	similar_row (const std::vector< float > &hash, float norm, uint64_t probe_num, uint64_t ret_num, std::vector< std::pair< std::string, float > > &ids) const

void	similar_row (const std::string &id, uint64_t ret_num, std::vector< std::pair< std::string, float > > &ids) const

size_t	table_num () const

void	unpack (msgpack::object o)

virtual	~lsh_index_storage ()

Private Member Functions
const lsh_entry *	get_lsh_entry (const std::string &row) const

void	get_sorted_similar_rows (const jubatus::util::data::unordered_set< uint64_t > &cands, const bit_vector &query_simhash, float query_norm, uint64_t ret_num, std::vector< std::pair< std::string, float > > &ids) const

std::vector< float >	make_entry (const std::vector< float > &hash, float norm, lsh_entry &entry) const

void	put_empty_entry (uint64_t row_id, const lsh_entry &entry)

lsh_master_table_t::iterator	remove_and_get_row (const std::string &row)

void	remove_model_row (const std::string &row)

bool	retrieve_hit_rows (uint64_t hash, size_t ret_num, jubatus::util::data::unordered_set< uint64_t > &cands) const

void	set_mixed_row (const std::string &row, const lsh_entry &entry)

Private Attributes
common::key_manager	key_manager_

lsh_table_t	lsh_table_

lsh_table_t	lsh_table_diff_

lsh_master_table_t	master_table_

lsh_master_table_t	master_table_diff_

std::vector< float >	shift_

uint64_t	table_num_

Detailed Description

Definition at line 51 of file lsh_index_storage.hpp.

Constructor & Destructor Documentation

jubatus::core::storage::lsh_index_storage::lsh_index_storage ( )

Definition at line 127 of file lsh_index_storage.cpp.

127 {

128 }

jubatus::core::storage::lsh_index_storage::lsh_index_storage	(	size_t	lsh_num,
		size_t	table_num,
		uint32_t	seed
	)

Definition at line 130 of file lsh_index_storage.cpp.

References shift_.

     : shift_(lsh_num * table_num),
       table_num_(table_num) {
   initialize_shift(seed, shift_);
 }

jubatus::core::storage::lsh_index_storage::lsh_index_storage	(	size_t	table_num,
		const std::vector< float > &	shift
	)

jubatus::core::storage::lsh_index_storage::~lsh_index_storage ( )

virtual

Definition at line 146 of file lsh_index_storage.cpp.

146 {

147 }

Member Function Documentation

size_t jubatus::core::storage::lsh_index_storage::all_lsh_num ( ) const

inline

Definition at line 83 of file lsh_index_storage.hpp.

References shift_.

                              {
     return shift_.size();
   }

void jubatus::core::storage::lsh_index_storage::clear ( )

Definition at line 192 of file lsh_index_storage.cpp.

References jubatus::core::common::key_manager::clear(), key_manager_, lsh_table_, lsh_table_diff_, master_table_, and master_table_diff_.

                               {
   lsh_master_table_t().swap(master_table_);
   lsh_master_table_t().swap(master_table_diff_);
   lsh_table_t().swap(lsh_table_);
   lsh_table_t().swap(lsh_table_diff_);
   key_manager_.clear();
 }

Here is the call graph for this function:

void jubatus::core::storage::lsh_index_storage::get_all_row_ids ( std::vector< std::string > & ids ) const

Definition at line 200 of file lsh_index_storage.cpp.

References master_table_, and master_table_diff_.

                                                                  {
   const size_t size_upper_bound = master_table_.size()
       + master_table_diff_.size();
 
   unordered_set<std::string> id_set;
   // equivalent to id_set.reserve(size_upper_bound) in C++11
   id_set.rehash(std::ceil(size_upper_bound / id_set.max_load_factor()));
 
   for (lsh_master_table_t::const_iterator it = master_table_.begin();
       it != master_table_.end(); ++it) {
     if (!it->second.lsh_hash.empty()) {
       id_set.insert(it->first);
     }
   }
   for (lsh_master_table_t::const_iterator it = master_table_diff_.begin();
       it != master_table_diff_.end(); ++it) {
     if (!it->second.lsh_hash.empty()) {
       id_set.insert(it->first);
     }
   }
 
   vector<string> ret(id_set.size());
   copy(id_set.begin(), id_set.end(), ret.begin());
   ids.swap(ret);
 }

void jubatus::core::storage::lsh_index_storage::get_diff ( lsh_master_table_t & diff ) const

Definition at line 295 of file lsh_index_storage.cpp.

References master_table_diff_.

                                                                {
   diff = master_table_diff_;
 }

const lsh_entry * jubatus::core::storage::lsh_index_storage::get_lsh_entry ( const std::string & row ) const

private

Definition at line 472 of file lsh_index_storage.cpp.

References master_table_, and master_table_diff_.

Referenced by get_sorted_similar_rows(), and remove_model_row().

                                                                          {
   lsh_master_table_t::const_iterator it = master_table_diff_.find(row);
   if (it == master_table_diff_.end()) {
     it = master_table_.find(row);
     if (it == master_table_.end()) {
       return 0;
     }
   }
   return &it->second;
 }

Here is the caller graph for this function:

void jubatus::core::storage::lsh_index_storage::get_sorted_similar_rows	(	const jubatus::util::data::unordered_set< uint64_t > &	cands,
		const bit_vector &	query_simhash,
		float	query_norm,
		uint64_t	ret_num,
		std::vector< std::pair< std::string, float > > &	ids
	)		const

private

Definition at line 436 of file lsh_index_storage.cpp.

References jubatus::core::clustering::dist(), jubatus::core::common::key_manager::get_key(), get_lsh_entry(), key_manager_, and jubatus::core::storage::lsh_entry::lsh_hash.

                                              {
   // Avoid string copy as far as possible
   vector<pair<uint64_t, float> > scored;
   scored.reserve(cands.size());
   for (unordered_set<uint64_t>::const_iterator it = cands.begin();
       it != cands.end(); ++it) {
     const lsh_entry* entry = get_lsh_entry(key_manager_.get_key(*it));
     if (!entry || entry->lsh_hash.empty()) {
       continue;
     }
     const float dist = calc_euclidean_distance(*entry, query_simhash,
                                                query_norm);
     scored.push_back(make_pair(*it, -dist));
   }
 
   if (scored.size() <= ret_num) {
     sort(scored.begin(), scored.end(), greater_second());
   } else {
     partial_sort(scored.begin(),
                  scored.begin() + ret_num, scored.end(),
                  greater_second());
     scored.resize(ret_num);
   }
 
   ids.resize(scored.size());
   for (size_t i = 0; i < scored.size(); ++i) {
     ids[i].first = key_manager_.get_key(scored[i].first);
     ids[i].second = scored[i].second;
   }
 }

Here is the call graph for this function:

storage::version jubatus::core::storage::lsh_index_storage::get_version ( ) const

inline

Definition at line 86 of file lsh_index_storage.hpp.

                                      {
     return storage::version();
   }

vector< float > jubatus::core::storage::lsh_index_storage::make_entry	(	const std::vector< float > &	hash,
		float	norm,
		lsh_entry &	entry
	)		const

private

Definition at line 373 of file lsh_index_storage.cpp.

References jubatus::core::storage::lsh_probe_generator::base(), jubatus::core::nearest_neighbor::binarize(), jubatus::core::storage::lsh_entry::lsh_hash, jubatus::core::storage::lsh_entry::norm, jubatus::core::storage::lsh_vector::push_back(), shift_, jubatus::core::storage::lsh_entry::simhash_bv, and table_num_.

Referenced by set_row().

                             {
   const vector<float> shifted = shift_hash(hash, shift_);
   lsh_probe_generator gen(shifted, table_num_);
 
   entry.lsh_hash.resize(table_num_);
   for (uint64_t i = 0; i < table_num_; ++i) {
     lsh_vector key = gen.base(i);
     key.push_back(i);
     entry.lsh_hash[i] = hash_lv(key);
   }
 
   entry.simhash_bv = binarize(hash);
   entry.norm = norm;
 
   return shifted;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::lsh_index_storage::mix	(	const lsh_master_table_t &	lhs,
		lsh_master_table_t &	rhs
	)		const

Definition at line 320 of file lsh_index_storage.cpp.

                                    {
   for (lsh_master_table_t::const_iterator it = lhs.begin(); it != lhs.end();
        ++it) {
     rhs[it->first] = it->second;
   }
 }

jubatus::core::storage::lsh_index_storage::MSGPACK_DEFINE	(	master_table_	,
		master_table_diff_	,
		lsh_table_	,
		lsh_table_diff_	,
		shift_	,
		table_num_	,
		key_manager_
	)

string jubatus::core::storage::lsh_index_storage::name ( ) const

Definition at line 283 of file lsh_index_storage.cpp.

                                      {
   return "lsh_index_storage";
 }

void jubatus::core::storage::lsh_index_storage::pack ( framework::packer & packer ) const

Definition at line 287 of file lsh_index_storage.cpp.

                                                           {
   packer.pack(*this);
 }

bool jubatus::core::storage::lsh_index_storage::put_diff ( const lsh_master_table_t & mixed_diff )

Definition at line 299 of file lsh_index_storage.cpp.

References lsh_table_diff_, master_table_, master_table_diff_, remove_model_row(), and set_mixed_row().

                                     {
   for (lsh_master_table_t::const_iterator it = diff.begin(); it != diff.end();
       ++it) {
     if (it->second.lsh_hash.empty()) {
       remove_model_row(it->first);
       master_table_.erase(it->first);
     } else {
       remove_model_row(it->first);
       set_mixed_row(it->first, it->second);
     }
   }
 
   master_table_diff_.clear();
 
   // lsh_table_diff_ is actually not MIXed, but must be cleared as well as diff
   // of usual model.
   lsh_table_diff_.clear();
   return true;
 }

Here is the call graph for this function:

void jubatus::core::storage::lsh_index_storage::put_empty_entry	(	uint64_t	row_id,
		const lsh_entry &	entry
	)

private

Definition at line 353 of file lsh_index_storage.cpp.

References jubatus::core::storage::lsh_entry::lsh_hash, and lsh_table_diff_.

Referenced by remove_and_get_row(), and remove_row().

                             {
   for (size_t i = 0; i < entry.lsh_hash.size(); ++i) {
     lsh_table_t::iterator it = lsh_table_diff_.find(entry.lsh_hash[i]);
     if (it != lsh_table_diff_.end()) {
       vector<uint64_t>& range = it->second;
       vector<uint64_t>::iterator jt = lower_bound(range.begin(),
                                                   range.end(),
                                                   row_id);
       if (jt != range.end() && row_id == *jt) {
         range.erase(jt);
         if (range.empty()) {
           lsh_table_diff_.erase(it);
         }
       }
     }
   }
 }

Here is the caller graph for this function:

lsh_master_table_t::iterator jubatus::core::storage::lsh_index_storage::remove_and_get_row ( const std::string & row )

private

Definition at line 331 of file lsh_index_storage.cpp.

References jubatus::core::common::key_manager::get_id_const(), key_manager_, master_table_, master_table_diff_, jubatus::core::common::key_manager::NOTFOUND, and put_empty_entry().

Referenced by set_row().

                        {
   const uint64_t row_id = key_manager_.get_id_const(row);
   if (row_id == common::key_manager::NOTFOUND) {
     return master_table_diff_.end();
   }
 
   lsh_master_table_t::iterator entry_it = master_table_diff_.find(row);
   lsh_master_table_t::iterator ret_it = entry_it;
   if (entry_it == master_table_diff_.end()) {
     ret_it = master_table_diff_.insert(make_pair(row, lsh_entry())).first;
     entry_it = master_table_.find(row);
     if (entry_it == master_table_.end()) {
       return ret_it;
     }
   }
   lsh_entry& entry = entry_it->second;
   put_empty_entry(row_id, entry);
 
   return ret_it;
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::lsh_index_storage::remove_model_row ( const std::string & row )

private

Definition at line 395 of file lsh_index_storage.cpp.

References jubatus::core::common::key_manager::get_id_const(), get_lsh_entry(), key_manager_, jubatus::core::storage::lsh_entry::lsh_hash, and lsh_table_.

Referenced by put_diff().

                                                              {
   const lsh_entry* entry = get_lsh_entry(row);
   if (!entry) {
     return;
   }
 
   const uint64_t row_id = key_manager_.get_id_const(row);
   for (size_t i = 0; i < entry->lsh_hash.size(); ++i) {
     lsh_table_t::iterator it = lsh_table_.find(entry->lsh_hash[i]);
     if (it != lsh_table_.end()) {
       vector<uint64_t>& range = it->second;
       vector<uint64_t>::iterator jt = find(range.begin(), range.end(), row_id);
       if (jt != range.end()) {
         range.erase(jt);
         if (range.empty()) {
           lsh_table_.erase(it);
         }
       }
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::lsh_index_storage::remove_row ( const std::string & row )

Definition at line 170 of file lsh_index_storage.cpp.

References jubatus::core::common::key_manager::get_id_const(), key_manager_, master_table_, master_table_diff_, jubatus::core::common::key_manager::NOTFOUND, and put_empty_entry().

                                                     {
   const uint64_t row_id = key_manager_.get_id_const(row);
   if (row_id == common::key_manager::NOTFOUND) {
     // Non-existence row
     return;
   }
 
   lsh_master_table_t::iterator entry_it = master_table_.find(row);
   if (entry_it == master_table_.end()) {
     // Since the row is not yet mixed, it can be immediately erased.
     master_table_diff_.erase(row);
     return;
   }
 
   // Otherwise, keep the row with empty entry until next MIX.
   master_table_diff_.insert(make_pair(row, lsh_entry()));
   lsh_entry& entry = entry_it->second;
   put_empty_entry(row_id, entry);
 
   return;
 }

Here is the call graph for this function:

bool jubatus::core::storage::lsh_index_storage::retrieve_hit_rows	(	uint64_t	hash,
		size_t	ret_num,
		jubatus::util::data::unordered_set< uint64_t > &	cands
	)		const

private

Definition at line 427 of file lsh_index_storage.cpp.

References lsh_table_, and lsh_table_diff_.

                                           {
   retrieve_hit_rows_from_table(hash, lsh_table_diff_, cands);
   retrieve_hit_rows_from_table(hash, lsh_table_, cands);
   return cands.size() >= static_cast<uint64_t>(ret_num);
 }

void jubatus::core::storage::lsh_index_storage::set_mixed_row	(	const std::string &	row,
		const lsh_entry &	entry
	)

private

Definition at line 417 of file lsh_index_storage.cpp.

References jubatus::core::common::key_manager::get_id(), key_manager_, jubatus::core::storage::lsh_entry::lsh_hash, lsh_table_, and master_table_.

Referenced by put_diff().

                             {
   const uint64_t row_id = key_manager_.get_id(row);
   master_table_[row] = entry;
   for (size_t i = 0; i < entry.lsh_hash.size(); ++i) {
     lsh_table_[entry.lsh_hash[i]].push_back(row_id);
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::lsh_index_storage::set_row	(	const std::string &	row,
		const std::vector< float > &	hash,
		float	norm
	)

Definition at line 149 of file lsh_index_storage.cpp.

References jubatus::core::common::key_manager::get_id(), key_manager_, lsh_table_diff_, make_entry(), master_table_diff_, and remove_and_get_row().

Referenced by jubatus::core::recommender::euclid_lsh::update_row().

                 {
   lsh_master_table_t::iterator it = remove_and_get_row(row);
   if (it == master_table_diff_.end()) {
     it = master_table_diff_.insert(make_pair(row, lsh_entry())).first;
   }
   make_entry(hash, norm, it->second);
 
   const uint64_t id = key_manager_.get_id(row);
   const vector<uint64_t>& lsh_hash = it->second.lsh_hash;
   for (size_t i = 0; i < lsh_hash.size(); ++i) {
     vector<uint64_t>& range = lsh_table_diff_[lsh_hash[i]];
     vector<uint64_t>::iterator it = lower_bound(range.begin(), range.end(), id);
     if (it == range.end() || id != *it) {
       range.insert(it, id);
     }
   }
 }

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::lsh_index_storage::similar_row	(	const std::vector< float > &	hash,
		float	norm,
		uint64_t	probe_num,
		uint64_t	ret_num,
		std::vector< std::pair< std::string, float > > &	ids
	)		const

void jubatus::core::storage::lsh_index_storage::similar_row	(	const std::string &	id,
		uint64_t	ret_num,
		std::vector< std::pair< std::string, float > > &	ids
	)		const

size_t jubatus::core::storage::lsh_index_storage::table_num ( ) const

inline

Definition at line 79 of file lsh_index_storage.hpp.

References table_num_.

                            {
     return table_num_;
   }

void jubatus::core::storage::lsh_index_storage::unpack ( msgpack::object o )

Definition at line 291 of file lsh_index_storage.cpp.

                                               {
   o.convert(this);
 }

Member Data Documentation

common::key_manager jubatus::core::storage::lsh_index_storage::key_manager_

private

Definition at line 132 of file lsh_index_storage.hpp.

Referenced by clear(), get_sorted_similar_rows(), remove_and_get_row(), remove_model_row(), remove_row(), set_mixed_row(), and set_row().

lsh_table_t jubatus::core::storage::lsh_index_storage::lsh_table_

private

Definition at line 127 of file lsh_index_storage.hpp.

Referenced by clear(), remove_model_row(), retrieve_hit_rows(), and set_mixed_row().

lsh_table_t jubatus::core::storage::lsh_index_storage::lsh_table_diff_

private

Definition at line 128 of file lsh_index_storage.hpp.

Referenced by clear(), put_diff(), put_empty_entry(), retrieve_hit_rows(), and set_row().

lsh_master_table_t jubatus::core::storage::lsh_index_storage::master_table_

private

Definition at line 124 of file lsh_index_storage.hpp.

Referenced by clear(), get_all_row_ids(), get_lsh_entry(), put_diff(), remove_and_get_row(), remove_row(), and set_mixed_row().

lsh_master_table_t jubatus::core::storage::lsh_index_storage::master_table_diff_

private

Definition at line 125 of file lsh_index_storage.hpp.

Referenced by clear(), get_all_row_ids(), get_diff(), get_lsh_entry(), put_diff(), remove_and_get_row(), remove_row(), and set_row().

std::vector<float> jubatus::core::storage::lsh_index_storage::shift_

private

Definition at line 130 of file lsh_index_storage.hpp.

Referenced by all_lsh_num(), lsh_index_storage(), and make_entry().

uint64_t jubatus::core::storage::lsh_index_storage::table_num_

private

Definition at line 131 of file lsh_index_storage.hpp.

Referenced by make_entry(), and table_num().

The documentation for this class was generated from the following files:

jubatus/core/storage/lsh_index_storage.hpp
jubatus/core/storage/lsh_index_storage.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation