data_util.h

Go to the documentation of this file.

// Copyright 2012 Yandex Artem Babenko
#pragma once


#include <bitset>
#include <fstream>
#include <ios>
#include <iostream>
#include <map>
#include <set>
#include <vector>

#include <boost/bind.hpp>
#include <boost/thread.hpp>

#include "mkl_cblas.h"

#include "multitable.hpp"

using std::bitset;
using std::cout;
using std::ifstream;
using std::ios;
using std::endl;
using std::multimap;
using std::pair;
using std::set;
using std::string;
using std::vector;

typedef float Coord;
typedef float Distance;
typedef int Dimensions;
typedef int PointId;
typedef int ClusterId;
typedef vector<Coord> Point;
typedef vector<Point> Points;
typedef vector<PointId> PointIds;
typedef set<PointId> SetPoints;
typedef vector<ClusterId> ClusterIds;
typedef vector<ClusterId> CoarseQuantization;
typedef unsigned char FineClusterId;
typedef vector<FineClusterId> FineQuantization;
typedef vector<SetPoints> ClustersToPoints;
typedef std::vector<ClusterId> PointsToClusters; 
typedef std::vector<Point> Centroids;

enum PointType {
  FVEC,
  BVEC
};

enum RerankMode {
  USE_RESIDUALS, 
  USE_INIT_POINTS
};

template<class Record>
struct MultiIndex {
  vector<Record> multiindex;
  Multitable<int> cell_edges;    
};

Distance Eucldistance(const Point& x, const Point& y);
Distance Eucldistance(const Point& x, const Point& y, Dimensions start, Dimensions finish);

template<class T, class U>
inline U Round(T number) {
  return (U)(number + 0.5);
}

template<class T, class U>
void ReadPoints(const string& filename,
                vector<vector<U> >* points,
                int count) {
  ifstream input;
        input.open(filename.c_str(), ios::binary);
  if(!input.good()) {
    throw std::logic_error("Invalid filename");
  }
  points->resize(count);
  int dimension;
  for(PointId pid = 0; pid < count; ++pid) {
    input.read((char*)&dimension, sizeof(dimension));
    if(dimension <= 0) {
      throw std::logic_error("Bad file content: non-positive dimension");
    }
    points->at(pid).resize(dimension);
    for(Dimensions d = 0; d < dimension; ++d) {
      T buffer;
      input.read((char*)&(buffer), sizeof(T));
      points->at(pid)[d] = Round<T, U>(buffer);
    }
  }
}

template<class T, class U>
void ReadVector(ifstream& input, vector<U>* v) {
  if(!input.good()) {
    throw std::logic_error("Bad input stream");
  }
  int dimension;
  input.read((char*)&dimension, sizeof(dimension));
  if(dimension <= 0) {
    throw std::logic_error("Bad file content: non-positive dimension");
  }
  v->resize(dimension);
  for(Dimensions d = 0; d < dimension; ++d) {
    T buffer;
    input.read((char*)&buffer, sizeof(buffer));
    v->at(d) = Round<T, U>(buffer);
  }    
}

template<class T>
void ReadVocabulary(ifstream& input,
                    Dimensions dimension,
                    int vocabulary_size,
                    Centroids* centroids) {
  if(!input.good()) {
    throw std::logic_error("Bad input stream");
  }
  centroids->resize(vocabulary_size);
  for(ClusterId centroid_index = 0; centroid_index < centroids->size(); ++centroid_index) {
    centroids->at(centroid_index).resize(dimension);
    for(Dimensions dimension_index = 0; dimension_index < dimension; ++dimension_index) {
      T buffer;
      input.read((char*)&buffer, sizeof(buffer));
      centroids->at(centroid_index)[dimension_index] = Round<T, Coord>(buffer);
    }
  }
}

