JUST技术:分布式时序相似查询初探

2020-12-02 00:00:00 序列 数据 时序 分区 相似性
时序数据,即随时间变化的数据,在人们的日常生活中无处不在。过去的近十年来,随着电子监控和智能穿戴等设备的普及,更是产生了海量的时序数据。例如,经过多年的发展,火力发电行业的数字化程度已经达到了很高的水平,以一台60万千瓦的中型火电机组为例,其内置的上万个传感器,每秒可产生数万条实时监控数据。

其中,时序相似查询,即查询出与给定序列q相似的k个序列,可用于推荐、聚类和异常检测等上层应用。在小规模数据下,时序相似查询是没有问题的,只要将给定序列q与数据库中所有数据进行两两相似性计算后取Top-k即可。
但是,在大数据的背景下,这种方法往往是行不通的,主要挑战体现在两个方面:,时序数据基数大,两两计算相似性哪怕是一种线性的解决方案(即仅需扫描一遍数据库),其耗时也是难以接受的;第二,时序数据维度高,两条时序数据计算相似性的耗时也随之增加。
针对挑战一,一种很自然的想法便是将相似的数据放在同一分区,查询时仅需扫描给定序列q所属的分区数据即可,无需全量扫描,这就是基于分布式存储数据的思想。针对挑战二,既然数据的维度高计算耗时,那么进行降维便可使计算成本下降,但如何在降维的同时又保持其在高维的相似性呢?
综上,本次技术分享,针对时序相似查询在大数据背景下遇到的困难,介绍几种基于分布式索引和查询的解决方案。

一、问题定义
下面给出一些基本定义。一条长度为n的时序数据X=<x1,x2,…,xn>,其中xi代表在某个时刻的读数,为了简单起见,我们假设每个读数的时间间隔相等,且xi为二进制0或1。数据库中存有海量的时序数据集合D={X1,X2,…},相似查询指的是对于给定的查询序列q,返回与其相似的k个时序数据。序列之间的相似性使用Jaccard相似度来衡量。设A和B是两个时序序列,其非零值个数分别为a和b,共有的非零值个数为c,则Jaccard相似度定义为: 
Jaccard相似度可以简单理解为A和B的交集与其并集的比值,当A等于B时,其交集等于并集,Jaccard相似度大,为1;当A和B所有位均不相等时,其交集为0,Jaccard相似度小,为0。所以两序列越相似,其交集也就越多,Jaccard相似度也就越大。

二、基于分区的解决方案
为了将相似的时序数据分至同一个分区,我们需要指定一些分区策略。
种想法自然便是划网格,我们想象一个维度为n(即时序数据的特征维度)的超立方体,将数据映射至该立方体,然后均匀地二分网格,显然,相近的序列很大可能会被划分至同一分区(少部分相似数据可能在分区边界附近被分隔开)。但是这样必然会导致数据的热点问题,即有的分区数据密集,有的分区数据稀疏甚至没有数据,这是因为划分网格时并没有考虑数据分布,如图1所示: 

图1 均匀二分网格(其中点表示二维的时序数据)
进一步,我们可以优化下划分网格的方法,不再一味地均匀划分,而是实时根据数据分布进行划分,总的原则就是尽量使网格中包含的数据量大致相等,例如基于KD树的思想划分网格并建立相应索引[2],如图2所示: 

 

图2 基于KD树的思想划分网格(保证每个网格中的数据量大致相等)
网格划分完成后,对于一个查询q,我们可以先计算其属于哪个分区,再将查询任务指派给该分区进行相似查询,这样便避免了数据的全量扫描。但是这样的查询存在一些问题,因为我们无法保证与q相似的k条数据一定在同一分区,所以这只是一个近似的相似查询。当需要的相似查询时,不可避免的就需要扫描其它分区,但结合一些分区过滤规则,也可以大大减少数据的扫描量[2]。
 
三、基于降维的解决方案
对数据进行降维本身并不难,但在降维的同时保持数据高维时的相似性,却并不简单。这里简单其中的一种代表性算法:小哈希算法(MinHash)。
设A和B分别为两个长度为n的时序序列,其值为二进制,<i1,i2,…,in>为其索引下标序列,其中ik在0至n之间。
MinHash的操作步骤如下:首先对<i1,i2,…,in>作一个随机打乱,并让A和B按打乱后的索引序列进行重新排列,然后分别取个非零行的索引下标作为其MinHash。这样得到的A和B的MinHash有一个重要的性质:

这里省去该性质的证明。这个性质为我们降维的同时保持相似性提供了可能。我们可以将上述步骤重复m次(m通常远远小于原序列的长度n),记录每一次的MinHash值得到序列<h1,h2,…,hm>,即得到两向量的Signature签名向量sig(A)=[h1(A),h2(A),…,hm(B)]和sig(B)=[h1(B),h2(B),…,hm(B)]。
这样我们既进行了降维(维度由n降维m,m远小于n),又近似保持了向量的相似性(sig(A)和sig(B)以概率保持A和B的Jaccard相似性),计算相似性时仅需计算Signature向量的相似性即可,降低了计算成本。

四、结合分区和降维的解决方案
上述的MinHash算法虽然将数据映射到低维空间中的签名向量,并近似保持了高维时数据之间的相似性,解决了挑战二中时序数据维度高的问题,但是仍需两两计算数据之间的相似性,没有解决挑战一。试想,若我们对降维后的数据再进行分区,是否可以得到更好的效果,具体思想是:先对原数据进行降维,再将降维后的数据分桶,将可能相似的数据以较大概率分至同一个桶内,这个每个时序数据的“备选相似数据集”就会相对较小,从而降低了寻找其相似数据的计算复杂度。其中,局部敏感哈希(Locality Sensitive Hashing,LSH)便是这类算法的代表。
LSH是建立在MinHash所得到的Signature向量基础上,将每一个向量等分为几段,称之为band,其基本思想是:若两个向量的一个或多个band相同,那么这两个向量的相似度高的可能性就较大。LSH的做法是,对每条数据的Signature向量在每一个band上分别进行哈希分桶(哈希算法并无特殊要求),任意一个band上被分到同一桶的数据就互为Candidate数据,这样仅需要计算Candidate数据集的相似性就可以找到每个数据的相似数据了。这里的分桶即为分区,利用分布式将数据存储在不同的分区上。
当然,LSH是一种基于概率的方法,必然会有漏网之鱼,所以我们希望以下两种情况的数据越少越好:1)False Positives:相似度低的数据被哈希到了同一个桶;2)False Negatives:相似度高的数据在每一个band上都没有被哈希到同一个桶。
当对序列q进行相似查询时,我们可以先计算q所属的桶编号,将查询下发至桶,后进行整合取Top-k,这样大大过滤掉了不必要的相似性计算,同时也以概率保证了查询结果的正确性。但是,因为LSH是基于概率的,所以是一种近似的相似查询,并且不能处理的相似查询的需求。

目前,我们JUST正在构建自己的分布式时序数据平台,敬请关注。


参考文献:
[1] Alghamdi N, Zhang L, Zhang H, et al. ChainLink: Indexing Big Time Series Data For Long Subsequence Matching[C]//2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020: 529-540.
[2] Yagoubi D E, Akbarinia R, Masseglia F, et al. Massively distributed time series indexing and querying[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 32(1): 108-120.
[3] Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//Vldb. 1999, 99(6): 518-529.

转载请注明:康瑞部落 » JUST技术:分布式时序相似查询初探

相关文章