intellistream / sesame

Sesame

This project aims at building a scalable stream mining library on modern hardware.

• The repo contains currently several representative real-world stream clustering algorithms and several synthetic algorithms.
• We welcome your contributions, if you are interested to contribute to the project, please fork and submit a PR. If you have questions, feel free to log an issue.

Build Dependency

• GCC-11 (In our paper, we use gcc-11.2.0)
• Boost: 1.78.0 Link
• GFLAGS: 2.2.0 Link

Real-world algorithms

Algorithm	Window Model	Outlier Detection	Summarizing Data Structure	Offline Refinement
BIRCH	LandmarkWM	OutlierD	CFT	❌
CluStream	LandmarkWM	OutlierD-T	MCs	✅
DenStream	DampedWM	OutlierD-BT	MCs	✅
DStream	DampedWM	OutlierD-T	Grids	❌
StreamKM++	LandmarkWM	NoOutlierD	CoreT	✅
DBStream	DampedWM	OutlierD-T	MCs	✅
EDMStream	DampedWM	OutlierD-BT	DPT	❌
SL-KMeans	SlidingWM	NoOutlierD	AMS	❌

Synthetic algorithms

Algorithm	Window Model	Outlier Detection	Summarizing Data Structure	Offline Refinement
G1	LandmarkWM	OutlierD	MCs	✅
G2	LandmarkWM	OutlierD	MCs	✅
G3	LandmarkWM	OutlierD	CFT	❌
G4	SlidingWM	OutlierD	MCs	❌
G5	DampedWM	OutlierD-B	MCs	❌
G6	LandmarkWM	NoOutlierD	MCs	❌
G8	LandmarkWM	OutlierD	MCs	❌
G9	LandmarkWM	OutlierD	Grids	❌
G10	LandmarkWM	OutlierD	DPT	❌
G11	LandmarkWM	OutlierD-T	MCs	❌
G12	LandmarkWM	OutlierD-B	MCs	❌
G13	LandmarkWM	OutlierD-BT	MCs	❌
G14	LandmarkWM	OutlierD	AMS	❌
G15	LandmarkWM	OutlierD	CoreT	❌

Datasets

DataSet	Length	Dimension	Cluster Number
CoverType	581012	54	7
KDD-99	4898431	41	23
Insects	905145	33	24
Sensor	2219803	5	55
EDS	45690, 100270, 150645, 200060, 245270	2	75, 145, 218, 289, 363
ODS	94720,97360,100000	2	90, 90, 90

You may download the datasets here: https://zenodo.org/records/8210331

How to Cite Sesame

• [SIGMOD 2023] Xin Wang and Zhengru Wang and Zhenyu Wu and Shuhao Zhang and Xuanhua Shi and Li Lu. Data Stream Clustering: An In-depth Empirical Study, SIGMOD, 2023

@inproceedings{wang2023sesame,
	title        = {Data Stream Clustering: An In-depth Empirical Study},
	author       = {Xin Wang and Zhengru Wang and Zhenyu Wu and Shuhao Zhang and Xuanhua Shi and Li Lu},
	year         = 2023,
	booktitle    = {Proceedings of the 2023 International Conference on Management of Data (SIGMOD)},
	location     = {Seattle, WA, USA},
	publisher    = {Association for Computing Machinery},
	address      = {New York, NY, USA},
	series       = {SIGMOD '23},
	abbr         = {SIGMOD},
	bibtex_show  = {true},
	selected     = {true},
	pdf          = {papers/Sesame.pdf},
	code         = {https://github.com/intellistream/Sesame},
	doi	         = {10.1145/3589307},
        url          = {https://doi.org/10.1145/3589307}
}

sesame's Issues

Add Algorithm_parameters

design a parameter class for each algorithm to store the needed parameters

Implement EDMStream

Implement evaluation metrics

Linked to #25

CMM

Concept Drift Algorithm Collection

general or aim at clustering

Code Reformat to include more evaluations

Let data source load from external sensors, e.g., HTTP.

Data Generator

Many existing works use their own syntetic data generator. We need to design our own comprehensive synthetic data generator to evaluate different workload aspects.

Implement EDMStream algorithm

Outlier Detection Seperation

Implement BIRCH algorithm

DataSource.cpp

load method still contains hard-coded components, try to remove them and clean up the code.

Fix bug01 of StreamKM++

Problem: endless loop and the program cannot print any result information

Make print_help more useful.

void BenchmarkUtils::print_help(char *string) {
SESAME_ERROR("Usage: " << string << " [options]"); SESAME_ERROR(" Available options: ");
}

Compared to Noah

https://github.com/huawei-noah/streamDM-Cpp

Extremely Fast Decision Tree Mining for Evolving Data Streams, KDD'17

Useful component: streaming generator (todo).

Implement denstream

Den-stream

• Need to summarize Den-stream in paper
• Complete coding of Den-stream

Streaming Kmeans

change the way to pass parameters

SL-KMeans implementation

NIPS 2020: https://arxiv.org/abs/2006.05850
We are still lacking an algorithm using the sliding window model, so we have to implement it into our framework!
The source code link is: https://github.com/google-research/google-research/tree/master/sliding_window_clustering/

Survey online clustering algorithms.

Parallel implementation of stream clustering algorithms

https://dl.acm.org/doi/pdf/10.1145/2806416.2806545

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.300.2643&rep=rep1&type=pdf

Collect datasets and transform the data format

ODAC

remove hard-coded queue initialization

DataSource.hpp

Add GTest for Clustream

Add GTest and evluation criteria for CluStream

Identify Cluster Evolving Methods

Adaption methods,
Detection methods.

Add Threading Model

Implement STREAM algorithm

Clustering Data Streams, by Sudipto Guha, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan, which appeared in FOCS 2000.

Add GTest for StreamKM++

pull request link: add GTest #22

Refactor offline KMeans and KMeans++

current version is difficult to reuse

Implement swem

Implement Clustream

Identify real-world usecases to measure

Fix bugs in Clustream

1. Fix compiler error
2. Still debug online part

Learn from iMLBench

https://github.com/ChenyangZhang-cs/iMLBench

multithreading.

Multithread engine

Support multithreaded engine.

Tree Structure Integration

AI/ML/DM Review

1. https://medium.com/@zaleslaw/weakness-of-the-apache-spark-ml-library-41e674103591

Related work of other ML lib.

bug in denstream

elastic time maybe zero.

D-Stream

in debug

Synthetic DataSet

The previous synthetic dataset is not suitable so we need to design a new one. Below are some considerations:
length / cluster number / dimension / arrival rate / concept evolution occurring frequency / outliers

Remove hard-coded queue initialization

For example.

SESAME::DataSource::DataSource() {
inputQueue = std::make_shared<rigtorp::SPSCQueue>(1000);//TODO: remove hard-coded queue initialization.
threadPtr = std::make_shared();
}

Identify Algorithms to test.

• Need to finish writing data structure part -- feature vector part
• CluStream summarization

outlier_detection (paper)

A feature-based framework for detecting technical outliers in water-quality data from in situ sensors
https://arxiv.org/abs/1902.06351

Implement DBStream

Add SSE evaluation measurement

Add external evaluation measurement -- Which can measure stream clustering on evolution stream

Reference to ‘An Effective Evaluation Measure for Clustering on Evolving Data Streams’ (CMM)

An existing implementation of MOA

Stream Clustering for NLP

https://aclanthology.org/D18-1483.pdf

Add time measurement

Compile on Mac

Log4cxx not available on Mac.
Use a Macro to control it.
If Log4cxx is not available, change Log4cxx_LOG to cout.

Add time measurement

Learn from AlianceDB.