空間文本數據流上連續查詢評估技術綜述

楊 茸，牛保寧

太原理工大學信息與計算機學院，山西晉中 030600

空間文本數據流上連續查詢（continuous queries over spatial-textual data streams，CQST），也稱為位置感知的發布/訂閱查詢（location-aware publish/subscribe query），是在不斷更新的空間文本對象數據流上，檢索并實時更新滿足空間和文本約束的對象，是廣告定位、微博分析和地圖服務等基于位置的應用程序的核心操作[1-21]。與一次查詢（Ad-hoc query）相比，CQST是指在一段時間內（指查詢有效期內），隨著數據集的更新，系統連續地為CQST 計算并返回結果。評估CQST 的挑戰性在于在CQST 上構建高效的過濾技術。通常系統中包含大量的CQST，數據流上的對象可能以很快的速度到來，對象的處理必須及時，任何延遲都有可能導致結果過時，使得用戶體驗變差，因此過濾技術的構建至關重要。

在本文，O 表示空間文本數據流。一個空間文本對象表示為o=(ρ,ψ,t)。其中o.ρ表示對象的地理位置，o.ψ是一組描述對象的文本集合，o.t表示與對象生命期有關的時間戳。近年來，空間文本數據流上連續查詢主要包含連續布爾范圍查詢[1-11]及連續Top-k查詢[12-21]，定義如下：

空間文本數據流上連續布爾范圍查詢：連續布爾范圍查詢（continuous Boolean range query，CBRQ）表示為q=(r,ψ,t)。其中q.r是描述查詢范圍的一個空間區域，q.ψ是一組描述查詢需求的文本（或數值）集合（或布爾表達式，本文只考慮“與”操作），稱為關鍵字，q.t表示與查詢生命期有關的時間戳。查詢結果集為q(O)={o∈O|o.ρ∈q.r∧o.ψ?q.ψ}，即返回落入查詢范圍內且包含全部查詢關鍵字的對象。

空間文本數據流上連續Top-k查詢：連續Top-k查詢（continuous Top-knearest neighbor query，CTkN）表示為q=(ρ,ψ,k,α,t)。其中q.ρ表示查詢的地理位置，q.k表示查詢返回的對象個數，q.α表示平衡空間鄰近度及文本相似度的查詢偏好參數，其他參數意義同上。為CTkN 查詢定義一個評分函數ST(o,q)，返回ST(o,q)值最高的q.k個對象，即q(O)={o∈O|?o′∈Oq(O),ST(o,q)≤ST(o′,q)}}，其中|q(O)|=q.k。

CQST 的評估流程如圖1 所示。用戶向服務器端提交查詢，服務器為查詢計算并返回滿足條件的結果。在查詢有效期內，若對象更新，服務器為受影響的查詢重新計算結果，直到查詢失效。服務器端包含對象處理模塊及查詢處理模塊。（1）對象處理模塊負責處理到來的對象，包含查詢過濾技術及對象處理算法。當新對象到來時，利用對象處理算法及查詢過濾技術評估該對象可能會影響哪些查詢的結果，更新相應查詢的結果列表。（2）查詢處理模塊處理新提交的查詢，包含對象索引及查詢算法。新提交的查詢依據查詢算法在對象索引中檢索滿足空間文本約束的結果，更新結果列表。此外，將新提交的對象、查詢插入相應索引。將到期的對象、查詢從相應索引中刪除，并更新查詢結果列表。

Fig.1 Framework of evaluating CQST圖1 評估CQST 框架

值得注意的是，與本文密切相關的工作有：（1）連續移動的查詢[22-25]，即在查詢有效期內，為移動的查詢連續返回結果，如用戶在移動過程中，查找附近的加油站或者出租車。為了減小客戶端與服務器端的通信代價，通常采用安全區域模型，為移動的查詢或對象建立安全區域。構建安全區域的代價是巨大的，因此這類工作專注于減小構建安全區域的代價。Qi 等人[26]綜述了不同場景下的安全區域模型及其構建方式。（2）空間文本數據流上的一次查詢，即在當前空間文本數據流上，為查詢計算并返回結果，查詢結束。GeoTrend[27]及Mercury[28]檢索最近T時間段內與用戶地理位置鄰近、時間較新的微博，是在已有對象集上的一次檢索，類似于經典的空間關鍵字查詢。該類工作專注于數據流上到來對象索引的構建及更新，組織微博的地理位置及時間分值，忽略文本屬性。（3）空間關鍵字查詢[29-30]，即在靜態空間文本數據集上檢索滿足空間文本約束的對象。Chen等人[31]綜述了多種空間文本查詢模型下的空間文本索引性能。

