吳裔 郭棋林 陳顥天 郭乃網(wǎng)

摘 要：時(shí)間序列的研究已經(jīng)被應(yīng)用到越來(lái)越多的領(lǐng)域中。越來(lái)越多的領(lǐng)域應(yīng)用需要索引和分析海量的時(shí)間序列，代表性的比如金融，電力，生物信息等等。這類應(yīng)用往往面臨數(shù)以億計(jì)的時(shí)間序列的處理，然后從中識(shí)別出一些隱藏的模式來(lái)。然而目前對(duì)時(shí)間序列的索引技術(shù)都是單機(jī)版本，需要用漫長(zhǎng)的時(shí)間來(lái)對(duì)大量的時(shí)間序列進(jìn)行索引，限制了時(shí)間序列分析的產(chǎn)出率。提出了一種基于Isax表達(dá)的分布式時(shí)間序列索引算法，并在Spark分布式計(jì)算框架下實(shí)現(xiàn)算法。首先，給出了基于Isax的分布式索引算法的樸素實(shí)現(xiàn)想法，指明了其存在的問(wèn)題。然后提出一種先建立索引結(jié)構(gòu)，再將時(shí)間序列哈希到相應(yīng)葉子節(jié)點(diǎn)的分布式索引算法。最終，構(gòu)建了一個(gè)完整的電力時(shí)間序列的近鄰近似查詢系統(tǒng)，再保證查詢精確率的前提下大大提高了計(jì)算效率。并在實(shí)驗(yàn)數(shù)據(jù)集上證明了算法的正確性、高效性和可擴(kuò)展性。

關(guān)鍵詞：時(shí)間序列;分布式;索引

DOI：10.15938/j.jhust.2021.06.011

中圖分類號(hào)： TP392

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 1007-2683（2021）06-0081-06

A Distributed Algorithm for Indexing Power Time Series

WU Yi1， GUO Qi-lin2， CHEN Hao-tian1， GUO Nai-wang1

（1.State Grid Shanghai Municipal Electric Power Company， Shanghai 200122， China;

2.School of Economics， Fudan University， Shanghai 200433， China）

Abstract：Time series research has been applied to more and more areas. More and more domain applications need to index and analyze massive time series， such as finance， electricity， bioinformatics， and so on. Such applications are often faced with hundreds of millions of time series of processing， and then identify some hidden pattern from the model. Firstly， we give a simple idea of the distributed indexing algorithm based on Isax， which points out its existing problems. Then we propose a distributed indexing algorithm to establish the index structure and then insert the time series to the corresponding leaf node. Finally， this paper constructs a complete approximation query system of power time series， and greatly improves the computational efficiency under the premise of ensuring the accuracy of query. The correctness， efficiency and expansibility of the algorithm are proved on the experimental data set.

Keywords：time series; distributed algorithm; index

0 引 言

隨著配用電網(wǎng)技術(shù)的發(fā)展、電力采集設(shè)備的更新，電力系統(tǒng)積累了海量用電負(fù)荷數(shù)據(jù)。而電網(wǎng)的穩(wěn)定運(yùn)行和智能化發(fā)展在很大程度上依賴于對(duì)這些數(shù)據(jù)的挖掘分析[1]，如用電預(yù)測(cè)、錯(cuò)峰調(diào)度、用戶用電行為模式識(shí)別、設(shè)備狀態(tài)和風(fēng)險(xiǎn)評(píng)估[2-3]等等。在這個(gè)過(guò)程中，我們會(huì)涉及到數(shù)以億計(jì)的數(shù)據(jù)資源的調(diào)取、運(yùn)算以及分類等，而這樣級(jí)別的運(yùn)算量對(duì)于計(jì)算性能、數(shù)據(jù)庫(kù)性能有著極高的要求，在數(shù)據(jù)挖掘領(lǐng)域，尤其是每天都有百萬(wàn)更新數(shù)據(jù)的電力數(shù)據(jù)分析領(lǐng)域，用更少的計(jì)算資源、更短的時(shí)間搜索到更加精確可靠的結(jié)果是我們的最終目標(biāo)，也是所有數(shù)據(jù)挖掘研究的前提條件。而在這些搜索的背后，都需要近似近鄰查詢。

