數據流環境下的關鍵詞輪廓查詢算法

宋栿堯,朱 睿,張 豪,邱 濤,夏秀峰

(沈陽航空航天大學 計算機學院,沈陽 110135)

1 引 言

輪廓查詢是多維數據管理中的經典問題,它通過用戶偏好幫助用戶從大量信息中提取有用信息,在許多應用中發揮著重要作用.近年來,隨著科技、互聯網技術的不斷發展,數據的來源和生成形勢日益多樣化,產生了大量文本數據.不同于傳統的數值型數據,它們由標準屬性和文本屬性兩部分構成.其中,標準屬性包括結構化數據,如數值型數據,而文本屬性包括非結構化數據,如標簽、評論等.和結構化數據相比,非結構化數據能夠提供更豐富的語義情感信息并且更好地表達用戶的個人偏好,因此結合文本信息的輪廓查詢,即關鍵詞輪廓查詢已經成為越來越流行的熱點問題.

給定d維數據集合D中的兩個對象o1,o2,如果o1在任意維度上的表現都不比o2差,且至少在一個維度上表現優于o2,則稱o1支配o2(記為o1o2).D中所有不被其他對象所支配的對象組成的集合稱為D所對應的輪廓集合,記為SK.而關鍵詞輪廓查詢和傳統輪廓查詢有所不同,對于d維數據集合D,其中每一條記錄o均可以由二元組表示.其中V表示o的d維屬性值,V=(v1,v2,…,vd),key表示o所對應的由m個關鍵詞組成的集合,key=(k1,k2,…,km).給定一組關鍵詞kw,D中所有包含kw的對象所對應的輪廓集合稱為D所對應的關鍵詞輪廓集合,記為KSK.

下面舉例來說明輪廓查詢與關鍵詞輪廓查詢的區別.用戶在社交網絡平臺上瀏覽評論信息時,通常更加關注發言用戶等級較高且位置與自己更接近的評論信息.如圖1(a)所示,圖中x坐標表示發言用戶的等級,y坐標表示發言用戶與瀏覽用戶之間的距離.給定數據集合D={o1,…,o8},o1～o8分別代表8條評論,由于o1、o2、o4和o5這4個對象在所有維度上的表現都不差于其他對象,且至少在一個維度上的表現比其他對象要好,即它們不被其他對象所支配,因此,這4條評論構成了輪廓集合SK.而當我們給定查詢詞kw時,得到的查詢結果與SK不同.如圖1(b)所示,當我們給定關鍵詞kw=k4時,由于對象o2的文本屬性中只包含關鍵詞k2和k3,而不包含關鍵詞k4,因此o2不是關鍵詞輪廓對象.而對象o3雖然不是D所對應的輪廓對象,但它包含關鍵詞k4,且不被其它包含關鍵詞k4的對象所支配,因此它是D所對應的關鍵詞輪廓對象.也就是說,當給定關鍵詞k4時,數據集D所對應的關鍵詞輪廓集合KSK={o1,o3,o4,o5}.通過觀察,我們不難發現,關鍵詞輪廓查詢和傳統的輪廓查詢均是通過對各維度屬性進行比較來選取最優點的集合,但由于關鍵詞輪廓查詢引入了文本屬性,因此需要考慮對象與關鍵詞之間的匹配關系,這導致了其在查詢方法以及查詢結果上均與傳統的輪廓查詢有所不同.

圖1 傳統輪廓查詢與關鍵詞輪廓查詢

隨著科技的不斷發展,流數據逐漸成為當前的主流數據類型之一.和傳統數據類型相比,它具有數據規模大、速度快、變化頻繁等特點,這使得研究面向數據流環境下的關鍵詞輪廓查詢問題具有重要意義.例如,在社交網絡平臺上,隨著用戶不斷評論、留言,評論信息實時更新,而用戶在瀏覽這些評論信息時,通常只關注當前最新的評論信息.因此,算法可針對最新的評論信息進行分析,將包含用戶給定關鍵詞并且各項屬性表現比較好的評論信息實時推薦給用戶.