1 評估CQST 的索引

索引是過濾大量不相關查詢的基礎，因此本章介紹評估CQST 的索引技術，并討論它們的索引性能及優缺點。

表1 列出了現有評估CQST 的索引技術。

1.1 空間索引

從空間過濾角度看，評估CQST 為點刺探搜索（point stabbing search）問題，即返回該位置點命中的區域中的查詢。空間索引是空間過濾的基礎，定位到來對象落入的空間節點，驗證該節點內的查詢。驗證的查詢數量越少，過濾性能越好。評估CQST 采用的基本空間索引可分為以下兩大類。

Table 1 Indexes of evaluating CQST表1 評估CQST 的索引技術

（1）數據驅動型（data-driven）索引。節點的邊界由數據的空間分布決定。優點是不需要整個空間區域的先驗知識，根節點空間信息由子節點得到。缺點是索引構建時間及更新時間較長。R-tree[1，12-15]，索引自底向上構建，葉節點按照數據的空間范圍或地理位置構建，非葉節點由葉節點迭代構建。R-tree是平衡樹，節點中插入的查詢數量不超過閾值。kd-tree[8-10]，是二叉樹，將整個空間區域不斷從水平或垂直方向劃分為兩個子區域，劃分后兩個子區域的查詢數量基本相同。

（2）空間驅動型（space-driven）索引。節點邊界不依賴于數據的空間分布。優點是索引構建時間及更新時間短。缺點是需要明確整個空間區域的大小。Quad-tree/空間金字塔[2-4，9，16-18]，從根節點開始，將整個空間區域迭代地劃分為多層不同粒度的、均勻的、不重疊的節點。除葉節點外，每個節點包含四個子節點，數據既可插入葉節點，也可插入中間節點。網格/哈希桶[5-7，10，19]，整個空間區域被劃分為多個非重疊的矩形節點，并將查詢插入到所有映射節點。粒度選擇是關鍵。單粒度網格（哈希桶）范圍較小，包含的數據集較少，過濾性能較強，但查詢范圍較大時，占用內存將成倍增加。

1.2 文本索引

從文本過濾角度看，評估CQST 為超集包含搜索（superset containment search）問題，即返回關鍵字包含在對象中的查詢。文本索引是文本過濾的基礎，用來檢查數據流中的對象包含了哪些查詢的關鍵字。驗證的查詢數量越少，過濾性能越好。評估CQST 采用的基本文本索引可分為以下兩大類。

（1）數據無序性索引。索引中的數據無序，當進行數據驗證時，需要驗證索引中所有數據項。優點是索引構建簡單，更新代價小。缺點是過濾性能弱。倒排文件（inverted file）[1，3，8，10，12-13，16，18，20]是最基本的文本索引，評估CQST 的大量過濾技術均采用倒排文件組織查詢關鍵字。倒排文件包含一個文本集，每個文本對應一個列表（posting list）。為了增加倒排文件的過濾能力，一般每個CBRQ 查詢只插入到一個列表，而每個CTkN 查詢需要插入到其關鍵字對應的所有列表。Ranked-key 倒排文件（ranked-key inverted file，RIF）[2]，查詢按照包含關鍵字的頻率被插入到低頻關鍵字對應的列表（即最短的列表），以減少高頻關鍵字對應的列表中的查詢數量，適用于CBRQ 查詢。多層倒排列表（multi-level inverted list）[17]是二叉樹，每個葉節點指向一個倒排列表，該列表包含的查詢數量不超過給定閾值。在非葉節點維護多個屬性值，以提高倒排列表的過濾能力。

（2）數據有序性索引。索引中的數據有序，評估CQST 時只需驗證部分數據項。優點是過濾性能強。缺點是索引構建復雜，更新代價大。有序關鍵字字典樹（ordered keyword trie，OKT）[3，5-6]將一組查詢按照其包含的關鍵字分為多個分支，到來對象只需要驗證包含文本項的分支。自適應關鍵字索引（adaptive keyword index，AKI）[4，9]是一個混合索引，集成了RIF與OKT，利用關鍵字的頻率提高索引的過濾能力。簡而言之，檢查待插入查詢包含的關鍵字頻率，若查詢包含低頻關鍵字，則將其插入RIF 中；若查詢只包含高頻關鍵字，則將其插入OKT 中。

