空間關鍵字查詢綜述

孟祥福，王丹丹，張 峰

遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105

空間關鍵字查詢在實際中的應用越來越廣泛，研究方面也逐漸增多。傳統的空間關鍵字查詢主要是同時考慮查詢對象、查詢點的位置信息和它們關鍵字的匹配程度的新型的查詢處理類型，空間關鍵詞查詢具有重要的理論研究價值?？臻g關鍵字查詢包含索引機制、查詢模型和與其他技術結合的查詢算法等三個方面。隨著對空間關鍵字查詢的研究，研究者們提出了多種索引結構，例如文本搜索的索引技術倒排文件（Inverted file）、簽名文件（Signature file）和位圖索引（Bitmap）等，基本的空間索引結構R-Tree，基于R-Tree改進的索引結構R+-Tree、R*-Tree，結合空間和文本索引技術的索引結構IR2-Tree、bR*-Tree、IR-Tree、Light-Weighted、兩階段索引等，基于IR-Tree的改進CIR-Tree、CDIR-Tree、WIR-Tree以及SIR-Tree等，其他索引結構VP-Tree、G-index索引、IRS-Tree、QuadTree、KR*-Tree、S2I等。

還有研究者對空間關鍵字查詢處理模式改進，現有的對于空間關鍵字的查詢處理模式主要可以分為4類：（1）布爾范圍查詢，該查詢模式返回那些地理位置在查詢區域內且文本描述包含所有查詢關鍵字的興趣點；（2）布爾kNN查詢，該類方法用于檢索文本描述包含所有查詢關鍵字且距離查詢位置最近的前k個空間對象；（3）top-k范圍查詢，用于檢索位于查詢區域內且與查詢關鍵字具有最高文本相似度的前k個空間對象；（4）top-kkNN查詢：該類方法根據空間對象的文本相關性和位置相近性進行top-k檢索和排序，排序分數根據空間對象的文本描述與查詢關鍵字的文本相似度和對象到查詢位置的距離的權重進行評估。近年，又提出一種新的查詢處理-反最近鄰（RNN），反最近鄰是由最近鄰查詢擴展而來的。

最后，傳統的空間關鍵字查詢通常是假定用戶明確自己的查詢意圖并且僅支持嚴格查詢匹配，但是隨著用戶需求的不斷劇增，顯然，這種簡單的形式上的匹配已經不能夠滿足用戶的需要。通常情況下，用戶的查詢意圖是模糊或不精確的，用戶往往會使用自己熟知的關鍵字表達查詢意圖，因此提出的關鍵字查詢也并非能夠有效表達出用戶的查詢需求，所以考慮語義近似、用戶偏好等能夠更好地滿足用戶的個性化查詢需求。所以進而學者們提出了一些新的改進，結合語義近似或用戶偏好進行查詢。之前傳統的空間關鍵字查詢大多數在歐式空間上進行，但實際上，歐式空間的位置、距離并不與實際路線完全吻合，所以進一步研究了路網上的空間關鍵字查詢。并且隨著社會的發展和用戶的實際需要，研究者們研究了路線規劃查詢、社交網絡上的查詢、基于影響約束下的查詢等。近年，隨著大數據與可視化的流行，研究者們也將目光放到了可視化技術上面，結合空間關鍵字和可視化進行查詢。

1 索引結構

傳統索引方法有哈希表和B-Tree。哈希表可以對數值進行精確匹配，但是不能進行范圍查詢。B-Tree是對鍵值的一維排序，但不能搜索多維空間。B-Tree是一種相對來說比較復雜的數據結構，尤其是在它的刪除與插入操作過程中，因為它涉及到了葉子結點的分解與合并。除了傳統的索引方法，還提出一些空間索引結構，就是指依據空間實體的位置和形狀或空間實體之間的某種空間關系，按一定順序排列的一種數據結構，其中包含空間實體的概要信息如對象的標識、外接矩形及指向空間實體數據的指針等。簡單的說，就是將空間對象按某種空間關系進行劃分，以后對空間對象的存取都基于劃分塊進行。

1.1 空間索引結構

R-Tree[1]：R-Tree是最基本的空間索引結構，Guttman在1984年最早提出。R-Tree是一種高度平衡樹，由非葉子結點和葉結點組成，空間對象的最小邊界矩形（Minimum Bounding Rectangle，MBR）存儲在葉結點中，非葉子結點通過聚合其孩子結點的外接矩形而形成，根結點包含了所有這些外接矩形。R-Tree葉子結點存儲結構形式(Rectangle,Obj),Rectangle表示圍住葉子結點中所有空間對象區域的最小邊界矩形MBR,Obj表示一個空間數據對象；非葉子結點存儲結構形式(Rectangle,Child),Rectangle表示的是包圍其所有子結點所在區域的MBR,Child是指向該非葉子結點的子結點。圖1是RTree結點存儲結構，如果該結點是葉子結點，E表示空間數據對象；若該結點是非葉子結點，E表示指向子結點的條目。

圖1 R-Tree結點存儲結構Fig.1 R-Tree node storage structure

