| 本文已被：浏览 2822次 下载 6906次 |
码上扫一扫！ |
|
|
| 基于键值存储的分布式时序相似性搜索方法 |
|
俞自生1,2, 李瑞远3,2, 郭阳4, 蒋忠元1, 鲍捷2, 郑宇2
|
|
1.西安电子科技大学 网络与信息安全学院, 陕西 西安 710126;2.北京京东智能城市大数据研究院, 北京 100176;3.重庆大学 计算机学院, 重庆 400044;4.北京航空航天大学 计算机学院, 北京 100191
|
|
| 摘要: |
| 时序相似性搜索是时序数据分析最基本的操作之一，具有广泛的应用场景.针对现有分布式算法无法应对维度增长、扫描范围过大和相似性计算耗时的问题，提出一种面向键值存储的分布式时序相似性搜索方法KV-Search.首先对时序数据分块，并设计其键值存入键值数据库，解决了时序数据维度高且不断增长的问题；其次，基于切比雪夫距离计算其下界，并利用键值范围扫描提前过滤无效数据，减少了数据传输；最后，利用基于分块的时序表示计算距离下界，避免了更高维度真实数据的计算，加快了查询效率.使用HBase实现了KV-Search，并利用真实的大规模数据集做了大量实验.实验结果表明，KV-Search算法在效率和扩展性方面均优于基准实验. |
| 关键词: 时间序列 相似性搜索 键值存储 剪枝过滤 分布式查询 |
| DOI：10.13328/j.cnki.jos.006445 |
| 分类号: |
| 基金项目:国家重点研发计划（2019YFB2103201）；国家自然科学基金（61976168，62076191，61502375） |
|
| Distributed Time Series Similarity Search Method Based on Key-value Data Stores |
|
YU Zi-Sheng1,2, LI Rui-Yuan3,2, GUO Yang4, JIANG Zhong-Yuan1, BAO Jie2, ZHENG Yu2
|
|
1.School of Cyber Engineering, Xidian University, Xi’an 710126, China;2.JD Intelligent Cities Research, Beijing 100176, China;3.College of Computer Science, Chongqing University, Chongqing 400044, China;4.School of Computer Science and Engineering, Beihang University, Beijing 100191, China
|
| 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. |
| Key words: time series similarity search key-value storage pruning filtration distributed query |