在大規(guī)模的高維時(shí)間序列的應(yīng)用場(chǎng)景中，精確的近鄰查詢需要耗費(fèi)大量存儲(chǔ)和計(jì)算資源，實(shí)際應(yīng)用中效果不理想。近似近鄰查詢技術(shù)可以大幅度縮短查詢時(shí)間，同時(shí)效果比較好的近似近鄰查詢方法都可以保證查詢結(jié)果與精確查詢結(jié)果近似。由于其在的高應(yīng)用價(jià)值，近似近鄰技術(shù)被廣泛應(yīng)用于信息檢索，統(tǒng)計(jì)分析，機(jī)器學(xué)習(xí)等領(lǐng)域。

近年來(lái)，時(shí)間序列的近似近鄰查詢技術(shù)有了很大的進(jìn)展，但是隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，需要處理的數(shù)據(jù)規(guī)模越來(lái)越大。傳統(tǒng)的單機(jī)版索引算法和索引結(jié)構(gòu)往往只能處理小規(guī)模數(shù)據(jù)。大規(guī)模數(shù)據(jù)往往無(wú)法做到單機(jī)存儲(chǔ)，這些數(shù)據(jù)往往存儲(chǔ)于分布式系統(tǒng)中且需要一種分布式索引結(jié)構(gòu)來(lái)支持查詢和檢索。

隨著google、facebook等企業(yè)和實(shí)驗(yàn)室相繼開(kāi)源了Haoop、Stotm、Spark等分布式計(jì)算平臺(tái)，有效的管理和分析海量分布式數(shù)據(jù)成為可能。本文基于Spark分布式計(jì)算平臺(tái)提出一種使用Isax表達(dá)的分布式時(shí)間序列索引算法。

本文第2節(jié)介紹了Spark分布式計(jì)算平臺(tái)，Isax表達(dá)式以及時(shí)間序列上的分布式索引研究進(jìn)展。第三章介紹了基于Isax的分布式時(shí)間序列索引算法及其在Spark上的設(shè)計(jì)與實(shí)現(xiàn)。第四節(jié)分析討論了索引算法和基于索引的最近鄰查詢?cè)诖笠?guī)模時(shí)間序列數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。第五節(jié)介紹了算法在電力數(shù)據(jù)挖掘中的實(shí)際應(yīng)用。第六節(jié)對(duì)本文工作進(jìn)行了總結(jié)和展望。

1 相關(guān)工作

1.1 SPARK與MR編程模型

分布式編程模型（MapReduce，MR）[4]是一種用于并行運(yùn)算的編程范式，用戶無(wú)需關(guān)注分布式通信和傳輸?shù)募?xì)節(jié)，只需關(guān)注包裝在map、reduce中的核心業(yè)務(wù)邏輯，就可在分布式系統(tǒng)上運(yùn)行自己的程序。簡(jiǎn)單的說(shuō)，MR編程范式采用了”分而冶之”的思想，將一個(gè)大而復(fù)雜的作業(yè)分割成眾多小而簡(jiǎn)單的獨(dú)立任務(wù)，然后將這些任務(wù)分發(fā)給集群中的各節(jié)點(diǎn)獨(dú)立執(zhí)行。MR為用戶提供了一個(gè)極其簡(jiǎn)單的分布式編程模型。

主流的實(shí)現(xiàn)MR編程模型的框架主要有Google的Hadoop平臺(tái)和UC Berkeley AMP lab的Spark[5]。相對(duì)于Hadoop，Spark啟用了分布式內(nèi)存數(shù)據(jù)庫(kù)，可以在內(nèi)存中完成所有的數(shù)據(jù)分析操作再將結(jié)果存入集群，其在迭代計(jì)算中速度要遠(yuǎn)遠(yuǎn)快于Hadoop。同時(shí)其提供了更豐富的api接口，以及覆蓋整個(gè)數(shù)據(jù)分析流程的DAG圖，更有利于分布式算法的設(shè)計(jì)和實(shí)現(xiàn)。

1.2 時(shí)間序列表達(dá)式

時(shí)間序列通常維度非常高，高維空間下時(shí)間序列呈現(xiàn)稀疏性，導(dǎo)致不符合大數(shù)定律，統(tǒng)計(jì)結(jié)果不具備可信度。時(shí)間序列的降維手段主要有分段聚集近似PAA[6]，符號(hào)聚集近似SAX[7]和可索引的符號(hào)聚集近似iSAX[8]等等。分段段聚集近似PAA[6]。將時(shí)間序列在時(shí)間軸上劃分為若干段，每段用平均值來(lái)表示。SAX[7]將標(biāo)準(zhǔn)化后的時(shí)間序列PAA處理，然后根據(jù)高斯分布和子段值將序列離散化為符號(hào)串。iSAX時(shí)SAX基礎(chǔ)之上提出的一種多辨析率的符號(hào)化表示，通過(guò)選擇不同的基數(shù)大小表達(dá)不同的辨析率層次。