除了上述文本索引外，部分CQST 查詢請求中包含數值屬性，故在空間節點中采用OpIndex[7]及區間樹[14-15]等組織節點內查詢的數值屬性，即為每個屬性值建立相應的倒排列表，列表包含了數值數據的區間。

2 評估CQST 的過濾策略

評估CQST 的查詢優化技術采用一項或多項過濾策略及方法，以盡可能提升索引的空間和文本過濾性能，為到來對象過濾大量不相關的查詢，提高對象與查詢的匹配效率。

2.1 提升空間過濾性能的策略

將提升評估CQST 的空間過濾性能的策略分為以下四類。

（1）限制空間節點內插入的查詢數量。為了提高空間過濾性能，空間節點中插入的查詢數量是關鍵。Rt-tree 及其兩個變體[1]、擴展Rt-tree 及其變體[13]、RI-tree[14]及RI-tree[15]利用R-tree 組織查詢范圍，HISP（hierarchical index with spatio-textual and region-aware prefix）[12]利用R-tree 組織查詢地理位置。R-tree 節點內的查詢數量不超過給定閾值。FAST（frequencyaware spatio-textual）[4]利用空間金字塔組織查詢范圍，HSFTS（hierarchical summarization and fast computation of the ranking score based subscription filtering to solve top-kspatial-temporal term subscription）[19]利用Quad-tree 組織查詢的地理位置。它們在空間金字塔或Quad-tree 節點限制插入的查詢數量，若查詢數量大于閾值，則增加空間節點劃分深度，將查詢插入到下一級空間節點。

（2）最小化覆蓋查詢范圍的空間節點區域，以減少評估查詢時驗證對象的數量。將查詢范圍映射到Quad-tree、空間金字塔的葉節點或小粒度的網格、哈希桶均可實現這一途徑。Elaps（new location-aware pub/sub system）[7]考慮因查詢位置更新導致的通信代價及數據流中對象的匹配代價，為移動的查詢計算最佳安全區域。因查詢在不斷移動，查詢安全區域需不斷更新，為此該文獻將查詢的安全區域映射到網格，利用倒排文件組織映射到網格的查詢，以適應查詢移動（即查詢在網格中的更新）。IGPT（index combining both individual and group pruning techniques）[18]利用Quad-tree 的葉子節點組織查詢地理位置。該類策略空間節點內插入的查詢數量沒有約束，且查詢范圍較大的查詢被插入到多個空間節點，其更新代價及存儲代價增加。

（3）計算數據分布，將查詢映射到相應的空間節點。針對第（2）種策略存在的問題，本策略通過計算系統中查詢與對象的空間分布，為查詢計算最佳映射節點，即將查詢范圍映射到多個大小不一的空間節點。IQ-tree[2]利用Quad-tree 組織查詢范圍，利用一個基于磁盤的代價模型將一組查詢與一組Quad-tree節點關聯，將查詢插入到一個或多個Quad-tree 節點中，以平衡索引匹配及更新的I/O 代價。FAST[4]利用空間金字塔組織查詢范圍，查詢按照關鍵字的頻率劃分到高層或較低層的空間金字塔節點。查詢范圍較小或只包含高頻關鍵字的查詢更傾向于插入到高層金字塔節點。AP-tree、AP+-tree[5]及AP-tree+[6]計算節點內查詢及對象的空間分布，采用自適應的網格組織查詢范圍，即網格大小是由查詢空間分布決定的。CIQ（conditional influence region based quadtree）[16]及IQ*-tree[17]使用條件影響區域（conditional influence ring，CIR）或者近似條件影響區域（approximate conditional influence ring，ACIR）表示查詢。在CIQ 中，查詢用一組CIR 表示，CIR 是與查詢文本相關度及時間新近性有關的圓形區域。在IQ*-tree 中，查詢用一組ACIR 表示，ACIR 是與查詢文本相關度及時間新近性有關的環形區域。為此，將查詢映射到一組覆蓋整個空間區域的非重疊Quad-tree 節點，節點粒度由查詢地理位置決定。

