基于時(shí)間條件提取序列的數(shù)據(jù)流偏好查詢

李潤(rùn)澤，孫雪姣

（煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院，山東煙臺(tái) 264005）

0 引言

隨著網(wǎng)絡(luò)和信息技術(shù)的不斷發(fā)展，連續(xù)、快速、實(shí)時(shí)、無(wú)限的數(shù)據(jù)元素序列形成數(shù)據(jù)流被應(yīng)用在新的數(shù)據(jù)流應(yīng)用中，在這些應(yīng)用中，新信息不斷被添加，現(xiàn)有信息不斷被改變或刪除。從這些無(wú)限可能的數(shù)據(jù)集中提取有用信息是數(shù)據(jù)流技術(shù)［1-3］的重要任務(wù)之一。正因?yàn)閿?shù)據(jù)的不斷變化，使得用戶需要長(zhǎng)期地連續(xù)查詢，同時(shí)查詢結(jié)果需要不斷地更新，因此對(duì)數(shù)據(jù)流的偏好推理和偏好查詢成為當(dāng)今熱點(diǎn)研究領(lǐng)域之一。

StreamSeq 語(yǔ)言使用了TPref［4］的語(yǔ)義形式，TPref 的命題是簡(jiǎn)單等式，基本公式為時(shí)態(tài)判斷“直到”。相比之下，StreamSeq 語(yǔ)言更具有準(zhǔn)確性，支持對(duì)不同屬性和時(shí)刻的判斷，即用戶對(duì)一個(gè)屬性的偏好會(huì)受到另一個(gè)屬性的值的影響，且基本公式包括時(shí)態(tài)判斷“現(xiàn)在”和“未來(lái)”，因此更適合運(yùn)用在對(duì)數(shù)據(jù)流的處理中。

StreamSeq 語(yǔ)言、提取序列和占優(yōu)對(duì)比算法的學(xué)習(xí)都是在數(shù)據(jù)流上重要的操作。本文提出了偏好查詢算法，首先使用基于時(shí)間條件的數(shù)據(jù)流提取算法，將數(shù)據(jù)流按照時(shí)間順序、以序列的形式進(jìn)行提取，再通過(guò)占優(yōu)對(duì)比算法對(duì)提取序列偏好進(jìn)行比較，得到最符合用戶偏好的信息。以上述主要概念為基礎(chǔ)，本文展開(kāi)了如下工作：

1）設(shè)計(jì)條件偏好查詢語(yǔ)言StreamSeq，在偏好規(guī)則中加入時(shí)間條件，并驗(yàn)證偏好規(guī)則的時(shí)間兼容性；

2）設(shè)計(jì)從數(shù)據(jù)流中提取序列的算法，使用基于哈希的訪問(wèn)方法來(lái)降低時(shí)間復(fù)雜性，根據(jù)一組標(biāo)識(shí)符屬性對(duì)數(shù)據(jù)流進(jìn)行識(shí)別檢索，每個(gè)時(shí)刻、每個(gè)對(duì)象在標(biāo)識(shí)符屬性上具有唯一的值；

3）設(shè)計(jì)序列間占優(yōu)對(duì)比的算法，根據(jù)時(shí)間偏好條件得出占優(yōu)序列；

4）通過(guò)合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)結(jié)果表明，與其他數(shù)據(jù)流查詢的方法相比，本文方法所需的運(yùn)行時(shí)間短，得到結(jié)果的效率更高。

1 相關(guān)工作

1.1 偏好推理

偏好推理是與偏好查詢相關(guān)的一個(gè)基本問(wèn)題，用來(lái)得到數(shù)據(jù)流中最符合用戶需求的信息。

文獻(xiàn)［5］中提出了Preference SQL 語(yǔ)言，首次引入了偏好推理的概念，它通過(guò)基于嚴(yán)格偏序的偏好模型擴(kuò)展了SQL（Structured Query Language），提出了基本偏好構(gòu)造函數(shù)，將偏好查詢轉(zhuǎn)換為標(biāo)準(zhǔn)的SQL 查詢。CP-nets［6-7］使用圖模型，在偏好推理過(guò)程中，根據(jù)偏好關(guān)系用網(wǎng)絡(luò)結(jié)構(gòu)得到最優(yōu)結(jié)果的過(guò)程。支持條件偏好的CPrefSQL［8］查詢語(yǔ)言在Preference SQL 的基礎(chǔ)上引入了條件偏好，StreamSeq 語(yǔ)言在CPrefSQL語(yǔ)言的基礎(chǔ)上加入了時(shí)間條件，主要用于處理具有時(shí)間條件偏好的連續(xù)查詢。