時(shí)間序列的索引方法中，效果比較好的主要有iSAX[8]索引，以及iSAX2.0[9]。iSAX2.0[9]通過(guò)增加bulk loading機(jī)制和一種基于統(tǒng)計(jì)的分裂策略大大減少了索引所需的時(shí)間，使得索引算法能夠處理數(shù)億級(jí)的時(shí)間序列。

但是不論是iSAX[8]還是iSAX2.0[9]都是單機(jī)版的算法，受到單機(jī)內(nèi)存和計(jì)算資源的制約，在面臨更大數(shù)據(jù)的時(shí)間序列時(shí)擴(kuò)展性不足。本文提出一種分布式iSAX索引算法。不僅提高了索引速度，而且具備很強(qiáng)的擴(kuò)展性。

1.3 分布式相似性索引算法

分布式索引算法不等于相似性索引算法。樹(shù)結(jié)構(gòu)相似性索引方法有很多，比如R樹(shù)、KD樹(shù)等。

經(jīng)典的KD樹(shù)會(huì)將原始的數(shù)據(jù)空間按數(shù)據(jù)的維度劃分為一棵二叉樹(shù)。也有解決kd樹(shù)在高維空間退化現(xiàn)象的隨機(jī)化kd樹(shù)的方法。李天駒等人提出一種面向KD樹(shù)建樹(shù)過(guò)程的多核并行算法-ParK[10]。FLANN[11]中包含的層次Kmeans樹(shù)，在每一層都使用Kmeans聚類，若類中節(jié)點(diǎn)小于某個(gè)閾

值則作為葉子節(jié)點(diǎn)，否則是中間節(jié)點(diǎn)繼續(xù)對(duì)節(jié)點(diǎn)下的數(shù)據(jù)進(jìn)行Kmeans聚類，Kmeans算法可以利用MR框架并行化，相比單機(jī)版提升了建樹(shù)的速度。但是這樣的Kmeans樹(shù)雖然能夠快速的找到近鄰候選集合，但是在樹(shù)的每一層都需要進(jìn)行一次Kmeans聚類所消耗的空間和時(shí)間資源還是非常之大。Murphy等的工作中介紹了這種算法的MR版本[12]。

傳統(tǒng)的樹(shù)結(jié)構(gòu)索引在大規(guī)模數(shù)據(jù)下往往迎來(lái)空間資源不足的局面。而基于哈希的索引方法有著良好的擴(kuò)展性，適合在分布式環(huán)境下處理海量的數(shù)據(jù)。

局部敏感哈希（LSH）[11]是最常見(jiàn)的數(shù)據(jù)無(wú)關(guān)哈希方法。其基本思想是在空間轉(zhuǎn)換中保持原始空間和轉(zhuǎn)換后空間的相似性。原始空間中越相似的兩個(gè)數(shù)據(jù)點(diǎn)，經(jīng)過(guò)哈希之后，越有可能被哈希到同一個(gè)桶，桶的編號(hào)就可以作為他們的整體編碼。常見(jiàn)的有基于歐式距離、余弦距離、Jaccard距離的局部敏感哈希算法。局部敏感哈希算法非常適合利用MR框架并行化，Szmit等[13]已經(jīng)實(shí)現(xiàn)了相應(yīng)的分布式版本。LSH為了有更好的索引效果，并行化的LSH算法往往需要經(jīng)歷多輪不同節(jié)點(diǎn)間的數(shù)據(jù)傳輸（shuffle）。本文基于isax索引的特性，提出了一種只需要一次shuffle的基于MR的分布式時(shí)間序列索引算法。

2 分布式的時(shí)間序列索引算法

2.1 并行模式分析

2.1.1 樸素想法