（4）在空間節點中引入空間鄰近度過濾條件，避免對象驗證不可能的查詢，適用于計算分值的CTkN查詢。給定任意查詢，若確定文本相似度上界，可得到對象與查詢匹配的空間鄰近度下界。在空間節點引入節點內所有查詢的最小空間鄰近度下界，若對象和節點的空間鄰近度小于該值，則對象與節點內所有查詢均不匹配。HISP[12]在R-tree 節點，維護一個輕量級簽名。LSB(R|w)表示節點中關鍵字前綴中包含w的查詢的空間鄰近度下界中的最小值。CIQ[16]及IQ*-tree[17]在每個Quad-tree 節點按照查詢與節點的空間鄰近度，將查詢分為多個桶。IGPT[18]利用Quad-tree 的葉子節點組織查詢地理位置，并在節點維護查詢的最小空間鄰近度下界。RI[14]在R-tree 節點集成查詢最小及最大空間偏好參數，以及其他屬性的聚合信息。當對象到來時，計算對象與R-tree 節點的相似度上界，以實現快速過濾。HSFTS[19]在Quad-tree 節點為每個查詢集成一個存放結果的最小堆，并標記所有查詢最小的第k個時空流行度。

2.2 提升文本過濾性能的策略

將提升評估CQST 文本過濾性能的策略分為以下四類。

（1）增加文本劃分深度。Rt-tree及其變體[1]，從Rtree 根節點開始，在R-tree 各層節點記錄其后代節點內查詢的一個或多個代表性關鍵字。MBRTrie（trie integrated with minimum bounding rectangle）[3]、APtree、AP+-tree[5]及AP-tree+[6]采用OKT 組織查詢關鍵字，按關鍵字偏移度，查詢被劃分到自適應的文本區間內，即文本區間大小是由查詢文本分布決定的。AP-tree+[6]在AP-tree 的查詢節點及文本節點集成最小簽名，以支持近似關鍵字匹配。為了改善數據處理性能，在GPU 平臺上實現AP-tree+的并行化。利用一維數組將AP-tree+數據結構（即空間節點、文本節點及查詢節點等）映射到GPU 中以形成G-AP-tree+。基于數據流中到來的一組對象的關鍵字和G-AP-tree+特征矩陣中的關鍵字（即查詢的q-gram 關鍵字的最小簽名）并行構造簽名矩陣，計算簽名矩陣中最小簽名間的相似度，以加速對象與G-AP-tree+中查詢的關鍵字的近似匹配。FAST[4]在空間金字塔節點，采用AKI 組織查詢。若查詢無法插入到任何低頻關鍵字對應的RIF 中，將查詢根據關鍵字的字典順序插入OKT 中。若對應文本節點查詢數量超過閾值，則增加OKT 劃分深度。

（2）限制倒排列表中包含的查詢數量。IQ-tree[2]在Quad-tree 節點利用RIF 組織查詢關鍵字，但倒排列表可能依然很長。FAST[4]在空間金字塔節點的RIF 中限制了倒排列表的長度，將多余的查詢插入到OKT 或子節點中，若查詢更新，會導致查詢在RIF 和OKT 間不斷調整。IQ*-tree[17]根據查詢關鍵字的數量對查詢進行分類，對每類查詢構建單獨的IQ*-tree，這是因為查詢和對象的文本相似度與兩者包含的關鍵字數量有關。在Quad-tree 節點集成多層倒排列表，限制倒排列表內查詢的數量。

（3）為查詢計算對象與其匹配需滿足的文本前綴，查詢只插入文本前綴對應的倒排列表中，減少查詢關聯的倒排列表數量。若到來對象不包含關鍵字前綴中的任一文本，則對象不可能是查詢的結果，適用于CTkN 查詢。HISP[12]為查詢計算兩類前綴：Spatial-oriented 前綴（SP 前綴）和Region-Aware 前綴（RA 前綴）。在R-tree 葉節點，查詢插入到其前綴關鍵字對應的倒排列表中。SP 前綴的計算——對任意匹配的對象查詢對，令空間鄰近度為1，得到需滿足的文本相似度下界θT。從查詢最后一個權重最小的關鍵字開始向前求和，得到使權重和小于θT的最小關鍵字對應的序號p，則查詢的SP 前綴為從第一個關鍵字到第p-1 個關鍵字構成的集合。若查詢與對象匹配，則對象必須至少包含查詢SP 前綴中的一個關鍵字，因為第p個關鍵字之后文本的總權重小于θT。類似地，RA 前綴的計算——對任意匹配的對象查詢對，根據查詢到葉節點邊界的最小距離，計算需滿足的文本相似度下界θ′T，根據該值，得到縮小的RA 前綴。SP 前綴對應的倒排列表用于過濾區域內部的對象，RA 前綴對應的倒排列表用于過濾區域外部的對象。擴展的Rt+-tree[13]，利用空間鄰近度上界計算對象與查詢匹配需滿足的關鍵字前綴，在R-tree 節點，記錄后代子節點內查詢的關鍵字前綴。

