楊 茸，牛保寧

太原理工大學(xué)信息與計(jì)算機(jī)學(xué)院，山西晉中 030600

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

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

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

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

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

Fig.1 Framework of evaluating CQST圖1 評(píng)估CQST 框架

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

1 評(píng)估CQST 的索引

索引是過濾大量不相關(guān)查詢的基礎(chǔ)，因此本章介紹評(píng)估CQST 的索引技術(shù)，并討論它們的索引性能及優(yōu)缺點(diǎn)。

表1 列出了現(xiàn)有評(píng)估CQST 的索引技術(shù)。

1.1 空間索引

從空間過濾角度看，評(píng)估CQST 為點(diǎn)刺探搜索（point stabbing search）問題，即返回該位置點(diǎn)命中的區(qū)域中的查詢。空間索引是空間過濾的基礎(chǔ)，定位到來對(duì)象落入的空間節(jié)點(diǎn)，驗(yàn)證該節(jié)點(diǎn)內(nèi)的查詢。驗(yàn)證的查詢數(shù)量越少，過濾性能越好。評(píng)估CQST 采用的基本空間索引可分為以下兩大類。

Table 1 Indexes of evaluating CQST表1 評(píng)估CQST 的索引技術(shù)

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

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

1.2 文本索引

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

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

（2）數(shù)據(jù)有序性索引。索引中的數(shù)據(jù)有序，評(píng)估CQST 時(shí)只需驗(yàn)證部分?jǐn)?shù)據(jù)項(xiàng)。優(yōu)點(diǎn)是過濾性能強(qiáng)。缺點(diǎn)是索引構(gòu)建復(fù)雜，更新代價(jià)大。有序關(guān)鍵字字典樹（ordered keyword trie，OKT）[3，5-6]將一組查詢按照其包含的關(guān)鍵字分為多個(gè)分支，到來對(duì)象只需要驗(yàn)證包含文本項(xiàng)的分支。自適應(yīng)關(guān)鍵字索引（adaptive keyword index，AKI）[4，9]是一個(gè)混合索引，集成了RIF與OKT，利用關(guān)鍵字的頻率提高索引的過濾能力。簡而言之，檢查待插入查詢包含的關(guān)鍵字頻率，若查詢包含低頻關(guān)鍵字，則將其插入RIF 中；若查詢只包含高頻關(guān)鍵字，則將其插入OKT 中。

除了上述文本索引外，部分CQST 查詢請(qǐng)求中包含數(shù)值屬性，故在空間節(jié)點(diǎn)中采用OpIndex[7]及區(qū)間樹[14-15]等組織節(jié)點(diǎn)內(nèi)查詢的數(shù)值屬性，即為每個(gè)屬性值建立相應(yīng)的倒排列表，列表包含了數(shù)值數(shù)據(jù)的區(qū)間。

2 評(píng)估CQST 的過濾策略

評(píng)估CQST 的查詢優(yōu)化技術(shù)采用一項(xiàng)或多項(xiàng)過濾策略及方法，以盡可能提升索引的空間和文本過濾性能，為到來對(duì)象過濾大量不相關(guān)的查詢，提高對(duì)象與查詢的匹配效率。

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

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

（1）限制空間節(jié)點(diǎn)內(nèi)插入的查詢數(shù)量。為了提高空間過濾性能，空間節(jié)點(diǎn)中插入的查詢數(shù)量是關(guān)鍵。Rt-tree 及其兩個(gè)變體[1]、擴(kuò)展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 節(jié)點(diǎn)內(nèi)的查詢數(shù)量不超過給定閾值。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 組織查詢的地理位置。它們?cè)诳臻g金字塔或Quad-tree 節(jié)點(diǎn)限制插入的查詢數(shù)量，若查詢數(shù)量大于閾值，則增加空間節(jié)點(diǎn)劃分深度，將查詢插入到下一級(jí)空間節(jié)點(diǎn)。