1）單機(jī)版建立isax索引如圖1所示，每條時(shí)間序列計(jì)算isax表達(dá)，并分配到一個(gè)節(jié)點(diǎn)，如果節(jié)點(diǎn)上時(shí)間序列的數(shù)量超過(guò)閾值，則進(jìn)行split。而split的策略是從左到右依次基數(shù)加倍，將父節(jié)點(diǎn)上的時(shí)間序列根據(jù)新基數(shù)重新計(jì)算isax表達(dá)并分配到新的節(jié)點(diǎn)上。

2）由上述過(guò)程可以發(fā)現(xiàn)，每個(gè)時(shí)間序列在這個(gè)樹(shù)中的操作是相互獨(dú)立的?？梢詫⒚恳粚拥膇sax表達(dá)式視為哈希桶的key，每一層的各個(gè)節(jié)點(diǎn)分別是不同key值的哈希桶。樸素的分布式建樹(shù)可以視為一個(gè)層次的哈希過(guò)程，每一層某個(gè)哈希桶中數(shù)據(jù)量小于閾值為葉子，否則繼續(xù)進(jìn)入下一輪哈希。但是這樣的分布式算法擴(kuò)展性較差，且面臨一系列問(wèn)題。

2.1.2 樸素想法存在的問(wèn)題

1）算法存在數(shù)據(jù)傾斜問(wèn)題：其一方面是由于時(shí)間序列的分布本身并不均勻，有些中間節(jié)點(diǎn)分裂后信息熵減少有限。另一方面是由于程序多次使用shuffle算子。

2）算法耗費(fèi)大量的傳輸時(shí)間，成為性能瓶頸。在建立索引樹(shù)的每一層節(jié)點(diǎn)時(shí)都需要一次shuffle過(guò)程，而shuffle過(guò)程消耗大量的傳輸時(shí)間，是hadoop，spark這類分布式計(jì)算平臺(tái)的性能瓶頸。

3）解決方案：①讓shuffle算子提高并行度，緩解數(shù)據(jù)傾斜問(wèn)題;

②把部分?jǐn)?shù)據(jù)清洗掉，比如數(shù)據(jù)集中中很多0.0的時(shí)間序列，往往是導(dǎo)致數(shù)據(jù)傾斜的原因，需要過(guò)濾掉;

③盡量避免join操作，將reduce join改為map join，用廣播的形式存放小rdd。

這些方案能夠大大優(yōu)化算法的性能，但是卻是治標(biāo)不治本，算法的shuffle次數(shù)依賴于樹(shù)的層次無(wú)法減少。因此我們提出了一種建立索引不依賴于樹(shù)的層次、只需要經(jīng)過(guò)一次shuffle的分布式索引算法。

2.2 算法設(shè)計(jì)

可以發(fā)現(xiàn)，樸素想法中每次shuffle過(guò)程的目的只是為了通過(guò)獲得哈希到每個(gè)索引節(jié)點(diǎn)的時(shí)間序列數(shù)目判斷是否需要分裂。換而言之，每層的shuffle都只是為了獲得樹(shù)的索引結(jié)構(gòu)。改進(jìn)算法的思想就是先通過(guò)所有的時(shí)間序列通過(guò)一次shuffle建立整棵索引樹(shù)的結(jié)構(gòu)，再并行的將所有時(shí)間序列分配到相應(yīng)的葉子節(jié)點(diǎn)。

算法過(guò)程如下：

1）生成一個(gè)長(zhǎng)度為depth的由每一層基組成的集合。

2）并行對(duì)每條時(shí)間序列計(jì)算其在索引中經(jīng)過(guò)的長(zhǎng)度為depth的路徑集合。

3）對(duì)所有時(shí)間序列的路徑集合中的每個(gè)iSAX索引節(jié)點(diǎn)進(jìn)行計(jì)數(shù)。

4）若某個(gè)iSAX索引節(jié)點(diǎn)計(jì)數(shù)值大于閾值，則其是中間節(jié)點(diǎn)，否則是葉子節(jié)點(diǎn)。

5）并行將每條時(shí)間序列插入到葉子節(jié)點(diǎn)中

算法通過(guò)計(jì)算每一個(gè)時(shí)間序列的路徑，對(duì)路徑上所有節(jié)點(diǎn)計(jì)數(shù)，然后根據(jù)每個(gè)節(jié)點(diǎn)計(jì)數(shù)值與閾值的關(guān)系獲得了整棵樹(shù)的結(jié)構(gòu)。如表1、表2。