（4）在索引節點或倒排列表引入文本相似度下界，提前終止節點或倒排列表內查詢的驗證，實現節點、倒排列表或倒排列表組內查詢過濾，適用于CTkN查詢。按照過濾性能分為三類：①索引節點查詢過濾。PT-Quadtree[3]在Quad-tree 節點集成后代節點內查詢包含的共同文本項，或者多個最頻繁的文本項。擴展的Rt-tree[13]，除在R-tree 節點記錄其后代節點內查詢的關鍵字外，還記錄節點中查詢關鍵字的最小權重及最小的查詢范圍。當對象到來時，首先計算對象與節點的相似度，若相似度小于閾值，則該節點過濾。②倒排列表查詢過濾。擴展的Rt++-tree[13]除在R-tree 節點依次記錄其后代節點內查詢的關鍵字外，關鍵字相應倒排列表中增加文本相似度下界，以加快對象處理。③倒排列表組內查詢過濾。對倒排列表中的查詢進行分組，每個組維護相應的文本相似度下界，若到來對象與當前組內查詢的文本相似度小于該值，則提前終止該倒排列表的驗證。CIQ[16]在Quad-tree 節點內各桶中建立基于塊的倒排文件，倒排列表中的查詢按ID 升序排列，每個塊維護一個最低條件文本相似度，若到來的對象與塊的文本相似度小于該值，則對象不可能是當前塊內查詢的結果，實現組過濾。否則，在每個桶中，基于DAAT（document at a time）技術并行遍歷對象中所有關鍵字所在的倒排列表。IQ*-tree[17]在Quad-tree 節點，根據查詢到節點的最小及最大距離，生成兩個ACIR，即在倒排列表中存儲查詢的文本相似度區間。IGPT[18]在Quad-tree 節點中建立倒排列表，查詢根據偏好參數分組，且組內按相關性分值升序排列。若到來對象與倒排列表各組的文本相似度小于組中所有查詢的最小文本相似度，過濾組。TPG（top-ktemporal popularity score index integrated with a subscription grouping mechanism）[19]將查詢范圍有共同交集的一組查詢歸為一組，并在其共同交集的區域，維護組流行度分值及組內擁有最大流行度分值，以實現組過濾。SBCP（segmentgen based block-wise inverted file with a cluster summary index to solve cluster publish/subscribe）[20]倒排列表內查詢按照ID 插入，并分塊，每個塊維護查詢統計信息及與其匹配的對象簇摘要信息，將與查詢匹配的對象簇按相關度分組，并維護組內最大及最小相關度值，以實現組過濾。

2.3 調整空間文本索引結合機制提升過濾性能的策略

評估CQST 的查詢技術緊密結合空間索引和文本索引，到來對象可同時使用兩者過濾搜索空間。二者結合機制大多為空間優先，即將查詢按照空間范圍或地理位置進行組織，在空間節點內集成文本索引提高索引的過濾性能。為了進一步提高索引的過濾性能，研究人員計算當前節點內包含數據的空間分布和文本分布，比較空間劃分與文本劃分的過濾性能，通過相應的代價模型，擇優選取過濾性能較強的索引組織方式。

FAST[4]雖然是空間優先的索引，但查詢關聯到金字塔的哪個節點，是由查詢包含的關鍵字頻率決定的。FAST 從金字塔頂層開始，嘗試將查詢插入到低頻關鍵字對應的RIF 中，若該列表包含的查詢數量小于閾值，則將查詢插入。若查詢無法插入到任何低頻關鍵字對應的RIF 中，將查詢按照關鍵字的字典順序插入到OKT 中。若插入到OKT 的查詢數量超過閾值，則選取查詢范圍較小的查詢進行降維操作。AP-tree 及AP+-tree[5]利用查詢集的空間和文本分布及一個劃分代價模型，將一組查詢自適應地劃分到f個網格或f個文本有序區間，自頂向下遞歸構建。若查詢位置較松散，則將當前節點中的查詢按空間劃分到f個自適應的網格中，每個查詢按其查詢范圍屬于多個網格；若文本區分度大，則按該節點當前關鍵字偏移度將查詢劃分到f個文本有序區間中，每個查詢按關鍵字偏移度屬于一個文本區間。AP+-tree 修整代價模型，在查詢移動方向上增加額外的成本，以反映查詢的移動，使AP-tree 適用于移動場景。LFILTER（location-based filtering algorithm）[3]采用一個代價模型確定采用MBRTrie[3]或者PT-Quadtree[3]過濾驗證到來的對象。