（2）最小化覆蓋查詢范圍的空間節(jié)點(diǎn)區(qū)域，以減少評(píng)估查詢時(shí)驗(yàn)證對(duì)象的數(shù)量。將查詢范圍映射到Quad-tree、空間金字塔的葉節(jié)點(diǎn)或小粒度的網(wǎng)格、哈希桶均可實(shí)現(xiàn)這一途徑。Elaps（new location-aware pub/sub system）[7]考慮因查詢位置更新導(dǎo)致的通信代價(jià)及數(shù)據(jù)流中對(duì)象的匹配代價(jià)，為移動(dòng)的查詢計(jì)算最佳安全區(qū)域。因查詢?cè)诓粩嘁苿?dòng)，查詢安全區(qū)域需不斷更新，為此該文獻(xiàn)將查詢的安全區(qū)域映射到網(wǎng)格，利用倒排文件組織映射到網(wǎng)格的查詢，以適應(yīng)查詢移動(dòng)（即查詢?cè)诰W(wǎng)格中的更新）。IGPT（index combining both individual and group pruning techniques）[18]利用Quad-tree 的葉子節(jié)點(diǎn)組織查詢地理位置。該類策略空間節(jié)點(diǎn)內(nèi)插入的查詢數(shù)量沒有約束，且查詢范圍較大的查詢被插入到多個(gè)空間節(jié)點(diǎn)，其更新代價(jià)及存儲(chǔ)代價(jià)增加。

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

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

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

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

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

（2）限制倒排列表中包含的查詢數(shù)量。IQ-tree[2]在Quad-tree 節(jié)點(diǎn)利用RIF 組織查詢關(guān)鍵字，但倒排列表可能依然很長。FAST[4]在空間金字塔節(jié)點(diǎn)的RIF 中限制了倒排列表的長度，將多余的查詢插入到OKT 或子節(jié)點(diǎn)中，若查詢更新，會(huì)導(dǎo)致查詢?cè)赗IF 和OKT 間不斷調(diào)整。IQ*-tree[17]根據(jù)查詢關(guān)鍵字的數(shù)量對(duì)查詢進(jìn)行分類，對(duì)每類查詢構(gòu)建單獨(dú)的IQ*-tree，這是因?yàn)椴樵兒蛯?duì)象的文本相似度與兩者包含的關(guān)鍵字?jǐn)?shù)量有關(guān)。在Quad-tree 節(jié)點(diǎn)集成多層倒排列表，限制倒排列表內(nèi)查詢的數(shù)量。

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

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

2.3 調(diào)整空間文本索引結(jié)合機(jī)制提升過濾性能的策略

評(píng)估CQST 的查詢技術(shù)緊密結(jié)合空間索引和文本索引，到來對(duì)象可同時(shí)使用兩者過濾搜索空間。二者結(jié)合機(jī)制大多為空間優(yōu)先，即將查詢按照空間范圍或地理位置進(jìn)行組織，在空間節(jié)點(diǎn)內(nèi)集成文本索引提高索引的過濾性能。為了進(jìn)一步提高索引的過濾性能，研究人員計(jì)算當(dāng)前節(jié)點(diǎn)內(nèi)包含數(shù)據(jù)的空間分布和文本分布，比較空間劃分與文本劃分的過濾性能，通過相應(yīng)的代價(jià)模型，擇優(yōu)選取過濾性能較強(qiáng)的索引組織方式。

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

此外，TN（triplet network for learning relevancy metric）[21]訓(xùn)練三元組卷積神經(jīng)網(wǎng)絡(luò)而非空間文本索引，計(jì)算新更新的對(duì)象簇是否與查詢相關(guān)。

3 分布式集群上評(píng)估CQST 的過濾策略

