Lib.rs

MASS：Rust中用于相似度搜索的Mueen算法！

时间序列子序列的相似度搜索是时间序列模式挖掘中最重要的子程序。在DTW（动态时间扭曲）和欧几里得距离下，子序列相似度搜索已经扩展到万亿级别的观测值[a]。算法非常快且高效。自1994年以来，使算法有用的关键技术是早期放弃技术[b,e]。然而，这些算法缺少一些对许多时间序列数据挖掘算法有用的属性。

1. 早期放弃依赖于数据集。最坏情况下的复杂度仍然是O(nm)，其中n是较长时间序列的长度，m是较短查询的长度。
2. 该算法可以产生与查询最相似的子序列，但不能产生给定查询的所有子序列的Distance Profile。MASS是一种创建查询到长时间序列的Distance Profile的算法。在本页中，我们分享了在欧几里得距离下对时间序列子序列进行最快相似度搜索算法的代码。在某些数据集和某些查询上，偶尔可以击败这个算法。此算法与数据和查询无关。该算法的基本概念已经为信号处理社区所熟知。我们首次在z-归一化下的时间序列子序列搜索中使用了它。该算法被用作我们论文[c,d]中的子程序，代码如下。

1. 该算法的总时间复杂度为O(n log n)，不依赖于数据集，并且是时间序列子序列相似度搜索的下界。
2. 该算法产生查询到长时间序列子序列的所有距离。在我们的最近论文中，我们推广了使用MASS计算的距离剖面在寻找基序、形状和冲突中的应用。

摘自

@misc{
FastestSimilaritySearch,
title={The Fastest Similarity Search Algorithm for Time Series Subsequences under Euclidean Distance},
author={ Mueen, Abdullah and Zhu, Yan and Yeh, Michael and Kamgar, Kaveh and Viswanathan, Krishnamurthy and Gupta, Chetan and Keogh, Eamonn},
year={2017},
month={August},
note = {\url{http://www.cs.unm.edu/~mueen/FastestSimilaritySearch.html}}
}

功能

"jemalloc" 启用jemallocator作为内存分配器。

"pseudo_distance" 简化了具有相同优化目标的最优距离。距离输出不再是MASS距离，而是一个具有相同最优值的分数。

"auto" 使用所有逻辑核心来并行化批量函数。默认启用。禁用此功能会暴露 ['init_pool()'] 用于初始化全局线程池。

恐慌

待办事项

示例

use rand::{thread_rng, Rng};

let mut rng = thread_rng();
let ts = (0..10_000).map(|_| rng.gen()).collect::<Vec<f64>>();
let query = (0..500).map(|_| rng.gen()).collect::<Vec<f64>>();
let res = super_mass::mass_batch(&ts[..], &query[..], 501, 3);
 //top_matches (only the best per batch considered) tuples of (index,distance score).
dbg!(res);

use rand::{thread_rng, Rng};

let mut rng = thread_rng();
let ts = (0..10_000).map(|_| rng.gen()).collect::<Vec<f64>>();
let query = (0..500).map(|_| rng.gen()).collect::<Vec<f64>>();
let res = super_mass::mass(&ts[..], &query[..]);
 //Complete distance profile
dbg!(res);