孟祥福，王丹丹，張 峰

遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105

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

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

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

1 索引結(jié)構(gòu)

傳統(tǒng)索引方法有哈希表和B-Tree。哈希表可以對數(shù)值進(jìn)行精確匹配，但是不能進(jìn)行范圍查詢。B-Tree是對鍵值的一維排序，但不能搜索多維空間。B-Tree是一種相對來說比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，尤其是在它的刪除與插入操作過程中，因?yàn)樗婕暗搅巳~子結(jié)點(diǎn)的分解與合并。除了傳統(tǒng)的索引方法，還提出一些空間索引結(jié)構(gòu)，就是指依據(jù)空間實(shí)體的位置和形狀或空間實(shí)體之間的某種空間關(guān)系，按一定順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間實(shí)體的概要信息如對象的標(biāo)識、外接矩形及指向空間實(shí)體數(shù)據(jù)的指針等。簡單的說，就是將空間對象按某種空間關(guān)系進(jìn)行劃分，以后對空間對象的存取都基于劃分塊進(jìn)行。

1.1 空間索引結(jié)構(gòu)

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

圖1 R-Tree結(jié)點(diǎn)存儲結(jié)構(gòu)Fig.1 R-Tree node storage structure

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

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

R*-Tree[5]是R-Tree的變體，是在R-Tree的基礎(chǔ)上對部分算法進(jìn)行了優(yōu)化改進(jìn)，相對R-Tree優(yōu)化的地方是強(qiáng)制重新插入算法。R-Tree的插入操作導(dǎo)致結(jié)點(diǎn)溢出時(shí)，采用分裂的方法進(jìn)行處理，而R*-Tree對新的空間對象索引項(xiàng)的插入導(dǎo)致結(jié)點(diǎn)溢出時(shí)，它將會選擇部分結(jié)點(diǎn)在同層結(jié)點(diǎn)間進(jìn)行調(diào)整，以推遲結(jié)點(diǎn)分裂，從而達(dá)到優(yōu)化R-Tree整體結(jié)構(gòu)的目的?；赗*-Tree的空間索引算法優(yōu)點(diǎn)是提高了空間的利用率，插入成本低于R-Tree，但缺點(diǎn)是增加了CPU代價(jià)。

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

圖2 數(shù)據(jù)對象Fig.2 Data objects

圖3 數(shù)據(jù)對象所對應(yīng)的R*-TreeFig.3 R*-Tree corresponding to data object

R-Tree及基于R-Tree改進(jìn)的索引結(jié)構(gòu)都只存儲空間信息，較適合范圍查詢，R+-Tree不易實(shí)現(xiàn)不規(guī)則空間對象的任意查詢。

1.2 空間文本混合索引結(jié)構(gòu)

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

圖4 表1對應(yīng)的IR2-TreeFig.4 Corresponding IR2-Tree in Table1

表1 空間對象的樣本數(shù)據(jù)集Table 1 Sample dataset of spatial objects

bR*-Tree[7]：R*-Tree+BitMap，R*-Tree結(jié)點(diǎn)包含MBR，并且有結(jié)點(diǎn)中所有關(guān)鍵字的位圖和關(guān)鍵字MBR，它的優(yōu)點(diǎn)是存儲空間小，缺點(diǎn)是關(guān)鍵字匹配需求高，關(guān)鍵字多，I/O代價(jià)高。

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

圖5描述8個(gè)空間對象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結(jié)點(diǎn)包含MBR和結(jié)點(diǎn)到根結(jié)點(diǎn)路徑的Label，倒排結(jié)點(diǎn)包含標(biāo)記位置組成它的可擴(kuò)展性較強(qiáng)，搜索效率高，但存儲代價(jià)高，需要頻繁進(jìn)行插入操作，導(dǎo)致計(jì)算代價(jià)過高。

兩階段索引[9]，它是由R-Tree和Inverted file構(gòu)成的，其中R-Tree結(jié)點(diǎn)包含MBR，倒排文件結(jié)點(diǎn)包含關(guān)鍵字信息。具有結(jié)構(gòu)簡單的優(yōu)點(diǎn)，但存儲代價(jià)高，無法確定第一階段產(chǎn)生的候選對象個(gè)數(shù)。

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

1.3 其他索引結(jié)構(gòu)

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

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

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

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

G-index索引[13]：聚類標(biāo)準(zhǔn)+聚類操作，通過聚類操作。但是，可泛化成其他索引結(jié)構(gòu)。具有通用性，但是有較高的泛化計(jì)算代價(jià)，存儲代價(jià)較高。