不失一般性地,本文基于滑動窗口模型展開研究.給定滑動窗口W,它可分為基于計數的滑動窗口和基于時間的滑動窗口.其中,基于計數的滑動窗口包含最近到達窗口的N個對象,s表示每次窗口滑動時流入以及流出的對象數目.基于時間的滑動窗口包含最近N個時刻內到達窗口的對象,s指的是窗口每次滑動的時間間隔(即每隔s時刻滑動一次).為方便描述,本文以第一類窗口為例描述算法,但本文所提算法同樣適用于第2類窗口.

目前,許多學者[1-5]對于流數據環境下的輪廓查詢展開了研究,而其中還沒有算法引入關鍵詞屬性.其原因在于:關鍵詞輪廓查詢由兩個獨立的步驟構成,即首先使用給定關鍵詞集合kw過濾出文本屬性中包含kw的對象集合,再在此對象集合之上進行輪廓查詢.由于中間結果與關鍵詞相關,因此無法有效地構建索引來維護關鍵詞對象.此外,隨著大數據時代的到來,數據量急劇增長,如何對流數據中的關鍵詞對象和輪廓對象進行有效維護也是一個需要解決的問題.

本文首次提出查詢處理框架PCKSWI(Partition-based Continuous Keyword Skyline with Index)來支持數據流環境下的關鍵詞輪廓查詢.具體地,給定滑動窗口W0,PCKSWI將W0劃分成m個不相交的子窗口{P0,P1,…,Pm-1},分別過濾出每個子窗口中包含關鍵詞集合kw的對象集合LK={LK0,LK1,…,LKm-1}.隨后,本文分別在每個分片中利用查詢關鍵字集合過濾與之無關的對象,并針對剩余對象計算該分片中的輪廓對象,得到最終各分片的局部關鍵詞輪廓對象集合LKS={LKS0,LKS1,…,LKSm-1}.分片的好處在于:對于任何一個分片Pi,Pi-LKSi中的對象在Pi成為窗口中的第一個分片前都不會成為查詢結果.換句話說,算法只需維護{P1,…,Pm-1}中的局部關鍵詞輪廓對象和P0中的候選關鍵詞輪廓對象便可支持查詢,這可有效避免維護所有候選關鍵詞輪廓對象給算法性能帶來的影響.當Pi成為窗口中的第一個分片時(此時窗口為Wi),算法可利用Wi-Pi中的關鍵詞輪廓對象高效篩選Wi-Pi中的非關鍵詞輪廓對象.因此,PCKSWI可有效降低候選輪廓集合規模,降低總體查詢代價.

本文主要貢獻如下:首先,提出了一種分片策略,其按照對象到達時間對窗口進行劃分,根據劃分后得到的性質過濾掉大部分不可能成為查詢結果的對象,從而克服了數據間時序關系對算法性能帶來的影響.其次,提出了一種基于多分辨率網格的關鍵詞輪廓網格索引(Keyword Skyline Grid,KSG)用來維護各分片中的對象.該索引一方面利用網格來有效過濾出窗口中的關鍵詞對象,另一方面可利用關鍵詞對象中的輪廓對象和網格單元格的關系高效計算出窗口中的關鍵詞輪廓對象.最后,分析了分片粒度的設置,通過對分片粒度進行合理設置,提高了PCKSWI的整體效率.

2 相關工作

輪廓查詢是多維數據管理領域中的經典問題,輪廓查詢及其變種已被大量學者深入研究.和本文相關的研究包含兩類:1)滑動窗口模型下連續的輪廓查詢;2)關鍵詞輪廓查詢.下面,本節對這兩類研究進行介紹.

2.1 滑動窗口模型下連續輪廓查詢.

