基于键值存储的分布式时序相似性搜索方法
作者:
作者单位:

作者简介:

俞自生(1996-),男,硕士生,CCF学生会员,主要研究领域为城市计算,时空数据管理与分析,分布式数据库;
蒋忠元(1988-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为复杂网络系统安全,隐私保护,社交网络,数据挖掘;
李瑞远(1990-),男,博士,副教授,CCF专业会员,主要研究领域为时空数据管理与挖掘,城市计算;
鲍捷(1985-),男,博士,CCF专业会员,主要研究领域为城市计算,时空数据管理与挖掘;
郭阳(1997-),女,硕士,CCF学生会员,主要研究领域为机器学习,计算机视觉,数据挖掘;
郑宇(1979-),男,博士,教授,CCF杰出会员,主要研究领域为时空数据挖掘,城市计算.

通讯作者:

李瑞远,E-mail:liruiyuan@whu.edu.cn

中图分类号:

基金项目:

国家重点研发计划(2019YFB2103201);国家自然科学基金(61976168,62076191,61502375)


Distributed Time Series Similarity Search Method Based on Key-value Data Stores
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Time series similarity search is one of the most basic operations for temporal data analysis, which has various application scenarios. Existing distributed methods face the problems of dimension explosion, too large scan range, and time-consuming similarity calculation. To this end, this study proposes a distributed time series similarity search algorithm KV-Search. First, time series are segmented into blocks and stored in the key-value database, which solves the problem of high and growing dimension. Second, the lower bound is calculated based on Chebyshev distance, and the invalid data is filtered out in advance using key value range scanni ng, which reduce the data transmission and calculation overhead. Third, a block-based time series representation is used to calculate the lower bound of distance, which avoids the calculation of higher dimensional real data. KV-Search is implemented based on HBase, and a set of extensive experiments are conducted using both real and synthetic time series data. The results show that the proposed KV-Search is superior to benchmark experiment in efficiency and scalability.

    参考文献
    相似文献
    引证文献
引用本文

俞自生,李瑞远,郭阳,蒋忠元,鲍捷,郑宇.基于键值存储的分布式时序相似性搜索方法.软件学报,2022,33(3):950-967

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-06-30
  • 最后修改日期:2021-07-31
  • 录用日期:
  • 在线发布日期: 2021-10-21
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号