如果分裂閾值為2，那么中間節(jié)點(diǎn)為0.2_0.2_1.2， 0.4_0.2_1.2.其他都為葉子節(jié)點(diǎn).因此我們就獲得了iSAX索引樹(shù)的形狀。找到時(shí)間序列對(duì)應(yīng)的葉子節(jié)點(diǎn)的具體的做法是再對(duì)時(shí)間序列計(jì)算一次路徑，找到路徑中第一個(gè)不為中間節(jié)點(diǎn)的iSAX表達(dá)，該表達(dá)即時(shí)間序列對(duì)應(yīng)的葉子節(jié)點(diǎn).比如對(duì)于時(shí)間序列t= （-1.3，-0.35，0.35），發(fā)現(xiàn)第三層的iSAX表達(dá)式0.4_1.4_1.2不在中間節(jié)點(diǎn)列表中，將其作為插入的葉子節(jié)點(diǎn)表達(dá)式.

2.3 索引存儲(chǔ)結(jié)構(gòu)

為了適應(yīng)分布式的插入和查詢，我們需要放棄單機(jī)版的索引存儲(chǔ)方案，因?yàn)槠鋾?huì)成為整個(gè)并行過(guò)程中的瓶頸。我們?cè)趆adoop大數(shù)據(jù)分析架構(gòu)的基礎(chǔ)上，采用Hbase技術(shù)對(duì)用電數(shù)據(jù)進(jìn)行存儲(chǔ)與管理，提出一種基于iSAX的分布式索引技術(shù)對(duì)用電數(shù)據(jù)進(jìn)行存儲(chǔ)索引，實(shí)現(xiàn)海量時(shí)間序列的高效查詢與匹配，如圖2所示。

在HBase中，建立表用于存放iSAX的索引結(jié)構(gòu)以及所有的原始時(shí)間序列。我們將每一個(gè)iSAX節(jié)點(diǎn)作為一行存放在HBase中，每一個(gè)iSAX節(jié)點(diǎn)作為一個(gè)對(duì)象，對(duì)象的內(nèi)容除了原始iSAX的內(nèi)容還包括節(jié)點(diǎn)類型等內(nèi)容。根節(jié)點(diǎn)的key為“root_node_00”，中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)的key為iSAX表達(dá)，value是iSAX索引節(jié)點(diǎn)對(duì)象序列化的byte數(shù)組。

3 實(shí)驗(yàn)和結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)是在Spark平臺(tái)下完成的，硬件設(shè)備為8臺(tái)ubuntu15.04的系統(tǒng)，其中主節(jié)點(diǎn)配置為3核16G內(nèi)存;從設(shè)備節(jié)點(diǎn)采用配置為3核10G內(nèi)存。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

1）上海市浦東居民和工商業(yè)用戶的日凍結(jié)量，它包括了200萬(wàn)個(gè)電表850天的用電數(shù)據(jù)，數(shù)據(jù)集的大小為10GB（以下簡(jiǎn)稱200萬(wàn)用戶用電數(shù)據(jù)）。

2）典型上海市30萬(wàn)用戶用電數(shù)據(jù)，365天日凍結(jié)量（以下簡(jiǎn)稱30萬(wàn)用戶用電數(shù)據(jù)）。

3.3 實(shí)驗(yàn)參數(shù)

根據(jù)isax索引構(gòu)建的描述，本實(shí)驗(yàn)設(shè)置的參數(shù)如下：

1）30萬(wàn)用戶用電數(shù)據(jù)：根節(jié)點(diǎn)的基數(shù)4;

分段數(shù)=14;分裂閾值=100;原始時(shí)間序列長(zhǎng)度=364;

2）100萬(wàn)、200萬(wàn)用戶用電數(shù)據(jù)：根節(jié)點(diǎn)的基數(shù)4;分段數(shù)=17;分裂閾值=100;原始時(shí)間序列長(zhǎng)度=850;限制最大樹(shù)高為52;

3.4 結(jié)果及分析

首先對(duì)單機(jī)版的時(shí)間序列索引算法和本文提出的分布式算法的運(yùn)行效率進(jìn)行比較.為了證明分布式索引算法的高效性還實(shí)現(xiàn)了樸素的分布式索引版本并增加實(shí)驗(yàn)對(duì)比。

