李潤澤，孫雪姣

（煙臺大學(xué)計算機與控制工程學(xué)院，山東煙臺 264005）

0 引言

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 偏好推理

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

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

1.2 偏好查詢

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

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

2 StreamSeq時間條件偏好查詢語言

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

定義1序列。設(shè)X={A1，A2，…，Al}為屬性集，X上的對象集為O(X)=Dom(A1)×Dom(A2)× …×Dom(Al)，其中Dom(Ai)為Ai的定義域。X上的序列是一個有序的對象集，因此對于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，那么用來判定命題為True 和False 的為基本公式；如果F和G是基本公式，那么?F，?G，(F∧G)，(F∨G)和(FsinceG)也為基本公式。序列在位置i∈{1，2，…，k}（由(s，i)=F表示）滿足公式F的概念定義歸納如下：

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

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

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

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

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

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

1）如果在某一個時刻，球員控球，并且在此時刻之前，該球員處于防守中場，那么教練更喜歡該球員去中場而不是防守中場，與球員移動的類型無關(guān)。

2）如果在某一個時刻，球員沒有控球，而在這一時刻之前，球員控球并且處于進攻中間位置，那么教練更喜歡球員在中場而不是進攻中間位置。

3）橫向移動比前進移動更好。

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

圖1 運動員s的運動軌跡Fig.1 Trajectory of athletes

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

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

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

設(shè)Φ為TCP 理論，φ為TCP 規(guī)則，符號Φφ表示Φ和φ是時間兼容的。Φφ的兼容性測試可以僅使用TCP 規(guī)則的非時間部分來完成，給定一個TCP 規(guī)則φ，符號φ0表示從φ中獲取一個規(guī)則，用代替Cφ。例如，對于例1 中的TCP 規(guī)則，有。從一組TCP規(guī)則Φφ中提取的條件偏好理論被定義為。可以針對每個φ∈Φ來檢測TCP 理論φ的時間兼容性。引理1和引理2 驗證了TCP 理論具有時間兼容性。

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

證明 假設(shè)φ和φ′為兩個TCP 規(guī)則，如果存在一個包含位置i的序列s使(s，i)=，(s，i)=，但φ和φ′是不兼容的。如果φ和φ′不兼容，那么在中至少有一個子式F，在中至少有一個子式G，F(xiàn)和G在時間上不兼容。要做到這一點，有以下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中沒有這樣的位置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中沒有這 樣的位置i使得(s，i)=F，(s，i)=G，所以與假設(shè)矛盾。 證畢。

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

證明 假設(shè)Φ是一個TCP 理論，對于所有的φ∈Φ，如果Γ(Φφ)是時間兼容的，那么Φ也是時間兼容的。如果Φ在時間上不兼容，則存在規(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是時間兼容的，因此這些規(guī)則在同一組兼容的規(guī)則中，然而由兼容的集合Φφ產(chǎn)生的條件偏好理論Γ(Φφ)具有時間兼容性，與假設(shè)矛盾。 證畢。

3 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入 提取序列s，s′；

輸出 序列s?s′。

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

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

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

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

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

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

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

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

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 算法搜索樹的查找過程，當(dāng)查找到搜索目標(biāo)（加橫線）時，算法返回真。

圖2 搜索樹的查找過程Fig.2 Finding process of search tree

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

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

4 實驗與結(jié)果分析

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

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

合成數(shù)據(jù)采用了由整數(shù)屬性組成的數(shù)據(jù)流的形式，屬性數(shù)ATT（number of Attributes）決定了數(shù)據(jù)維度影響算法的運行時間，序列數(shù)SEQ（number of Sequences）決定每個瞬間生成元組的數(shù)量，時間范圍RAN（Temporary Range）和時間滑動間隔SLI（Slide Interval）決定提取序列算法對流中對象的選擇，合成數(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ī)則對數(shù)據(jù)中的序列進行提取，序列屬性標(biāo)識符為A1：

具體實驗結(jié)果如圖3 所示。

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

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

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

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

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

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

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

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

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

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

實驗使用了與例1 相同的TCP 理論：

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

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

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

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

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

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

5 結(jié)語

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