1.2 偏好查詢

連續(xù)查詢是指一個(gè)查詢確立后將長(zhǎng)時(shí)間連續(xù)執(zhí)行。對(duì)數(shù)據(jù)流在一段時(shí)間內(nèi)連續(xù)查詢，隨著新數(shù)據(jù)的到達(dá)將不斷產(chǎn)生新的查詢結(jié)果，而數(shù)據(jù)流偏好查詢是一種在查詢過(guò)程中考慮用戶偏好的連續(xù)查詢。

近年來(lái)，數(shù)據(jù)流環(huán)境下的連續(xù)查詢已被深入研究，包括連續(xù)join 查詢［9］、連續(xù)skyline 查詢［10］、連續(xù)離群點(diǎn)監(jiān)測(cè)［11］、連續(xù)top-k查詢［12-13］等查詢方法。文獻(xiàn)［14］中首次提出偏好查詢的概念，用SKYLINEOF 子句擴(kuò)展SQL，設(shè)計(jì)skyline 查詢算法，使用索引完成數(shù)據(jù)流偏好查詢；傳統(tǒng)的CQL（Continuous Query Language）［15］不支持序列結(jié)構(gòu)，CQL 等效算法［16］則在CQL 中加入了元組，以一組元組表示序列完成對(duì)序列的處理；Top-k算法［17］采用“格”框架（Lattice），實(shí)現(xiàn)了基于CP-nets的偏好查詢；Incpartition 算法［18］更新了partition 算法［19］，使用cp-queries 規(guī)則對(duì)數(shù)據(jù)流元組分區(qū)，在分區(qū)中尋找并返回占優(yōu)元組。本文算法加入了時(shí)間索引，使用基于Hash 的訪問(wèn)方法對(duì)數(shù)據(jù)序列進(jìn)行處理，占優(yōu)對(duì)比得到最優(yōu)序列，能減少序列間對(duì)象的對(duì)比次數(shù)，提高偏好信息的查詢效率。

2 StreamSeq時(shí)間條件偏好查詢語(yǔ)言

本章將介紹StreamSeq 語(yǔ)句和相關(guān)定義，將時(shí)間條件引入偏好關(guān)系中，并證明其時(shí)間兼容性。

定義1序列。設(shè)X={A1，A2，…，Al}為屬性集，X上的對(duì)象集為O(X)=Dom(A1)×Dom(A2)× …×Dom(Al)，其中Dom(Ai)為Ai的定義域。X上的序列是一個(gè)有序的對(duì)象集，因此對(duì)于i∈{1，2，…，k}，有oi∈O(X)。

定義2偏好規(guī)則。在偏好規(guī)則中命題的形式表示為Aθa，其中a∈Dom(A)，θ∈{<，≤，=，≠，≥，>}。使用a=Q(A)表示a滿足命題Q(A)，SQ(A)={a∈Dom(A)|a=Q(A)}表示滿足Q(A)的值的集合，用于構(gòu)造定義3 中的基本公式。

定義3基本公式。如果存在命題F和命題G，那么用來(lái)判定命題為T(mén)rue 和False 的為基本公式；如果F和G是基本公式，那么?F，?G，(F∧G)，(F∨G)和(FsinceG)也為基本公式。序列在位置i∈{1，2，…，k}（由(s，i)=F表示）滿足公式F的概念定義歸納如下：

由基本公式可以推出子公式：

這些子公式用于構(gòu)成時(shí)間條件（定義4）。

定義4時(shí)間條件。F=(F1∧F2∧… ∧Fp)為時(shí)間條件，其中F1∧F2∧… ∧Fp是子公式。F?是F中所有子公式的合取，F(xiàn)0是F中所有命題的合取。在時(shí)間條件偏好（Temporal Conditional Preference，TCP）規(guī)則和TCP 理論（定義5）中采用了時(shí)間條件。