R-Tree是B-Tree在k維空間上的自然擴展，R-Tree的優點是一種動態索引結構，即它的查詢可與插入或刪除同時進行，并且不需要定期地對樹結構進行重新組織。R-Tree索引結構的作用在于，進行一個空間查詢時，只需遍歷少數幾個中間結點即可定位到要找的空間對象（即逐漸縮小到某個區域進行查詢），但是缺點是只能存儲空間對象的位置信息，不能存儲其文本信息?；赗-Tree改進的索引結構IR-Tree[2-3]、CIR-Tree[4]、CDIRTree以及SIR-Tree等也是當前的研究熱點。R-Tree空間索引算法的研究應該做到：支持高維數據空間；有效劃分數據空間，以適應索引的組織；實現多種查詢方式系統中的統一。對于R-Tree的索引結構最新研究不應該僅僅為了加快某種查詢方式或提高某個方面的性能而忽略其他方面的影響，這樣可能會導致更多不必要的性能消耗。

R+-Tree：R+-Tree與R-Tree類似，主要區別在于R+-Tree中兄弟結點對應的空間區域無重疊，這樣劃分空間消除了R-Tree因允許結點間的重疊而產生的“死區域”（一個結點內不含本結點數據的空白區域），該索引結構的優點是減少了無效的查詢，大大提高空間索引的效率，但對于插入、刪除空間對象，由于操作要保證空間區域無重疊而效率降低。同時R+-Tree對存儲跨區域的空間物體的數據是冗余的，隨著數據庫中數據的增加，冗余信息會不斷增加。

R*-Tree[5]是R-Tree的變體，是在R-Tree的基礎上對部分算法進行了優化改進，相對R-Tree優化的地方是強制重新插入算法。R-Tree的插入操作導致結點溢出時，采用分裂的方法進行處理，而R*-Tree對新的空間對象索引項的插入導致結點溢出時，它將會選擇部分結點在同層結點間進行調整，以推遲結點分裂，從而達到優化R-Tree整體結構的目的?；赗*-Tree的空間索引算法優點是提高了空間的利用率，插入成本低于R-Tree，但缺點是增加了CPU代價。

下述例子描述R*-tree結構，R7～R14表示數據對象。采用空間分割方法構造R*-Tree，用最小邊界矩形圍住空間中的每個數據對象，然后將空間中彼此距離接近，使得矩形增加的面積最小的空間對象用更大的最小邊界矩形包圍起來。如圖2中，由更大的最小邊界矩形R4將彼此最為鄰近的R8、R9、R10包圍起來，用此方法將空間區域劃分好后，將這些矩形存儲到R*-Tree，圖2中的數據對象所構成的R*-Tree結構如圖3所示。

圖2 數據對象Fig.2 Data objects

圖3 數據對象所對應的R*-TreeFig.3 R*-Tree corresponding to data object

R-Tree及基于R-Tree改進的索引結構都只存儲空間信息，較適合范圍查詢，R+-Tree不易實現不規則空間對象的任意查詢。

1.2 空間文本混合索引結構

IR2-Tree[6]：MBR和簽名文件Signature組成了IR2-Tree。它的優點是存儲代價小、搜索效率高，但查詢關鍵字必須嚴格匹配。圖4顯示使用表1的空間對象數據集的IR2-Tree示例。與R-Tree相比，IR2-Tree的結點中存儲包含文本信息的簽名文件，并且在這里簽名文件被簡化，每個比特為一個關鍵詞：Shop，spa，internet，pool，launch，pet，1表示結點包含了對應的關鍵詞，0表示不包含。

圖4 表1對應的IR2-TreeFig.4 Corresponding IR2-Tree in Table1

表1 空間對象的樣本數據集Table 1 Sample dataset of spatial objects

bR*-Tree[7]：R*-Tree+BitMap，R*-Tree結點包含MBR，并且有結點中所有關鍵字的位圖和關鍵字MBR，它的優點是存儲空間小，缺點是關鍵字匹配需求高，關鍵字多，I/O代價高。

IR-Tree：IR-Tree本質上是一個R-Tree，是由R-Tree和Inverted file構成，IR-Tree的每個結點含有倒排文件（倒排文件是用于復雜的查詢，是一種特殊的文件結構）。對于IR-Tree的一個葉結點N，它的形式為(O,rectangle,O.di)，其中O是一個空間對象，rectangle是對象O的邊界矩形，O.di是空間對象O的關鍵詞信息。葉子結點還包含一個指向被索引對象的文本文檔的倒排文件的指針。對于IR-Tree的一個非葉子結點R，它的形式是(cp,rectangle,cp.di)，其中cp是R的一個子結點的地址，rect angle是最小邊界矩形（是查找、刪除、插入操作的關鍵），cp.di是子結點偽文檔的標識符。倒排文件中包含兩個主要部分：（1）所有文檔關鍵詞；（2）一個記錄列表集合，每一個記錄里，對于一個關鍵詞t有d表示包含t的文檔，Wd,t表示t在文檔d中的權重。它提高了搜索效率，所占的存儲空間較小，允許查詢關鍵字部分匹配。

圖5描述8個空間對象O1,O2,…,O8的位置，表2描述了空間對象的文本信息，圖6是圖5的IR-Tree示例。

圖6 IR-Tree索引Fig.6 IR-Tree index

