基于MapReduce的时间序列索引与批量查询技术

doi:10.19678/j.issn.1000-3428.0054487

计算机工程 ›› 2019, Vol. 45 ›› Issue (11): 47-53. doi: 10.19678/j.issn.1000-3428.0054487

基于MapReduce的时间序列索引与批量查询技术

陈军晓^1,2, 李中升³, 刘逸敏¹, 李秋虹⁴, 汪卫⁴

1. 上海东方肝胆外科医院信息科, 上海 200438;
2. 海军军医大学研究生四大队, 上海 200433;
3. 江南计算技术研究所, 江苏无锡 214081;
4. 复旦大学计算机学院, 上海 201203

收稿日期:2019-04-03 修回日期:2019-06-26 发布日期:2019-08-06
作者简介:陈军晓(1990-),男,硕士研究生,主研方向为医疗数据分析、大数据应用;李中升,高级工程师;刘逸敏(通信作者),主任技师;李秋虹,讲师;汪卫,教授。
基金资助:
国家自然科学基金"面向工业应用的大数据分析理论与关键技术"（U1509213）；国家人口与健康科学数据共享服务平台肝肿瘤信息资源专题服务项目（NCMI-SFS14-201806）。

Time Series Index and Batch Query Technology Based on MapReduce

CHEN Junxiao^1,2, LI Zhongsheng³, LIU Yimin¹, LI Qiuhong⁴, WANG Wei⁴

1. Department of Information, Shanghai Eastern Hepatobiliary Surgery Hospital, Shanghai 200438, China;
2. Forth Team of Postgraduates, Naval Medical University, Shanghai 200433, China;
3. Jiangnan Institute of Computing Technology, Wuxi, Jiangsu 214081, China;
4. School of Computer Science, Fudan University, Shanghai 201203, China

Received:2019-04-03 Revised:2019-06-26 Published:2019-08-06

摘要/Abstract

摘要： 针对基于不平衡树的时间序列索引对海量时间序列数据查询性能较差的问题，提出一种基于MapReduce的DB-DSTree索引。利用平衡的时间序列索引DHD作为路由树创建分布式的DSTree，并充分挖掘批量查询中的数据局部性，将相似的查询路由到局部节点上，以改善DSTree索引的非平衡性。实验结果表明，DB-DSTree索引的平衡性和局部性较好，可减少子树的查询范围和磁盘I/O次数，提高查询效率。

关键词: 时间序列, 相似性查询, 下界, MapReduce模型, 索引

Abstract: To address the problem of poor performance of massive time series data query based on time series index of unbalanced tree,a DB-DSTree index based on MapReduce is proposed.The balanced time series index DHD is used as a routing tree to create a distributed DSTree,and the data locality in batch queries is fully mined.Similar queries are routed to local nodes to improve the non-balance property of DSTree index.Experimental results show that DB-DSTree index has good balance and locality,it can reduce the query range of subtree and I/O time of disks,and improve the query efficiency.

Key words: time series, similarity query, lower bound, MapReduce model, index

中图分类号:

TP311

陈军晓, 李中升, 刘逸敏, 李秋虹, 汪卫. 基于MapReduce的时间序列索引与批量查询技术[J]. 计算机工程, 2019, 45(11): 47-53.

CHEN Junxiao, LI Zhongsheng, LIU Yimin, LI Qiuhong, WANG Wei. Time Series Index and Batch Query Technology Based on MapReduce[J]. Computer Engineering, 2019, 45(11): 47-53.

http://www.ecice06.com/CN/Y2019/V45/I11/47

图/表 8

20191118164442

20191118164445

20191118164447

20191118164450

20191118164453

20191118164456

20191118164459

20191118164501

参考文献

