基于键值存储的分布式时序相似性搜索方法

• 作者: 俞自生 李瑞远 郭阳 蒋忠元 鲍捷 郑宇
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 时间序列 相似性搜索 键值存储 剪枝过滤 分布式查询
• 年，卷（期）: 2022,（3）
• 所属期刊栏目: 数据库系统新型技术专题|SPECIAL TOPIC ON NEW TECHNIQUES OF DATABASE SYSTEMS
• 页码范围: 950-967
• 页数: 18页
• 分类号: TP311
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.006445

摘要

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