表2 空間對象的文本信息Table 2 Text information for spatial objec

圖5 空間對象及邊界矩形Fig.5 Spatial objects and boundary rectangles

Light-Weighted[8]將R*-Tree和Inverted file分開存儲，R*-Tree結點包含MBR和結點到根結點路徑的Label，倒排結點包含標記位置組成它的可擴展性較強，搜索效率高，但存儲代價高，需要頻繁進行插入操作，導致計算代價過高。

兩階段索引[9]，它是由R-Tree和Inverted file構成的，其中R-Tree結點包含MBR，倒排文件結點包含關鍵字信息。具有結構簡單的優點，但存儲代價高，無法確定第一階段產生的候選對象個數。

空間文本混合索引結構是空間和文本索引技術的集成，能夠同時存儲位置和文本信息，IR2-Tree和bR*-Tree對關鍵字匹配要求較高，適合對關鍵字進行精確匹配的查詢；IR-Tree允許查詢關鍵字部分匹配，比較適合top-kKNN查詢。

1.3 其他索引結構

VP-Tree[10]：1993年被提出，VP-Tree是二叉空間劃分樹，隨機選取某數據點作為制高點，計算其他點到制高點的距離并根據制高點的距離劃分點。求出距離中值，小于中值的數據分給左子樹，大于中值的數據點分給右子樹，遞歸建立左子樹、右子樹，VP-Tree作用于任何度量空間，可利用VP-Tree做k近鄰查詢，圖7是VPTree的一個例子，選取<5，6>為制高點。

圖7 VP-Tree例子Fig.7 Example of VP-Tree

QuadTree[11]：其區域搜索效率較高，但是樹結構不平衡，動態性差，存儲代價較高。QuadTree是將已知范圍的空間劃成四個相等的子空間，并且子空間可以繼續劃分直到一定深度或滿足某種要求，圖8是VP-Tree的一個例子。一些QuadTree的改進是將QuadTree和結點中文本信息對應的倒排文件組成，例如IL-QuadTree[12]。

圖8 四叉樹示例Fig.8 Example of quadtree

G-index索引[13]：聚類標準+聚類操作，通過聚類操作。但是，可泛化成其他索引結構。具有通用性，但是有較高的泛化計算代價，存儲代價較高。

IRS-Tree[14]是一種擁有Synopses的倒排R-Tree的混合索引結構，能夠有效處理一組位置敏感等級查詢?；贗RS-Tree的查詢算法要求提供數值屬性的精確范圍，這樣可能會導致過少甚至沒有查詢結果返回。

此外，還有一些其他的索引結構，例如Hariharan等人提出KR*-Tree（關鍵字R*-Tree）。KR*-Tree的每個結點實際上都被一組關鍵字擴充了，這些關鍵字出現在以該結點為根的子樹中。KR*-Tree的結點被組織成倒排的列表，對象也是如此。在文獻[15]中提出了一種新的索引來提高top-k空間關鍵字查詢的性能，即空間倒索引（Spatial Reverse Index，S2I）。Wu等人[16]提出了WIR-Tree，其目的是將對象劃分為多個組，使不同的組盡可能少地共享公共關鍵字。

QuadTree適合空間對象分布均勻的查詢。VP-Tree通過選擇空間中的制高點，并將數據點分為兩個分區來分離度量空間中的數據。因此，可以使用VP-Tree來查找在特定點附近沿距離方向的數據，適合范圍查詢和近鄰查詢。IRS-Tree適用于包含數值屬性的空間對象，但需提供數值屬性的精確范圍。

1.4 文本索引

文本搜索的索引技術有：倒排文件（Inverted file）、簽名文件（Signature file）和位圖索引（Bitmap）等。它們主要集中于關鍵字的精確匹配，但由于文本表達形式的多樣性，可能導致結果太少。

現有的索引技術主要分為空間索引、文本索引和空間文本混合索引，各個索引有不同的優點，但是同時它們也存在不足之處，文本索引需要精確匹配，所以得到的結果有時候不能滿足用戶的需求?？臻g索引包含RTree和基于R-Tree改進的索引結構、VP-Tree、QuadTree及對其的改進索引結構、G-index等。R-Tree是比較基礎的且被利用得較多的一種索引結構，但是R-Tree不能存儲文本信息；R*-Tree對R-Tree整體結構優化，但是CPU代價較高；QuadTree搜索效率較高但存儲代價大；G-index具有通用性，但泛化計算代價高?，F有的空間文本索引大多是將空間索引技術和文本索引技術結合，例如，BR*-Tree將R*-Tree和Bitmap結合；IR-Tree將RTree和Inverted file結合；IRS-Tree還考慮了包含空間對象的數值屬性信息，但是需要提供數值的精確范圍，具有一定的局限性。

2 空間關鍵字查詢處理模式