IRS-Tree[14]是一種擁有Synopses的倒排R-Tree的混合索引結(jié)構(gòu)，能夠有效處理一組位置敏感等級查詢。基于IRS-Tree的查詢算法要求提供數(shù)值屬性的精確范圍，這樣可能會導(dǎo)致過少甚至沒有查詢結(jié)果返回。

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

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

1.4 文本索引

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

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

2 空間關(guān)鍵字查詢處理模式

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

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

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

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

3 其他技術(shù)結(jié)合的查詢算法

3.1 空間-文本查詢

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

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

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

3.2 語義近似查詢

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

現(xiàn)有的語義相似度計(jì)算方法：（1）通過本體定義術(shù)語/概念之間的距離定義拓?fù)湎嗨菩詠砉烙?jì)語義相似性。（2）通過向量空間模型等統(tǒng)計(jì)手段估計(jì)語言單元（單詞、句子等）之間的語義相關(guān)性。（3）利用概率主題模型對文本信息進(jìn)行語義相似處理。通過主題模型可以測量文本與主題之間的語義關(guān)系，也可以測量不同文本之間的語義關(guān)系。現(xiàn)已有很多經(jīng)典的主題模型：Latent Dirichlet Allocation（LDA）[43]、Dynamic Topic Model[45]、Dynamic HDP[46]、Sequential Topic Models[47]等。

3.3 基于路網(wǎng)的查詢

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

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

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

文獻(xiàn)[49]首次提出了路網(wǎng)中連續(xù)的top-k空間關(guān)鍵字查詢，提出了兩種以增量方式遍歷網(wǎng)絡(luò)的方法，即以查詢?yōu)橹行牡乃惴ǎ≦CA）——從查詢位置所在的邊的結(jié)束結(jié)點(diǎn)開始遍歷網(wǎng)絡(luò)，直到找到top-k結(jié)果為止。同時(shí)，它維護(hù)了一個(gè)擴(kuò)展樹，以避免后續(xù)處理時(shí)不必要地遍歷一些網(wǎng)絡(luò)邊緣。和以對象為中心的算法（OCA）——從與查詢關(guān)鍵字相關(guān)的對象開始遍歷。這樣，經(jīng)過初始處理后，構(gòu)造出一棵最短路徑樹，后續(xù)處理可以利用這棵樹顯著減少遍歷的邊數(shù)。原則上，這兩種方法都可以通過查找感興趣的對象來減少問題，從而將查詢轉(zhuǎn)移到檢查靜態(tài)網(wǎng)絡(luò)結(jié)點(diǎn)，減少連續(xù)監(jiān)控時(shí)不必要的重復(fù)遍歷網(wǎng)絡(luò)邊緣。

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

3.4 路線規(guī)劃查詢

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

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

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

3.5 社交網(wǎng)絡(luò)查詢

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

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

圖10 {O1,O2,O3,O4,O5}中個(gè)體之間的社交網(wǎng)絡(luò)Fig.10 {O1,O2,O3,O4,O5}social networks among individuals

在上述例子中，如果不考慮團(tuán)隊(duì)成員的協(xié)作效率，團(tuán)隊(duì){O2,O3,O5}或{O1,O5}都可以滿足所需的技能，但如果考慮團(tuán)隊(duì)成員的協(xié)作效率，根據(jù)圖10可以得出團(tuán)隊(duì){O2,O3,O5}是最優(yōu)解，圖中結(jié)構(gòu)表明O1和O5不能一起工作，因?yàn)橥唤M或部門的人比在不同部門工作的人更容易溝通。

3.6 空間關(guān)鍵字組查詢

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

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

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

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

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

3.7 基于影響區(qū)域約束下的查詢

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

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

3.8 其他相關(guān)技術(shù)

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

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

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

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

4 結(jié)束語

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

（1）時(shí)間約束

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

（2）查詢結(jié)果的多樣性

現(xiàn)有的集合空間關(guān)鍵字查詢的一些研究工作中，雖然能夠查找到覆蓋所有查詢關(guān)鍵字的一組對象，但是這一組對象可能會重復(fù)出現(xiàn)某個(gè)關(guān)鍵字，忽略了組內(nèi)對象的多樣性。因此未來工作中，在選取空間對象進(jìn)行組合時(shí)，應(yīng)該避免選取具有相同關(guān)鍵字的空間對象作為一組；或在最終選取查詢結(jié)果時(shí)，考慮空間對象之間的多樣性對排序結(jié)果的影響。

（3）查詢結(jié)果的可視化

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