jubatus::core::storage::inverted_index_storage Class Reference

#include <inverted_index_storage.hpp>

Collaboration diagram for jubatus::core::storage::inverted_index_storage:

Classes
struct	diff_type

Public Member Functions
void	calc_scores (const common::sfv_t &sfv, std::vector< std::pair< std::string, float > > &scores, size_t ret_num) const
void	clear ()
float	get (const std::string &row, const std::string &column) const
void	get_all_column_ids (std::vector< std::string > &ids) const
void	get_diff (diff_type &diff_str) const
storage::version	get_version () const
	inverted_index_storage ()
void	mix (const diff_type &lhs_str, diff_type &rhs_str) const
	MSGPACK_DEFINE (inv_, inv_diff_, column2norm_, column2norm_diff_, column2id_)
std::string	name () const
void	pack (framework::packer &packer) const
bool	put_diff (const diff_type &mixed_diff)
void	remove (const std::string &row, const std::string &column)
void	set (const std::string &row, const std::string &column, float val)
void	unpack (msgpack::object o)
	~inverted_index_storage ()

Private Member Functions
void	add_inp_scores (const std::string &row, float val, std::vector< float > &scores) const
float	calc_columnl2norm (uint64_t column_id) const
float	get_from_tbl (const std::string &row, uint64_t column_id, const tbl_t &tbl, bool &exist) const

Static Private Member Functions
static float	calc_l2norm (const common::sfv_t &sfv)

Private Attributes
common::key_manager	column2id_
imap_float_t	column2norm_
imap_float_t	column2norm_diff_
tbl_t	inv_
tbl_t	inv_diff_

Detailed Description

Definition at line 37 of file inverted_index_storage.hpp.

Constructor & Destructor Documentation

jubatus::core::storage::inverted_index_storage::inverted_index_storage

(

)

Definition at line 41 of file inverted_index_storage.cpp.

                                               {
}

jubatus::core::storage::inverted_index_storage::~inverted_index_storage

(

)

Definition at line 44 of file inverted_index_storage.cpp.

                                                {
}

Member Function Documentation

void jubatus::core::storage::inverted_index_storage::add_inp_scores ( const std::string &  row, float  val, std::vector< float > &  scores  ) const

private

Definition at line 307 of file inverted_index_storage.cpp.

References jubatus::core::common::assoc_vector< K, V >::begin(), jubatus::core::common::assoc_vector< K, V >::end(), jubatus::core::common::assoc_vector< K, V >::find(), inv_, and inv_diff_.