現有的對于空間關鍵字的查詢處理模式主要可以分為4類：布爾范圍查詢、布爾k近鄰（KNN）[17]查詢、top-k范圍查詢[18]和top-k k近鄰查詢[19]。布爾范圍查詢返回文本描述包含所有查詢關鍵字且地理位置在查詢區域內的興趣點。需要精確匹配文本，而且不能控制查詢結果規模、不能對查詢結果進行排序。布爾k近鄰（KNN）查詢用于檢索文本描述包含所有查詢關鍵字且距離查詢位置最近的前k個空間對象，它是通過查詢點與興趣點之間的距離對查詢結果進行排序，排序先后與距離大小成反比。上述兩種查詢方法都需要所有文本精確匹配，這將會導致沒有結果或很少的結果被返回，或者是查詢結果與查詢點位置較遠。top-k范圍查詢用于檢索位于查詢區域內且與查詢關鍵字具有最高文本相似度的前k個空間對象，其結果只能包含部分關鍵字，但是該方法并沒有考慮位置相關性。top-k k近鄰查詢根據空間對象的文本相關性和位置相近性進行top-k檢索和排序，根據空間對象的文本描述與查詢關鍵字的文本相似度以及對象到查詢位置的距離的權重來評估排序分數。

近年，提出一種新的查詢處理-反最近鄰（RNN），反最近鄰查詢是在最近鄰查詢的基礎上提出來的，反最近鄰問題本質上就是數據集中某些點所帶來的影響集的問題，比如一家咖啡館要在某個商場開店，這就必定會對周邊的一些咖啡店或者飲品店帶來客戶上的影響，其中受影響最大的咖啡店或飲品店就是想要的結果，也是RNN查詢最終的目的，RNN應用廣泛成為一項重要的研究。對RNN查詢的研究主要是基于R-Tree及其擴展進行的，這樣引入了R-Tree的缺點。Korn等人[20]提出一種RNN查詢算法，基于R*Tree構造了RNN-Tree（Reverse Nearest Neighbor Tree，RNN-Tree）來實現查詢，但是這種方法的缺點主要在于動態情況下需要建立兩個索引，而且由于存儲區域較大的重疊導致性能降低。Yang等人[21]提出一種基于RDNN-Tree（R-Tree containing Distance of Nearest Neighbor）的RNN查詢算法，該算法有效地避免建立兩個索引結構，提高了查詢效率。然而，RDNN查詢僅僅對低維數據有效，并且隨著維數的增加，RDNN查詢性能會因為R*-Tree的限制而急劇下降。郝忠孝等人[22]提出了基于SRdnn-Tree（SR-Tree containing distance of nearest neighbor）索引結構的RNN查詢算法，突破了R*Tree在高維數據空間查詢的局限性。李松等人[23]使用Voronoi圖和空間劃分區域的性質計算查詢點的反最近鄰，并結合R*Tree構造了一種新的基于Voronoi圖的索引結構（Voronoi diagram-based Reverse Nearest Neighbor query Tree，VRNN-Tree），基于該索引結構的RNN查詢適用于平面和復雜曲面上的數據點。王淼等人[24]提出了一種新的基于Delaunay圖的索引結構Delaunay-Tree用來解決反最近鄰問題，將查詢點作為Delaunay圖的一個生成點，利用Delaunay圖的生成點與其鄰接生成點之間的關系來查詢數據集中的反最近鄰。

2013年，Jiang等人提出了top-k組反最近鄰查詢，識別并解決了一種新的查詢，即反向top-k組最近鄰（RkGNN）查詢。他們定義了RkGNN查詢（GNN的一種變體），以最佳優先方式搜索[25]，并使用當前條目e與查詢對象q之間的最小距離作為排序鍵。然后，他們采用了一些有效的修剪啟發式算法來剔除不合格的候選子集，利用排序和閾值機制來縮小搜索空間，并充分利用了惰性修剪和空間修剪技術的優點有效地處理了RkGNN查詢，即開發了兩種算法LRkGNN（惰性LRkGNN）和SLRkGNN（空間修剪LRkGNN）來有效地解決top-k組反最近鄰查詢。之后，Cheema等人[26]研究了反k最近鄰（ReversekNearest Neighbor query，RkNN）和反top-k查詢，并利用基于區域修剪的算法和線性評分函數對SPTk（Spatial reverse top-k）查詢進行了優化。Wang等人[27]研究了基于動態軌跡的反k最近鄰查詢，提出了RkNNT（ReversekNearest Neighbor search over Trajectories）算法來解決動態路線規劃問題。Wang等人[28]改進了傳統的基于位置查詢的反k最近鄰查詢算法，利用遞增的臨時網絡擴展樹更新道路網絡的權重變化，從而實現動態監測目標的結果。Hidayat等人[29]在影響區域的基礎上提出了影響因子的概念，同時利用新定義的修剪圓對空間進行修剪，篩選合適的數據，從而提高RkNN查詢的效率和準確性。Guillaume等人[30]提出了一種近似求解RkNN查詢的方法，該方法基于內在維度的特征優化修剪操作，降低了預處理成本，并提高了在高維度時的查詢性能。Francisco等人[31]分布式的思想應用于處理RkNN查詢，利用無共享空間云基礎架構Spatial Hadoop和Location-Spark設計分布式RkNN查詢算法，提高了分布式空間數據管理系統的效率和可擴展性。