上述工作都是基于中央服務(wù)器，即所有工作都在一臺(tái)中央服務(wù)器上完成，為了進(jìn)一步加快數(shù)據(jù)流中對(duì)象的匹配，研究人員擴(kuò)展實(shí)時(shí)流處理系統(tǒng)Storm，研究分布式服務(wù)器集群上CQST 的評(píng)估，提出多個(gè)分布式空間文本數(shù)據(jù)流處理系統(tǒng)。如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]解決分布式集群上多種查詢模型。服務(wù)器集群計(jì)算資源可分為兩類：一類為全局分發(fā)單元（global routing unit，GRU），負(fù)責(zé)全局調(diào)度，將到來的對(duì)象或查詢分發(fā)到相應(yīng)的數(shù)據(jù)處理單元；另一類為數(shù)據(jù)處理單元（data processing unit，DPU），負(fù)責(zé)數(shù)據(jù)處理。在分布式服務(wù)器集群上評(píng)估CQST，除了需要提高系統(tǒng)吞吐量，減小數(shù)據(jù)處理延遲外，GRU 數(shù)據(jù)分發(fā)、DPU 工作負(fù)載均衡及數(shù)據(jù)遷移等問題也需要考慮。本文只綜述比較與查詢優(yōu)化技術(shù)息息相關(guān)的數(shù)據(jù)分發(fā)及數(shù)據(jù)處理兩個(gè)模塊。（1）數(shù)據(jù)分發(fā)。如何分發(fā)數(shù)據(jù)流中到來對(duì)象及查詢到相應(yīng)的DPU？通常劃分整個(gè)空間區(qū)域，每個(gè)DPU 對(duì)應(yīng)一塊空間區(qū)域，查詢及對(duì)象映射到一個(gè)或多個(gè)DPU 上，因此空間區(qū)域的劃分需考慮DPU 中處理的對(duì)象及查詢占用的內(nèi)存。（2）數(shù)據(jù)處理。如何處理映射到DPU 的查詢或?qū)ο?？這一問題同在中央服務(wù)器上評(píng)估CQST。

Tornado[8]在Storm 中引入了自適應(yīng)的時(shí)空文本索引層，根據(jù)對(duì)象和查詢負(fù)載變化動(dòng)態(tài)重新分配DPU 中的數(shù)據(jù)。（1）數(shù)據(jù)分發(fā)。在GRU 上，建立全局空間索引（kd-tree），對(duì)象和查詢根據(jù)地理位置分發(fā)到相應(yīng)DPU。（2）數(shù)據(jù)處理。在DPU 上，構(gòu)建局部時(shí)空文本索引（多個(gè)kd-tree）組織對(duì)象，kd-tree 非葉節(jié)點(diǎn)集成倒排列表，以匹配查詢。連續(xù)查詢保存在連續(xù)查詢緩沖區(qū)中，以處理到來對(duì)象。

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

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

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

DSkype[18]擴(kuò)展IGPT 到分布式集群上以解決CTkN 問題。（1）數(shù)據(jù)分發(fā)。DSkype 為GRU 設(shè)計(jì)四種高效的、輕量級(jí)分發(fā)機(jī)制（hashing-based，locationbased，keyword-based 及prefix-based），將數(shù)據(jù)流中對(duì)象及查詢分發(fā)給DPU。hashing-based 機(jī)制根據(jù)查詢ID 將查詢均勻地分發(fā)到各DPU，location-based 機(jī)制利用kd-tree 將地理位置鄰近的查詢分發(fā)到同一個(gè)DPU，且kd-tree 劃分方向?yàn)樽钚』瘍蓚€(gè)子節(jié)點(diǎn)代價(jià)差的方向。兩類機(jī)制中，查詢只會(huì)分發(fā)到一個(gè)DPU，但對(duì)象到來時(shí)需分發(fā)到所有DPU，通信成本較高。在keyword-based 及prefix-based 機(jī)制中，每個(gè)DPU 關(guān)聯(lián)一個(gè)文本集合，查詢根據(jù)關(guān)鍵字關(guān)聯(lián)到多個(gè)DPU。為了降低查詢關(guān)聯(lián)的DPU 數(shù)，只將查詢插入到前綴關(guān)鍵字對(duì)應(yīng)的DPU 中。數(shù)據(jù)流中對(duì)象只分發(fā)到相關(guān)的DPU。（2）數(shù)據(jù)處理。利用IGPT 組織查詢，以快速處理到來的對(duì)象。

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

4 總結(jié)與未來發(fā)展方向

本章總結(jié)全文工作，并討論評(píng)估CQST 的未來研究方向。

4.1 總結(jié)

4.2 未來發(fā)展方向

本文綜述揭示了評(píng)估CQST 的兩大趨勢。

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

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