Lin等人[1]最早提出了基于滑動窗口的輪廓查詢的概念,并提出了n-of-N輪廓查詢算法.該算法利用一個間隔樹來維護窗口中的各個對象,記錄對象成為輪廓查詢結果的時間段,從而快速計算出任意時間段對應的輪廓集合,因此只需通過維護滑動窗口中少量數據即可完成滑動窗口上輪廓集合的計算.Tao等人[2]提出了兩種算法框架Lazy和Eager用于持續監測滑動窗口中的輪廓對象,算法引入數據的時間屬性,利用R-Tree索引管理流數據,并刪除其中不可能成為查詢結果的對象,從而降低了計算代價.Morse等人[3]提出了LookOut算法,它采用改進的四叉樹索引來對數據進行維護,該索引具有比R-Tree索引更高效的維護效率.Tang等人[4]提出了kdStreamSky算法,它基于kd-Tree索引,采用事件鏈機制來處理數據點的狀態變化,能夠更快地響應用戶的查詢要求.Ren等人[5]針對不完整數據流展開研究,提出了算法Sky-iDS,從不完整數據流中檢索具有高可信度的輪廓對象,通過差異依賴規則來填充不完整數據流中對象的缺失屬性.

這些查詢算法普遍存在的問題是沒有考慮對象的時序關系對查詢效率帶來的影響.即一個對象是否會成為候選輪廓對象由其在各維度的表現情況以及其到達順序共同決定.例如:對象o1能夠支配對象o2,且o1的到達時間晚于o2,則o2不會成為候選輪廓對象.極端情況下:窗口中最后一個到達的對象無論其在各維度的表現如何,由于其到達順序最晚,它仍為候選輪廓對象.因此,提出一種算法,通過利用對象的時序關系來對候選集合進行合理篩選,對解決上述問題具有重要的理論意義.

2.2 關鍵詞輪廓查詢

Choi等人[6]提出了基于倒排索引的關鍵字輪廓查詢算法(INverted-index-based Keyword Skyline algorithm,INKS),其首先通過倒排索引得到包含關鍵詞的數據集合,之后使用環算法[7](Block-Nested-Loop algorithm,BNL)計算出其對應的輪廓集合.另外,他們還提出了優化的關鍵詞匹配輪廓算法(Keyword-Matched Skyline algorithm,KMS),該算法基于R-Tree索引和簽名文檔過濾,在維度較低的情況下,具有較高的計算效率.Regalado等人[8]通過計算用戶輸入的關鍵詞與對象的關鍵詞之間的相關性,并以此作為標準維度來進行輪廓計算.Chen等人[9]將社交關系應用到關鍵詞輪廓查詢中,提出了基于社交的空間文本輪廓查詢算法(Social-based Spatial-textual Skylinealgorithm,SSTS),并引入了新型函數來計算SSTS的社交相關性;在此基礎之上,他們通過有效的剪枝策略對SSTS進行擴展,并提出了了受限的基于社交的空間文本輪廓查詢算法(Constrained Social-based Spatial-textual Skylinealgorithm,CSSTS).Li等人[10]提出了空間關鍵詞輪廓查詢算法(Spatial Keywords Skyline algorithm,SKS),引入了最小值過濾等策略,并提出了一種索引結構STR-Tree,將空間區域信息與對象文本信息相結合,快速過濾掉與查詢無關的區域,進一步提升了查詢效率.

目前被提出的這些查詢算法都是針對于靜態數據所展開的,在流數據環境下,它們均無法有效地解決關鍵詞輪廓查詢的問題.因此,提出一種增量算法,使得其能夠在數據流環境下高效維護當前窗口中的關鍵詞輪廓集合,具有重要的理論意義和應用價值.

3 問題分析及定義

在本章,我們首先介紹了輪廓集合和關鍵詞輪廓集合的相關概念,之后,正式介紹問題定義.

定義1.(輪廓集合)給定d維數據集合D,?o1,o2∈D,如果o1在任意維度上的表現都不比o2差,且至少在一個維度上表現優于o2,則稱o1支配o2(記為o1o2).對于D中任意對象o,如果D中不存在其他對象支配o,則稱o為輪廓對象.D中的所有輪廓對象組成了輪廓集合,記為SK.