最近，劉潤濤等人[32]提出了一種基于新型索引結構的反最近鄰查詢，先定義空間物體間的4種序關系，然后利用這些序關系提出了一種新的索引結構：MBDNNTree（index Tree based on the Minimum Bounding square and the Distance of Nearest Neighbor），這種索引結構運用了R-Tree中分割數據空間的思想，將數據點集通過最近鄰距離擴展為空間物體，繼而利用其中多種序關系優化索引結構，將空間位置相近的數據盡可能地存儲在同一結點中，使得該索引結構中同層結點之間均滿足同一種序關系，運用該關系，給出進行RNN查詢的高效修剪規則，再對中間結點進行較少量的簡單計算即可有效地減少了結點的訪問數量，從而提高查詢效率。

3 其他技術結合的查詢算法

3.1 空間-文本查詢

傳統的空間關鍵字查詢將用戶位置和用戶提供的關鍵字作為參數，并返回與這些參數在空間和文本上相關的web對象。文獻[2-3，6，15，33-40]在研究空間-文本查詢的不同方面做出了一系列的貢獻。在文獻[2-3，15]中，研究了歐氏空間中top-kkNN查詢。一些工作[2，6]主要集中在需要精確關鍵字匹配的空間關鍵字布爾查詢（SKBQ），但是很明顯，由于文本表達的多樣性，它們可能導致返回結果太少或沒有。為了克服這個問題，研究人員最近[15，35，38]提出了一些新的索引結構去支持空間關鍵字近似查詢（SKAQ），這些結構能夠處理在實際應用中經常出現的拼寫錯誤和傳統拼寫差異（例如“theater”和“theatre”）。

空間對象的位置信息通常由經緯度表示，因此對于空間對象位置的度量是至關重要的，現有的方法大多可以計算位置間的距離，幾種比較常用的方法例如歐氏距離、馬氏距離、曼哈頓距離、切比雪夫距離和余弦相似度?，F有的文本相似度的計算方法：內積法、余弦法、Dice系數法、Jaccard系數法、基于向量空間模型等。

但傳統的空間關鍵字查詢主要關注空間和文本相似性，忽略了用戶偏好、語義近似等方面。

3.2 語義近似查詢

現有的空間關鍵字查詢方法主要關注空間和文本相似性，忽略了對空間Web對象和查詢中關鍵字的語義理解。由于對對象和查詢中的語義缺乏理解，它們仍然無法檢索與查詢中的關鍵字同義但完全不同的對象，如“theater”和“cinema”。這種差異促使研究其他語義感知的方法，以捕獲空間關鍵字的語義含義。在文獻[37，41]中研究了具有語義的空間關鍵字查詢，其目標是找到在空間鄰近性和語義相關性方面最優的對象。Qian等人[42]定義了一種新的空間關鍵字查詢，它同時考慮了空間、文本和語義相似性。提出新穎的索引結構，即NIQTree和LHQ-Tree，該結構以一種分層的方式將空間、文本和語義信息集成在一起，以便在查詢處理時有效地修剪搜索空間。采用了一種改進的基于iDistance[41]的混合索引結構NIQ-Tree[43]。通過利用iDistance繪制主題分布，NIQ-Tree將支持同時對空間、文本和語義維度進行有效的修剪?？梢员苊庠诟呔S空間中索引所有對象時出現大量的死空間。但由于“維數災難”，算法[44]性能受到大量潛在主題的影響。所以他們進一步設計了一個基于局部敏感哈希（LSH）的混合索引結構，稱為LHQ-Tree，它能根據查詢的空間、文本和語義一致性，避免掃描無希望的對象。在LHQ-Tree的基礎上，提出了一種新的查詢處理機制，基于一定的理論邊界有效地裁剪搜索空間。

現有的語義相似度計算方法：（1）通過本體定義術語/概念之間的距離定義拓撲相似性來估計語義相似性。（2）通過向量空間模型等統計手段估計語言單元（單詞、句子等）之間的語義相關性。（3）利用概率主題模型對文本信息進行語義相似處理。通過主題模型可以測量文本與主題之間的語義關系，也可以測量不同文本之間的語義關系?，F已有很多經典的主題模型：Latent Dirichlet Allocation（LDA）[43]、Dynamic Topic Model[45]、Dynamic HDP[46]、Sequential Topic Models[47]等。

3.3 基于路網的查詢

已有的研究大多數集中在歐式空間中如何有效處理空間關鍵字查詢，但事實上人們的日常生活是被路網約束的，空間鄰近性應該由最短路徑距離而不是歐氏距離來決定，在歐式空間查詢的最優結果在實際中不一定是最優的結果。所以現在一些工作研究了一個新的問題，即在路網上進行空間關鍵字查詢。與歐式空間相比，基于路網的空間關鍵字查詢的研究更具有現實的意義和價值，也給研究者們帶來了更大的挑戰。

Rocha-Junior等人[48]首次解決了在路網上處理top-k空間關鍵字查詢的問題，該文利用覆蓋網絡使查詢處理更高效。例如，圖9展示了一個景點的路網和空間文本對象。圓圈表示空間文本對象o,q.l表示查詢位置。假設一名游客在q.l帶著一部手機并提出一個top-k空間關鍵字查詢，尋找“hotel”。如果是歐式空間中的傳統查詢，O9將作為top-1結果，但是考慮路網后，top-1結果是O6。在路網的top-k空間關鍵詞查詢中，同時考慮了最短路徑和文本相關。