定義5TCP 規(guī)則和TCP 理論。設(shè)X為一組屬性集，時(shí)間條件偏好規(guī)則是格式為φ：Cφ→Q+φ(Aφ)?Q-φ(Aφ)[Wφ]的表達(dá)式，Att(F)表示出現(xiàn)在F中的屬性。其中：

給出TCP 理論Φ，TCP 規(guī)則φ∈Φ。設(shè)存在s和s′兩個(gè)序列和位置i，定義s?φs′，那么有：

例1 假設(shè)一個(gè)足球教練可以訪問(wèn)提供足球比賽實(shí)時(shí)數(shù)據(jù)的信息系統(tǒng)，這些數(shù)據(jù)包括當(dāng)前球員的位置、球員是否持球和球員移動(dòng)的類(lèi)型。教練希望根據(jù)以下偏好選擇最佳球員：

1）如果在某一個(gè)時(shí)刻，球員控球，并且在此時(shí)刻之前，該球員處于防守中場(chǎng)，那么教練更喜歡該球員去中場(chǎng)而不是防守中場(chǎng)，與球員移動(dòng)的類(lèi)型無(wú)關(guān)。

2）如果在某一個(gè)時(shí)刻，球員沒(méi)有控球，而在這一時(shí)刻之前，球員控球并且處于進(jìn)攻中間位置，那么教練更喜歡球員在中場(chǎng)而不是進(jìn)攻中間位置。

3）橫向移動(dòng)比前進(jìn)移動(dòng)更好。

給出屬性集Pp（球員的位置）、Tt（球員是否持球）和Mm（球員移動(dòng)的類(lèi)型）。Pp的值是防守區(qū)域（aa）、防守中場(chǎng)區(qū)域（ab）、中場(chǎng)（ac）、進(jìn)攻中場(chǎng)區(qū)域（ad）和進(jìn)攻區(qū)域（ae）；當(dāng)球隊(duì)控球時(shí)用1 表示，否則用0 表示；移動(dòng)的類(lèi)型有前進(jìn)移動(dòng)（Qi）、后退移動(dòng)（Ho）和橫向移動(dòng)（pi）。序列s=代表運(yùn)動(dòng)員s的運(yùn)動(dòng)軌跡為：在中場(chǎng)無(wú)持球前進(jìn)，在中場(chǎng)持球做橫向移動(dòng)，在防守中間區(qū)域持球做向后移動(dòng)，用-s表示球員控球，運(yùn)動(dòng)軌跡如圖1 所示。使用時(shí)間偏好理論Φ={φ1，φ2，φ3}來(lái)表示偏好信息。

圖1 運(yùn)動(dòng)員s的運(yùn)動(dòng)軌跡Fig.1 Trajectory of athletes

根據(jù)TCP 理論Φ={φ1，φ2，φ3}，對(duì)以下序列的優(yōu)先級(jí)進(jìn)行推理。

由φ1可知在第2 個(gè)位置處sa?φ1sc且sb?φ1sc，由φ2可知在第4 個(gè)位置處sb?φ2sc，因此sb?Φsa?Φsc。

定義6時(shí)間兼容性。設(shè)φ和φ′為兩個(gè)TCP 規(guī)則，且Cφ=(F1∧F2∧… ∧Fp)，Cφ′=(F′1∧F′2∧… ∧Fp′)。對(duì) 于i∈{1，2，…，p}，j∈{1，2，…，q}，如果Fi和Fj′在時(shí)間上都是兼容的，那么φ和φ′時(shí)間兼容。

設(shè)Φ為T(mén)CP 理論，φ為T(mén)CP 規(guī)則，符號(hào)Φφ表示Φ和φ是時(shí)間兼容的。Φφ的兼容性測(cè)試可以僅使用TCP 規(guī)則的非時(shí)間部分來(lái)完成，給定一個(gè)TCP 規(guī)則φ，符號(hào)φ0表示從φ中獲取一個(gè)規(guī)則，用代替Cφ。例如，對(duì)于例1 中的TCP 規(guī)則，有。從一組TCP規(guī)則Φφ中提取的條件偏好理論被定義為?？梢葬槍?duì)每個(gè)φ∈Φ來(lái)檢測(cè)TCP 理論φ的時(shí)間兼容性。引理1和引理2 驗(yàn)證了TCP 理論具有時(shí)間兼容性。