如圖1(a)中所示,給定數據集合D={o1,…,o8},其所對應的輪廓集合SK0={o1,o2,o4,o5}.

定義2.(關鍵詞輪廓集合)給定d維數據集合D,D中每一條記錄o可以由二元組表示.其中V表示o的d維屬性值,V=(v1,v2,…,vd),key表示o所對應的由m個關鍵詞組成的集合,key=(k1,k2,…,km).給定一組關鍵詞kw,集合K滿足K={p|kw?p.key∧p∈D},則集合K所對應的輪廓集合稱為D所對應的關鍵詞輪廓集合,記為KSK.

如圖1(b)中所示,給定數據集合D={o1,…,o8},以及關鍵詞kw=k4,其所對應的關鍵詞輪廓集合KSK={o1,o3,o4,o5}.

定義3.(連續的關鍵詞輪廓查詢)設W為規模為N的查詢窗口,查詢q監視窗口,當窗口滑動時,q返回當前窗口中關鍵詞kw對應的關鍵詞輪廓集合KSK.

如圖1(b)中所示,給定當前窗口W0對應的對象集合O0={o1,…,o8},窗口流速s=2,以及關鍵詞kw=k4,其所對應的關鍵詞輪廓集合KSK0={o1,o3,o4,o5}.在窗口經過一次滑動之后,對象o1和o2離開窗口,o9和o10進入窗口.如圖1(c)中所示,此時當前窗口W1所對應的關鍵詞輪廓集合更新為KSK1={o3,o4,o5,o10}.

4 查詢處理框架PCKSWI

本章提出一種帶索引的基于分片技術的算法框架PCKSWI(Partition-based Continuous Keyword Skyline with Index)來支持連續的關鍵詞輪廓查詢.它根據窗口中對象的到達順序將窗口劃分為若干個子窗口,之后,之后計算出各子窗口中的局部關鍵詞輪廓集合,并在此基礎之上計算出全局關鍵詞輪廓集合.根據分片的性質,該算法可以過濾掉大部分不會成為查詢結果的對象,實現查詢在數據流環境下的高效維護.為幫助PCKSWI高效計算各分片的關鍵詞輪廓對象,本章提出了關鍵詞輪廓網格索引(Keyword Skyline Grid,KSG)來管理各分片中的數據.此外,為了提高各分片的查詢效率,我們通過分析找到了一個適合的劃分粒度.

4.1 框架概覽

4.1.1 PCKSWI框架的基本思想

給定窗口W,我們將其劃分為m個分片{P0,P1,…,Pm-1}.對于每一個分片Pi,我們使用一個索引Ii來維護其中對象,并從中選擇局部關鍵詞輪廓對象來作為候選關鍵詞輪廓對象.這里,索引Ii的構建將在4.2節中詳細介紹.此外,令LKSi為分片Pi的局部關鍵詞輪廓對象,其滿足?o∈LKSi,o的文本屬性中包含給定關鍵詞集合kw且o不被任意文本屬性中包含kw的對象所支配.

4.1.2 PCKSWI的增量維護算法