圖9 從波士頓大學到波士頓市中心的路線Fig.9 Route from Boston University to downtown Boston

文獻[49]首次提出了路網中連續的top-k空間關鍵字查詢，提出了兩種以增量方式遍歷網絡的方法，即以查詢為中心的算法（QCA）——從查詢位置所在的邊的結束結點開始遍歷網絡，直到找到top-k結果為止。同時，它維護了一個擴展樹，以避免后續處理時不必要地遍歷一些網絡邊緣。和以對象為中心的算法（OCA）——從與查詢關鍵字相關的對象開始遍歷。這樣，經過初始處理后，構造出一棵最短路徑樹，后續處理可以利用這棵樹顯著減少遍歷的邊數。原則上，這兩種方法都可以通過查找感興趣的對象來減少問題，從而將查詢轉移到檢查靜態網絡結點，減少連續監控時不必要的重復遍歷網絡邊緣。

上文提及的文獻[28]利用遞增的臨時網絡擴展樹更新道路網絡的權重變化，從而實現動態監測目標的結果。文獻[50-53]將top-kkNN查詢應用于路網。Cho等人[50]提出了一種新的算法ALPS來對路段對象進行分組，并將分組對象轉換為數據段，從而實現最小化數據對象的數量。此外，Rocha-Junior等人[52]提出了一種提高查詢處理性能的新算法，該算法避免了在查詢執行過程中檢查數據對象的空間鄰域。與此同時，文獻[53]提出了一個新的問題：利用社會影響（RSkNN）對路網進行kNN搜索。但現有的路網空間索引不能夠支持大規模的路網環境，而且目前基于路網環境下的查詢方法能夠處理考慮位置鄰近和文本相似的空間關鍵字查詢，但對于考慮用戶偏好的空間關鍵字查詢還不能夠有效地處理。

3.4 路線規劃查詢

路線規劃查詢旨在找到滿足用戶需求的最優路線，比如可以利用基于關鍵字的最優路線查詢為用戶規劃包含用戶所有感興趣的旅游景點并且花費較低的一條路線。例如Li等人[54]在空間數據庫和路網中提出了一個旅行計劃查詢（Trip Planning Query，TPQ），其中每個空間對象都有一個位置和一個類別。查詢的目的是找到起點和目標位置之間的最短路徑，并且該路徑需要通過用戶指定的每個類別中的至少一個對象。例如，一個用戶要從波士頓大學到波士頓市中心，他在途中想要經過ATM機、加油站和希臘餐館，目標是為他提供可能的最佳路線（根據距離、交通、道路狀況等），這個查詢的困難在于每個類別都有多個選擇，對于這個查詢，存儲上述類別（以及其他類別）對象位置的數據庫，應該有效地計算出最小化總旅行距離的可行行程。另一種應該是提供一種能使總旅行時間最小化的行程。

圖9（a）和（b）展示了文獻[54]中的例子，從波士頓大學（1）到波士頓市中心（2）需要途經加油站（3）、自動取款機（4）和希臘餐館（5）。在圖9的例子中，用戶明確地選擇了一條包括ATM機、加油站和希臘餐館的路線。顯然，該系統不僅可以對停下的順序重新排列以優化這條路線，也能為用戶建議用戶所不知道的其他選項（例如在地圖上所示的大量的自動取款機）。

Sharifzadeh等人[55]研究了TPQ的一個變體，稱之為最優順序路由查詢（OSR）。在OSR中，對查詢類別施加總順序，只指定起始位置。另一個例子是Cao等人[56]提出的關鍵字感知最優路由（Keywords-aware Optimal Route，KOR）搜索查詢，該查詢發現目標分值最小且路由的預算分值小于某一閾值的路由，同時覆蓋所有查詢關鍵字。并且前文提到的文獻[27]提出了RkNNT算法，解決動態路線規劃，該算法研究了基于動態軌跡的反k最近鄰查詢。

3.5 社交網絡查詢

有一些研究者們沒有考慮上述部分，而是考慮身邊朋友的影響，關注于社交網絡中的查詢。比如，Yang等人[57]提出了一個社會空間組查詢，該查詢選擇一組附近的具有緊密社交關系的參與者。要求與會者到集合點的空間距離最小，同時滿足一定的社會約束。

Lappas等人[58]研究了在社交網絡中尋找專家團隊的問題。目標是從社交網絡找到一群人，每個人都有特定的技能，這樣他們可以合作完成一項任務，使他們的溝通成本最小化，這項工作不考慮空間方面。文獻[58]中一個社交網絡查詢例子，現在要建立一個工程師團隊來完成一個項目，這些項目需要以下方面的技能：算法、軟件工程、分布式系統、web編程。同時假設有5個候選對象{O1,O2,O3,O4,O5}，他們具有以下背景：XO1={軟件工程，分布式系統，web編程}，XO2={web編程}，XO3={軟件工程，分布式系統}，XO4={軟件工程，分布式系統，web編程}，XO5={算法}。但一個項目的成功不僅取決于參與人員的專業知識，還取決于他們作為一個團隊如何有效地協作、溝通和工作。所以下面用圖10所示的社交網絡表示了這些候選對象之間的關系，其中圖中兩個結點之間存在一條邊，說明對應的人可以有效地協作。