此外，TN（triplet network for learning relevancy metric）[21]訓練三元組卷積神經網絡而非空間文本索引，計算新更新的對象簇是否與查詢相關。

3 分布式集群上評估CQST 的過濾策略

上述工作都是基于中央服務器，即所有工作都在一臺中央服務器上完成，為了進一步加快數據流中對象的匹配，研究人員擴展實時流處理系統Storm，研究分布式服務器集群上CQST 的評估，提出多個分布式空間文本數據流處理系統。如Tornado[8]、Tornado（FAST）[9]及PS2Stream[10]解決分布式集群上CBRQ 查詢問題，DSkype（distributed real-time top-kspatial-keyword publish/subscribe）[18]解決分布式集群上CTkN 查詢問題。SSTD（streaming spatio-textual data）[11]解決分布式集群上多種查詢模型。服務器集群計算資源可分為兩類：一類為全局分發單元（global routing unit，GRU），負責全局調度，將到來的對象或查詢分發到相應的數據處理單元；另一類為數據處理單元（data processing unit，DPU），負責數據處理。在分布式服務器集群上評估CQST，除了需要提高系統吞吐量，減小數據處理延遲外，GRU 數據分發、DPU 工作負載均衡及數據遷移等問題也需要考慮。本文只綜述比較與查詢優化技術息息相關的數據分發及數據處理兩個模塊。（1）數據分發。如何分發數據流中到來對象及查詢到相應的DPU？通常劃分整個空間區域，每個DPU 對應一塊空間區域，查詢及對象映射到一個或多個DPU 上，因此空間區域的劃分需考慮DPU 中處理的對象及查詢占用的內存。（2）數據處理。如何處理映射到DPU 的查詢或對象？這一問題同在中央服務器上評估CQST。

Tornado[8]在Storm 中引入了自適應的時空文本索引層，根據對象和查詢負載變化動態重新分配DPU 中的數據。（1）數據分發。在GRU 上，建立全局空間索引（kd-tree），對象和查詢根據地理位置分發到相應DPU。（2）數據處理。在DPU 上，構建局部時空文本索引（多個kd-tree）組織對象，kd-tree 非葉節點集成倒排列表，以匹配查詢。連續查詢保存在連續查詢緩沖區中，以處理到來對象。

如南宋．梁楷《李白行吟圖》畫唐朝大詩人李白，未畫任何背景，也不講究人體比例，只在表現人物精神上下功夫，寥寥幾筆，便意溢神足，使李白灑脫飄逸的形象躍然紙上。

Tornado（FAST）[9]擴展Tornado。（1）數據分發。采用索引A-Grid（augmented-grid），該索引分為兩層，底層為覆蓋整個空間區域的細化的虛擬網格，上層為與各DPU 對應的非重疊矩形分區。這些分區覆蓋在虛擬網格之上，每個網格單元只屬于一個DPU 分區。到來對象及查詢根據地理位置找到網格，繼而找到相應的分區。A-Grid 為每個DPU 維護包含查詢的文本摘要，以盡早過濾不相關的查詢，減少網絡通信開銷。（2）數據處理。在每個DPU，查詢通過索引FAST 組織，以快速處理數據流中到來的對象。

PS2Stream[10]與Tornado 最大的不同之處在于PS2Stream 考慮所有DPU 上的最佳工作負載分配問題。（1）數據分發?；诓樵兗皩ο蟮目臻g和文本分布，提出最佳工作負載分配算法，使得工作負載總量最小，且DPU 間的工作負載均衡。從kd-tree 根節點開始，計算查詢與對象的文本相似度。若該值小于閾值，比較空間劃分和文本劃分產生的工作負載，并選擇工作負載較小的策略。否則，選擇使查詢及對象文本相似度變小的方向執行空間劃分。這樣將整個空間區域劃分為多個子空間得到的索引稱為kdttree。為了減輕GRU 的負擔，kdt-tree 的葉節點利用網格組織，每個節點中有兩張hash 表描述文本項與DPU 的映射。當對象到來時，根據文本項找到需要驗證的DPU。當新查詢提交時，找到查詢范圍覆蓋的節點，將查詢插入到低頻關鍵字對應的DPU 上。（2）數據處理。采用索引GI2（grid-inverted-index）組織查詢，即在網格節點中集成倒排列表。

