JUMP: A Fast Deterministic Algorithm to Find the Closest Pair of Subsequences
JUMP: A Fast Deterministic Algorithm to Find the Closest Pair of Subsequences
复制标题
JUMP：一种查找最近的子序列对的快速确定性算法
DOI：
10.1137/1.9781611975321.9
复制
发表时间：
2018
影响因子：
3
通讯作者：
S. Rajasekaran
中科院分区：
文献类型：
--
作者：
Xingyu Cai;Shangli Zhou;S. Rajasekaran
在本文中，我们解决了一个经典的序列挖掘问题，即寻找最近的子序列对。给定长度为 n 的序列 A，问题是识别 lengthleach inA 的两个不重叠的子序列，使得它们的距离在所有此类对中最小。这是一个具有广泛应用的基本问题，例如时间序列数据挖掘、序列数据模式匹配、数据签名识别、生物基序挖掘、宏基因组聚类等。为了解决这个问题，最先进的算法利用了连续子序列的重叠部分。通过利用这些重叠，研究人员开发了一种运行时间为 O(n2) 的算法，该算法与维度无关。在本文中，我们提出了一种称为 JUMP 的确定性算法，该算法通过跳过不必要的比较和乘法运算来进一步突破极限，并大幅提高运行时间。我们使用标准基准数据集进行了广泛的实验，发现 JUMP 的性能比现有的 O(n2) 方法高出 100 倍。我们的实验涵盖了 nandland 的不同设置，为读者提供了不同条件下全面、公正的比较。
In this paper we address a classical sequence mining problem, namely, that of finding the Closest Pair of Subsequences. Given a sequence A of lengthn, the problem is to identify two non-overlapping subsequences of lengthleach inA, such that their distance is minimum from among all such pairs. This is a fundamental problem that has a wide range of applications such as time series data mining, sequence data pattern matching, data signature identification, biological motif mining, metagenomic clustering, etc. To solve this problem, the state-of-the-art algorithm takes advantage of the overlapping parts of consecutive subsequences. By exploiting these overlaps, researchers have developed an algorithm with a run time ofO(n2), which is independent of the dimensionl. In this paper, we propose a deterministic algorithm called JUMP, which further pushes the limit by skipping unnecessary comparisons and multiplication operations, and improves the running time by a large factor. We have performed extensive experiments using standard benchmark datasets, and found that JUMP outperforms existingO(n2) methods by a factor of up to 100. Our experiments cover different settings ofnandland provide the readers a comprehensive and unbiased comparison under different conditions.