引理1設(shè)φ和φ′為兩個(gè)TCP 規(guī)則，如果存在一個(gè)包含位置i的序列s使(s，i)=，(s，i)=，那么φ和φ′是時(shí)間兼容的。

證明 假設(shè)φ和φ′為兩個(gè)TCP 規(guī)則，如果存在一個(gè)包含位置i的序列s使(s，i)=，(s，i)=，但φ和φ′是不兼容的。如果φ和φ′不兼容，那么在中至少有一個(gè)子式F，在中至少有一個(gè)子式G，F(xiàn)和G在時(shí)間上不兼容。要做到這一點(diǎn)，有以下3 種情況：

1）F=First，G=PreQ(A)，G=SomePreQ(A)或G=AllPreQ(A)；如果i=1，那么(s，i)=F，但是(s，i) ≠G；如果i>1，那么(s，i)=G，但是(s，i) ≠F，所以在這兩種情況下都兼容，與假設(shè)矛盾。

2）F=PreQ(A)，G=AllPreQ′(A) 或G=PreQ′(A)，SQ(A)∩SQ′(A)=?；在s中沒(méi)有這樣的位置i使得(s，i)=F，(s，i)=G，所以與假設(shè)矛盾。

3）F=AllPreQ(A)，G=PreQ′(A)，G=SomePreQ′(A)或G=AllPreQ′(A)，SQ(A)∩SQ′(A)=?。s中沒(méi)有這 樣的位置i使得(s，i)=F，(s，i)=G，所以與假設(shè)矛盾。 證畢。

引理2Φ是一個(gè)TCP 理論，對(duì)于所有的φ∈Φ，如果Γ(Φφ)是時(shí)間兼容的，那么Φ也是時(shí)間兼容的。

證明 假設(shè)Φ是一個(gè)TCP 理論，對(duì)于所有的φ∈Φ，如果Γ(Φφ)是時(shí)間兼容的，那么Φ也是時(shí)間兼容的。如果Φ在時(shí)間上不兼容，則存在規(guī)則φ1，φ2，…，φm∈Φ和序列s1，s2，…，sm∈Seq(X)使得Cs1?φ1Cs2?φ2…Csm?φms1。根據(jù)定義，在比較序列s1，s2，…，sm中存在共同的位置i，使得s1[1，i-1]=s2[1，i-1]=…=sm[1，i-1]，(s1，i)=φ1，(s1，i)=φ2，…，(s1，i)=φm。根據(jù)引理1，規(guī)則φ1，φ2，…，φm是時(shí)間兼容的，因此這些規(guī)則在同一組兼容的規(guī)則中，然而由兼容的集合Φφ產(chǎn)生的條件偏好理論Γ(Φφ)具有時(shí)間兼容性，與假設(shè)矛盾。 證畢。

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

本章詳細(xì)介紹了如何利用提取序列算法EXT sequences（EXTract sequences）對(duì)數(shù)據(jù)流中的序列進(jìn)行提取，對(duì)提取的序列執(zhí)行占優(yōu)對(duì)比（Dominant Contrast，DC）算法得到占優(yōu)序列，并分析了算法的時(shí)間復(fù)雜度。

定義7序列識(shí)別。設(shè)X為一組屬性，Y和Z為兩個(gè)不相交的集合，使得Y∪Z=X。識(shí)別序列的形式為sz=，對(duì)于i∈{1，2，…，k}，z∈O(Z)有oi∈O(Y)。

定義8序列提取。序列提取根據(jù)一組屬性標(biāo)識(shí)符Z在數(shù)據(jù)流S上檢索識(shí)別的序列（定義7）。在每個(gè)時(shí)刻，每個(gè)對(duì)象必須在屬性標(biāo)識(shí)符Z上具有唯一的值，以便在對(duì)象和結(jié)果序列之間保持一對(duì)一的關(guān)系。

算法1 使用哈希表H#來(lái)增量地執(zhí)行序列提取，基于時(shí)間滑動(dòng)窗口，以秒為單位接收時(shí)間范圍參數(shù)k。時(shí)間滑動(dòng)范圍為ks，時(shí)間滑動(dòng)間隔為1 s。參數(shù)k和時(shí)間滑動(dòng)間隔用于從數(shù)據(jù)流中選擇元組的一部分，X用于對(duì)序列中具有相同標(biāo)識(shí)符的元組進(jìn)行分組。