template<class T>
void ReadVocabularies(const string& filename,
                      Dimensions space_dimension,
                      vector<Centroids>* centroids) {
  ifstream vocabulary;
  vocabulary.open(filename.c_str(), ios::binary);
  if(!vocabulary.good()) {
    throw std::logic_error("Bad vocabulary file");
  }
  int dimension;
  vocabulary.read((char*)&dimension, sizeof(dimension));
  if(dimension <= 0) {
    throw std::logic_error("Bad file content: non-positive dimension");
  }
  int vocabs_count = space_dimension / dimension;
  if(space_dimension < dimension) {
    throw std::logic_error("Space dimension is less than vocabulary dimension");
  }
  centroids->resize(vocabs_count);
  int vocabulary_size;
  vocabulary.read((char*)&vocabulary_size, sizeof(vocabulary_size));
  for(int vocab_item = 0; vocab_item < vocabs_count; ++vocab_item) {
    ReadVocabulary<T>(vocabulary, dimension, vocabulary_size, &(centroids->at(vocab_item)));
  }
}

template<class T>
void ReadFineVocabs(const string& fine_vocabs_filename, vector<Centroids>* fine_vocabs) {
  ifstream fine_vocabs_stream;
  fine_vocabs_stream.open(fine_vocabs_filename.c_str(), ios::binary);
  if(!fine_vocabs_stream.good()) {
    throw std::logic_error("Bad fine vocabulary file");
  }
  int vocabs_count, centroids_count, vocabs_dim;
  fine_vocabs_stream.read((char*)&vocabs_count, sizeof(vocabs_count));
  if(vocabs_count < 1) {
    throw std::logic_error("Bad fine vocabulary file content: number of vocabularies < 1");
  }
  fine_vocabs_stream.read((char*)&centroids_count, sizeof(centroids_count));
  if(centroids_count < 1) {
    throw std::logic_error("Bad fine vocabulary file content: vocabulary capacity < 1");
  }
  fine_vocabs_stream.read((char*)&vocabs_dim, sizeof(vocabs_dim));
  if(vocabs_dim < 1) {
    throw std::logic_error("Bad fine vocabulary file content: vocabulary dimension < 1");
  }
  fine_vocabs->resize(vocabs_count);
  for(int voc_index = 0; voc_index < vocabs_count; ++voc_index) {
    ReadVocabulary<T>(fine_vocabs_stream, vocabs_dim, centroids_count, &(fine_vocabs->at(voc_index)));
  }
}

void GetSubpoints(const Points& points,
                  const Dimensions start_dim,
                  const Dimensions final_dim,
                  Points* subpoints);

ClusterId GetNearestClusterId(const Point& point, const Centroids& centroids,
                              const Dimensions start_dim, const Dimensions final_dim);

void GetResidual(const Point& point, const CoarseQuantization& coarse_quantizations,
                 const vector<Centroids>& centroids, Point* residual);
void GetResidual(const Point& point, const CoarseQuantization& coarse_quantizations,
                 const vector<Centroids>& centroids, Coord* residual);

void GetNearestClusterIdsForPointSubset(const Points& points, const Centroids& centroids,
                                        const PointId start_pid, const PointId final_pid,
                                        vector<ClusterId>* nearest);

void GetNearestClusterIdsForSubpoints(const Points& points, const Centroids& centroids,
                                      const Dimensions start_dim, const Dimensions final_dim,
                                      int threads_count, vector<ClusterId>* nearest);

void GetPointsCoarseQuaintizations(const Points& points, const vector<Centroids>& centroids,
                                   const int threads_count,
                                   vector<CoarseQuantization>* coarse_quantizations);


struct IndexConfig {
  RerankMode rerank_mode;
  vector<Centroids> fine_vocabs;
};

struct RerankADC8 {
  PointId pid;
  FineClusterId quantizations[8];
  template<class Archive>
  void serialize(Archive& arc, unsigned int version) {
    arc & pid;
    arc & quantizations;
  }
};

struct RerankADC16 {
  PointId pid;
  FineClusterId quantizations[16];
  template<class Archive>
  void serialize(Archive& arc, unsigned int version) {
    arc & pid;
    arc & quantizations;
  }
};