圖3實(shí)驗(yàn)用來(lái)說(shuō)明本文提出的算法的擴(kuò)展性。從圖一可以看出在100萬(wàn)和200萬(wàn)數(shù)據(jù)下，隨著節(jié)點(diǎn)的增多，算法的運(yùn)行時(shí)間也線性的減少。但是在30萬(wàn)數(shù)據(jù)集下，運(yùn)行時(shí)間并沒(méi)有隨著節(jié)點(diǎn)數(shù)量增加而減少，反而有所增加。原因是增加節(jié)點(diǎn)減少計(jì)算時(shí)間的同時(shí)，反而消耗了更多的分布式通信調(diào)度的時(shí)間。因此需要根據(jù)數(shù)據(jù)量選擇合適的并行度。

圖4比較的是單機(jī)版及兩種分布式算法在不同規(guī)模數(shù)據(jù)集下的運(yùn)行效率對(duì)比。從圖4可以看出我們的算法在運(yùn)行效率遠(yuǎn)高于樸素的分布式索引算法。這是因?yàn)闃闼胤植际剿惴ㄔ诿恳粚佣夹枰?jīng)歷一次shuffle，使得傳輸時(shí)間成為了算法的瓶頸。而本文的分布式算法通過(guò)先建樹(shù)再插入的想法，只需要一次shuffle，從而避免了這個(gè)問(wèn)題。單機(jī)版的索引算法在30萬(wàn)數(shù)據(jù)下就需要運(yùn)行8h，在我們的機(jī)器配置下無(wú)法在超過(guò)百萬(wàn)的數(shù)據(jù)集下運(yùn)行。

3.5 查詢效果展示

查詢[7]可以指定返回與查詢序列相似的若干條時(shí)間序列數(shù)目，我們選取返回5條時(shí)間序列為例，展示查詢效果。其中序列1代表查詢序列，序列2-6代表返回的相似時(shí)間序列。查詢電表號(hào)為2470032、4041308和7073795的相似序列發(fā)現(xiàn)，返回的時(shí)間序列形狀上查詢時(shí)間序列均非常相似。其中綠色時(shí)間序列為所要查詢的時(shí)間序列。可以發(fā)現(xiàn)查詢到的時(shí)間序列整體上與目標(biāo)非常接近。

3.6 查詢性能對(duì)比

下面分別對(duì)本地順序存儲(chǔ)的時(shí)間序列和基于Hbase的iSAX索引的時(shí)間序列數(shù)據(jù)進(jìn)行查詢響應(yīng)速度對(duì)比實(shí)驗(yàn)，結(jié)果如表4所示。

比較兩者的平均查詢時(shí)間可知，當(dāng)時(shí)間序列的數(shù)量超過(guò)10000時(shí)，在HBase的查詢速度超過(guò)在本地。當(dāng)時(shí)間序列的數(shù)量較小時(shí)，因?yàn)楸镜豂O的速度大于網(wǎng)絡(luò)IO的速度，所以Hbase的查詢速度小于本地。當(dāng)時(shí)間序列數(shù)量越大，Hbase查詢的優(yōu)越性就越能體現(xiàn)，如表5所示。

分布式索引算法的優(yōu)勢(shì)在于可以快速對(duì)海量時(shí)間序列建立索引，以此來(lái)應(yīng)對(duì)相似序列查詢，這在數(shù)據(jù)挖掘中有重要意義。同在具體的分析中，如聚類、關(guān)聯(lián)，異常識(shí)別等，通過(guò)大幅節(jié)約數(shù)據(jù)從數(shù)據(jù)庫(kù)提取的時(shí)間，可以大大加速分析過(guò)程。

4 結(jié) 論

用電負(fù)荷大數(shù)據(jù)分析為電力系統(tǒng)的穩(wěn)定運(yùn)行和智能化發(fā)展提供了數(shù)據(jù)支撐，而快速有效的索引對(duì)日益龐大的數(shù)據(jù)的存儲(chǔ)和讀取至關(guān)重要。本文基于上海市浦東新區(qū)200萬(wàn)電表850d時(shí)間序列數(shù)據(jù)，通過(guò)Spark平臺(tái)實(shí)現(xiàn)了分布式索引算法，能夠快速準(zhǔn)確的進(jìn)行時(shí)間序列查詢，同時(shí)可以建立多條索引，對(duì)不同周期的時(shí)間序列進(jìn)行查詢，返回多條相似的完整的時(shí)間序列。分布式索引算法避免了通過(guò)全局掃描的方法查詢，速度比單機(jī)版高數(shù)十倍，可以有效的提高數(shù)據(jù)挖掘的產(chǎn)出率，不僅保證了數(shù)據(jù)分析的正常運(yùn)行，還可以和數(shù)據(jù)挖掘算法有機(jī)結(jié)合大大提高分析效率。除了用電負(fù)荷數(shù)據(jù)，我們的分布式索引算法同樣可以應(yīng)用到更多存在海量時(shí)間序列數(shù)據(jù)的領(lǐng)域。