算法1 提取序列算法（EXT sequences）。

輸入 數(shù)據(jù)流S，屬性標(biāo)識(shí)符Z，時(shí)間范圍參數(shù)k；

輸出 哈希表H#中的序列。

哈希表H#：(z?sz)將每個(gè)識(shí)別符z與識(shí)別的序列sz關(guān)聯(lián)，o/Z是從對(duì)象o中移除z中的屬性標(biāo)識(shí)符，當(dāng)前時(shí)刻數(shù)據(jù)流S中的對(duì)象集合用S[λ]來(lái)表示。在第一次迭代之前，哈希表H#是一個(gè)空表，此后在每個(gè)時(shí)刻，提取序列算法更新H#并返回序列，直到當(dāng)前時(shí)刻λ。提取序列算法的時(shí)間滑動(dòng)間隔設(shè)置為1 s，如果對(duì)象的時(shí)間戳小于或等于λ-k，則該對(duì)象過(guò)期，Delete指從sz中刪除過(guò)期的對(duì)象。

提取序列算法的第1 個(gè)循環(huán)（第1）～5）行）將對(duì)象插入到它們各自的序列中，這個(gè)任務(wù)的成本是，其中：n是S[λ]中的對(duì)象數(shù)，l是s的屬性數(shù)。因?yàn)槊總€(gè)時(shí)刻，標(biāo)識(shí)符z都有一個(gè)唯一的對(duì)象，即，因此對(duì)象插入的成本為O(nl)。第2 個(gè)循環(huán)（第6）行）的成本為O(nk)，k為時(shí)間范圍。因此提取序列算法的復(fù)雜度為O(nl+nk)，即O(n)。

算法2 占優(yōu)對(duì)象查找（Find Dominant Object，F(xiàn)DO）算法。

輸入 條件偏好理論Γ，對(duì)象o+和對(duì)象o-；

輸出 占優(yōu)對(duì)象o′。

FDO 算法使用深度優(yōu)先搜索尋找從對(duì)象o+到對(duì)象o-的規(guī)則，用來(lái)驗(yàn)證序列間對(duì)應(yīng)位置i處對(duì)象s[i]是否優(yōu)于對(duì)象s′[i]。首先循環(huán)第1）～6）行，通過(guò)迭代尋找符合偏好條件的目標(biāo)對(duì)象，創(chuàng)建包括轉(zhuǎn)換為區(qū)間符號(hào)對(duì)象o+的堆棧，IntervalObject(o+)指令將對(duì)象o+的值轉(zhuǎn)換為區(qū)間。例如o.Ai=5，那么在轉(zhuǎn)換之后o.Ai=(5，5)。當(dāng)continue不為空，從continue中獲取對(duì)象o并將o標(biāo)記為已訪問(wèn)。使用IsGoal（）檢驗(yàn)對(duì)于每一個(gè)屬性Ai，是否存在從對(duì)象o.Ai到對(duì)象o-.Ai的規(guī)則，如果有則返回True；否則通過(guò)循環(huán)9）在對(duì)象o上應(yīng)用偏好規(guī)則φ∈Φ，獲取一個(gè)新的對(duì)象o-，如果o-不為空且不在interviewed中，則將o-推回至continue中，用于在另一個(gè)堆棧中搜索。

根據(jù)一組屬性X={A1，A2，…，Al}分析算法的時(shí)間復(fù)雜度，循環(huán)9）的時(shí)間復(fù)雜度為)，在最壞的情況下，序列中沒(méi)有滿足偏好條件的對(duì)象，那么，其中l(wèi)=|X|為屬性的數(shù)量，F(xiàn)DO 算法查找所有滿足偏好規(guī)則的組合，算法搜索樹(shù)的高度和節(jié)點(diǎn)數(shù)等于偏好規(guī)則數(shù)m，因此FDO 算法的時(shí)間復(fù)雜度為O(lmm)。

算法3 占優(yōu)序列（Dominant Sequence，DS）查找算法。

輸入 提取序列s，s′；