[1] WANG Yang,WANG Peng,PEI Jian,et al.A data-adaptive and dynamic segmentation index for whole matching on time series[J].Proceedings of the VLDB Endowment,2013,6(10):793-804.
[2] SHIEH J,KEOGH E.iSAX:indexing and mining terabyte sized time series[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2008:623-631.
[3] DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation.San Francisco,USA:USENIX Association,2004:1-10.
[4] LI Qiuhong,WANG Peng,WANG Yang,et al.Clustering time series utilizing a dimension hierarchical decomposition approach[C]//Proceedings of International Conference on Database Systems for Advanced Applications.Berlin,Germany:Springer,2017:247-261.
[5] CHAN Kinpong,FU A W C.Efficient time series matching by wavelets[C]//Proceedings of the 15th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,1999:126-133.
[6] AGRAWAL R,FALOUTSOS C,SWAMI A N.Efficient similarity search in sequence databases[C]//Proceedings of International Conference on Foundations of Data Organization and Algorithms.Berlin,Germany:Springer,1993:69-84.
[7] LIN J,KEOGH E,LONARDI S,et al.A symbolic representation of time series,with implications for streaming algorithms[C]//Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.New York,USA:ACM Press,2003:2-11.
[8] KORN F,JAGADISH H V,FALOUTSOS C.Efficiently supporting ad hoc queries in large datasets of time sequences[EB/OL].[2019-03-20].http://www.cs.cmu.edu/~christos/PUBLICATIONS.OLDER/sigmod97.pdf.
[9] KEOGH E,CHAKRABARTI K,PAZZANI M,et al.Locally adaptive dimensionality reduction for indexing large time series databases[J].ACM Transactions on Database Systems,2002,27(2):188-228.
[10] KEOGH E,CHAKRABARTI K,PAZZANI M,et al.Dimensionality reduction for fast similarity search in large time series databases[J].Knowledge and Information Systems,2001,3(3):263-286.
[11] KEOGH E,CHU S,HART D,et al.Segmenting time series:a survey and novel approach[M].[S.l.]:World Scientific Publishing Company,1993.
[12] 陶洋,李鹏亮,沈敬红,等.基于DTW的时间序列流相似性搜索方法[J].计算机工程与设计,2017,38(12):3291-3297.
[13] ZOUMPATIANOS K,LOU Y,PALPANAS T,et al.Query workloads for data series indexes[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2015:1603-1612.
[14] ZOUMPATIANOS K,PALPANAS T.Data series management:fulfilling the need for big sequence analytics[EB/OL].[2019-03-30]. https://www.irt-systemx.fr/wp-content/uploads/2018/03/Seminar-SystemX_ThemisPalpanas.pdf.
[15] 蔡青林,陈岭,梅寒蕾,等.基于两级过滤的时间序列近似查询[J].浙江大学学报(工学版),2019,36(2):232-236.
[16] KATE R J.Using dynamic time warping distances as features for improved time series classification[J].Data Mining and Knowledge Discovery,2016,30(2):283-312.
[17] 晏臻,苏维均,于重重,等.一种改进的DTW相似性搜索方法[J].计算机仿真,2016,50(7):1290-1297.
[18] CAMERRA A,PALPANAS T,SHIEH J,et al.iSAX 2.0:indexing and mining one billion time series[C]//Proceedings of 2010 IEEE International Conference on Data Mining.Washington D.C.,USA:IEEE Computer Society,2010:58-67.
[19] CAMERRA A,SHIEH J,PALPANAS T,et al.Beyond one billion time series:indexing and mining very large time series collections with iSAX2+[J].Knowledge and Information Systems,2014,39(1):123-151.
[20] ZOUMPATIANOS K,IDREOS S,PALPANAS T.ADS:the adaptive data series index[J].The VLDB Journal,2016,25(6):843-866.
[21] KONDYLAKIS H,DAYAN N,ZOUMPATIANOS K,et al.Coconut:a scalable bottom-up approach for building data series indexes[EB/OL].[2019-03-20].https://www.vldb.org/pvldb/vol11/p677-kondylakis.pdf.

选择文件类型/文献管理软件名称

选择包含的内容

基于MapReduce的时间序列索引与批量查询技术

Time Series Index and Batch Query Technology Based on MapReduce

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	汤卫芬, 高翠芳. 极值点自适应加权的动态时间规整算法[J]. 计算机工程, 2023, 49(7): 150-160.
[2]	蔡瑞初, 伍运金, 陈薇, 郝志峰. 面向多元时间序列的群体因果关系发现算法[J]. 计算机工程, 2023, 49(2): 127-135.
[3]	高峰, 李秋, 顾进广. 基于图结构特征采样数据摘要的联邦知识图谱查询[J]. 计算机工程, 2023, 49(1): 73-81.
[4]	刘杭, 殷歆, 陈杰, 罗恒. 基于混合网络模型的多维时间序列预测[J]. 计算机工程, 2023, 49(1): 121-129.
[5]	李海林, 夏燕燕, 邹金串. 基于CPET时序聚类的中长跑耐力运动员选拔方法[J]. 计算机工程, 2022, 48(9): 262-268.
[6]	梁小慧, 郭晟楠, 万怀宇. 基于自适应小波分解的时间序列分类方法[J]. 计算机工程, 2022, 48(4): 81-88,98.
[7]	李晓, 卢先领. 基于双重注意力机制和GRU网络的短期负荷预测模型[J]. 计算机工程, 2022, 48(2): 291-296,305.
[8]	陆怡, 王鹏, 汪卫. 基于子序列相似性的时间序列语义挖掘算法[J]. 计算机工程, 2022, 48(10): 88-94.
[9]	白梅, 苌仕涵, 王习特. 基于位置的路网Skyline查询处理研究[J]. 计算机工程, 2022, 48(1): 127-134.
[10]	刘苗苗, 周从华, 张婷. 基于分段特征及自适应加权的DTW相似性度量[J]. 计算机工程, 2021, 47(8): 62-68,77.
[11]	李勇, 董思秀, 张强, 程方颀, 王常青. 注意力流网络中节点影响力的层级性研究[J]. 计算机工程, 2021, 47(8): 109-115,123.
[12]	夏磊, 杨华, 宋玉蓉. 多用户载波索引差分混沌移位键控通信系统及性能分析[J]. 计算机工程, 2021, 47(5): 181-188.
[13]	蔡瑞初, 林峰极, 郝志峰, 王立, 温雯. 面向轨迹流数据的索引构建与存储方法研究[J]. 计算机工程, 2021, 47(3): 62-70.
[14]	夏寒松, 张力生, 桑春艳. 基于LDTW的动态时间规整改进算法[J]. 计算机工程, 2021, 47(11): 108-120.
[15]	顾岩, 赵崇宇, 黄平. 基于高阶统计信息的深度哈希学习模型[J]. 计算机工程, 2020, 46(7): 260-267,276.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于MapReduce的时间序列索引与批量查询技术

Time Series Index and Batch Query Technology Based on MapReduce

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献

相关文章 15

编辑推荐

Metrics

本文评价