一种流数据立方体分析挖掘框架

doi:10.3969／j.issn.1000-0801.2014.09.009

Abstract

Abstract:

Stream data has been one of the most significant data format recently. OLAM（online analytical mining） operation could provide multi-level data views for analysts. However, OLAM operations depend on data aggregation, which is in conflict with the continuous incensement and dynamic nature of stream data. Thus, partial materialized view from stream data directly by typical OLAP approaches cannot be created and all data cells for the limitation of storage cannot be saved. In order to solve the above problems, an advanced sketch based OLAM framework named sketch cube to analyze stream data was proposed. Sketch cube maps a set of attributes to a unique number and stores it in sub-linear data structure, and then builds an inverted index by tiled time window. The precondition of using sketch cube by theoretical analysis was given and the storage efficiency and query performance on mass mobile data corpus was evaluated, which supports requirements of real-time analysis.

Key words: stream data, sketch cube, online analytical mining, real-time analysis

Canghong Jin,Zemin Liu,Minghui Wu,Jing Ying. A Cube Analytical Mining Framework for Stream Data[J]. Telecommunications Science, 2014, 30(9): 61-71.

Figures/Tables 16

References 23

1	Aggarwal C C . An Introduction to Data Streams. Data Streams. Springer US, 2007.
2	Hellerstein J M , Haas P J , Wang H J . Online aggregation. ACM SIGMOD Record, 1997,26(2): 171～182.
3	Zhang X , Chou P L , Dong G . Efficient computation of iceberg cubes by bounding aggregate functions. IEEE Transactions on Knowledge and Data Engineering, 2007,19(7)
4	Chen Y , Do ng G , Han J , et al. Multi-dimensional regression analysis of time-series data streams. Proceedings of the 28th International Conference on Very Large Data Bases,VLDB Endowment, Hong Kong, China 2002:323～334.
5	胡文瑜 , 孙志挥 , 吴英杰 . 数据挖掘取样方法研究. 计算机研究与发展 2009,48(1): 45～54.
6	De Rougemont M , Cao P T . Approximate answers to OLAP queries on streaming data warehouses. Proceedings of the Fifteenth International Workshop on Data Warehousing and OLAP,Maui, Hi, USA 2012:121～128
7	Babcock B , Shinath B , Mayur D , et al. Models and issues in data stream systems. Proceedings of the 21st ACM Symposium on Principles of Database Systems,Madison,Wiscomsin,USA 2002:1～16
8	Chandrasekaran S , Cooper O , Deshpande A . TelegraphCQ:continuous dataflow processing for an uncertain world. Proceedings of the Conf on Innovative Data Systems Research,Asilomar, CA, USA 2003
9	Hetal T , Nikolay L , Hamid M , et al. SMM: a data stream management system for knowledge discovery. Proceedings of International Conference on Data Engineering,Hannover, Germany 2011:757～768
10	Rosenberg A L . Efficient pairing functions-and why you should care. International Journal of Foundations of Computer Science, 2003,14(1): 3～17.
11	Zhang D , Zhai C , Han J , et al. Topic modeling for OLAP on multidimensional text database: topic cube and its applications. Stat Anal Data Min, 2009,2(56):378～395
12	Ding B , Zhao B , Lin C , et al. Topcells: keyword-based search of top-k aggregated documents in text cube. Proceedings of International Conference on Data Engineering（ICDE）,Long Beach, USA 2010:381～384
13	Lin C , Ding B , Han J , et al. TextCube: computingirmeansures for multidimensional text database analysis. Proceedings of the 8th IEEE International Conference on Data Mining（ICDM）, 2008:905～910
14	Liu X , Tang K Z , Hancock J , et al. A text cube approach to human, social and cultural behavior in the Twitter stream. LNCS 7812, 2013:321～330
15	Cuzzocrea A . Retrieving accurate estimates to OLAP queries over uncertain and imprecise multidimensional data streams. Proceedings of the 23rd International Conference on SSDBM,Portland, OR, USA 2011
16	Aggarwal C C . Managing and Mining Sensor Data. New York：Springer US, 2013
17	张进 , 邬江兴 , 刘勤让 . 4种技术型Bloom Filter的性能分析与比较. 软件学报 2010,21(5): 1098～1114.
18	Cormode G , Hadjieleftheriou M . Finding frequent items in data streams. Proceedings of the VLDB Endowment, 2008,1(2):1530～1541
19	Considine J , Hadjieleftheriou M , Li F . Robust approximate aggregation in sensor data management systems. ACM Transactions on Database Systems（TODS）, 2009,34(1)
20	Han J , Kamber M , Pei J . Data Mining Concepts and Techniques. Elsevier Ltd, 2012
21	Cormode G , Muthukrishnan S . An improved data stream summary: the count-min sketch and its applications. J Algorithms, 2005,55(1):58～75
22	Cormode G , Muthukrishnan S . Summarizing and mining skewed data streams. Proceedings of SDM,Trondheim, Normay 2005
23	Giannella C , Han J , Pei J , et al Mining frequent patterns in data streams at multiple time granularities. Next Generation Data Mining, 2003(212):191～212

Metrics

Recommended 0

No Suggested Reading articles found!

属性描述	维度基数
终端联网类型字典编号	9
当前应用的版本号	23
屏幕分辨率字典编号	123
操作系统字典编号	133
当前应用的发布渠道编号	165
运营商字典编号	402
城市字典编号	413
移动设备型号字典编号	4 436

时间窗口	样本大小	维度组合数量	偏斜因子
20 min	321 315	2 795	1.92
40 min	636 795	3 257	1.99
60 min	963 675	3 529	2.05

实验参数	取值
散列类型	MurmurHash V3
时间窗口／min	20,40,60
CM-sketch行数（d）	5
CM-sketch列数（w）	521,1 021,2 027
ACM参数m	10,20,30,40,50
比较结果	20,40, …,200
维度个数	8

模型	sketch 性能数据集大小=170 880	DCI大小			MPE（20 min,w=521）			MPE（20 min,w=2 027）
模型	sketch 性能数据集大小=170 880	20 min	40 min	60 min	top-20	top-80	top-160	top-20	top-80	top-160
ACM（10）	37 ms	15 896	18 796	20 498	0.081 6	0.142 7	0.259 7	0.006 337	0.014 63	0.021 59
ACM（30）	239 ms	90 592	123 650	145 258	0.168 6	0.359 5	0636 1	0.024 38	0.056 01	0.104 5
ACM（50）	424 ms	113 719	157 519	187 134	0.188 5	0.412 9	0.723 2	0.029 09	0.067 73	0.124 5
FCM	2 024 ms	654 202	1 026 186	1 551 168	0.552 1	1.307 3	2.084 2	0.123 4	0.266 1	0.436 7

时间窗口	数据集大小	运行时间／ms
10 min	7 035	67
20 min	13 470	72
30 min	19 815	81

A Cube Analytical Mining Framework for Stream Data

RichHTML

PDF下载

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 16

References 23

Related Articles 0

Metrics

Recommended 0