Repository: intellistream/Sesame (language: python)

Issue:
Code Reformat to include more evaluations



Discussion / hints:

Fix patch:
diff --git a/include/Algorithm/Algorithm.hpp b/include/Algorithm/Algorithm.hpp
index 85f60152..4b0ec7dd 100644
--- a/include/Algorithm/Algorithm.hpp
+++ b/include/Algorithm/Algorithm.hpp
@@ -14,7 +14,7 @@
 using namespace std;
 namespace SESAME {
 
-enum algoType { BirchType, StreamKMeansType, CluStreamType, DenStreamType, DBStreamType};
+enum algoType { BirchType, StreamKMeansType, CluStreamType, DenStreamType, DBStreamType, EDMStreamType};
 
 class Algorithm;
 typedef std::shared_ptr<Algorithm> AlgorithmPtr;
diff --git a/include/Algorithm/DataStructure/Cache.hpp b/include/Algorithm/DataStructure/Cache.hpp
new file mode 100644
index 00000000..91872807
--- /dev/null
+++ b/include/Algorithm/DataStructure/Cache.hpp
@@ -0,0 +1,59 @@
+//
+// Created by tuidan on 2021/9/9.
+//
+
+#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_CACHE_HPP_
+#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_CACHE_HPP_
+#include <Algorithm/DataStructure/DPNode.hpp>
+#include <Algorithm/DataStructure/OutlierReservoir.hpp>
+#include <Algorithm/DataStructure/DPTree.hpp>
+#include <vector>
+#include <iostream>
+#include <memory>
+#include <unordered_set>
+
+namespace SESAME {
+
+// define the share point of the class object
+class Cache;
+typedef std::shared_ptr<Cache> CachePtr;
+
+class Cache {
+ private:
+  int num;
+  int size;
+  double a;
+  double lamd;
+  double r;
+  std::vector<DPNodePtr> buffer;
+  std::vector<DPNodePtr> clus;
+  int pnum;
+ public:
+  Cache();
+  ~Cache();
+  int GetNum()  ;
+  void SetNum(int num);
+  int GetSize()  ;
+  void SetSize(int size);
+  double GetA()  ;
+  void SetA(double a);
+  double GetLamd()  ;
+  void SetLamd(double lamd);
+  double GetR()  ;
+  void SetR(double r);
+    std::vector<DPNodePtr> &GetBuffer()  ;
+  void SetBuffer(  std::vector<DPNodePtr> &buffer);
+    std::vector<DPNodePtr> &GetClus()  ;
+  void SetClus(  std::vector<DPNodePtr> &clus);
+  int GetPnum()  ;
+  void SetPnum(int pnum);
+  Cache(int num, double a, double lamd, double r);
+  DPNodePtr add(PointPtr &p, double startTime);
+  bool isFull();
+  void compDeltaRho(double time);
+  void getDPTree(double minRho, double minDelta, DPTreePtr &dpTree,
+                 OutPtr &outs, std::unordered_set<ClusterPtr> &clusters);
+  //void outputBuffer(String outpath, double minRho)
+};
+}
+#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_CACHE_HPP_
diff --git a/include/Algorithm/DataStructure/DPNode.hpp b/include/Algorithm/DataStructure/DPNode.hpp
new file mode 100644
index 00000000..0e543417
--- /dev/null
+++ b/include/Algorithm/DataStructure/DPNode.hpp
@@ -0,0 +1,98 @@
+//
+// Created by tuidan on 2021/9/9.
+//
+
+#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPNODE_HPP_
+#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPNODE_HPP_
+#include <vector>
+#include <iostream>
+#include <memory>
+#include <unordered_set>
+#include <Algorithm/DataStructure/Point.hpp>
+namespace SESAME {
+class DPNode;
+class Cluster;
+typedef std::shared_ptr<DPNode> DPNodePtr;
+typedef std::shared_ptr<Cluster> ClusterPtr;
+
+class Cluster {
+ private:
+  int label;
+  std::unordered_set<DPNodePtr> cells;
+
+ public:
+  explicit Cluster();
+  explicit Cluster(int label);
+  void add(DPNodePtr &node);
+  void remove(DPNodePtr &node);
+  int GetLabel() ;
+  void SetLabel(int label);
+  [[nodiscard]] std::unordered_set<DPNodePtr> &GetCells() ;
+  void SetCells(std::unordered_set<DPNodePtr> &cells);
+};
+class DPNode {
+ private:
+  int cid;
+  int Cid;
+  int num;
+  double rho;
+  double delta;
+  SESAME::DPNodePtr dep; //TODO: father
+  SESAME::PointPtr center;
+  double lastTime;
+  bool active;
+  std::unordered_set<DPNodePtr> sucs; //TODO: children
+  SESAME::ClusterPtr cluster;
+  // public double sumDelta;
+  // public int sucNum;
+  double inactiveTime;
+
+  /**
+   * we will use dis to quickly update the delta of CluCell
+   */
+  double dis;
+ public:
+
+  DPNode();
+  ~DPNode();
+  DPNode(SESAME::PointPtr &p, double time);
+  [[nodiscard]] int GetId() ;
+  void SetId(int id);
+  [[nodiscard]] int GetCId() ;
+  void SetCId(int Cid);
+  [[nodiscard]] int GetNum() ;
+  void SetNum(int num);
+  [[nodiscard]] double GetRho() ;
+  void SetRho(double rho);
+  [[nodiscard]] double GetDelta() ;
+  void SetDelta(double delta);
+  [[nodiscard]] DPNodePtr &GetDep() ;
+  void SetDep(DPNodePtr &dep);
+  [[nodiscard]] PointPtr &GetCenter() ;
+  void SetCenter(PointPtr &center);
+  [[nodiscard]] double GetLastTime() ;
+  void SetLastTime(double last_time);
+  [[nodiscard]] bool IsActive()  ;
+  void SetActive(bool active);
+  [[nodiscard]] std::unordered_set<SESAME::DPNodePtr> &GetSucs() ;
+  void SetSucs(std::unordered_set<SESAME::DPNodePtr> &sucs);
+  [[nodiscard]] ClusterPtr &GetCluster() ;
+  void SetCluster(SESAME::ClusterPtr &cluster);
+  [[nodiscard]] double GetInactiveTime() ;
+  void SetInactiveTime(double inactive_time);
+  [[nodiscard]] double GetDis() ;
+  void SetDis(double dis);
+  SESAME::DPNodePtr copy();
+
+
+  void insert(double startTime);
+  void add(double coef, double startTime);
+  double getDisTo(SESAME::DPNodePtr &node);
+  void removeSuccessor(SESAME::DPNodePtr &node);
+  bool hasSuccessor();
+
+  void addSuccessor(DPNodePtr &node);
+};
+
+}
+#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPNODE_HPP_
diff --git a/include/Algorithm/DataStructure/DPTree.hpp b/include/Algorithm/DataStructure/DPTree.hpp
new file mode 100644
index 00000000..7a67c2b4
--- /dev/null
+++ b/include/Algorithm/DataStructure/DPTree.hpp
@@ -0,0 +1,85 @@
+//
+// Created by tuidan on 2021/9/1.
+//
+
+#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPTREE_HPP_
+#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPTREE_HPP_
+#include <iostream>
+#include <memory>
+#include <vector>
+#include <Algorithm/DataStructure/FeatureVector.hpp>
+#include <Algorithm/DataStructure/Point.hpp>
+#include <Algorithm/DataStructure/DPNode.hpp>
+#include <Algorithm/DataStructure/OutlierReservoir.hpp>
+namespace SESAME {
+
+// define the share point of the class object
+class DPTree;
+typedef std::shared_ptr<DPTree> DPTreePtr;
+
+class DPTree {
+ private:
+  double lastTime;
+  int size;
+  int num;
+  std::vector<SESAME::DPNodePtr> Clus;
+
+  double a;
+  double lamd;
+  double CluR;
+
+  int cluLabel;
+ public:
+  double GetLastTime()     ;
+  void SetLastTime(double last_time);
+  int GetSize()  ;
+  void SetSize(int size);
+  int GetNum()  ;
+  void SetNum(int num);
+  std::vector<SESAME::DPNodePtr> &GetClus()  ;
+  void SetClus(  std::vector<SESAME::DPNodePtr> &clus);
+  double GetA()  ;
+  void SetA(double a);
+  double GetLamd()  ;
+  void SetLamd(double lamd);
+  double GetCluR()    ;
+  void SetCluR(double clu_r);
+  int GetCluLabel()  ;
+  void SetCluLabel(int clu_label);
+  double GetMinDelta()  ;
+  void SetMinDelta(double min_delta);
+ private:
+  double minDelta;
+ public:
+  DPTree();
+  ~DPTree();
+  DPTree(int num, double CluR);
+  void insert(SESAME::DPNodePtr &cc, int opt);
+  void init(std::vector<SESAME::DPNodePtr> &clus, int size, double minRho, double minDelta,
+            SESAME::OutPtr &outs, std::unordered_set<ClusterPtr> &clusters);
+  SESAME::DPNodePtr findNN(PointPtr p, double coef, int opt, double time);
+  void adjustNoDelta(int index);
+  void adjustNoOpt(int index);
+  void computeDeltaNoOpt(int index);
+  void adjustOpt1(int index);
+  void computeDeltaF1(int index);
+  void adjust(int index);
+  void computeHeadDelta();
+  void computeDelta(int index);
+  void deleteInact(SESAME::OutPtr &outres, double minRho, double time);
+  double computeAlpha(double minDelta);
+  double adjustMinDelta(double alpha);
+  //double djustMinDelta(double alpha, double minDelta);
+  double fun(double alpha, double upavg, double downavg, double avg);
+ // bool check(SESAME::OutPtr outres);
+  //void check(std::vector<SESAME::ClusterPtr> clusters);
+  void adjustCluster(std::unordered_set<SESAME::ClusterPtr> &clusters);
+
+
+};
+
+
+
+
+}
+#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPTREE_HPP_
diff --git a/include/Algorithm/DataStructure/DataStructureFactory.hpp b/include/Algorithm/DataStructure/DataStructureFactory.hpp
index 21567023..b7ef0598 100644
--- a/include/Algorithm/DataStructure/DataStructureFactory.hpp
+++ b/include/Algorithm/DataStructure/DataStructureFactory.hpp
@@ -12,6 +12,10 @@
 #include <Algorithm/DataStructure/MicroCluster.hpp>
 #include <Algorithm/DataStructure/Snapshot.hpp>
 #include <Algorithm/DataStructure/CFTree.hpp>
+#include <Algorithm/DataStructure/DPTree.hpp>
+#include <Algorithm/DataStructure/DPNode.hpp>
+#include <Algorithm/DataStructure/OutlierReservoir.hpp>
+#include <Algorithm/DataStructure/Cache.hpp>
 #include <Algorithm/DataStructure/FeatureVector.hpp>
 #include <Algorithm/DataStructure/WeightedAdjacencyList.hpp>
 namespace SESAME {
@@ -34,6 +38,15 @@ class DataStructureFactory {
   static void clearSnapshot(SnapshotPtr snapshot);
   static CFTreePtr createCFTree();
   static NodePtr createNode();
+  //EDMStream
+  static DPTreePtr createDPTree(int num, double r);
+  static DPNodePtr createDPNode();
+  static DPNodePtr createDPNode(SESAME::PointPtr p, double time);
+  static CachePtr creatCache();
+  static CachePtr creatCache(int num, double a, double lamd, double r);
+  static OutPtr createOutlierReservoir();
+  static OutPtr createOutlierReservoir(double r, double a, double lamd);
+
   static MicroClusterPairPtr createMicroClusterPair(MicroClusterPtr microCluster1,MicroClusterPtr microCluster2);
   static void clearMicroClusterPair(MicroClusterPairPtr microClusterPair);
   static AdjustedWeightPtr createAdjustedWeight(double weight, clock_t pointTime);
diff --git a/include/Algorithm/DataStructure/OutlierReservoir.hpp b/include/Algorithm/DataStructure/OutlierReservoir.hpp
new file mode 100644
index 00000000..d83e8993
--- /dev/null
+++ b/include/Algorithm/DataStructure/OutlierReservoir.hpp
@@ -0,0 +1,55 @@
+//
+// Created by tuidan on 2021/9/9.
+//
+
+#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_OUTLIERRESERVOIR_HPP_
+#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_OUTLIERRESERVOIR_HPP_
+#include <Algorithm/DataStructure/DPNode.hpp>
+#include <vector>
+#include <iostream>
+#include <memory>
+#include <unordered_set>
+
+namespace SESAME {
+
+class OutlierReservoir;
+typedef std::shared_ptr<OutlierReservoir> OutPtr;
+class OutlierReservoir {
+ private:
+  double r;
+  double timeGap;
+  long lastDelTime;
+
+  double a;
+  double lamd;
+
+  std::unordered_set<DPNodePtr> outliers;
+
+ public:
+  [[nodiscard]] double GetR()    ;
+  void SetR(double r);
+  [[nodiscard]] double GetTimeGap()    ;
+  void SetTimeGap(double time_gap);
+  [[nodiscard]] long GetLastDelTime()    ;
+  void SetLastDelTime(long last_del_time);
+  [[nodiscard]] double GetA()    ;
+  void SetA(double a);
+  [[nodiscard]] double GetLamd()    ;
+  void SetLamd(double lamd);
+  [[nodiscard]]     std::unordered_set<SESAME::DPNodePtr> &GetOutliers()    ;
+  void SetOutliers(    std::unordered_set<SESAME::DPNodePtr> &outliers);
+  OutlierReservoir();
+  ~OutlierReservoir();
+  OutlierReservoir(double r, double a, double lamd);
+
+  void setTimeGap(double timeGap);
+
+  void insert(SESAME::DPNodePtr &c);
+
+  SESAME::DPNodePtr insert(SESAME::PointPtr &p, double time);
+
+  void remove(SESAME::DPNodePtr &nn);
+};
+
+}
+#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_OUTLIERRESERVOIR_HPP_
diff --git a/include/Algorithm/DataStructure/Point.hpp b/include/Algorithm/DataStructure/Point.hpp
index 736def28..5cf3693f 100644
--- a/include/Algorithm/DataStructure/Point.hpp
+++ b/include/Algorithm/DataStructure/Point.hpp
@@ -18,6 +18,9 @@ class Point {
   int index; // 1,2,3,4,5....
   double weight; // considering the outdated effect
   double cost;
+  double minDist;
+ private:
+  // the distance to the nearest data point
   int clusteringCenter;  // using index to identify
   int dimension;// feature Length
   std::vector<double> *feature;//TODO: need to think how to remove * here.
@@ -37,6 +40,9 @@ class Point {
   int getDimension() const;
   void setDimension(int d);
   int getFeatureLength();
+  double getDisTo(SESAME::PointPtr p);
+  double getMinDist() const;
+  void setMinDist(double min_dist);
   SESAME::PointPtr copy();
 };
 }
diff --git a/include/Algorithm/EDMStream.hpp b/include/Algorithm/EDMStream.hpp
new file mode 100644
index 00000000..ad64688d
--- /dev/null
+++ b/include/Algorithm/EDMStream.hpp
@@ -0,0 +1,63 @@
+//
+// Created by tuidan on 2021/9/1.
+//
+
+#ifndef SESAME_INCLUDE_ALGORITHM_EDMSTREAM_HPP_
+#define SESAME_INCLUDE_ALGORITHM_EDMSTREAM_HPP_
+#include <Algorithm/Algorithm.hpp>
+#include <Algorithm/DataStructure/DPNode.hpp>
+#include <Sinks/DataSink.hpp>
+#include <Algorithm/DataStructure/Cache.hpp>
+#include <Algorithm/DataStructure/DataStructureFactory.hpp>
+#include <Algorithm/DataStructure/OutlierReservoir.hpp>
+#include <Algorithm/DataStructure/DPTree.hpp>
+#include <Utils/BenchmarkUtils.hpp>
+#include <unordered_set>
+
+namespace SESAME {
+class EDMParameter : public AlgorithmParameters {
+ public:
+  bool isInit = false;
+
+  double a;
+  double lamda;
+  double beta;
+  int cacheNum;
+  double radius;
+
+  double minDelta;
+  int opt;
+};
+
+class EDMStream : public Algorithm {
+
+ public:
+  double deltaT;
+  int actCluMaxNum = 10000;
+  double minRho;
+  double alpha;
+
+  EDMParameter EDMParam;
+  DPTreePtr dpTree;
+  OutPtr outres;
+  CachePtr cache;
+  std::unordered_set<ClusterPtr> clusters;
+
+  EDMStream(param_t &cmd_params);
+  ~EDMStream();
+  void Initilize() override;
+  void setMinDelta(double minDelta);
+
+  void InitDP(double time);
+  SESAME::DPNodePtr streamProcess(SESAME::PointPtr p, int opt, double time);
+  double computeAlpha();
+  double adjustMinDelta();
+  void delCluster();
+  SESAME::DPNodePtr retrive(SESAME::PointPtr p, int opt, double time);
+
+  void runOnlineClustering(SESAME::PointPtr input) override;
+
+  void runOfflineClustering(DataSinkPtr sinkPtr) override;
+};
+}
+#endif //SESAME_INCLUDE_ALGORITHM_EDMSTREAM_HPP_
diff --git a/include/Utils/BenchmarkUtils.hpp b/include/Utils/BenchmarkUtils.hpp
index 28901d2b..edd9d557 100644
--- a/include/Utils/BenchmarkUtils.hpp
+++ b/include/Utils/BenchmarkUtils.hpp
@@ -44,6 +44,12 @@ struct param_t {
   double lambda;
   double mu;
   double beta;
+  // EDMStream
+  double a;
+  int cacheNum;
+  double delta;
+  int opt;
+
   //used in DBStream
   double radius;
   int cleanUpInterval;
diff --git a/src/Algorithm/AlgorithmFactory.cpp b/src/Algorithm/AlgorithmFactory.cpp
index 89e11085..c1a9daca 100644
--- a/src/Algorithm/AlgorithmFactory.cpp
+++ b/src/Algorithm/AlgorithmFactory.cpp
@@ -9,6 +9,7 @@
 #include <Algorithm/DenStream.hpp>
 #include <Algorithm/DBStream.hpp>
 #include <Algorithm/Birch.hpp>
+#include <Algorithm/EDMStream.hpp>
 #include <Algorithm/AlgorithmFactory.hpp>
 
 SESAME::AlgorithmPtr SESAME::AlgorithmFactory::create(param_t &cmd_params) {
@@ -28,9 +29,14 @@ SESAME::AlgorithmPtr SESAME::AlgorithmFactory::create(param_t &cmd_params) {
     shared_ptr<DenStream> denStream = std::make_shared<DenStream>(cmd_params);
     return (SESAME::AlgorithmPtr) denStream;
   }
+  if (cmd_params.algoType == SESAME::EDMStreamType) {
+    shared_ptr<EDMStream> eDMStream = std::make_shared<EDMStream>(cmd_params);
+    return (SESAME::AlgorithmPtr) eDMStream;
+  }
   if (cmd_params.algoType == DBStreamType) {
     shared_ptr<DBStream> dbStream = std::make_shared<DBStream>(cmd_params);
     return (SESAME::AlgorithmPtr) dbStream;
   }
   throw std::invalid_argument("Unsupported");
+
 }
diff --git a/src/Algorithm/CMakeLists.txt b/src/Algorithm/CMakeLists.txt
index a6f7bf78..2b34a2f6 100644
--- a/src/Algorithm/CMakeLists.txt
+++ b/src/Algorithm/CMakeLists.txt
@@ -3,6 +3,7 @@ add_source_sesame(
         CluStream.cpp
         Birch.cpp
         DenStream.cpp
+        EDMStream.cpp
         DBStream.cpp
         Algorithm.cpp
         AlgorithmFactory.cpp
diff --git a/src/Algorithm/DataStructure/CMakeLists.txt b/src/Algorithm/DataStructure/CMakeLists.txt
index 3336d264..4b876647 100644
--- a/src/Algorithm/DataStructure/CMakeLists.txt
+++ b/src/Algorithm/DataStructure/CMakeLists.txt
@@ -7,5 +7,9 @@ add_source_sesame(
         WeightedAdjacencyList.cpp
         DataStructureFactory.cpp
         CFTree.cpp
+        DPTree.cpp
+        DPNode.cpp
+        Cache.cpp
+        OutlierResevoir.cpp
         FeatureVector.cpp
 )
\ No newline at end of file
diff --git a/src/Algorithm/DataStructure/Cache.cpp b/src/Algorithm/DataStructure/Cache.cpp
new file mode 100644
index 00000000..9a9f7375
--- /dev/null
+++ b/src/Algorithm/DataStructure/Cache.cpp
@@ -0,0 +1,131 @@
+//
+// Created by tuidan on 2021/9/9.
+//
+
+#include <Algorithm/DataStructure/Cache.hpp>
+#include <cfloat>
+#include <cmath>
+#include <algorithm>
+bool cmp(SESAME::DPNodePtr &c1,SESAME::DPNodePtr &c2){
+  return c1->GetRho() > c2->GetRho();
+}
+SESAME::Cache::Cache(int num, double a, double lamd, double r) {
+  std::vector<DPNodePtr> clu(num);
+  this->buffer = clu;
+  this->num = num;
+  this->pnum = 0;
+  this->size = 0;
+  this->a = a;
+  this->lamd = lamd;
+  this->r = r;
+}
+SESAME::Cache::~Cache() = default;
+SESAME::Cache::Cache() = default;
+SESAME::DPNodePtr SESAME::Cache::add(SESAME::PointPtr &p, double startTime) {
+  this->pnum++;
+  double dis = FLT_MAX;
+  double minDis = FLT_MAX;
+  SESAME::DPNodePtr nn;
+  for (int i = 0; i < size; i++) {
+    dis = p->getDisTo(buffer[i]->GetCenter());
+    if (dis < minDis) {
+      minDis = dis;
+      nn = buffer[i];
+    }
+  }
+  if (minDis <= r) {
+    double coef = pow(a, lamd * double (startTime - nn->GetLastTime()));
+    nn->add(coef, startTime);
+    return nn;
+  } else {
+    SESAME::DPNodePtr c = std::make_shared<DPNode>(p, startTime);
+    buffer[size] = c;
+    size++;
+    return c;
+  }
+}
+bool SESAME::Cache::isFull() {
+  return pnum == num;
+}
+void SESAME::Cache::compDeltaRho(double time) {
+  std::vector<DPNodePtr> blankNode(size);
+  clus = blankNode;
+  for (int i = 0; i < size; i++) {
+    buffer[i]->SetRho((float) (pow(a, lamd * (time - buffer[i]->GetLastTime())) * buffer[i]->GetRho()));
+    clus[i] = buffer[i];
+  }
+  sort(clus.begin(), clus.end(), cmp);
+
+  double dis = 0;
+  clus[0]->SetDelta(0);
+  for (int i = 1; i < size; i++) {
+    DPNodePtr cc = clus[i];
+    auto minDis = DBL_MAX;
+    for (int j = i - 1; j >= 0; j--) {
+      dis = cc->GetCenter()->getDisTo(clus[j]->GetCenter());
+      if (minDis > dis) {
+        minDis = dis;
+        cc->SetDep(clus[j]);
+      }
+    }
+    cc->SetDelta(minDis);
+    if (clus[0]->GetDelta() < minDis) {
+      clus[0]->SetDelta(minDis);
+    }
+  }
+}
+void SESAME::Cache::getDPTree(double minRho,
+                              double minDelta,
+                              SESAME::DPTreePtr &dpTree,
+                              SESAME::OutPtr &outs,
+                              std::unordered_set<ClusterPtr> &clusters) {
+  dpTree->init(clus, size, minRho, minDelta, outs, clusters);
+}
+int SESAME::Cache::GetNum()  {
+  return num;
+}
+void SESAME::Cache::SetNum(int num) {
+  Cache::num = num;
+}
+int SESAME::Cache::GetSize()  {
+  return size;
+}
+void SESAME::Cache::SetSize(int size) {
+  Cache::size = size;
+}
+double SESAME::Cache::GetA()  {
+  return a;
+}
+void SESAME::Cache::SetA(double a) {
+  Cache::a = a;
+}
+double SESAME::Cache::GetLamd()  {
+  return lamd;
+}
+void SESAME::Cache::SetLamd(double lamd) {
+  Cache::lamd = lamd;
+}
+double SESAME::Cache::GetR()  {
+  return r;
+}
+void SESAME::Cache::SetR(double r) {
+  Cache::r = r;
+}
+ std::vector<SESAME::DPNodePtr> &SESAME::Cache::GetBuffer()  {
+  return buffer;
+}
+void SESAME::Cache::SetBuffer( std::vector<DPNodePtr> &buffer) {
+  Cache::buffer = buffer;
+}
+ std::vector<SESAME::DPNodePtr> &SESAME::Cache::GetClus()  {
+  return clus;
+}
+void SESAME::Cache::SetClus( std::vector<DPNodePtr> &clus) {
+  Cache::clus = clus;
+}
+int SESAME::Cache::GetPnum()  {
+  return pnum;
+}
+void SESAME::Cache::SetPnum(int pnum) {
+  Cache::pnum = pnum;
+}
diff --git a/src/Algorithm/DataStructure/DPNode.cpp b/src/Algorithm/DataStructure/DPNode.cpp
new file mode 100644
index 00000000..cf726bc0
--- /dev/null
+++ b/src/Algorithm/DataStructure/DPNode.cpp
@@ -0,0 +1,173 @@
+//
+// Created by tuidan on 2021/9/9.
+//
+
+#include <Algorithm/DataStructure/DPNode.hpp>
+#include <cfloat>
+#include <cmath>
+#include <cassert>
+/**
+ * DPNode
+ */
+static int id = 0;
+SESAME::DPNode::DPNode() {
+  this->cid = -1;
+  this->Cid = -1;
+  this->lastTime = 0;
+  this->inactiveTime = 0;
+  this->num = 0;
+  this->active = false;
+}
+
+SESAME::DPNode::~DPNode() {}
+
+int SESAME::DPNode::GetId(){
+  return cid;
+}
+void SESAME::DPNode::SetId(int id) {
+  DPNode:: cid = id;
+}
+int SESAME::DPNode::GetCId(){
+  return Cid;
+}
+void SESAME::DPNode::SetCId(int Cid) {
+  DPNode:: Cid = Cid;
+}
+int SESAME::DPNode::GetNum(){
+  return num;
+}
+void SESAME::DPNode::SetNum(int num) {
+  DPNode::num = num;
+}
+double SESAME::DPNode::GetRho() {
+  return rho;
+}
+void SESAME::DPNode::SetRho(double rho) {
+  DPNode::rho = rho;
+}
+double SESAME::DPNode::GetDelta() {
+  return delta;
+}
+void SESAME::DPNode::SetDelta(double delta) {
+  DPNode::delta = delta;
+}
+SESAME::DPNodePtr &SESAME::DPNode::GetDep() {
+  return dep;
+}
+void SESAME::DPNode::SetDep(SESAME::DPNodePtr &dep) {
+  DPNode::dep = dep;
+}
+ SESAME::PointPtr &SESAME::DPNode::GetCenter() {
+  return center;
+}
+void SESAME::DPNode::SetCenter(SESAME::PointPtr &center) {
+  DPNode::center = center;
+}
+double SESAME::DPNode::GetLastTime() {
+  return lastTime;
+}
+void SESAME::DPNode::SetLastTime(double last_time) {
+  lastTime = last_time;
+}
+bool SESAME::DPNode::IsActive() {
+  return active;
+}
+void SESAME::DPNode::SetActive(bool active) {
+  DPNode::active = active;
+}
+ std::unordered_set<SESAME::DPNodePtr> &SESAME::DPNode::GetSucs() {
+  return sucs;
+}
+void SESAME::DPNode::SetSucs(std::unordered_set<SESAME::DPNodePtr> &sucs) {
+  DPNode::sucs = sucs;
+}
+ SESAME::ClusterPtr &SESAME::DPNode::GetCluster() {
+  return cluster;
+}
+void SESAME::DPNode::SetCluster(SESAME::ClusterPtr &cluster) {
+  DPNode::cluster = cluster;
+}
+double SESAME::DPNode::GetInactiveTime() {
+  return inactiveTime;
+}
+void SESAME::DPNode::SetInactiveTime(double inactive_time) {
+  inactiveTime = inactive_time;
+}
+double SESAME::DPNode::GetDis() {
+  return dis;
+}
+void SESAME::DPNode::SetDis(double dis) {
+  DPNode::dis = dis;
+}
+
+SESAME::DPNode::DPNode(SESAME::PointPtr &p, double time) {
+  this->cid = id++;
+  this->rho = 1;
+  this->delta = FLT_MAX;
+  this->dep = nullptr;
+  this->center = p->copy();
+  this->lastTime = time;
+  this->active = false;
+  this->Cid = 0;
+  this->inactiveTime = 0;
+  this->dis = 0;
+}
+
+
+/**
+ * Cluster
+ */
+int SESAME::Cluster::GetLabel() {
+  return label;
+}
+void SESAME::Cluster::SetLabel(int label) {
+  Cluster::label = label;
+}
+ std::unordered_set<SESAME::DPNodePtr> &SESAME::Cluster::GetCells() {
+  return cells;
+}
+void SESAME::Cluster::SetCells( std::unordered_set<DPNodePtr> &cells) {
+  Cluster::cells = cells;
+}
+SESAME::Cluster::Cluster() {
+  this->label = -1;
+}
+SESAME::Cluster::Cluster(int label) {
+  this->label = label;
+}
+void SESAME::Cluster::add(DPNodePtr &node) {
+  assert(node);
+  this->cells.insert(node);
+}
+void SESAME::Cluster::remove(DPNodePtr &node) {
+  this->cells.erase(node);
+}
+
+void SESAME::DPNode::insert(double time) {
+  this->rho++;
+  this->lastTime = time;
+}
+void SESAME::DPNode::add(double coef, double time) {
+  this->rho = coef * this->rho + 1;
+  this->lastTime = time;
+}
+void SESAME::DPNode::addSuccessor(SESAME::DPNodePtr &node) {
+  this->sucs.insert(node);
+}
+void SESAME::DPNode::removeSuccessor(SESAME::DPNodePtr &node) {
+  this->sucs.erase(node);
+}
+bool SESAME::DPNode::hasSuccessor() {
+  return !sucs.empty();
+}
+double SESAME::DPNode::getDisTo(SESAME::DPNodePtr &node) {
+  double distance = 0;
+  for(int i = 0; i < this->center->getDimension(); i++){
+    distance = distance + pow(node->center->getFeatureItem(i) - this->center->getFeatureItem(i), 2);
+  }
+  return sqrt(distance);
+}
+SESAME::DPNodePtr SESAME::DPNode::copy() {
+  return std::make_shared<DPNode>(*this);
+}
+
diff --git a/src/Algorithm/DataStructure/DPTree.cpp b/src/Algorithm/DataStructure/DPTree.cpp
new file mode 100644
index 00000000..22a7589f
--- /dev/null
+++ b/src/Algorithm/DataStructure/DPTree.cpp
@@ -0,0 +1,593 @@
+//
+// Created by tuidan on 2021/9/1.
+//
+
+#include <Algorithm/DataStructure/DPTree.hpp>
+#include <Utils/Logger.hpp>
+#include <cfloat>
+#include <cmath>
+#include <unordered_set>
+
+
+/**
+ * DPTree
+ */
+SESAME::DPTree::DPTree() {}
+SESAME::DPTree::~DPTree() {}
+SESAME::DPTree::DPTree(int num, double CluR) {
+  this->num = num;
+  std::vector<DPNodePtr> clus(this->num);
+  this->Clus = clus;
+  this->CluR = CluR;
+  this->cluLabel = 0;
+}
+void SESAME::DPTree::insert(SESAME::DPNodePtr &cc, int opt) {
+  cc->SetActive(true);
+  Clus[size] = cc;
+  size++;
+
+  if (opt == 0) {
+    adjustNoOpt(size - 1);
+  }
+  if (opt == 1) {
+    adjustOpt1(size - 1);
+  }
+
+  if (opt == 2) {
+    adjust(size - 1);
+  }
+
+  if (opt == -1) {
+    adjustNoDelta(size - 1);
+  }
+
+  if (size == num) {
+    SESAME_DEBUG("lack of DPTree nodes");
+  }}
+void SESAME::DPTree::init(std::vector<SESAME::DPNodePtr> &clus,
+                          int size,
+                          double minRho,
+                          double minDelta,
+                          SESAME::OutPtr &outs,
+                          std::unordered_set<ClusterPtr> &clusters) {
+  this->minDelta = minDelta;
+  Clus[0] = clus[0];
+  SESAME::ClusterPtr cluster = std::make_shared<Cluster>(cluLabel++);;
+  cluster->add(Clus[0]);
+  Clus[0]->SetCluster(cluster);
+  clusters.insert(cluster);
+  int i = 1;
+
+  for (; i < size && clus[i]->GetRho() >= minRho; i++) {
+    Clus[i] = clus[i];
+    std::unordered_set<DPNodePtr> sucs = Clus[i]->GetDep()->GetSucs();
+    sucs.insert(Clus[i]);
+    if (Clus[i]->GetDelta() > minDelta) {
+      SESAME::ClusterPtr c = std::make_shared<Cluster>(cluLabel++);;
+      c->add(Clus[i]);
+      Clus[i]->SetCluster(c);
+      clusters.insert(c);
+    } else {
+      Clus[i]->GetDep()->GetCluster()->add(Clus[i]);
+      Clus[i]->SetCluster(Clus[i]->GetDep()->GetCluster());
+    }
+
+  }
+  double maxDelta = 0;
+  for (int j = 1; j < size && j < i; j++) {
+    if (maxDelta < Clus[j]->GetDelta()) {
+      maxDelta = Clus[j]->GetDelta();
+    }
+  }
+  Clus[0]->SetDelta(maxDelta);
+  this->size = i;
+  for (; i < size; i++) {
+    outs->insert(clus[i]);
+  }
+
+}
+SESAME::DPNodePtr SESAME::DPTree::findNN(SESAME::PointPtr p,
+                                         double coef,
+                                         int opt,
+                                         double time) {
+  int index = 0;
+  double dis = 0;
+  auto minDis = DBL_MAX;
+  for (int i = 0; i < size; i++) {
+    Clus[i]->SetRho(Clus[i]->GetRho() * coef);
+    dis = p->getDisTo(Clus[i]->GetCenter());
+    Clus[i]->SetDis(dis);
+    if (dis < minDis) {
+      minDis = dis;
+      index = i;
+    }
+  }
+
+  p->setMinDist(minDis);
+  auto cc = Clus[index];
+  if (minDis <= CluR) {
+    Clus[index]->insert(time);
+    if (opt == 0) {
+      adjustNoOpt(index);
+    }
+    if (opt == 1) {
+      adjustOpt1(index);
+    }
+
+    if (opt == 2) {
+      adjust(index);
+    }
+
+    if (opt == -1) {
+      adjustNoDelta(index);
+    }
+  }
+  return cc;
+}
+void SESAME::DPTree::adjustNoDelta(int index) {
+  Clus[0]->SetDelta(DBL_MAX);
+  auto clu = Clus[index];
+
+  if (index > 0) {
+    for (int i = index - 1; i >= 0; i--) {
+      if (clu->GetRho() > Clus[i]->GetRho()) {
+        Clus[i + 1] = Clus[i];
+        Clus[i] = clu;
+      } else {
+        break;
+      }
+    }
+  }
+}
+void SESAME::DPTree::adjustNoOpt(int index) {
+  Clus[0]->SetDelta(DBL_MAX);
+  auto clu = Clus[index];
+  int position = index;
+
+  if (index > 0) {
+    for (int i = index - 1; i >= 0; i--) {
+      if (clu->GetRho() > Clus[i]->GetRho()) {
+        Clus[i + 1] = Clus[i];
+        Clus[i] = clu;
+        position = i;
+      } else {
+        break;
+      }
+    }
+  }
+  if (Clus[0] == clu) {
+    clu->SetDelta(DBL_MAX);
+  }
+
+  computeDeltaNoOpt(position);
+  computeHeadDelta();
+}
+void SESAME::DPTree::computeDeltaNoOpt(int index) {
+  auto clu = Clus[index];
+  if (clu->GetDep() != nullptr) {
+    clu->GetDep()->removeSuccessor(clu);
+  }
+  double dis = 0;
+  clu->SetDelta(DBL_MAX);
+  for (int i = size - 1; i >= 0; i--) {
+    if (i < index) {
+      dis = clu->GetCenter()->getDisTo(Clus[i]->GetCenter());
+      if (clu->GetDelta() > dis) {
+        if (clu->GetDep() != nullptr) {
+          clu->GetDep()->removeSuccessor(clu);
+        }
+        clu->SetDelta(dis);
+        clu->SetDep(Clus[i]);
+        Clus[i]->addSuccessor(clu);
+      }
+    }
+    if (i > index) {
+      if (Clus[i]->GetDelta() > dis) {
+        if (Clus[i]->GetDep() != nullptr) {
+          Clus[i]->GetDep()->removeSuccessor(Clus[i]);
+        }
+        Clus[i]->SetDep(clu);
+        clu->addSuccessor(Clus[i]);
+        Clus[i]->SetDelta(dis);
+      }
+    }
+  }
+}
+void SESAME::DPTree::adjustOpt1(int index) {
+  Clus[0]->SetDelta(DBL_MAX);
+  auto clu = Clus[index];
+  if (clu->GetDep() != nullptr && clu->GetDep()->GetRho() < clu->GetRho()) {
+    clu->GetDep()->removeSuccessor(clu);
+    clu->SetDelta(DBL_MAX);
+  }
+  int position = index;
+  double dis = 0;
+
+  if (index > 0) {
+    for (int i = index - 1; i >= 0; i--) {
+      if (clu->GetRho() > Clus[i]->GetRho()) {
+        dis = Clus[i]->getDisTo(clu);
+        if (dis <= Clus[i]->GetDelta()) {
+          if (Clus[i]->GetDep() != nullptr) {
+            Clus[i]->GetDep()->removeSuccessor(Clus[i]);
+          }
+          Clus[i]->SetDep(clu);
+          clu->addSuccessor(Clus[i]);
+          Clus[i]->SetDelta(dis);
+        }
+        Clus[i + 1] = Clus[i];
+        Clus[i] = clu;
+        position = i;
+      } else {
+        break;
+      }
+    }
+  }
+  if (Clus[0] == clu) {
+    clu->SetDelta(DBL_MAX);
+    position = 0;
+  }
+
+  if (position != 0 && (clu->GetDep() == nullptr || clu->GetRho() > clu->GetDep()->GetRho())) {
+
+    clu->SetDelta(DBL_MAX);
+
+    computeDeltaF1(position);
+  }
+  computeHeadDelta();
+}
+void SESAME::DPTree::computeDeltaF1(int index) {
+  auto clu = Clus[index];
+  if (clu->GetDep() != nullptr) {
+    clu->GetDep()->removeSuccessor(clu);
+  }
+  clu->SetDelta(DBL_MAX);
+  if (index == 0) {
+    return;
+  }
+  double dis = 0;
+
+  // with one optimization
+
+  for (int i = index - 1; i >= 0; i--) {
+    dis = clu->GetCenter()->getDisTo(Clus[i]->GetCenter());
+    if (dis < clu->GetDelta()) {
+      clu->SetDep(Clus[i]);
+      clu->SetDelta(dis);
+    }
+  }
+
+  if (clu->GetDep() != nullptr) {
+    clu->GetDep()->addSuccessor(clu);
+  }
+}
+void SESAME::DPTree::adjust(int index) {
+  Clus[0]->SetDelta(DBL_MAX);
+  auto clu = Clus[index];
+  if (clu->GetDep() != nullptr && clu->GetDep()->GetRho() < clu->GetRho()) {
+    clu->GetDep()->removeSuccessor(clu);
+    clu->SetDelta(DBL_MAX);
+  }
+  int position = index;
+  double dis = 0;
+
+  if (index > 0) {
+    for (int i = index - 1; i >= 0; i--) {
+      if (clu->GetRho() > Clus[i]->GetRho()) {
+        if (Clus[i]->GetDelta() > Clus[i]->GetDis() - clu->GetDis()) {
+          dis = Clus[i]->getDisTo(clu);
+          if (dis < Clus[i]->GetDelta()) {
+            if (Clus[i]->GetDep() != nullptr) {
+              Clus[i]->GetDep()->removeSuccessor(Clus[i]);
+            }
+            Clus[i]->SetDep(clu);
+            clu->addSuccessor(Clus[i]);
+            Clus[i]->SetDelta(dis);
+          }
+        }
+        Clus[i + 1] = Clus[i];
+        Clus[i] = clu;
+        position = i;
+      } else {
+        break;
+      }
+    }
+  }
+  if (Clus[0] == clu) {
+    clu->SetDelta(DBL_MAX);
+  }
+  if (position != 0 && (clu->GetDep() == nullptr || clu->GetRho() > clu->GetDep()->GetRho())) {
+
+    clu->SetDelta(DBL_MAX);
+
+    computeDelta(position);
+  }
+  computeHeadDelta();
+}
+void SESAME::DPTree::computeHeadDelta() {
+  auto clu = Clus[0];
+  if (clu->GetDep() != nullptr) {
+    clu->GetDep()->removeSuccessor(clu);
+  }
+
+  double maxValue = 0;
+  double secondValue = 0;
+  for (int i = 1; i < size; i++) {
+    if (maxValue < Clus[i]->GetDelta()) {
+      secondValue = maxValue;
+      maxValue = Clus[i]->GetDelta();
+    } else if (secondValue < Clus[i]->GetDelta()) {
+      secondValue = Clus[i]->GetDelta();
+    }
+  }
+  if (maxValue > 3 * secondValue) {
+    clu->SetDelta(maxValue);
+  } else {
+    clu->SetDelta((maxValue + secondValue) / 2);
+  }
+}
+void SESAME::DPTree::computeDelta(int index) {
+  auto clu = Clus[index];
+  if (clu->GetDep() != nullptr) {
+    clu->GetDep()->removeSuccessor(clu);
+  }
+  clu->SetDelta(DBL_MAX);
+  if (index == 0) {
+    return;
+  }
+  double dis = 0;
+
+  for (int i = index - 1; i >= 0; i--) {
+    if (clu->GetDelta() > Clus[i]->GetDis() - clu->GetDis()) {
+      dis = clu->GetCenter()->getDisTo(Clus[i]->GetCenter());
+
+      if (dis < clu->GetDelta()) {
+        clu->SetDep(Clus[i]);
+        clu->SetDelta(dis);
+      }
+    }
+  }
+
+  if (clu->GetDep() != nullptr) {
+    clu->GetDep()->addSuccessor(clu);
+  }
+}
+void SESAME::DPTree::deleteInact(SESAME::OutPtr &outres, double minRho, double time) {
+  for (int i = size - 1; i > 0; i--) {
+
+    if (Clus[i]->GetRho() < minRho) {
+      auto cc = Clus[i];
+      Clus[i] = nullptr;
+      size--;
+      cc->SetActive(false);
+      cc->SetInactiveTime(time);
+      std::unordered_set<DPNodePtr> cells = cc->GetDep()->GetSucs();
+      cells.erase(cc);
+      cc->GetCluster()->remove(cc);
+      outres->insert(cc);
+    } else {
+      break;
+    }
+  }
+  if (size > 0 && Clus[0]->GetRho() < minRho) {
+    auto cc = Clus[0];
+    Clus[0] = nullptr;
+    size--;
+    cc->SetActive(false);
+    cc->SetInactiveTime(time);
+    cc->GetCluster()->remove(cc);
+    outres->insert(cc);
+  }
+}
+double SESAME::DPTree::computeAlpha(double minDelta) {
+  std::vector<double> deltas(size);
+  for (int i = 0; i < size; i++) {
+    deltas[i] = Clus[i]->GetDelta();
+  }
+  sort(deltas.begin(), deltas.end());
+  double delta1;
+  double delta2;
+  int m = 0;
+  int n = 0;
+  double avg;
+  double up = 0;
+  double down = 0;
+  int i = 0;
+  for (i = 0; i < size - 1 && deltas[i] < minDelta; i++) {
+    n++;
+    down += deltas[i];
+
+  }
+  delta1 = deltas[i - 1];
+  delta2 = deltas[i];
+  for (; i < size; i++) {
+    m++;
+    up += deltas[i];
+  }
+  avg = up + down;
+  avg = avg / (m + n);
+  up = up / m;
+  down = down / n;
+  double alpha = (up * (down - delta1) * (m * up + delta1))
+      / (avg * avg * (delta1 - up) * (n - 1) + (down - delta1) * up
+          * (m * up + delta1));
+  double alpha2 = ((delta2 - down) * up * (m * up - delta2))
+      / ((delta2 - down) * up * (m * up - delta2) + avg * avg
+          * (up - delta2) * (n + 1));
+  if (alpha < alpha2) {
+    return (alpha + alpha2) / 2;
+  } else {
+    return 0;
+  }
+}
+double SESAME::DPTree::adjustMinDelta(double alpha) {
+  if (size < 2) {
+    return 0;
+  }
+  std::vector<double> deltas(size);
+  for (int i = 0; i < size; i++) {
+    deltas[i] = Clus[i]->GetDelta();
+  }
+  sort(deltas.begin(), deltas.end());
+  int m = 0;
+  int n = 0;
+  double avg = 0;
+  double up = 0;
+  double down = 0;
+  up = deltas[size - 1];
+  for (int i = 0; i < size - 1; i++) {
+    down += deltas[i];
+  }
+  n = size - 1;
+
+  m = 1;
+  avg = (up + down) / (m + n);
+  double score = fun(alpha, up / m, down / n, avg);
+  int index = size - 2;
+  up += deltas[index];
+  m++;
+  down -= deltas[index];
+  n--;
+  double scoredown = fun(alpha, up / m, down / n, avg);
+  while (score > scoredown && index > 0) {
+    score = scoredown;
+    index--;
+    up += deltas[index];
+    m++;
+    down -= deltas[index];
+    n--;
+    scoredown = fun(alpha, up / m, down / n, avg);
+  }
+  return (deltas[index + 1] + deltas[index]) / 2;
+}
+double SESAME::DPTree::fun(double alpha, double upavg, double downavg, double avg) {
+  return alpha * (avg / upavg) + (1 - alpha) * (downavg / avg);
+}
+void SESAME::DPTree::adjustCluster(std::unordered_set<SESAME::ClusterPtr> &clusters) {
+  std::vector<ClusterPtr> set;//
+
+  if (Clus[0] == nullptr) {
+    SESAME_DEBUG(size);
+    SESAME_DEBUG("there is no cluser-cell, r is very small");
+    SESAME_DEBUG("please adjust your r parameter larger");
+  } else if (Clus[0]->GetCluster() == nullptr) {// there is new cluster center appearing
+    auto cluster = std::make_shared<Cluster>(cluLabel++);
+    clusters.insert(cluster);
+    cluster->add(Clus[0]);
+    Clus[0]->SetCluster(cluster);
+    set.push_back(cluster);
+  } else {
+    set.push_back(Clus[0]->GetCluster());
+  }
+
+  for (int i = 1; i < size; i++) {
+    if (Clus[i]->GetDelta() >= minDelta) {// clusters split or new cluster
+      // appears
+      if (Clus[i]->GetDep() == nullptr) {
+        SESAME_DEBUG("error contains null dep");
+      }
+      if (Clus[i]->GetCluster() == Clus[i]->GetDep()->GetCluster()) {// clusters split
+        auto c1 = Clus[i]->GetCluster();
+        auto c2 = std::make_shared<Cluster>(cluLabel++);
+        if (c1 != nullptr) {
+          c1->remove(Clus[i]);
+        }
+        c2->add(Clus[i]);
+        Clus[i]->SetCluster(c2);
+        clusters.insert(c2);
+        set.push_back(c2);
+      }
+      if (Clus[i]->GetCluster() == nullptr) {// new cluster appears
+        auto cluster = std::make_shared<Cluster>(cluLabel++);
+        clusters.insert(cluster);
+        cluster->add(Clus[i]);
+        Clus[i]->SetCluster(cluster);
+        set.push_back(cluster);
+      } else {
+        bool flag = false;
+        for(auto c : set){
+          if(c->GetLabel() == Clus[i]->GetCluster()->GetLabel()) flag = true;
+        }
+        if (flag) { // this is because when
+          // minDelta become smaller
+          Clus[i]->GetCluster()->remove(Clus[i]);
+          auto cluster = std::make_shared<Cluster>(cluLabel++);
+          clusters.insert(cluster);
+          cluster->add(Clus[i]);
+          Clus[i]->SetCluster(cluster);
+          set.push_back(cluster);
+        } else {
+          set.push_back(Clus[i]->GetCluster());
+        }
+      }
+
+    } else {
+      if (Clus[i]->GetDep() == nullptr) {
+        SESAME_DEBUG("error contains null dep");
+      }
+      if (Clus[i]->GetCluster() != Clus[i]->GetDep()->GetCluster()) {
+        auto c1 = Clus[i]->GetCluster();
+        auto c2 = Clus[i]->GetDep()->GetCluster();
+        if (c1 != nullptr) {
+          c1->remove(Clus[i]);
+        }
+        c2->add(Clus[i]);
+        Clus[i]->SetCluster(c2);
+      }
+    }
+  }
+}
+double SESAME::DPTree::GetLastTime()    {
+  return lastTime;
+}
+void SESAME::DPTree::SetLastTime(double last_time) {
+  lastTime = last_time;
+}
+int SESAME::DPTree::GetSize()    {
+  return size;
+}
+void SESAME::DPTree::SetSize(int size) {
+  DPTree::size = size;
+}
+int SESAME::DPTree::GetNum()    {
+  return num;
+}
+void SESAME::DPTree::SetNum(int num) {
+  DPTree::num = num;
+}
+   std::vector<SESAME::DPNodePtr> &SESAME::DPTree::GetClus()    {
+  return Clus;
+}
+void SESAME::DPTree::SetClus(   std::vector<SESAME::DPNodePtr> &clus) {
+  Clus = clus;
+}
+double SESAME::DPTree::GetA()    {
+  return a;
+}
+void SESAME::DPTree::SetA(double a) {
+  DPTree::a = a;
+}
+double SESAME::DPTree::GetLamd()    {
+  return lamd;
+}
+void SESAME::DPTree::SetLamd(double lamd) {
+  DPTree::lamd = lamd;
+}
+double SESAME::DPTree::GetCluR()    {
+  return CluR;
+}
+void SESAME::DPTree::SetCluR(double clu_r) {
+  CluR = clu_r;
+}
+int SESAME::DPTree::GetCluLabel()    {
+  return cluLabel;
+}
+void SESAME::DPTree::SetCluLabel(int clu_label) {
+  cluLabel = clu_label;
+}
+double SESAME::DPTree::GetMinDelta()    {
+  return minDelta;
+}
+void SESAME::DPTree::SetMinDelta(double min_delta) {
+  minDelta = min_delta;
+}
diff --git a/src/Algorithm/DataStructure/DataStructureFactory.cpp b/src/Algorithm/DataStructure/DataStructureFactory.cpp
index bf973964..58a6a427 100644
--- a/src/Algorithm/DataStructure/DataStructureFactory.cpp
+++ b/src/Algorithm/DataStructure/DataStructureFactory.cpp
@@ -53,6 +53,28 @@ SESAME::CFTreePtr SESAME::DataStructureFactory::createCFTree() {
 SESAME::NodePtr SESAME::DataStructureFactory::createNode() {
   return std::make_shared<SESAME::CFNode>();
 }
+SESAME::DPNodePtr SESAME::DataStructureFactory::createDPNode() {
+  return std::make_shared<SESAME::DPNode>();
+}
+SESAME::DPNodePtr SESAME::DataStructureFactory::createDPNode(SESAME::PointPtr p, double time) {
+  return std::make_shared<SESAME::DPNode>(p, time);
+}
+SESAME::OutPtr SESAME::DataStructureFactory::createOutlierReservoir() {
+  return std::make_shared<SESAME::OutlierReservoir>();
+}
+SESAME::CachePtr SESAME::DataStructureFactory::creatCache() {
+  return std::make_shared<SESAME::Cache>();
+}
+SESAME::OutPtr SESAME::DataStructureFactory::createOutlierReservoir(double r, double a, double lamd) {
+  return std::make_shared<SESAME::OutlierReservoir>(r, a, lamd);
+}
+SESAME::CachePtr SESAME::DataStructureFactory::creatCache(int num, double a, double lamd, double r) {
+  return std::make_shared<SESAME::Cache>(num, a, lamd, r);
+}
+SESAME::DPTreePtr SESAME::DataStructureFactory::createDPTree(int num, double r) {
+  return std::make_shared<SESAME::DPTree>(num, r);
+}
+
 SESAME::MicroClusterPairPtr SESAME::DataStructureFactory::createMicroClusterPair(MicroClusterPtr microCluster1,
                                                                                  MicroClusterPtr microCluster2){
   return std::make_shared<SESAME::MicroClusterPair>(microCluster1,microCluster2);
@@ -67,4 +89,4 @@ SESAME::AdjustedWeightPtr SESAME::DataStructureFactory::createAdjustedWeight(dou
 }
 void SESAME::DataStructureFactory::clearAdjustedWeight(SESAME::AdjustedWeightPtr adjustedWeight){
   adjustedWeight.reset();
-}
\ No newline at end of file
+}
diff --git a/src/Algorithm/DataStructure/OutlierResevoir.cpp b/src/Algorithm/DataStructure/OutlierResevoir.cpp
new file mode 100644
index 00000000..37b4cd1a
--- /dev/null
+++ b/src/Algorithm/DataStructure/OutlierResevoir.cpp
@@ -0,0 +1,98 @@
+//
+// Created by tuidan on 2021/9/9.
+//
+
+#include <Algorithm/DataStructure/OutlierReservoir.hpp>
+#include <Algorithm/DataStructure/DataStructureFactory.hpp>
+#include <cfloat>
+#include <cmath>
+
+
+/**
+ * OutlierReservoir
+ */
+SESAME::OutlierReservoir::OutlierReservoir() = default;
+SESAME::OutlierReservoir::~OutlierReservoir() = default;
+double SESAME::OutlierReservoir::GetR()  {
+  return r;
+}
+void SESAME::OutlierReservoir::SetR(double r) {
+  OutlierReservoir::r = r;
+}
+double SESAME::OutlierReservoir::GetTimeGap()  {
+  return timeGap;
+}
+void SESAME::OutlierReservoir::SetTimeGap(double time_gap) {
+  timeGap = time_gap;
+}
+long SESAME::OutlierReservoir::GetLastDelTime()  {
+  return lastDelTime;
+}
+void SESAME::OutlierReservoir::SetLastDelTime(long last_del_time) {
+  lastDelTime = last_del_time;
+}
+double SESAME::OutlierReservoir::GetA()  {
+  return a;
+}
+void SESAME::OutlierReservoir::SetA(double a) {
+  OutlierReservoir::a = a;
+}
+double SESAME::OutlierReservoir::GetLamd()  {
+  return lamd;
+}
+void SESAME::OutlierReservoir::SetLamd(double lamd) {
+  OutlierReservoir::lamd = lamd;
+}
+ std::unordered_set<SESAME::DPNodePtr> &SESAME::OutlierReservoir::GetOutliers()  {
+  return outliers;
+}
+void SESAME::OutlierReservoir::SetOutliers( std::unordered_set<SESAME::DPNodePtr> &outliers) {
+  OutlierReservoir::outliers = outliers;
+}
+SESAME::OutlierReservoir::OutlierReservoir(double r, double a, double lamd) {
+  this->r = r;
+  this->a = a;
+  this->lamd = lamd;
+}
+void SESAME::OutlierReservoir::setTimeGap(double timeGap) {
+  this->timeGap = timeGap;
+}
+void SESAME::OutlierReservoir::insert(SESAME::DPNodePtr &c) {
+  c->SetDelta(DBL_MAX);
+  if(c->GetDep() != nullptr){
+    std::unordered_set<SESAME::DPNodePtr> successors = c->GetDep()->GetSucs();
+    successors.erase(c);
+  }
+  this->outliers.insert(c);
+}
+SESAME::DPNodePtr SESAME::OutlierReservoir::insert(SESAME::PointPtr &p, double time) {
+  double dis = 0;
+  auto minDis = DBL_MAX;
+  SESAME::DPNodePtr nn = nullptr;
+  for(auto it = this->outliers.begin(); it != this->outliers.end();){
+    if(time - double(it->get()->GetLastTime()) > this->timeGap) {
+      this->outliers.erase(it++);
+      continue;
+    } else {
+      dis = p->getDisTo(it->get()->GetCenter());
+      if (dis < minDis) {
+        minDis = dis;
+        nn = it->get()->copy();
+      }
+      it++;
+    }
+  }
+
+  if (nn == nullptr || minDis > r) {
+    SESAME::DPNodePtr c = std::make_shared<SESAME::DPNode>(p, time);
+    this->outliers.insert(c);
+    return c;
+  } else {
+    double coef = pow(a, lamd * (time - nn->GetLastTime()));
+    nn->add(coef, time);
+    return nn;
+  }
+}
+void SESAME::OutlierReservoir::remove(SESAME::DPNodePtr &nn) {
+  this->outliers.erase(nn);
+}
diff --git a/src/Algorithm/DataStructure/Point.cpp b/src/Algorithm/DataStructure/Point.cpp
index 6a558074..6f72a8cd 100644
--- a/src/Algorithm/DataStructure/Point.cpp
+++ b/src/Algorithm/DataStructure/Point.cpp
@@ -4,6 +4,7 @@
 // Created by Shuhao Zhang on 19/07/2021.
 //
 
+#include <cmath>
 #include <Algorithm/DataStructure/Point.hpp>
 
 SESAME::Point::Point() {
@@ -77,3 +78,16 @@ int SESAME::Point::getFeatureLength() {
   return (int)this->feature->size();
 }
 
+double SESAME::Point::getDisTo(SESAME::PointPtr p) {
+  double distance = 0;
+  for(int i = 0; i < this->dimension; i++) {
+    distance = distance + pow(p->getFeatureItem(i) - this->getFeatureItem(i), 2);
+  }
+  return sqrt(distance);
+}
+double SESAME::Point::getMinDist() const {
+  return minDist;
+}
+void SESAME::Point::setMinDist(double min_dist) {
+  minDist = min_dist;
+}
diff --git a/src/Algorithm/EDMStream.cpp b/src/Algorithm/EDMStream.cpp
new file mode 100644
index 00000000..db10abfe
--- /dev/null
+++ b/src/Algorithm/EDMStream.cpp
@@ -0,0 +1,145 @@
+//
+// Created by tuidan on 2021/9/1.
+//
+
+#include <Algorithm/EDMStream.hpp>
+
+SESAME::EDMStream::EDMStream(param_t &cmd_params) {
+  this->EDMParam.pointNumber = cmd_params.pointNumber;
+  this->EDMParam.dimension = cmd_params.dimension;
+  this->EDMParam.a = cmd_params.a;
+  this->EDMParam.lamda = cmd_params.lambda;
+  this->EDMParam.beta = cmd_params.beta;
+  this->EDMParam.cacheNum = cmd_params.cacheNum;
+  this->EDMParam.radius = cmd_params.radius;
+  this->EDMParam.minDelta = cmd_params.delta;
+  this->EDMParam.opt = cmd_params.opt;
+}
+SESAME::EDMStream::~EDMStream(){};
+void SESAME::EDMStream::Initilize() {
+  this->alpha = 0;
+  this->cache = SESAME::DataStructureFactory::creatCache(this->EDMParam.cacheNum, this->EDMParam.a,
+                                                         this->EDMParam.lamda, this->EDMParam.radius);
+  this->outres = SESAME::DataStructureFactory::createOutlierReservoir(this->EDMParam.radius,
+                                                                      this->EDMParam.a, this->EDMParam.lamda);
+  this->dpTree = SESAME::DataStructureFactory::createDPTree(this->actCluMaxNum,
+                                                            this->EDMParam.radius);
+  this->dpTree->SetMinDelta(this->EDMParam.minDelta);
+}
+
+void SESAME::EDMStream::setMinDelta(double minDelta) {
+  this->EDMParam.minDelta = minDelta;
+  this->dpTree->SetMinDelta(minDelta);
+}
+
+void SESAME::EDMStream::InitDP(double time) {
+  cache->compDeltaRho(time);
+  SESAME_DEBUG("beta = " << this->EDMParam.beta);
+  this->minRho = this->EDMParam.beta / (1 - pow(this->EDMParam.a, this->EDMParam.lamda));
+  SESAME_DEBUG("minRho = " << this->minRho);
+
+  this->deltaT = (log(1 - pow(this->EDMParam.a, this->EDMParam.lamda)) / log(this->EDMParam.a) -
+      log(this->EDMParam.beta) / log(this->EDMParam.a))/ this->EDMParam.lamda;
+  //		double deltaT = 100;
+  SESAME_DEBUG("deltaT = " << this->deltaT);
+  outres->setTimeGap(this->deltaT);
+  cache->getDPTree(this->minRho, this->EDMParam.minDelta, dpTree, outres, clusters);
+  SESAME_DEBUG("dpTree size = " << dpTree->GetSize());
+  dpTree->SetLastTime(time);
+}
+
+SESAME::DPNodePtr SESAME::EDMStream::streamProcess(SESAME::PointPtr p, int opt, double time) {
+  double coef = pow(this->EDMParam.a, this->EDMParam.lamda * (time - dpTree->GetLastTime()));
+  dpTree->SetLastTime(time);
+  auto nn = dpTree->findNN(p, coef, opt, time);
+  if (nn == nullptr || nn->GetDis() > dpTree->GetCluR()) {
+
+    nn = outres->insert(p, time);
+    if (nn->GetRho() > this->minRho) {
+      outres->remove(nn);
+      dpTree->insert(nn, opt);
+    }
+  }
+
+  dpTree->deleteInact(outres, this->minRho, time);
+  return nn;
+}
+double SESAME::EDMStream::computeAlpha() {
+  return dpTree->computeAlpha(this->EDMParam.minDelta);
+}
+double SESAME::EDMStream::adjustMinDelta() {
+  return dpTree->adjustMinDelta(this->alpha);
+}
+void SESAME::EDMStream::delCluster() {
+  for(auto it = this->clusters.begin(); it != this->clusters.end();) {
+    auto cluster = it->get();
+    if(cluster->GetCells().begin() == cluster->GetCells().end()){
+      this->clusters.erase(it++);
+    } else {
+      it++;
+    }
+  }
+}
+
+SESAME::DPNodePtr SESAME::EDMStream::retrive(SESAME::PointPtr p, int opt, double time) {
+  SESAME::PointPtr curP = p;
+  if (!this->EDMParam.isInit) {
+    auto cc = cache->add(curP, time);
+    if (cache->isFull()) {
+      // draw decision graph
+      InitDP(time);
+      this->alpha = computeAlpha(); //TODO: what does it mean?
+      SESAME_DEBUG("alpha = " << this->alpha);
+      this->EDMParam.isInit = true;
+    }
+    return cc;
+  } else {
+    auto nn = streamProcess(curP, opt, time);
+
+    this->dpTree->adjustCluster(clusters);
+    delCluster();
+    return nn;
+  }
+}
+
+void CountNode(const SESAME::DPNodePtr &node, int &num) {
+  num = num + 1;
+  if(!node->GetSucs().empty()) {
+    for(const SESAME::DPNodePtr &el : node->GetSucs()) {
+      CountNode(el, num);
+    }
+  }
+}
+void SESAME::EDMStream::runOnlineClustering(SESAME::PointPtr input) {
+  double curTime = (input->getIndex() + 1) / 10;
+  auto c = retrive(input, this->EDMParam.opt, curTime);
+  if(input->getIndex() % 100 == 0 && this->EDMParam.isInit) {
+    setMinDelta(adjustMinDelta());
+    this->dpTree->adjustCluster(this->clusters);
+    this->delCluster();
+  }
+}
+void SESAME::EDMStream::runOfflineClustering(SESAME::DataSinkPtr sinkPtr) {
+  SESAME_DEBUG("Cluster number: "<< this->clusters.size());
+  int i = 0;
+  int num = 0;
+  int sum = 0;
+  for(auto it = this->clusters.begin(); it != this->clusters.end(); ++it) {
+    i++;
+    sum += num;
+    num = 0;
+    std::unordered_set<DPNodePtr> cells = it->get()->GetCells();
+    for(auto cell = cells.begin(); cell != cells.end(); ++cell) {
+      CountNode(cell->get()->copy(), num);
+      PointPtr center = cell->get()->GetCenter();
+      sinkPtr->put(center->copy());
+    }
+  }
+  for(auto out = this->outres->GetOutliers().begin(); out != this->outres->GetOutliers().end(); ++ out) {
+      i++;
+      sum += num;
+      num = 0;
+      CountNode(out->get()->copy(), num);
+   }
+}
+
diff --git a/src/Utils/BenchmarkUtils.cpp b/src/Utils/BenchmarkUtils.cpp
index e6ab0a27..eb4c7369 100644
--- a/src/Utils/BenchmarkUtils.cpp
+++ b/src/Utils/BenchmarkUtils.cpp
@@ -125,7 +125,7 @@ void BenchmarkUtils::parseArgs(int argc, char **argv, param_t &cmd_params) {
  * @Return:
  */
 void BenchmarkUtils::defaultParam(param_t &cmd_params) {
-  cmd_params.pointNumber = 1000;
+  cmd_params.pointNumber = 15120; // number of the data points in the dataset, use the whole dataset to run benchmark
   cmd_params.seed = 10;
   cmd_params.clusterNumber = 10;
   cmd_params.dimension = 54;
@@ -143,13 +143,24 @@ void BenchmarkUtils::defaultParam(param_t &cmd_params) {
   cmd_params.minPoints = 10;
   cmd_params.epsilon = 50;
   cmd_params.base = 2;
-  cmd_params.lambda = 1.8;
+  cmd_params.lambda = 1.8; // 1.8
   cmd_params.mu = 7;
-  cmd_params.beta = 5;
+  cmd_params.beta = 5; // 5
+
+  // EDMStream
+  cmd_params.a = 0.998;
+  cmd_params.cacheNum = 1000;
+  cmd_params.radius = 250;
+  cmd_params.lambda = 1;
+  cmd_params.delta = 1500;
+  cmd_params.beta = 0.0021;
+  cmd_params.opt = 2;
+
+
   cmd_params.inputPath = std::filesystem::current_path().generic_string() + "/datasets/CoverType.txt";
   SESAME_INFO("Default Input Data Directory: " + cmd_params.inputPath);
   cmd_params.outputPath = "results.txt";
-  cmd_params.algoType = SESAME::BirchType;
+  cmd_params.algoType = SESAME::EDMStreamType;
   cmd_params.evaluateType = SESAME::euclideanCostType;
 }
 


Test patch:
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index dcbb5001..4967eca2 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -3,6 +3,7 @@ add_executable(Google_Tests_run
         SystemTest/CluStreamTest.cpp
         SystemTest/StreamKMTest.cpp
         SystemTest/BirchTest.cpp
+        SystemTest/EDMStreamTest.cpp
         SystemTest/DenStreamTest.cpp
         SystemTest/DBStreamTest.cpp
         )
diff --git a/test/SystemTest/EDMStreamTest.cpp b/test/SystemTest/EDMStreamTest.cpp
new file mode 100644
index 00000000..23053991
--- /dev/null
+++ b/test/SystemTest/EDMStreamTest.cpp
@@ -0,0 +1,50 @@
+//
+// Created by tuidan on 2021/9/15.
+//
+
+#include <filesystem>
+#include <gtest/gtest.h>
+#include <Utils/BenchmarkUtils.hpp>
+#include <Utils/Logger.hpp>
+#include <Sources/DataSourceFactory.hpp>
+#include <Sinks/DataSinkFactory.hpp>
+#include <Algorithm/AlgorithmFactory.hpp>
+
+TEST(SystemTest, EDMStreamTest) {
+  //Setup Logs.
+  setupLogging("benchmark.log", LOG_DEBUG);
+
+  //Parse parameters.
+  param_t cmd_params;
+  cmd_params.pointNumber = 3000;
+  cmd_params.dimension = 54;
+  cmd_params.a = 0.998;
+  cmd_params.cacheNum = 500;
+  cmd_params.radius = 250;
+  cmd_params.lambda = 1;
+  cmd_params.delta = 1500;
+  cmd_params.beta = 0.0021;
+  cmd_params.opt = 2;
+
+
+  cmd_params.inputPath = std::filesystem::current_path().generic_string() + "/datasets/CoverType.txt";
+  cmd_params.outputPath = "results.txt";
+  cmd_params.algoType = SESAME::EDMStreamType;
+
+  std::vector<SESAME::PointPtr> input;
+  std::vector<SESAME::PointPtr> results;
+
+  //Create Spout.
+  SESAME::DataSourcePtr sourcePtr = SESAME::DataSourceFactory::create();
+  //Directly load data from file. TODO: configure it to load from external sensors, e.g., HTTP.
+  BenchmarkUtils::loadData(cmd_params, sourcePtr);
+
+  //Create Sink.
+  SESAME::DataSinkPtr sinkPtr = SESAME::DataSinkFactory::create();
+
+  //Create Algorithm.
+  SESAME::AlgorithmPtr algoPtr = SESAME::AlgorithmFactory::create(cmd_params);
+
+  //Run algorithm producing results.
+  BenchmarkUtils::runBenchmark(cmd_params, sourcePtr, sinkPtr, algoPtr);
+}
\ No newline at end of file