Skip to content

Commit ecaa42e

Browse files
tuidantuidan
authored
EDM (#64)
1 parent 3d882f8 commit ecaa42e

22 files changed

Lines changed: 1640 additions & 6 deletions

‎include/Algorithm/Algorithm.hpp‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
using namespace std;
1515
namespace SESAME {
1616

17-
enum algoType { BirchType, StreamKMeansType, CluStreamType, DenStreamType, DBStreamType};
17+
enum algoType { BirchType, StreamKMeansType, CluStreamType, DenStreamType, DBStreamType, EDMStreamType};
1818

1919
class Algorithm;
2020
typedef std::shared_ptr<Algorithm> AlgorithmPtr;

‎include/Algorithm/DataStructure/Cache.hpp‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
//
2+
// Created by tuidan on 2021/9/9.
3+
//
4+
5+
#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_CACHE_HPP_
6+
#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_CACHE_HPP_
7+
#include <Algorithm/DataStructure/DPNode.hpp>
8+
#include <Algorithm/DataStructure/OutlierReservoir.hpp>
9+
#include <Algorithm/DataStructure/DPTree.hpp>
10+
#include <vector>
11+
#include <iostream>
12+
#include <memory>
13+
#include <unordered_set>
14+
15+
namespace SESAME {
16+
17+
// define the share point of the class object
18+
class Cache;
19+
typedef std::shared_ptr<Cache> CachePtr;
20+
21+
class Cache {
22+
private:
23+
int num;
24+
int size;
25+
double a;
26+
double lamd;
27+
double r;
28+
std::vector<DPNodePtr> buffer;
29+
std::vector<DPNodePtr> clus;
30+
int pnum;
31+
public:
32+
Cache();
33+
~Cache();
34+
int GetNum() ;
35+
void SetNum(int num);
36+
int GetSize() ;
37+
void SetSize(int size);
38+
double GetA() ;
39+
void SetA(double a);
40+
double GetLamd() ;
41+
void SetLamd(double lamd);
42+
double GetR() ;
43+
void SetR(double r);
44+
std::vector<DPNodePtr> &GetBuffer() ;
45+
void SetBuffer( std::vector<DPNodePtr> &buffer);
46+
std::vector<DPNodePtr> &GetClus() ;
47+
void SetClus( std::vector<DPNodePtr> &clus);
48+
int GetPnum() ;
49+
void SetPnum(int pnum);
50+
Cache(int num, double a, double lamd, double r);
51+
DPNodePtr add(PointPtr &p, double startTime);
52+
bool isFull();
53+
void compDeltaRho(double time);
54+
void getDPTree(double minRho, double minDelta, DPTreePtr &dpTree,
55+
OutPtr &outs, std::unordered_set<ClusterPtr> &clusters);
56+
//void outputBuffer(String outpath, double minRho)
57+
};
58+
}
59+
#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_CACHE_HPP_

‎include/Algorithm/DataStructure/DPNode.hpp‎

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
//
2+
// Created by tuidan on 2021/9/9.
3+
//
4+
5+
#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPNODE_HPP_
6+
#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPNODE_HPP_
7+
#include <vector>
8+
#include <iostream>
9+
#include <memory>
10+
#include <unordered_set>
11+
#include <Algorithm/DataStructure/Point.hpp>
12+
namespace SESAME {
13+
class DPNode;
14+
class Cluster;
15+
typedef std::shared_ptr<DPNode> DPNodePtr;
16+
typedef std::shared_ptr<Cluster> ClusterPtr;
17+
18+
class Cluster {
19+
private:
20+
int label;
21+
std::unordered_set<DPNodePtr> cells;
22+
23+
public:
24+
explicit Cluster();
25+
explicit Cluster(int label);
26+
void add(DPNodePtr &node);
27+
void remove(DPNodePtr &node);
28+
int GetLabel() ;
29+
void SetLabel(int label);
30+
[[nodiscard]] std::unordered_set<DPNodePtr> &GetCells() ;
31+
void SetCells(std::unordered_set<DPNodePtr> &cells);
32+
};
33+
class DPNode {
34+
private:
35+
int cid;
36+
int Cid;
37+
int num;
38+
double rho;
39+
double delta;
40+
SESAME::DPNodePtr dep; //TODO: father
41+
SESAME::PointPtr center;
42+
double lastTime;
43+
bool active;
44+
std::unordered_set<DPNodePtr> sucs; //TODO: children
45+
SESAME::ClusterPtr cluster;
46+
// public double sumDelta;
47+
// public int sucNum;
48+
double inactiveTime;
49+
50+
/**
51+
* we will use dis to quickly update the delta of CluCell
52+
*/
53+
double dis;
54+
public:
55+
56+
DPNode();
57+
~DPNode();
58+
DPNode(SESAME::PointPtr &p, double time);
59+
[[nodiscard]] int GetId() ;
60+
void SetId(int id);
61+
[[nodiscard]] int GetCId() ;
62+
void SetCId(int Cid);
63+
[[nodiscard]] int GetNum() ;
64+
void SetNum(int num);
65+
[[nodiscard]] double GetRho() ;
66+
void SetRho(double rho);
67+
[[nodiscard]] double GetDelta() ;
68+
void SetDelta(double delta);
69+
[[nodiscard]] DPNodePtr &GetDep() ;
70+
void SetDep(DPNodePtr &dep);
71+
[[nodiscard]] PointPtr &GetCenter() ;
72+
void SetCenter(PointPtr &center);
73+
[[nodiscard]] double GetLastTime() ;
74+
void SetLastTime(double last_time);
75+
[[nodiscard]] bool IsActive() ;
76+
void SetActive(bool active);
77+
[[nodiscard]] std::unordered_set<SESAME::DPNodePtr> &GetSucs() ;
78+
void SetSucs(std::unordered_set<SESAME::DPNodePtr> &sucs);
79+
[[nodiscard]] ClusterPtr &GetCluster() ;
80+
void SetCluster(SESAME::ClusterPtr &cluster);
81+
[[nodiscard]] double GetInactiveTime() ;
82+
void SetInactiveTime(double inactive_time);
83+
[[nodiscard]] double GetDis() ;
84+
void SetDis(double dis);
85+
SESAME::DPNodePtr copy();
86+
87+
88+
void insert(double startTime);
89+
void add(double coef, double startTime);
90+
double getDisTo(SESAME::DPNodePtr &node);
91+
void removeSuccessor(SESAME::DPNodePtr &node);
92+
bool hasSuccessor();
93+
94+
void addSuccessor(DPNodePtr &node);
95+
};
96+
97+
}
98+
#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPNODE_HPP_

‎include/Algorithm/DataStructure/DPTree.hpp‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
//
2+
// Created by tuidan on 2021/9/1.
3+
//
4+
5+
#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPTREE_HPP_
6+
#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPTREE_HPP_
7+
#include <iostream>
8+
#include <memory>
9+
#include <vector>
10+
#include <Algorithm/DataStructure/FeatureVector.hpp>
11+
#include <Algorithm/DataStructure/Point.hpp>
12+
#include <Algorithm/DataStructure/DPNode.hpp>
13+
#include <Algorithm/DataStructure/OutlierReservoir.hpp>
14+
namespace SESAME {
15+
16+
// define the share point of the class object
17+
class DPTree;
18+
typedef std::shared_ptr<DPTree> DPTreePtr;
19+
20+
class DPTree {
21+
private:
22+
double lastTime;
23+
int size;
24+
int num;
25+
std::vector<SESAME::DPNodePtr> Clus;
26+
27+
double a;
28+
double lamd;
29+
double CluR;
30+
31+
int cluLabel;
32+
public:
33+
double GetLastTime() ;
34+
void SetLastTime(double last_time);
35+
int GetSize() ;
36+
void SetSize(int size);
37+
int GetNum() ;
38+
void SetNum(int num);
39+
std::vector<SESAME::DPNodePtr> &GetClus() ;
40+
void SetClus( std::vector<SESAME::DPNodePtr> &clus);
41+
double GetA() ;
42+
void SetA(double a);
43+
double GetLamd() ;
44+
void SetLamd(double lamd);
45+
double GetCluR() ;
46+
void SetCluR(double clu_r);
47+
int GetCluLabel() ;
48+
void SetCluLabel(int clu_label);
49+
double GetMinDelta() ;
50+
void SetMinDelta(double min_delta);
51+
private:
52+
double minDelta;
53+
public:
54+
DPTree();
55+
~DPTree();
56+
DPTree(int num, double CluR);
57+
void insert(SESAME::DPNodePtr &cc, int opt);
58+
void init(std::vector<SESAME::DPNodePtr> &clus, int size, double minRho, double minDelta,
59+
SESAME::OutPtr &outs, std::unordered_set<ClusterPtr> &clusters);
60+
SESAME::DPNodePtr findNN(PointPtr p, double coef, int opt, double time);
61+
void adjustNoDelta(int index);
62+
void adjustNoOpt(int index);
63+
void computeDeltaNoOpt(int index);
64+
void adjustOpt1(int index);
65+
void computeDeltaF1(int index);
66+
void adjust(int index);
67+
void computeHeadDelta();
68+
void computeDelta(int index);
69+
void deleteInact(SESAME::OutPtr &outres, double minRho, double time);
70+
double computeAlpha(double minDelta);
71+
double adjustMinDelta(double alpha);
72+
//double djustMinDelta(double alpha, double minDelta);
73+
double fun(double alpha, double upavg, double downavg, double avg);
74+
// bool check(SESAME::OutPtr outres);
75+
//void check(std::vector<SESAME::ClusterPtr> clusters);
76+
void adjustCluster(std::unordered_set<SESAME::ClusterPtr> &clusters);
77+
78+
79+
};
80+
81+
82+
83+
84+
}
85+
#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_DPTREE_HPP_

‎include/Algorithm/DataStructure/DataStructureFactory.hpp‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,10 @@
1212
#include <Algorithm/DataStructure/MicroCluster.hpp>
1313
#include <Algorithm/DataStructure/Snapshot.hpp>
1414
#include <Algorithm/DataStructure/CFTree.hpp>
15+
#include <Algorithm/DataStructure/DPTree.hpp>
16+
#include <Algorithm/DataStructure/DPNode.hpp>
17+
#include <Algorithm/DataStructure/OutlierReservoir.hpp>
18+
#include <Algorithm/DataStructure/Cache.hpp>
1519
#include <Algorithm/DataStructure/FeatureVector.hpp>
1620
#include <Algorithm/DataStructure/WeightedAdjacencyList.hpp>
1721
namespace SESAME {
@@ -34,6 +38,15 @@ class DataStructureFactory {
3438
static void clearSnapshot(SnapshotPtr snapshot);
3539
static CFTreePtr createCFTree();
3640
static NodePtr createNode();
41+
//EDMStream
42+
static DPTreePtr createDPTree(int num, double r);
43+
static DPNodePtr createDPNode();
44+
static DPNodePtr createDPNode(SESAME::PointPtr p, double time);
45+
static CachePtr creatCache();
46+
static CachePtr creatCache(int num, double a, double lamd, double r);
47+
static OutPtr createOutlierReservoir();
48+
static OutPtr createOutlierReservoir(double r, double a, double lamd);
49+
3750
static MicroClusterPairPtr createMicroClusterPair(MicroClusterPtr microCluster1,MicroClusterPtr microCluster2);
3851
static void clearMicroClusterPair(MicroClusterPairPtr microClusterPair);
3952
static AdjustedWeightPtr createAdjustedWeight(double weight, clock_t pointTime);

‎include/Algorithm/DataStructure/OutlierReservoir.hpp‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
//
2+
// Created by tuidan on 2021/9/9.
3+
//
4+
5+
#ifndef SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_OUTLIERRESERVOIR_HPP_
6+
#define SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_OUTLIERRESERVOIR_HPP_
7+
#include <Algorithm/DataStructure/DPNode.hpp>
8+
#include <vector>
9+
#include <iostream>
10+
#include <memory>
11+
#include <unordered_set>
12+
13+
namespace SESAME {
14+
15+
class OutlierReservoir;
16+
typedef std::shared_ptr<OutlierReservoir> OutPtr;
17+
class OutlierReservoir {
18+
private:
19+
double r;
20+
double timeGap;
21+
long lastDelTime;
22+
23+
double a;
24+
double lamd;
25+
26+
std::unordered_set<DPNodePtr> outliers;
27+
28+
public:
29+
[[nodiscard]] double GetR() ;
30+
void SetR(double r);
31+
[[nodiscard]] double GetTimeGap() ;
32+
void SetTimeGap(double time_gap);
33+
[[nodiscard]] long GetLastDelTime() ;
34+
void SetLastDelTime(long last_del_time);
35+
[[nodiscard]] double GetA() ;
36+
void SetA(double a);
37+
[[nodiscard]] double GetLamd() ;
38+
void SetLamd(double lamd);
39+
[[nodiscard]] std::unordered_set<SESAME::DPNodePtr> &GetOutliers() ;
40+
void SetOutliers( std::unordered_set<SESAME::DPNodePtr> &outliers);
41+
OutlierReservoir();
42+
~OutlierReservoir();
43+
OutlierReservoir(double r, double a, double lamd);
44+
45+
void setTimeGap(double timeGap);
46+
47+
void insert(SESAME::DPNodePtr &c);
48+
49+
SESAME::DPNodePtr insert(SESAME::PointPtr &p, double time);
50+
51+
void remove(SESAME::DPNodePtr &nn);
52+
};
53+
54+
}
55+
#endif //SESAME_INCLUDE_ALGORITHM_DATASTRUCTURE_OUTLIERRESERVOIR_HPP_

‎include/Algorithm/DataStructure/Point.hpp‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,9 @@ class Point {
1818
int index; // 1,2,3,4,5....
1919
double weight; // considering the outdated effect
2020
double cost;
21+
double minDist;
22+
private:
23+
// the distance to the nearest data point
2124
int clusteringCenter; // using index to identify
2225
int dimension;// feature Length
2326
std::vector<double> *feature;//TODO: need to think how to remove * here.
@@ -37,6 +40,9 @@ class Point {
3740
int getDimension() const;
3841
void setDimension(int d);
3942
int getFeatureLength();
43+
double getDisTo(SESAME::PointPtr p);
44+
double getMinDist() const;
45+
void setMinDist(double min_dist);
4046
SESAME::PointPtr copy();
4147
};
4248
}

0 commit comments

Comments
 (0)