參 考 文 獻(xiàn)：

[1] 張曉晨. 電力大數(shù)據(jù)應(yīng)用研究與展望[J]. 山東工業(yè)技術(shù)， 2017（3）：155.

ZHANG Xiaochen. Research and Prospects of Electric Power Big Data Application[J]. Shandong Industrial Technology， 2017（3）：155.

[2] 鄭海雁， 金農(nóng)， 季聰，等. 電力用戶用電數(shù)據(jù)分析技術(shù)及典型場(chǎng)景應(yīng)用[J]. 電網(wǎng)技術(shù)， 2015， 39（11）：3147.

ZHEN Haiyan， JIN Nong， JI Cong， et al. Data Analysis Technology and Application of Electric Power User in Typical Scenarios[J]. Power Grid Technology， 2015， 39（11）：3147.

[3] 沈玉玲， 呂燕， 陳瑞峰. 基于大數(shù)據(jù)技術(shù)的電力用戶行為分析及應(yīng)用現(xiàn)狀[J]. 電氣自動(dòng)化， 2016， 38（3）：50.

SHEN Yulin， LV Yan， CHEN Ruifeng. Electric Power User Behavior Analysis and Application Status Based on Big Data Technology[J]. Electric Automation， 2016， 38（3）：50.

[4] DEAN J， GHEMAWAT S. Map Reduce： Simplified Data Processing on Large Clusters[J]. Communications of the ACM， 2008， 51（1）： 107.

[5] ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： Cluster Computing with Working Sets[C]// Hot Cloud， 2010： 10.

[6] KEOGH Eamonn， CHAKRABARTI Kaushik， PAZZANI Michael， et al. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J]. Knowledge and Information Systems， 2001， 3（3）： 263.

[7] JUNEJO Imran N.， AGHBARI Zaher Al. Using SAX Representation for Human Action Recognition[J]. Journal of Visual Communication and Image Representation， 2012， 23（6）： 853.

[8] SHIEH Jin， KEOGH Eamonn. iSAX： Disk-aware Mining and Indexing of Massive Time Series Datasets[J]. Data Mining and Knowledge Discovery， 2009， 19（1）： 24.

[9] CAMMERRA A， PALPANAS T， SHIEH J. iSAX2. 0： Indexing and Mining One Billion Teme Serees[C]// International Conference on Data Mining. Washington： IEEE. 2010： 1.

[10]李天駒， 張錚， 張為華. 高效KD樹(shù)并行算法優(yōu)化[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2015， 24（8）：1.

LI Tianju， ZHANG Zheng， ZHANG Weihua. Efficient KD Tree Parallel Algorithm Optimization[J]. Computer System Applicatoin， 2015， 24（8）：1.

[11]MUJA M， LOWE D G. Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration[J]. VISAPP （1）， 2009， 2（331/340）： 2.

[12]HUTCHISON S A. Distributed Kernelized Locality-Sensitive Hashing for Faster Image Based Navigation[R]. Air Force Institute of Technology Wright-Patterson Afb OH Graduate School of Engineering and Management， 2015.

[13]SZMIT R. Locality Sensitive Hashing for Similarity Search Using Map Reduce on Large Scale Data[M]//Language Processing and Intelligent Information Systems. Springer Berlin Heidelberg， 2013： 171.

（編輯：王 萍）

收稿日期： 2020-12-03

基金項(xiàng)目：

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（2017YFC0803700）;上海市科委科研計(jì)劃項(xiàng)目（19DZ2252800）;國(guó)家電網(wǎng)公司科技項(xiàng)目（52094016000A）;國(guó)網(wǎng)上海市電力公司科技項(xiàng)目（52094020001A）.

作者簡(jiǎn)介：

吳 裔（1987—），男，博士，工程師;

陳顥天（1996—），男，博士研究生.

通信作者：

郭棋林（1984—），男，碩士，E-mail：15210240072@fudan.edu.cn.

3073501908223