软件学报

作者：俞自生，李瑞远，郭阳，蒋忠元，鲍捷，郑宇

单位：俞自生，西安电子科技大学 网络与信息安全学院, 陕西 西安 710126;北京京东智能城市大数据研究院, 北京 10017611,李瑞远，重庆大学 计算机学院, 重庆 400044;北京京东智能城市大数据研究院, 北京 10017602,郭阳，北京航空航天大学 计算机学院, 北京 10019103,蒋忠元，西安电子科技大学 网络与信息安全学院, 陕西 西安 71012604,鲍捷，北京京东智能城市大数据研究院, 北京 10017605,郑宇，北京京东智能城市大数据研究院, 北京 10017606

关键词：时间序列;相似性搜索;键值存储;剪枝过滤;分布式查询

基金：国家重点研发计划（2019YFB2103201）；国家自然科学基金（61976168，62076191，61502375）

时序相似性搜索是时序数据分析最基本的操作之一，具有广泛的应用场景.针对现有分布式算法无法应对维度增长、扫描范围过大和相似性计算耗时的问题，提出一种面向键值存储的分布式时序相似性搜索方法KV-Search.首先对时序数据分块，并设计其键值存入键值数据库，解决了时序数据维度高且不断增长的问题；其次，基于切比雪夫距离计算其下界，并利用键值范围扫描提前过滤无效数据，减少了数据传输；最后，利用基于分块的时序表示计算距离下界，避免了更高维度真实数据的计算，加快了查询效率.使用HBase实现了KV-Search，并利用真实的大规模数据集做了大量实验.实验结果表明，KV-Search算法在效率和扩展性方面均优于基准实验.

来源：2022年第3期

《软件学报》期刊编辑部

查看软件学报杂志2022年第3期