輸出 序列s?s′。

DS 查找算法執(zhí)行序列的占優(yōu)對(duì)比s?Φs′，算法通過(guò)找到序列第一個(gè)不同的位置i，創(chuàng)建對(duì)應(yīng)于位置i處有效的TCP 規(guī)則和TCP 理論，通過(guò)序列間對(duì)應(yīng)位置i處對(duì)象的偏好關(guān)系驗(yàn)證序列間的偏好關(guān)系。DS 查找算法的時(shí)間復(fù)雜度與提取序列的長(zhǎng)度有關(guān)，設(shè)提取序列的最大長(zhǎng)度為k，在最壞的情況下，DS 查找算法的時(shí)間復(fù)雜度為O(klmm)。

定義9占優(yōu)對(duì)比。如果不存在s′∈T使得s′?Φs，那么s∈T是占優(yōu)的。

算法4 占優(yōu)對(duì)比（Dominant Contrast，DC）算法。

輸入 一組序列T，TCP 理論Φ；

輸出 占優(yōu)序列T′。

DC 算法接收一組序列T和一個(gè)TCP 理論Φ，并根據(jù)Φ返回T′中的占優(yōu)序列。將T復(fù)制到T′，對(duì)于每組s、s′∈T′，算法分別執(zhí)行s?Φs′和s′?Φs占優(yōu)對(duì)比，最后只在T′中保留占優(yōu)序列。DC 算法的時(shí)間復(fù)雜度與提取序列中的序列數(shù)量有關(guān)，設(shè)提取序列的序列數(shù) |T|=n，那么占優(yōu)對(duì)比算法的時(shí)間復(fù)雜度為O(n2klmm)，即O(n2mm)。

例2 給出例1 的TCP 理論和以下提取序列，用t1，t2，t3，t4，t5表示時(shí)刻1 到時(shí)刻5：

執(zhí)行t5中提取序列s1和s2的占優(yōu)對(duì)比：

1）在第3 次迭代中，算法找到要比較的位置i=3；

2）循環(huán)掃描Φ，尋找在位置i=3 處滿足序列s1和s2的TCP 規(guī)則；

3）滿足條件的規(guī)則是φ2和φ3，由此產(chǎn)生的偏好理論Γ由以下規(guī)則組成：

4）執(zhí)行FDO 算法，可得o+=(ac，0，Pi)，o-=(ad，0，Qi)，圖2 顯示了FDO 算法搜索樹(shù)的查找過(guò)程，當(dāng)查找到搜索目標(biāo)（加橫線）時(shí)，算法返回真。

圖2 搜索樹(shù)的查找過(guò)程Fig.2 Finding process of search tree

5）執(zhí)行DS 算法，可得序列s2?s1；

6）執(zhí)行DC 算法，可得T′={s2}。

4 實(shí)驗(yàn)與結(jié)果分析

將算法在合成數(shù)據(jù)集和2014 年足球世界杯真實(shí)數(shù)據(jù)集［20］上進(jìn)行實(shí)驗(yàn)，記錄算法在不同數(shù)據(jù)集中的運(yùn)行時(shí)間以驗(yàn)證算法的有效性。實(shí)驗(yàn)環(huán)境為：個(gè)人筆記本電腦，Intel Core i5-6500 CPU，主頻為3.2 GHz，內(nèi)存為8 GB，操作系統(tǒng)為64 位Windows 10，編程語(yǔ)言為Python。

4.1 合成數(shù)據(jù)結(jié)果及分析

合成數(shù)據(jù)采用了由整數(shù)屬性組成的數(shù)據(jù)流的形式，屬性數(shù)ATT（number of Attributes）決定了數(shù)據(jù)維度影響算法的運(yùn)行時(shí)間，序列數(shù)SEQ（number of Sequences）決定每個(gè)瞬間生成元組的數(shù)量，時(shí)間范圍RAN（Temporary Range）和時(shí)間滑動(dòng)間隔SLI（Slide Interval）決定提取序列算法對(duì)流中對(duì)象的選擇，合成數(shù)據(jù)生成參數(shù)如表1 所示，用于提取序列的參數(shù)如表2 所示。

表1 合成數(shù)據(jù)生成參數(shù)Tab.1 Synthetic data generation parameters