DSkype[18]擴展IGPT 到分布式集群上以解決CTkN 問題。（1）數據分發。DSkype 為GRU 設計四種高效的、輕量級分發機制（hashing-based，locationbased，keyword-based 及prefix-based），將數據流中對象及查詢分發給DPU。hashing-based 機制根據查詢ID 將查詢均勻地分發到各DPU，location-based 機制利用kd-tree 將地理位置鄰近的查詢分發到同一個DPU，且kd-tree 劃分方向為最小化兩個子節點代價差的方向。兩類機制中，查詢只會分發到一個DPU，但對象到來時需分發到所有DPU，通信成本較高。在keyword-based 及prefix-based 機制中，每個DPU 關聯一個文本集合，查詢根據關鍵字關聯到多個DPU。為了降低查詢關聯的DPU 數，只將查詢插入到前綴關鍵字對應的DPU 中。數據流中對象只分發到相關的DPU。（2）數據處理。利用IGPT 組織查詢，以快速處理到來的對象。

SSTD[11]支持多種查詢模型。（1）數據分發。在GRU上基于數據流中對象構建QT-tree（quad-text tree），旨在使DPU 保持負載平衡且總工作負載降至最低。對一組對象，QT-tree 從Quad-tree 根節點開始，計算當前節點執行空間劃分及文本劃分產生的負載量，選取負載量小的節點劃分方式。若執行空間劃分，節點被劃分為4 個均等的空間節點，對象按照地理位置被插入到相應的子節點；若執行文本劃分，節點被劃分為4 個文本節點，對象按照代價模型被插入到使負載增量最小的子節點。當對象到來時，其按照QT-tree構建方式，插入到相應葉節點，即相應的DPU；當查詢到來時，若其包含范圍屬性，遍歷QT-tree，找到與查詢范圍在空間上有重疊的所有葉節點，將查詢分發給相應的DPU；否則，將查詢分發到所有DPU。（2）數據處理。每個DPU 對應QT-tree 的多個葉節點。在DPU 上，為每個葉節點各類連續查詢構建單獨的索引以處理數據流中的對象。利用FAST[4]組織范圍查詢，利用網格組織k鄰近查詢，利用擴展的哈希表集成分組技術組織CTkN 查詢。

4 總結與未來發展方向

本章總結全文工作，并討論評估CQST 的未來研究方向。

4.1 總結

4.2 未來發展方向

本文綜述揭示了評估CQST 的兩大趨勢。

（1）追求更高效的評估CQST 的技術。①利用硬件技術提高CQST 的評估效率。通過GPU、分布式集群等硬件技術進一步加快數據流中對象的處理。AP-tree+將AP-tree 與GPU 技術結合，Tornado、PS2Stream、DSkype 及SSTD 實現了分布式系統上CQST 的評估。②犧牲精度提高數據流上對象處理效率。IQ*-tree 解決近似CTkN，判斷到來的對象與查詢匹配的條件是動態的，犧牲小的精度，極大提高數據流上對象處理效率。

（2）解決空間文本數據流上連續查詢的更多場景。除了基本的查詢需求外，CQST 的查詢模型也在不斷增多。①評估連續移動的CQST。AP+-tree 及Elaps 考慮了移動場景下CQST 的評估技術。②其他類型的CQST 查詢模型。擴展的Rt-tree 及變體檢索指定查詢范圍內相似度大于給定閾值的所有對象。AP-tree+解決指定查詢范圍內文本的近似匹配，IQ*-tree 查詢近似的CTkN 對象，即到來的對象與查詢相似度只要高于當前維護分值的1-?倍，則對象就有可能被匹配給查詢。HSFTS 及TPG 在數據流上檢索與查詢地理位置鄰近的、時空流行度最高的Top-k個趨勢關鍵字。SBCP 及TN 在數據流上檢索與查詢相關的對象簇摘要信息。