圖10 {O1,O2,O3,O4,O5}中個體之間的社交網絡Fig.10 {O1,O2,O3,O4,O5}social networks among individuals

在上述例子中，如果不考慮團隊成員的協作效率，團隊{O2,O3,O5}或{O1,O5}都可以滿足所需的技能，但如果考慮團隊成員的協作效率，根據圖10可以得出團隊{O2,O3,O5}是最優解，圖中結構表明O1和O5不能一起工作，因為同一組或部門的人比在不同部門工作的人更容易溝通。

3.6 空間關鍵字組查詢

現有的空間關鍵字查詢方法主要側重于尋找單個POI，但是單一對象可能不容易滿足用戶的需求，所以最近一些關于空間關鍵字查詢的研究側重于尋找一組對象作為滿足用戶需求的解決方案[57，59-69]，稱為集合空間關鍵字查詢（CSKQ）。CSKQ目的是給定用戶的查詢位置和關鍵字，將查找一組對象，這些對象覆蓋查詢的關鍵字，且接近查詢的位置，同時組內對象也互相接近。例如，一個游客可能有特定的購物、餐飲和住宿需求，所以最好由幾個空間web對象，來更好地滿足該游客的需求，這些web對象必須涵蓋所有查詢關鍵字，彼此互相接近且都接近查詢位置。近幾年集合空間關鍵字查詢（CSKQ）在空間文本數據庫領域受到了廣泛的關注。

Cao等人[60]提出高效處理空間關鍵字組查詢，解決了三個實例化的檢索top-k組的問題，設計了精確解和具有可證明的近似解，并研究了合并了對象權重的問題的加權版本。

Yu等人[61]提出新的個性化空間關鍵字查詢問題——集合關鍵字偏好查詢（Collective Keywords Preference Query，CKPQ）。首先設計了基于訪問歷史和潛在POIs主題的用戶偏好模型，然后可以根據集合內的距離、查詢位置的距離以及集合關鍵字的可達性（由POI流行度和擁塞度確定，避免在高峰時間訪問受歡迎的POI）構造一個成本函數，根據該模型計算候選群體的成本。還提出了一種基于IR-Tree和修剪策略的高效算法，可以找到一個CKPQ的解來實現多個優化目標之間的平衡。

Park等人[62]定義了反向集合空間關鍵字查詢（Reverse Collective Spatial Keyword Query，RCSKQ）。它是一種新穎的反向空間關鍵字查詢，用于查找CSKQ中包含查詢對象的所有用戶。提出了兩種新的過濾策略，一種是利用改進的G-Tree索引結構（具有最大距離的反向GTree）來解決計算開銷問題的用戶過濾策略。G-Tree是一種改善最短路徑問題計算性能的路網指標結構。另一種是無索引結構的啟發式過濾，減少搜索空間。

在文獻[8，63]中，Zhang等人提出了一種新的空間關鍵字查詢，稱為m-最近鄰關鍵字（mCK）查詢，其目的是找到與m個用戶指定關鍵字匹配的空間最近鄰元組。Cao等人提出了集合空間關鍵字查詢問題（Collective Spatial Keyword Query problem，CoSKQ），即檢索所有對象中包含的關鍵字共同覆蓋查詢關鍵字的一組對象[59-60]。值得一提的是，以往的工作僅針對歐式空間中的CoSKQ問題，Gao[64]、Su[65]等人研究了路網上的空間關鍵詞集合查詢處理問題。

3.7 基于影響區域約束下的查詢

基于影響區域約束下的查詢，查找距離與用戶查詢關鍵字最相關的特征對象的最近的興趣對象作為候選結果，這種查詢方式有效地避免了遺漏查詢結果以及與用戶關鍵字不匹配的情況。早期，文獻[70]研究了基于反向最近鄰查詢的影響集合，在該查詢中，給定一個查詢點，查詢查找一組使得該查詢點受到影響最大的集合。Hidayat等人[29]在影響區域的基礎上提出了影響因子的概念，同時利用新定義的修剪圓對空間進行修剪，篩選合適的數據，從而提高RkNN查詢的效率和準確性。

然而，由于影響區域約束需要檢索全部空間區域，在大數據量情況下會導致較低的查詢效率。在文獻[70]中，查詢返回的是一組使得查詢點受到影響最大的集合，而Cai等人研究了基于特征對象的偏好查詢，查詢返回一組排序的興趣點，這組興趣點以及興趣點周圍特征對象均滿足用戶偏好。Cai等人考慮了查詢對象周圍其他對象屬性滿足用戶偏好的程度，研究了歐式空間下基于影響約束的top-k空間關鍵字偏好查詢，提出了兩種有效的查詢改進算法：（1）閾值倒排文件算法TFIFA，通過閾值剪枝策略為每個R*-tree結點計算一個上界分數，對上界分數小于或等于當前閾值的結點以及結點包含的子樹進行剪枝。（2）基于貪心策略的最近鄰查詢算法GS-NNA。結合貪心策略和最近鄰方法，每次選擇文本相關度最高且滿足閾值判定條件的特征對象，將距離該特征對象最近的空間對象加入到候選結果集中，一定能夠從候選結果集中獲得滿足用戶需求的查詢結果。有效滿足了用戶的個性化top-k查詢需求，并提高了查詢效率。然而，上述基于影響區域約束下的查詢，僅在歐式空間下考慮，而現實中兩個興趣點之間的距離大多都是基于路網環境，因此考慮路網環境下的查詢具有更多的實際應用價值。