表2 合成數(shù)據(jù)中用于提取序列的參數(shù) 單位：sTab.2 Parameters used to extract sequences in synthetic data unit：s

根據(jù)下面TCP 規(guī)則對(duì)數(shù)據(jù)中的序列進(jìn)行提取，序列屬性標(biāo)識(shí)符為A1：

具體實(shí)驗(yàn)結(jié)果如圖3 所示。

第一組實(shí)驗(yàn)測(cè)試在合成數(shù)據(jù)集中生成屬性的數(shù)量ATT對(duì)算法性能的影響，ATT從8 增加到16，其他參數(shù)均使用默認(rèn)值。如圖3（a）所示，隨著ATT的增加：1）即使生成很少的ATT，EXT sequences 也優(yōu)于CQL equivalent；2）兩個(gè)算法的運(yùn)行時(shí)間都隨ATT的增加而增加，但EXT sequences 增加的幅度較小。

第二組實(shí)驗(yàn)測(cè)試在合成數(shù)據(jù)集中生成序列的數(shù)量SEQ對(duì)算法性能的影響，SEQ從4 增加到32，其他參數(shù)均使用默認(rèn)值。如圖3（b）所示，隨著SEQ的增加：1）EXT sequences 的性能更好；2）當(dāng)SEQ增加時(shí)，算法處理元組的數(shù)量也會(huì)增加，處理時(shí)間會(huì)迅速增加到較高值，并隨著SEQ的持續(xù)增加一直保持在較高的水平。

第三組實(shí)驗(yàn)測(cè)試在合成數(shù)據(jù)集中不同時(shí)間范圍RAN對(duì)算法性能的影響，RAN從10 s 擴(kuò)大到100 s，其他參數(shù)均使用默認(rèn)值。如圖3（c）所示，隨著時(shí)間范圍的擴(kuò)大：1）EXT sequences 算法的性能更好；2）當(dāng)查詢不同RAN內(nèi)獲得的結(jié)果時(shí)，隨著RAN的擴(kuò)大，導(dǎo)致更大序列的產(chǎn)生，對(duì)算法性能產(chǎn)生更大的影響。

第四組實(shí)驗(yàn)測(cè)試在合成數(shù)據(jù)集中不同時(shí)間滑動(dòng)間隔SLI對(duì)算法性能的影響，SLI隔從1s擴(kuò)大到40s，其他參數(shù)均使用默認(rèn)值。如圖3（d）所示，隨著SLI的擴(kuò)大：1）EXT sequences 算法的性能更好；2）兩個(gè)算法的運(yùn)行時(shí)間都隨著SEQ的擴(kuò)大而減少；3）持續(xù)增加的SEQ導(dǎo)致查詢過(guò)程中更多的元組過(guò)期被刪除，因此序列變小，處理時(shí)間會(huì)持續(xù)減少。

圖3 合成數(shù)據(jù)中不同參數(shù)EXT sequences和CQL equivalent運(yùn)行時(shí)間對(duì)比Fig.3 Comparison of time consumptions between EXT sequences and CQL equivalent with different parameters in synthetic data

綜上所述，在同一個(gè)子窗口中的數(shù)據(jù)往往呈單調(diào)上升或下降的趨勢(shì)，這樣一來(lái)，算法處理新增數(shù)據(jù)的能力就變得尤為重要，EXT sequences 的優(yōu)勢(shì)更明顯，對(duì)于CQL equivalent 而言，當(dāng)窗口長(zhǎng)度大于循環(huán)周期時(shí)，算法需要多次掃描窗口。因此，CQL equivalent 在該數(shù)據(jù)集下的性能較差。

4.2 真實(shí)數(shù)據(jù)結(jié)果及分析

真實(shí)數(shù)據(jù)采用了2014 年足球世界杯數(shù)據(jù)集，數(shù)據(jù)集包括2 742 個(gè)元組，元組分布在7 643 個(gè)時(shí)刻，數(shù)據(jù)參數(shù)如表3所示。

表3 真實(shí)數(shù)據(jù)實(shí)驗(yàn)參數(shù)Tab.3 Experiment parameters of real data

表4 真實(shí)數(shù)據(jù)中用于提取序列的參數(shù) 單位：sTab.4 Parameters used to extract sequences in real data unit：s

