hashtree.h

Entropy-based CLIQUE算法改进

// Statistics of a subspace
struct EntStat {
  float entropy;
  float interest;
  float interest_gain;
};

class HashTree;  // forward declaration

// Node of a hash tree
class TreeNode {
public:
  TreeNode(bool l, int d, int n);
  ~TreeNode();
  bool isLeaf() const { return (subspace!=NULL); }
  int hashFunc(int i);
  TreeNode* transver(const IntList& i);
  void insert(const IntList& ss);
  void split();
  void resize(int newsize);
  void remove(const IntList& ss, int& no_ss);
  void show() const;
  void group(const HashTree& hin, HashTree& hout);
  void convert2array(IntList*& ia, int& idx_ss) const;
  void setStat(const IntList& ss, const EntStat& es);
  void applyThreshold(EntStat es, int& no_ss, HashTree& ht);

  IntList** subspace; // Array of subspaces (leaf node)
  TreeNode** child;   // Array of pointers to children (internal node)
  EntStat* sta;       // Entropy and other measures for subspaces (leaf node)
  int len;            // No of subspaces stored (leaf node)
  int depth;          // Depth of current node
  int brFactor;       // Branching factor
};

// A hash tree
class HashTree {
public:
  HashTree(int n, int d);
  ~HashTree();
  void insert(const IntList& ss);
  void remove(const IntList& ss);
  void show() const { root->show(); }
  void group(HashTree& ht) { root->group(*this,ht); }
  bool exist(const IntList& il) const;
  bool prune(const IntList& cand) const;
  void convert2array(IntList*& ia, int& idx_ss) const;
  void locktree();
  void setStat(const IntList& ss, const EntStat& es);
  EntStat findStat(const IntList& ss) const;
  void applyThreshold(EntStat es, HashTree& ht);
  
  int get_dim() const { return dim; }
  int get_no_ss() const { return no_ss; }

private:
  int brFactor;    // Branching factor
  int dim;         // Dimension of subspaces
  int no_ss;       // No of subspaces stored
  
  TreeNode* root;  // Root of hash tree
};