3.8 其他相關技術

李盼等人[71]構建一種新的混合索引結構AIR-Tree，能夠同時支持文本和語義匹配，并利用Skyline方法對數值屬性進行處理，最終利用評價函數對候選集進行個性化排序的混合索引結構。該文利用LDA主題模型來實現空間對象的語義近似查詢的方法，并且利用Skyline對數值屬性進行處理，實現了查詢結果的個性化。提出的算法不僅支持空間關鍵字的精確匹配，并可以支持語義近似查詢和形式上的近似匹配，且能處理文本信息中的數值屬性，這樣更符合用戶查詢要求，在一定程度上提高了用戶體驗以及滿意度。

Luo等人[72]提出了一種新的分布式索引方案NPD index，在分布式設置中回答兩類空間關鍵字查詢。文獻[73]使用關鍵字進行空間偏好查詢的并行和分布式處理，提出并解決了一個新問題，即使用關鍵字對大規模分布的空間文本數據進行空間偏好查詢的并行/分布式評估，進一步提高了算法的性能，從而降低了處理成本。

另外，文獻[61，73]等均在空間關鍵字查詢中考慮了用戶偏好，更好地滿足用戶的個性化需求。

近幾年，隨著可視化技術的流行，也有一些工作[74-75]結合空間關鍵字查詢與可視化技術進行查詢。文獻[74]提出一種基于自然語言的不確定人體軌跡可視化查詢方法：（1）從文本語句中提取時空約束，并支持對不確定移動軌跡的有效查詢方法。（2）利用POI及其所覆蓋區域的語義信息對大量的空間不確定移動軌跡進行編碼，將軌跡文檔存儲在文本數據庫中，并采用有效的索引方案（根據提取的條件查詢軌跡，首先，城市空間被小的可能空間區域（PSR）細分，以容納不準確的采樣點。其次，將軌跡轉換為包含區域POI信息的文檔，使用特殊的索引方案存儲在數據庫中。然后使用概率檢索算法（Okapi BM25[76]）找到匹配輸入條件的top-kPOIs，并利用潛在Dirichlet分配（LDA）主題建模發現的區域POIs的功能主題進一步增強。最后，使用top-kPOIs提取數據庫中的相關軌跡。一旦獲得了一組軌跡，將根據計算出的每個軌跡的相關得分對它們進行排序。并且提供了一個有序的結果列表）?？梢暬糠郑翰樵儣l件規范視圖構建可視化分析系統，用于指定查詢和可視化地調整查詢條件；在地理環境下可視化軌跡的地圖視圖；做了一組可視化，包括時間圖視圖、語義視圖和用于檢查查詢結果的詳細結果視圖。

4 結束語

空間關鍵字查詢在實際中的應用越來越廣泛，研究方面也逐漸增多，到目前為止學者們已經做了很多的努力來支持有效的空間關鍵字索引和查詢。傳統的空間關鍵字查詢通常是假定用戶明確自己的查詢意圖并且僅支持嚴格查詢匹配，但是隨著社會的發展和用戶的實際需要，顯然這種簡單的形式上的匹配已經不能夠滿足用戶的需要，所以對空間關鍵字查詢有了進一步的研究。本文從索引機制、查詢模型和與其他技術結合的查詢算法三個方面對空間關鍵字查詢的研究進展進行綜述。但是目前的研究還存在著值得進一步研究的問題：

（1）時間約束

考慮空間和文本信息的同時，加入時間約束對空間關鍵字查詢具有一定的意義，根據用戶對時間的需求可以返回更能滿足用戶需求的結果，但同時這會增加問題的復雜度和技術實現的難度。所以在未來工作中，在這個問題中，應該更多地考慮如何解決時間約束帶來的復雜度和技術問題。

（2）查詢結果的多樣性

現有的集合空間關鍵字查詢的一些研究工作中，雖然能夠查找到覆蓋所有查詢關鍵字的一組對象，但是這一組對象可能會重復出現某個關鍵字，忽略了組內對象的多樣性。因此未來工作中，在選取空間對象進行組合時，應該避免選取具有相同關鍵字的空間對象作為一組；或在最終選取查詢結果時，考慮空間對象之間的多樣性對排序結果的影響。

（3）查詢結果的可視化

通過結合可視化，能夠更直觀地表達和分析查詢條件、結果，所以在未來的研究工作中可以考慮更多更豐富的可視化方法，可以將空間關鍵字查詢與地圖、圖表等結合起來?？梢越Y合地圖的地理條件、自帶的一些功能等做查詢，并且還可以通過在地圖上展示查詢結果，甚至可以對查詢結果在地圖上做路線規劃等。