Referenced by calc_scores().

                                    {
  tbl_t::const_iterator it_diff = inv_diff_.find(row);
  if (it_diff != inv_diff_.end()) {
    const row_t& row_v = it_diff->second;
    for (row_t::const_iterator row_it = row_v.begin(); row_it != row_v.end();
        ++row_it) {
      scores[row_it->first] += row_it->second * val;
    }
  }

  tbl_t::const_iterator it = inv_.find(row);
  if (it != inv_.end()) {
    const row_t& row_v = it->second;
    if (it_diff == inv_diff_.end()) {
      for (row_t::const_iterator row_it = row_v.begin(); row_it != row_v.end();
          ++row_it) {
        scores[row_it->first] += row_it->second * val;
      }
    } else {
      const row_t& row_diff_v = it_diff->second;
      for (row_t::const_iterator row_it = row_v.begin(); row_it != row_v.end();
          ++row_it) {
        if (row_diff_v.find(row_it->first) == row_diff_v.end()) {
          scores[row_it->first] += row_it->second * val;
        }
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

float jubatus::core::storage::inverted_index_storage::calc_columnl2norm ( uint64_t  column_id ) const

private

Definition at line 294 of file inverted_index_storage.cpp.

References column2norm_, and column2norm_diff_.

Referenced by calc_scores().

                                                                        {
  float ret = 0.f;
  imap_float_t::const_iterator it_diff = column2norm_diff_.find(column_id);
  if (it_diff != column2norm_diff_.end()) {
    ret += it_diff->second;
  }
  imap_float_t::const_iterator it = column2norm_.find(column_id);
  if (it != column2norm_.end()) {
    ret += it->second;
  }
  return std::sqrt(ret);
}

Here is the caller graph for this function:

float jubatus::core::storage::inverted_index_storage::calc_l2norm ( const common::sfv_t &  sfv )

staticprivate

Definition at line 286 of file inverted_index_storage.cpp.

Referenced by calc_scores().

                                                                {
  float ret = 0.f;
  for (size_t i = 0; i < sfv.size(); ++i) {
    ret += sfv[i].second * sfv[i].second;
  }
  return std::sqrt(ret);
}

Here is the caller graph for this function:

void jubatus::core::storage::inverted_index_storage::calc_scores	(	const common::sfv_t &	sfv,
		std::vector< std::pair< std::string, float > > &	scores,
		size_t	ret_num
	)		const

Definition at line 248 of file inverted_index_storage.cpp.

References add_inp_scores(), calc_columnl2norm(), calc_l2norm(), column2id_, jubatus::core::common::key_manager::get_key(), jubatus::core::common::key_manager::get_max_id(), jubatus::core::storage::fixed_size_heap< T, Comp >::get_sorted(), and jubatus::core::storage::fixed_size_heap< T, Comp >::push().

                          {
  float query_norm = calc_l2norm(query);
  if (query_norm == 0.f) {
    return;
  }

  std::vector<float> i_scores(column2id_.get_max_id() + 1, 0.0);
  for (size_t i = 0; i < query.size(); ++i) {
    const string& fid = query[i].first;
    float val = query[i].second;
    add_inp_scores(fid, val, i_scores);
  }

  storage::fixed_size_heap<pair<float, uint64_t>,
                           std::greater<pair<float, uint64_t> > > heap(ret_num);
  for (size_t i = 0; i < i_scores.size(); ++i) {
    float score = i_scores[i];
    if (score == 0.f)
      continue;
    float norm = calc_columnl2norm(i);
    if (norm == 0.f)
      continue;
    float normed_score = score / norm / query_norm;
    heap.push(make_pair(normed_score, i));
  }
  vector<pair<float, uint64_t> > sorted_scores;
  heap.get_sorted(sorted_scores);

  for (size_t i = 0; i < sorted_scores.size() && i < ret_num; ++i) {
    scores.push_back(
        make_pair(column2id_.get_key(sorted_scores[i].second),
                  sorted_scores[i].first));
  }
}

Here is the call graph for this function:

void jubatus::core::storage::inverted_index_storage::clear

(

)

Definition at line 149 of file inverted_index_storage.cpp.

References column2id_, column2norm_, column2norm_diff_, inv_, inv_diff_, and jubatus::core::common::key_manager::swap().

                                   {
  tbl_t().swap(inv_);
  tbl_t().swap(inv_diff_);
  imap_float_t().swap(column2norm_);
  imap_float_t().swap(column2norm_diff_);
  common::key_manager().swap(column2id_);
}

Here is the call graph for this function:

float jubatus::core::storage::inverted_index_storage::get	(	const std::string &	row,
		const std::string &	column
	)		const

Definition at line 66 of file inverted_index_storage.cpp.

References column2id_, get_from_tbl(), jubatus::core::common::key_manager::get_id_const(), inv_, inv_diff_, and jubatus::core::common::key_manager::NOTFOUND.

                                {
  uint64_t column_id = column2id_.get_id_const(column);
  if (column_id == common::key_manager::NOTFOUND) {
    return 0.f;
  }
  {
    bool exist = false;
    float ret = get_from_tbl(row, column_id, inv_diff_, exist);
    if (exist) {
      return ret;
    }
  }
  {
    bool exist = false;
    float ret = get_from_tbl(row, column_id, inv_, exist);
    if (exist) {
      return ret;
    }
  }
  return 0.0;
}

Here is the call graph for this function:

void jubatus::core::storage::inverted_index_storage::get_all_column_ids

(

std::vector< std::string > &

ids

)

const

Definition at line 157 of file inverted_index_storage.cpp.

References column2id_, column2norm_, column2norm_diff_, and jubatus::core::common::key_manager::get_key().

                                     {
  ids.clear();
  for (imap_float_t::const_iterator it = column2norm_.begin();
      it != column2norm_.end(); ++it) {
    ids.push_back(column2id_.get_key(it->first));
  }
  for (imap_float_t::const_iterator it = column2norm_diff_.begin();
      it != column2norm_diff_.end(); ++it) {
    if (column2norm_.find(it->first) == column2norm_.end()) {
      ids.push_back(column2id_.get_key(it->first));
    }
  }
}

Here is the call graph for this function:

void jubatus::core::storage::inverted_index_storage::get_diff

(

diff_type &

diff_str

)

const

Definition at line 172 of file inverted_index_storage.cpp.

References column2id_, jubatus::core::storage::inverted_index_storage::diff_type::column2norm, column2norm_diff_, jubatus::core::common::key_manager::get_key(), jubatus::core::storage::inverted_index_storage::diff_type::inv, inv_diff_, and jubatus::core::storage::sparse_matrix_storage::set_row().

                                                           {
  for (tbl_t::const_iterator it = inv_diff_.begin(); it != inv_diff_.end();
      ++it) {
    vector<pair<string, float> > columns;
    for (row_t::const_iterator it2 = it->second.begin();
        it2 != it->second.end(); ++it2) {
      columns.push_back(make_pair(column2id_.get_key(it2->first), it2->second));
    }
    diff.inv.set_row(it->first, columns);
  }

  for (imap_float_t::const_iterator it = column2norm_diff_.begin();
      it != column2norm_diff_.end(); ++it) {
    diff.column2norm[column2id_.get_key(it->first)] = it->second;
  }
}

Here is the call graph for this function:

float jubatus::core::storage::inverted_index_storage::get_from_tbl ( const std::string &  row, uint64_t  column_id, const tbl_t &  tbl, bool &  exist  ) const

private

Definition at line 90 of file inverted_index_storage.cpp.

References jubatus::core::common::key_manager::NOTFOUND.

Referenced by get(), and remove().

                       {
  exist = false;

  if (column_id == common::key_manager::NOTFOUND) {
    return 0.f;
  }
  tbl_t::const_iterator it = tbl.find(row);
  if (it == tbl.end()) {
    return 0.f;
  } else {
    row_t::const_iterator it_row = it->second.find(column_id);
    if (it_row == it->second.end()) {
      return 0.f;
    } else {
      exist = true;
      return it_row->second;
    }
  }
}

Here is the caller graph for this function:

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

inline

Definition at line 64 of file inverted_index_storage.hpp.

                                     {
    return storage::version();
  }

void jubatus::core::storage::inverted_index_storage::mix	(	const diff_type &	lhs_str,
		diff_type &	rhs_str
	)		const

Definition at line 221 of file inverted_index_storage.cpp.

References jubatus::core::storage::inverted_index_storage::diff_type::column2norm, jubatus::core::storage::sparse_matrix_storage::get_all_row_ids(), jubatus::core::storage::sparse_matrix_storage::get_row(), jubatus::core::storage::inverted_index_storage::diff_type::inv, and jubatus::core::storage::sparse_matrix_storage::set_row().

                                                                           {
  // merge inv diffs
  vector<string> ids;
  lhs.inv.get_all_row_ids(ids);
  for (size_t i = 0; i < ids.size(); ++i) {
    const string& row = ids[i];

    vector<pair<string, float> > columns;
    lhs.inv.get_row(row, columns);
    rhs.inv.set_row(row, columns);
  }

  // merge norm diffs
  for (map_float_t::const_iterator it = lhs.column2norm.begin();
      it != lhs.column2norm.end(); ++it) {
    rhs.column2norm[it->first] += it->second;
  }
}

Here is the call graph for this function:

jubatus::core::storage::inverted_index_storage::MSGPACK_DEFINE	(	inv_	,
		inv_diff_	,
		column2norm_	,
		column2norm_diff_	,
		column2id_
	)

std::string jubatus::core::storage::inverted_index_storage::name

(

)

const

Definition at line 340 of file inverted_index_storage.cpp.

                                             {
  return string("inverted_index_storage");
}

void jubatus::core::storage::inverted_index_storage::pack

(

framework::packer &

packer

)

const

Definition at line 240 of file inverted_index_storage.cpp.

                                                               {
  packer.pack(*this);
}

bool jubatus::core::storage::inverted_index_storage::put_diff

(

const diff_type &

mixed_diff

)

Definition at line 189 of file inverted_index_storage.cpp.

References column2id_, jubatus::core::storage::inverted_index_storage::diff_type::column2norm, column2norm_, column2norm_diff_, jubatus::core::common::assoc_vector< K, V >::erase(), jubatus::core::storage::sparse_matrix_storage::get_all_row_ids(), jubatus::core::common::key_manager::get_id(), jubatus::core::storage::sparse_matrix_storage::get_row(), jubatus::core::storage::inverted_index_storage::diff_type::inv, inv_, inv_diff_, and jubatus::core::common::jsonconfig::v().

                                 {
  vector<string> ids;
  mixed_diff.inv.get_all_row_ids(ids);
  for (size_t i = 0; i < ids.size(); ++i) {
    const string& row = ids[i];
    row_t& v = inv_[row];
    vector<pair<string, float> > columns;
    mixed_diff.inv.get_row(row, columns);
    for (size_t j = 0; j < columns.size(); ++j) {
      size_t id = column2id_.get_id(columns[j].first);
      if (columns[j].second == 0.f) {
        v.erase(id);
      } else {
        v[id] = columns[j].second;
      }
    }
  }
  inv_diff_.clear();

  for (map_float_t::const_iterator it = mixed_diff.column2norm.begin();
      it != mixed_diff.column2norm.end(); ++it) {
    uint64_t column_index = column2id_.get_id(it->first);
    column2norm_[column_index] += it->second;
    if (column2norm_[column_index] == 0.f) {
      column2norm_.erase(column_index);
    }
  }
  column2norm_diff_.clear();
  return true;
}

Here is the call graph for this function:

void jubatus::core::storage::inverted_index_storage::remove	(	const std::string &	row,
		const std::string &	column
	)

Definition at line 114 of file inverted_index_storage.cpp.

References column2id_, get_from_tbl(), jubatus::core::common::key_manager::get_id_const(), inv_, inv_diff_, jubatus::core::common::key_manager::NOTFOUND, and set().

Referenced by jubatus::core::recommender::inverted_index::clear_row().

                             {
  uint64_t column_id = column2id_.get_id_const(column);
  if (column_id == common::key_manager::NOTFOUND) {
    return;
  }

  set(row, column, 0.f);

  // Test if the data exists in the master table.
  bool exist = false;
  get_from_tbl(row, column_id, inv_, exist);

  // If the data exists in the master table, we should
  // keep it in the diff table until next MIX to propagate
  // the removal of this data to other nodes.
  // Otherwise we can immediately remove the row from
  // the diff table.
  if (!exist) {
    tbl_t::iterator it = inv_diff_.find(row);
    if (it != inv_diff_.end()) {
      row_t::iterator it_row = it->second.find(column_id);
      if (it_row != it->second.end()) {
        it->second.erase(it_row);
        if (it->second.empty()) {
          // There are no columns that belongs to this row,
          // so we can remove the row itself.
          inv_diff_.erase(it);
        }
      }
    }
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::inverted_index_storage::set	(	const std::string &	row,
		const std::string &	column,
		float	val
	)

Definition at line 47 of file inverted_index_storage.cpp.

References column2id_, column2norm_diff_, jubatus::core::common::key_manager::get_id(), jubatus::core::common::key_manager::get_id_const(), inv_diff_, and jubatus::core::common::key_manager::NOTFOUND.

Referenced by remove(), and jubatus::core::recommender::inverted_index::update_row().

               {
  uint64_t column_id = column2id_.get_id_const(column);

  if (column_id == common::key_manager::NOTFOUND) {
    column_id = column2id_.get_id(column);
  } else {
    float cur_val = get(row, column);
    column2norm_diff_[column_id] -= cur_val * cur_val;
  }
  inv_diff_[row][column_id] = val;
  column2norm_diff_[column_id] += val * val;
  if (column2norm_diff_[column_id] == 0) {
    column2norm_diff_.erase(column_id);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void jubatus::core::storage::inverted_index_storage::unpack

(

msgpack::object

o

)

Definition at line 244 of file inverted_index_storage.cpp.

                                                   {
  o.convert(this);
}

Member Data Documentation

common::key_manager jubatus::core::storage::inverted_index_storage::column2id_

private

Definition at line 93 of file inverted_index_storage.hpp.

Referenced by calc_scores(), clear(), get(), get_all_column_ids(), get_diff(), put_diff(), remove(), and set().

imap_float_t jubatus::core::storage::inverted_index_storage::column2norm_

private

Definition at line 91 of file inverted_index_storage.hpp.

Referenced by calc_columnl2norm(), clear(), get_all_column_ids(), and put_diff().

imap_float_t jubatus::core::storage::inverted_index_storage::column2norm_diff_

private

Definition at line 92 of file inverted_index_storage.hpp.

Referenced by calc_columnl2norm(), clear(), get_all_column_ids(), get_diff(), put_diff(), and set().

tbl_t jubatus::core::storage::inverted_index_storage::inv_

private

Definition at line 89 of file inverted_index_storage.hpp.

Referenced by add_inp_scores(), clear(), get(), put_diff(), and remove().

tbl_t jubatus::core::storage::inverted_index_storage::inv_diff_

private

Definition at line 90 of file inverted_index_storage.hpp.

Referenced by add_inp_scores(), clear(), get(), get_diff(), put_diff(), remove(), and set().

---

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

• jubatus/core/storage/inverted_index_storage.hpp
• jubatus/core/storage/inverted_index_storage.cpp