實(shí)驗(yàn)使用了與例1 相同的TCP 理論：

第五組實(shí)驗(yàn)測(cè)試在真實(shí)數(shù)據(jù)集中改變不同時(shí)間范圍、時(shí)間滑動(dòng)間隔參數(shù)對(duì)算法性能的影響，如圖4 所示，隨著時(shí)間范圍RAN和時(shí)間滑動(dòng)間隔SLI的擴(kuò)大：1）EXT sequences 的性能更好；2）真實(shí)數(shù)據(jù)獲得的結(jié)果與合成數(shù)據(jù)得到的結(jié)果相似?？梢钥闯鯡XT sequences 在所有的實(shí)驗(yàn)中都優(yōu)于CQL equivalent。綜上所述，EXT sequences 對(duì)數(shù)據(jù)流中序列處理效率較高，運(yùn)行時(shí)間最短。

圖4 真實(shí)數(shù)據(jù)中不同參數(shù)EXT sequences和CQL equivalent運(yùn)行時(shí)間對(duì)比Fig.4 Comparison of time consumptions between EXT sequences and CQL equivalent with different parameters in real data

最后測(cè)試不同時(shí)間范圍RAN、時(shí)間滑動(dòng)間隔SLI對(duì)占優(yōu)對(duì)比算法性能的影響，在這組實(shí)驗(yàn)中，數(shù)據(jù)集為2014 年足球世界杯數(shù)據(jù)集，對(duì)比算法為Dominant Contrast、mintopk、partition 和incpartition，數(shù)據(jù)參數(shù)如表5。

表5 真實(shí)數(shù)據(jù)中用于占優(yōu)對(duì)比的參數(shù) 單位：sTab.5 Parameters used to dominant contrast in real data unit：s

從圖5 可以看出：1）Dominant Contrast 的性能最好；2）隨著RAN的擴(kuò)大，四個(gè)算法的運(yùn)行時(shí)間都隨RAN的增加而增加，但Dominant Contrast 增加的幅度最??；3）隨著SLI的增加，過(guò)期元組被刪除，序列間占優(yōu)對(duì)比的次數(shù)減少，Dominant Contrast 運(yùn)行時(shí)間減少。原因總結(jié)如下：1）Dominant Contrast算法處理按時(shí)間條件提取的序列，無(wú)需多次掃描窗口；2）partition 和incpartition 算法采用偏好層次結(jié)構(gòu)，按照用戶偏好條件對(duì)數(shù)據(jù)流元組進(jìn)行分區(qū)，算法受SLI的影響很小，對(duì)時(shí)間滑動(dòng)參數(shù)并不敏感；3）mintopK 沒(méi)有采用批處理的技術(shù)，當(dāng)RAN固定而SLI增加時(shí)，候選集的訪問(wèn)次數(shù)迅速增加，被直接過(guò)濾的對(duì)象數(shù)目變少。綜上，Dominant Contrast 的表現(xiàn)最好。

圖5 真實(shí)數(shù)據(jù)中不同參數(shù)連續(xù)查詢算法運(yùn)行時(shí)間對(duì)比Fig.5 Comparison of time consumptions among continuous query algorithms with different parameters in real data

5 結(jié)語(yǔ)

本文提出一種在數(shù)據(jù)流中根據(jù)時(shí)間條件提取序列和對(duì)提取序列進(jìn)行占優(yōu)處理的方法，擴(kuò)展了連續(xù)查詢語(yǔ)言CQL，對(duì)數(shù)據(jù)流上的處理和查詢技術(shù)有了更深一步的學(xué)習(xí)。在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上，將本文算法與其他算法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，本文算法所需的運(yùn)行時(shí)間更少，根據(jù)偏好條件得到的查詢結(jié)果也更準(zhǔn)確，理論分析和實(shí)驗(yàn)結(jié)果都證明了本文算法優(yōu)于其他算法。未來(lái)的研究包括：1）對(duì)提取序列算法和占優(yōu)對(duì)比算法進(jìn)行改進(jìn)，降低時(shí)間復(fù)雜度，提高數(shù)據(jù)流處理和查詢效率；2）將算法應(yīng)用到產(chǎn)生順序和流入窗口的順序不一致的亂序數(shù)據(jù)流中。