Count Min (CM) Modeling Clause Samples

Count Min (CM) Modeling. The Count-Min algorithm is based on probabilistic techniques to serve various types of queries on streaming data. The Count-Min algorithm is able to handle massive data using data structures that occupy sub-linear space vs. the size of the input dataset. The CM sketch data structure can accurately summarize arbitrary data distributions with a compact, fixed memory footprint that is often small enough to fit within cache, ensuring fast processing of updates. There have been several efforts to implement sketch data structures in hardware to accelerate their performance. The simplicity and the parallelism of the sketching algorithms makes such implementations convenient. Lai et al. [51] presented an implementation of sketching techniques using an FPGA-based platform, for the purpose of anomaly detection. Their implementation scales easily to network data stream rates of 4Gbps. Lai and ▇▇▇▇ [52] implemented a Count-Min sketch on a low-power stream processor, which processes a throughput rate up to 13 Gbps according to their results. In [53], ▇▇▇▇▇▇ et al. describe their implementation on a IBM cell processor with 8 processing units. Their results show an almost 8-fold speedup vs. the single-thread sequential code. Wellem et al. in [54, 55] proposed to use Graphics Processing Units (GPUs) for offloading heavy sketch computations for network traffic change detection. Their experiment results showed that GPU can conduct fast change detection with query operation up to 9 million distinct keys per second and one order of magnitude faster than sequential software version. This section presents the analysis of the input and the output of the proposed sketch data structure. Also, we describe the datasets that were used for the analysis, the validation and the testing of the implemented hardware-based system. Next, the algorithmic analysis of the CM method is presented. Last, we present the basic data structures and their operations that the proposed algorithm implements.