下面正式介紹基于分片技術的增量維護算法.給定窗口W,及其所對應分片{P0,P1,…,Pm-1},索引Is維護CL中的所有局部關鍵詞輪廓對象.我們首先構建一個新的分片Pm來維護新到達的對象,并構建一個集合LKSm來維護Pm中的局部關鍵詞輪廓對象.當一個新的對象o流入窗口時,算法首先將其插入集合Pm,并檢測其關鍵詞是否包含給定關鍵詞kw,如果包含則將其插入集合LKSm,之后,對于任意流入窗口的對象oi(i>1),如果其包含關鍵詞kw,算法將其插入Pm并訪問LKSm,并通過索引Im判斷其是否被LKSm中對象支配.如果不被支配,則將oi插入LKSm.特別地,如果oi能夠支配LKSm中對象oj(j

除了維護新流入窗口的數據,算法還需要在關鍵詞輪廓失效時,對候選關鍵詞輪廓集合進行維護.具體地,算法首先逆序掃描LKS0中對象,將LK0-LKS0中的對象依次插入候選集.給定LK0-LKS0中對象o,如果其不被任何到達時間比它晚且包含關鍵詞kw的對象支配,則將o插入候選集.反之,則說明o不是關鍵詞輪廓對象,且在其離開窗口前不會成為查詢結果,無需操作.

當窗口Pm變滿時,算法首先構造索引Im,之后我們訪問Im來更新集合LKSm,這里,索引Im的構造以及集合LKSm的更新將在4.2節中詳細介紹.接下來,我們將LKS-LKSm中的對象全部插入到LKS中.在處理完分片Pm之后,我們判斷是否需要對分片P1進行重掃描操作.如果集合LKS1為空,則無須進行該操作,反之需要對分片P1進行重掃描操作,將P1中的所有候選關鍵詞輪廓對象插入集合LKS中.這里,重掃描操作將在4.2.4節中詳細介紹.最后,我們構建一個新的分片Pm+1.

4.2 網格索引KSG

為了對各分片中的對象進行有效的關鍵詞過濾,并且高效地計算出關鍵詞輪廓集合,PCKSWI采用網格索引結構KSG管理窗口中對象.首先,我們利用多分辨率網格將整個空間劃分為一組大小不等的單元格,之后,對于每一個非空單元格,我們使用R-Tree維護其中文本屬性中包含給定關鍵詞的對象.下面正式介紹網格索引KSG.

4.2.1 KSG的構建

觀察1.給定網格G,對象o1、o2以及其所在單元格c1、c2,如果c1在c2的左下方,則對象o2一定被對象o1所支配.

圖2 索引KSG的過濾步驟

算法1.關鍵詞過濾算法

輸入:數據集D,單元格集合C,關鍵詞kw

輸出:過濾之后的剩余對象集合D

1. fori=0;i<|C|-1;i++do;

2. ifkw?C[i].keywordthen

3.D.delete(C[i]);

4. fori=0;i<|C|-1;i++do;

5. ifC[i].tag=unskylinethen

6.D.delete(C[i]);

7. returnD;

在重構過程中,我們使用R-Tree索引來維護所有輪廓單元格以及最小輪廓單元格中的對象,由于R-Tree索引已經在文獻[11]中詳細介紹,為節省空間,這里不再重復敘述.

4.2.2 局部關鍵詞輪廓查詢

4.2.3 網格索引更新算法

當分片Pm變滿時,我們需要將集合LKSm中的對象合并到LKS中,并將LKS中的非關鍵詞輪廓對象刪除.我們可以根據觀察2,降低索引更新所需代價.

觀察2.給定對象o∈LKSi,o′∈LKSm,如果o被o′所支配,那么o的支配空間內的所有對象均被o′所支配.

另外,由于o′比這些對象的到達時間都要晚,因此它們在失效前不會成為關鍵詞輪廓對象.具體地,假設對象o∈LKSi,o′∈LKSm,如果o被o′所支配,我們訪問索引Ii的根節點,找到所有被對象o′所支配的對象.假設e為索引Ii的節點,e.m為e所對應的最小邊界矩形(MBR),我們可以利用o′和e.m左下方(或右上方)坐標之間的位置關系來判斷e中對象和o′之間的支配關系.如果e.m左下方坐標位于o′的右上方,則說明e中的所有對象均被o′所支配,我們可以將e從索引Ii中刪除;如果e.m右上方坐標位于o′的左下方,則說明e中的所有對象均不被o′所支配.如果結點e與o′不存在支配關系,我們繼續訪問e的孩子節點.特別地,如果Ii成為了一棵空樹,我們直接刪除索引Ii.

以圖3為例,索引Ii中對象以及LKSm中對象o′的分布情況如圖3(a)中所示,其對應的R-Tree結構如圖3(b)中所示.我們首先訪問Ii的根節點R,由于其孩子節點e6和e7所對應的最小邊界矩形與o′之間均不存在支配關系,因此我們繼續訪問e6的孩子節點e1、e2以及e7的孩子節點e3、e4和e5.由于e2.m、e3.m和e5.m的左下方均位于o′的右上方,因此e2、e3和e5中所有對象均被o′所支配,我們將其從Ii中刪除.接下來,我們繼續訪問剩余的節點e1和e4,找到其中所有被o′所支配的對象.最終,我們得到更新之后的關鍵詞輪廓集合{o1,o2,o11}.

圖3 索引KSG的過濾步驟

4.2.4 基于KSG的重掃描算法

如4.1節所述,當LKS0中對象均被LKS-LKS0中對象支配時,LK0中對象在失效之前均不會成為輪廓對象.此時,算法無需訪問LK0.反之,算法需要對LK0進行掃描以便找到其中所有可能成為查詢結果的對象,并將它們加入候選集.

為實現高效掃描,我們提出一種基于索引KSG的重掃描算法.它包括兩個步驟:非候選對象的過濾和候選對象的驗證.在非候選對象的過濾步驟,我們根據集合LKS-LKS0中的對象來檢測索引I0中的對象是否為候選關鍵詞輪廓對象.具體地,對于LKS-LKS0中的每一個對象o,我們訪問索引I0并找到所有被o所支配的對象,該掃描算法已經在4.1節中介紹過,這里為節省空間不再介紹.之后,我們利用LKS-LKS0中的其他對象來找到LK0中的所有非候選關鍵詞輪廓對象并從LK0和索引I0中刪除這些對象.

在候選對象的驗證步驟,我們逆序掃描LK0中的剩余對象.由于這些剩余對象均不被LKS-LKS0中的對象所支配,因此LK0中最后到達的對象o一定是候選關鍵詞輪廓對象,我們將其插入集合LKS中.另外,我們將o插入另一個R-Tree索引RI0中.之后,我們對LK0中的對象逆序掃描,判斷其是否被RI0中的其他對象所支配.如果不被支配,則將其插入RI0和LKS中,否則,我們將其從LK0中刪除.在訪問過LK0中的所有對象后,重掃描算法結束.

4.3 分片粒度的設置

在介紹了框架概覽和網格索引KSG之后,我們需要解決如何進行分片的問題.如前文所述,我們需要監測LKS∪LK0中的對象來支持關鍵詞輪廓查詢.需要注意的是,在最壞的情況下,分片Pi中的所有對象均為關鍵詞對象,因此,當分片粒度較大時,最壞情況下,各分片中的關鍵詞輪廓對象候選集LKS的規模較小,維護代價較小,但重新掃描LK0后,會導致加入候選集的對象過多;反之,LKS的維護代價則會較大,但重掃描LK0后,加入候選集的對象則會相對減少.因此,選擇一個合適的分片粒度是有必要的.下面,我們將對分片粒度的設置進行分析.

(1)

5 實驗分析

5.1 實驗準備

本節采用C++語言實現了PCKSWI算法,實驗環境為Intel i5-4210M～2.60GHz;8GB內存;1TB硬盤的PC機.

本節分別采用一個真實數據集和兩組合成數據集來驗證算法性能.真實數據集采用手機評論數據集,包含64MB條記錄,每條記錄包含3條數值型屬性.合成數據集包括一組獨立數據集和一組反相關數據集,其中每組包括4個數據集,分別包含2、3、4、6條數值型屬性和10M條記錄.本節在測試時,將窗口長度N從0.5MB變化到2MB,默認值為1MB;將關鍵詞數量n從2個增加到10個,默認值為2個;將維度d從2增加到6,默認值為3.

本文的實驗方法是按照數據產生的順序將數據一次性讀入內存.此后,對每條數據按照其到達時間添加ID屬性.隨后,將數據依次插入窗口并計算窗口中的關鍵詞輪廓對象.當所有數據都處理完畢之后,統計運行時間.本文采用相同的方法處理各個數據集中的對象,為節省空間,這里不對它們的生成過程進行詳細介紹.此外,本文將PCKSWI算法與基于文獻[12]中的連續輪廓查詢算法的baseline算法和不帶索引的算法PCKS進行對比.

5.2 實驗分析

本節第1組實驗測試窗口長度對算法性能的影響,分別在真實數據集、獨立數據集和反相關數據集下測試算法性能,其他參數均使用默認參數,窗口長度從0.5MB擴大到2MB,記錄算法的總運行時間.圖4(a)-圖4(c)分別為真實數據集、獨立數據集和反相關數據集下3種算法的運行時間.我們發現PCKSWI算法的性能最好,并且,隨著窗口長度的增加,3種算法性能均有下降,而PCKS和PCKSWI算法的性能下降更加緩慢.原因在于,PCKS和PCKSWI算法通過對滑動窗口進行分片,有效避免了對所有候選關鍵詞輪廓對象的維護,因此其性能受窗口長度的影響不大.

圖4 窗口長度N對算法效率的影響

本節第2組實驗測試關鍵詞數量對算法性能的影響,分別在真實數據集、獨立數據集和反相關數據集下測試算法性能,其他參數均使用默認參數,關鍵詞數量從2個增加到10個,記錄算法的總運行時間.圖5(a)-圖5(c)分別為真實數據集、獨立數據集和反相關數據集下3種算法的運行時間,我們發現PCKSWI算法的性能最好,并且,隨著關鍵詞數量的增加,3種算法性能均有下降,baseline算法下降最為明顯,PCKS算法次之,PCKSWI算法的性能下降最為緩慢.原因在于,隨著關鍵詞數量的增加,雖然通過給定關鍵詞可以過濾掉更多文本屬性中不包含關鍵詞的對象,但需要將對象的文本屬性與給定關鍵詞進行比對的次數也隨之增加,因此整體效率會有所降低.PCKSWI算法通過網格索引批量過濾掉大部分文本屬性中不包含關鍵詞的對象,這使得其將對象的文本屬性與給定關鍵詞進行比對的次數相應的減少,因此其效率降低最為緩慢.

圖5 關鍵詞數量n對算法效率的影響

本節第3組實驗測試數據維度對算法性能的影響,采用獨立數據集和反相關數據集作為測試數據,其他參數均使用默認參數,數據維度d從2擴大到6,記錄算法的總運行時間.圖6(a)和圖6(b)分別為獨立數據集和反相關數據集下3種算法的運行時間,可以發現PCKSWI算法的效率最高,并且隨著數據維度的增加,3種算法的效率都有明顯降低,其中PCKS算法效率的降低最為緩慢.這是因為,對于baseline算法來說,隨著維度的增加,R-Tree索引的有效性下降,因此效率大幅降低.然而,由于PCKS算法維護的候選對象少,所以和baseline算法相比,運行時間增加較慢.而對于PCKSWI算法來說,KSG索引的有效性也會隨著維度的增加有所下降,因此其效率也會隨著維度的增加而有所降低.

圖6 數據維度d對算法效率的影響

6 結束語

本文研究了數據流上的關鍵詞輪廓查詢問題,為支持該查詢,本文提出查詢處理框架PCKSWI.它通過對窗口進行有效劃分,過濾掉大部分不可能成為查詢結果的對象,從而克服了數據間時序關系對算法性能帶來的影響.隨后,本文提出了基于多分辨率網格的索引KSG,該索引一方面利用網格來有效過濾窗口中的關鍵詞對象,另一方面可利用關鍵詞對象中的輪廓對象和單元格的關系高效計算出窗口中的關鍵詞輪廓對象.另外,本文通過分析,根據流數據的規模對劃分粒度進行調整,提高了PCKSWI整體效率.最后,本文基于真實數據集以及合成數據集進行實驗,實驗結果表明本文所提算法在數據流上能夠有效處理關鍵詞輪廓查詢.