李維丹

空間關(guān)鍵詞查詢研究綜述

李維丹

（同濟(jì)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，上海201804）

隨著定位服務(wù)技術(shù)的出現(xiàn)，越來(lái)越多的應(yīng)用把現(xiàn)實(shí)對(duì)象與空間位置關(guān)聯(lián)起來(lái)，衍生出應(yīng)用廣泛的空間關(guān)鍵詞查詢，即結(jié)合空間查詢和文本查詢以尋求最優(yōu)結(jié)果的混合查詢。對(duì)空間關(guān)鍵詞查詢領(lǐng)域的研究進(jìn)展進(jìn)行總結(jié)，特別對(duì)各種查詢方法的索引機(jī)制、查詢策略、性能評(píng)估、適用范圍進(jìn)行詳細(xì)的分析與比較；同時(shí)，詳細(xì)介紹一種分布式空間關(guān)鍵詞查詢系統(tǒng)，并指出空間關(guān)鍵詞查詢尚存的開(kāi)放問(wèn)題。

空間數(shù)據(jù)庫(kù)；空間關(guān)鍵詞查詢；索引結(jié)構(gòu)；分布式計(jì)算

0　引言

隨著定位技術(shù)的發(fā)展，越來(lái)越多的對(duì)象（如行人）和空間位置緊密關(guān)聯(lián)起來(lái)。此外，Web上包含的位置信息也越來(lái)越多。這些變化促進(jìn)了空間關(guān)鍵詞查詢（Spatial Keyword Query，SKQ）[2~5]的發(fā)展。

空間關(guān)鍵詞查詢主要分為空間查詢和關(guān)鍵字查詢。目標(biāo)是找出包含查詢關(guān)鍵詞且距離查詢位置最近的若干對(duì)象。例如，用戶通過(guò)手機(jī)查詢距離當(dāng)前位置最近的書店。

近年來(lái)，快速有效地返回空間關(guān)鍵詞查詢結(jié)果成為學(xué)術(shù)界的研究熱點(diǎn)，并提出了各種解決方案。本文基于這些研究成果，對(duì)空間關(guān)鍵詞查詢的最新進(jìn)展進(jìn)行綜述，分析和比較了空間關(guān)鍵詞查詢處理關(guān)鍵技術(shù)，包括索引結(jié)構(gòu)、查詢策略及結(jié)果排序與評(píng)估等。

1　問(wèn)題定義與技術(shù)挑戰(zhàn)

在一個(gè)空間關(guān)鍵詞查詢中，給定一個(gè)數(shù)據(jù)集P。設(shè)o是P中的一個(gè)對(duì)象，o=〈o.id，o.s，o.t〉，o.id用于唯一標(biāo)識(shí)對(duì)象o；o.s是對(duì)象o的空間屬性；o.t是對(duì)象o的文本描述。

用q=〈q.s，q.t，q.k〉表示一個(gè)空間關(guān)鍵詞查詢。其中，q.s是查詢的位置，q.t是查詢關(guān)鍵詞，q.k是需要返回的結(jié)果數(shù)目。

空間關(guān)鍵詞查詢q的目標(biāo)是從數(shù)據(jù)集P中找出q.k個(gè)最優(yōu)對(duì)象。一般，評(píng)價(jià)函數(shù)f（o，q）定義為：

其中，δ（o.s，q.s）用于計(jì)算對(duì)象位置o.s和查詢位置q.s之間的距離；θ（o.t，q.t）用于計(jì)算對(duì)象的文本描述o.t和查詢的關(guān)鍵詞q.t之間的相關(guān)度；α是一個(gè)權(quán)重因子，用于兩種度量的權(quán)重分配。

下面給出了空間距離計(jì)算和文本相關(guān)度計(jì)算的主要公式：

（1）空間距離（δ）

在空間關(guān)鍵詞查詢中，δ一般是歐氏距離，計(jì)算公式為：

其中d（o.s，q.s）是o.s和q.s之間的距離，dmax是數(shù)據(jù)空間中距離的最大值，用于歸一化處理。

（2）文本相關(guān)度（θ）

計(jì)算文本相關(guān)度的方法很多，應(yīng)用較廣泛的是計(jì)算兩個(gè)文本向量的余弦值。使用這種方法，θ可表示為：

其中，Wt，o.t=q+ln（ft，o.t），ft，o.t表示關(guān)鍵詞t在文本描述o.t中出現(xiàn)的頻數(shù)；，其中|P|表示對(duì)象的個(gè)數(shù)，dft表示包含t的文檔數(shù)。根據(jù)余弦性質(zhì)可知計(jì)算結(jié)果在[0，1]內(nèi)，這樣就能和距離計(jì)算結(jié)果的范圍保持一致。

2　空間關(guān)鍵詞查詢處理的基本技術(shù)

空間關(guān)鍵詞查詢主要研究如何提高查詢效率并拓展其實(shí)際應(yīng)用。其中的關(guān)鍵問(wèn)題是如何構(gòu)建合適的索引結(jié)構(gòu)。此外，還需要對(duì)查詢結(jié)果進(jìn)行排序。以下將詳述這些內(nèi)容。

2.1索引技術(shù)

構(gòu)建高性能的索引是實(shí)現(xiàn)高效查詢的有效方法。下面，首先介紹基本的空間索引和文本索引技術(shù)，然后評(píng)述專門針對(duì)空間關(guān)鍵詞查詢的索引技術(shù)。

（1）空間索引技術(shù)

常見(jiàn)的空間索引技術(shù)大致可以分為四類，分別是：

①基于二叉樹的索引：基于此索引結(jié)構(gòu)的主要有KD樹[9]、K-D-B樹[10]、LSD樹[11]等。這類空間索引結(jié)構(gòu)適用于點(diǎn)狀對(duì)象。

②基于B-樹的索引：此類索引結(jié)構(gòu)中比較典型的是R-樹。R-樹將空間對(duì)象及索引空間用最小邊界矩形（Minimum Bounding Rectangle）來(lái)近似表示，將空間相鄰的對(duì)象組織到同一結(jié)點(diǎn)或同一分支，并將一個(gè)結(jié)點(diǎn)對(duì)應(yīng)成一個(gè)或者多個(gè)磁盤頁(yè)。該索引策略大大減少了I/O訪問(wèn)。

③基于哈希的網(wǎng)格技術(shù)：這類索引將索引空間劃為若干格子，并將每個(gè)格子相關(guān)聯(lián)的空間目標(biāo)存儲(chǔ)在同一磁盤頁(yè)，這樣，查詢時(shí)就能通過(guò)格子的標(biāo)號(hào)來(lái)定位空間對(duì)象。具有代表性的便是Grid文件[13]，多用于點(diǎn)狀對(duì)象。

④空間目標(biāo)排序法：此方法將多維對(duì)象映射到一維空間中，然后采用一維索引來(lái)實(shí)現(xiàn)。常見(jiàn)的映射方法有Z-排序、Hilbert曲線等。

（2）文本索引技術(shù)

文本索引主要是用于關(guān)鍵詞查詢。關(guān)鍵詞查詢中常用的索引結(jié)構(gòu)主要是倒排索引（Inverted Index）[14]和簽名文件（Signature File）[15]。

①倒排索引

倒排索引是一種簡(jiǎn)單高效的文本索引，它列出了每個(gè)關(guān)鍵詞以及包含該關(guān)鍵詞的所有對(duì)象，如表1所示。

表1　倒排索引

當(dāng)需查詢包含關(guān)鍵詞k1和k4的對(duì)象時(shí)，就相交這兩個(gè)關(guān)鍵詞的對(duì)象集合，得到的{o1，o6}即為結(jié)果。

（2）簽名文件

簽名文件也是一種常見(jiàn)的文本索引方式，它為每個(gè)關(guān)鍵詞分配一個(gè)固定大小的向量，稱為簽名（signature）。對(duì)一個(gè)空間對(duì)象的所有關(guān)鍵詞的簽名進(jìn)行OR運(yùn)算，就形成了該對(duì)象的簽名。

在查詢時(shí)，首先生成查詢關(guān)鍵詞的簽名，然后通過(guò)AND操作進(jìn)行檢索。

（3）基于空間關(guān)鍵詞查詢的索引技術(shù)

按照構(gòu)建索引方式的不同，現(xiàn)有針對(duì)空間關(guān)鍵詞查詢的索引結(jié)構(gòu)可分為兩類，一類是獨(dú)立索引[1，4]；另一類是混合索引[2~3，5~6]。

①獨(dú)立索引

針對(duì)空間關(guān)鍵詞查詢的獨(dú)立索引將傳統(tǒng)的文本索引技術(shù)和具有空間過(guò)濾功能的Quad樹[16]、R樹[12]、網(wǎng)格索引（grid index）[13]等空間索引獨(dú)立地用于查詢。

例如，文獻(xiàn)[3]中采用倒排索引來(lái)索引關(guān)鍵詞，用網(wǎng)格索引來(lái)索引空間位置；而文獻(xiàn)[17]使用Quad樹和R樹來(lái)進(jìn)行空間索引。

基于獨(dú)立索引的空間關(guān)鍵詞查詢的效率很低，不適合數(shù)據(jù)規(guī)模較大、查詢時(shí)間要求較高的情況。

②混合索引

目前，空間關(guān)鍵詞查詢處理大多采用混合索引，即將空間索引和文本索引結(jié)合成統(tǒng)一的索引結(jié)構(gòu)。混合索引可以分為松散混合索引[19]和緊密混合索引[2~3，5~7]。

●松散混合索引

混合索引中使用的空間索引大多是R樹[12]或其變體。例如，將空間索引和文本索引松散地結(jié)合，為每個(gè)關(guān)鍵詞建立一棵R*樹，查詢過(guò)程中，首先根據(jù)查詢關(guān)鍵詞找出對(duì)應(yīng)的R*樹，然后遍歷它查找結(jié)果。這種方法對(duì)單關(guān)鍵詞查詢非常有效。

本質(zhì)上，松散混合索引還未擺脫空間索引和文本索引順序檢索的特點(diǎn)，查詢效率波動(dòng)較大。

●緊密混合索引

緊密混合索引結(jié)合了空間索引和文本索引，在查詢過(guò)程中可同時(shí)訪問(wèn)空間索引和文本索引。

采用R-樹作為空間索引的緊密混合索引本質(zhì)上是在R樹的結(jié)點(diǎn)中加入子結(jié)點(diǎn)的文本信息，從而盡早實(shí)現(xiàn)對(duì)不合理路徑的剪枝。

同時(shí)進(jìn)行空間和文本的索引，避免了過(guò)多的數(shù)據(jù)訪問(wèn)，基于此類索引結(jié)構(gòu)的空間關(guān)鍵詞查詢可有效提高效率。

2.2查詢算法

空間關(guān)鍵詞查詢處理已有多種算法。下面介紹幾種代表性的算法。

（1）SK（Spatial Keyword）算法[7]

SK算法基于KR*樹索引結(jié)構(gòu)實(shí)現(xiàn)。該算法以查詢Q和KR*樹的根結(jié)點(diǎn)N為輸入，Q=〈Q.r，Q.t，Q.k〉，給出查詢區(qū)域、查詢關(guān)鍵詞和需返回的對(duì)象個(gè)數(shù)。首先，算法檢查當(dāng)前結(jié)點(diǎn)的所有子結(jié)點(diǎn)，若子結(jié)點(diǎn)包含所有的查詢關(guān)鍵詞，則加入列表。然后檢測(cè)結(jié)點(diǎn)是否與查詢區(qū)域相交，若相交，且該結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則將滿足條件的對(duì)象加入候選集；若相交，但其不是葉子結(jié)點(diǎn)，則重復(fù)以上計(jì)算；若不相交，則剪掉該結(jié)點(diǎn)及其子結(jié)點(diǎn)。最后，算法返回一個(gè)候選集，該候選集里的所有對(duì)象都與查詢區(qū)域相交且包含查詢關(guān)鍵詞。若要進(jìn)行top-k查詢，則需對(duì)候選集進(jìn)行排序，并取最優(yōu)的k個(gè)對(duì)象。

該算法較早實(shí)現(xiàn)對(duì)空間數(shù)據(jù)和文本數(shù)據(jù)的同時(shí)處理，能大大減小I/O開(kāi)銷。由于需要在算法結(jié)束后進(jìn)行排序，候選集較大時(shí)性能較差。

（2）距離優(yōu)先IR2樹算法[2]

距離優(yōu)先IR2樹算法基于IR2樹索引結(jié)構(gòu)實(shí)現(xiàn)。該算法中，查詢關(guān)鍵詞只用于過(guò)濾，即只考慮包含全部查詢關(guān)鍵詞的對(duì)象。最后，算法返回包含查詢關(guān)鍵詞的前k個(gè)距離查詢點(diǎn)最近的對(duì)象，并按與查詢點(diǎn)的距離排序。

該算法查詢效率很高，I/O開(kāi)銷較少。缺點(diǎn)在于只能實(shí)現(xiàn)關(guān)鍵詞的布爾查詢。

（3）LkT（Location-aware Top-k Text Retrieval）算法[3]

LkT算法主要用于基于位置的top-k空間關(guān)鍵詞查詢，采用的索引結(jié)構(gòu)是IR-樹。

該算法采用最好優(yōu)先遍歷策略[23]，依次取得k個(gè)查詢結(jié)果。該算法的查詢策略和距離優(yōu)先IR2樹算法基本一致。

（4）三種算法的比較分析

上述的三種算法中，SK查詢算法是范圍查詢，返回的是與給定查詢區(qū)域相交的對(duì)象；后兩種是基于距離的查詢，返回結(jié)果需要排序。三者均支持top-k查詢，不過(guò)SK查詢算法需要對(duì)算法的候選集進(jìn)行排序，而后兩種算法可以直接得出k個(gè)最優(yōu)結(jié)果。表3給出了三者比較信息。

表2　空間關(guān)鍵詞查詢算法比較

2.3查詢結(jié)果的排序與評(píng)估

空間關(guān)鍵詞查詢一般要返回多個(gè)對(duì)象。這就需要合適的排序策略。現(xiàn)有研究中，排序方式可分兩類，一類是直接由查詢算法返回排序好的結(jié)果；另一類是在查詢算法結(jié)束后進(jìn)行排序。

此外，還需評(píng)估查詢結(jié)果的好壞。評(píng)估方法主要考慮返回的候選對(duì)象的數(shù)目和最終結(jié)果與查詢要求的匹配程度。

2.4空間關(guān)鍵詞查詢的變體

還有空間關(guān)鍵詞查詢的變體，如移動(dòng)空間關(guān)鍵詞查詢、多目標(biāo)空間關(guān)鍵詞查詢等。

目前，針對(duì)移動(dòng)查詢的研究主要采用安全區(qū)域（safe zone）的思想，若用戶在安全區(qū)域內(nèi)，查詢結(jié)果不變。若用戶離開(kāi)該區(qū)域，則重新提交查詢，計(jì)算新的結(jié)果和新的安全區(qū)域。

針對(duì)多目標(biāo)關(guān)鍵詞查詢[8]給出了一種基于貪心算法的方案，首先查找包含部分或者全部關(guān)鍵詞的最近對(duì)象，然后用還未找到的關(guān)鍵詞組成新的查詢，直到所有關(guān)鍵詞都已經(jīng)找到或遍歷結(jié)束。

除了上述兩種外，還有其他形式的空間關(guān)鍵詞查詢。如文獻(xiàn)[24]中的基于位置的近似關(guān)鍵詞查詢，及文獻(xiàn)[25]中的聯(lián)合空間關(guān)鍵詞查詢等。

3　空間關(guān)鍵詞查詢的分布式處理

隨著實(shí)際應(yīng)用越來(lái)越廣，在集中式環(huán)境下處理空間關(guān)鍵詞查詢已不能滿足對(duì)性能和效率的需求。

首先，實(shí)際的查詢系統(tǒng)往往基于C/S或B/S架構(gòu)，若用戶規(guī)模極大，服務(wù)端將承擔(dān)巨大的負(fù)荷；其次，移動(dòng)終端的日益普及導(dǎo)致移動(dòng)查詢?nèi)找嫫占?，?duì)于移動(dòng)查詢，用戶行進(jìn)過(guò)程中不斷向服務(wù)端提交查詢，服務(wù)端不斷進(jìn)行繁重的計(jì)算；再次，實(shí)際的空間關(guān)鍵詞查詢往往并不基于歐氏距離，而是基于道路網(wǎng)絡(luò)（以下簡(jiǎn)稱路網(wǎng)），因?yàn)樵诂F(xiàn)實(shí)中，從一個(gè)地方并不能通過(guò)直線路徑抵達(dá)另一地方，而必須經(jīng)過(guò)道路路徑，相比歐氏空間，路網(wǎng)結(jié)構(gòu)更復(fù)雜，數(shù)據(jù)量級(jí)更大，查詢效率難免降低。

綜上，在集中式環(huán)境下進(jìn)行空間關(guān)鍵詞查詢已不能滿足現(xiàn)實(shí)應(yīng)用的需求。于是，在分布式環(huán)境中進(jìn)行處理已逐漸成為空間關(guān)鍵詞查詢問(wèn)題的研究方向。如文獻(xiàn)[27]提出了一種基于多核平臺(tái)的平行處理技術(shù)，能對(duì)SQL語(yǔ)句執(zhí)行分布處理，文獻(xiàn)[28]提出了一種分布式處理基于路網(wǎng)的空間關(guān)鍵詞查詢技術(shù)，文獻(xiàn)[29]提出了一種分布式空間關(guān)鍵詞查詢系統(tǒng)，以下將介紹一個(gè)具有代表性的分布式系統(tǒng)。

3.1DISKs(Distribured Spatial Keyword Search)

文獻(xiàn)[29]第一次提出基于分布式處理空間關(guān)鍵詞查詢問(wèn)題，并提出了能有效處理基于路網(wǎng)的空間關(guān)鍵詞查詢的分布式系統(tǒng)，即DISKs。

DISKs的架構(gòu)如圖1所示。包含三個(gè)模塊：分割器（Partitioner）、索引器（Indexer）和分布式查詢處理器（Distributed Query Processor）。分割器和索引器用于預(yù)先構(gòu)建索引模塊。

（1）分割器和索引器

分割器以一個(gè)路網(wǎng)為輸入，輸出N個(gè)小的節(jié)點(diǎn)不相交的分區(qū)，并將連接各分區(qū)的邊的終點(diǎn)作為后續(xù)步驟的入口節(jié)點(diǎn)。

索引器以分割器輸出的分區(qū)及入口節(jié)點(diǎn)為參數(shù)，輸出名為NPD-Index（Node Partition Distance Index）的索引結(jié)構(gòu)。NPD-Index由N個(gè)部分組成，每部分與一個(gè)分區(qū)關(guān)聯(lián)，并包含兩個(gè)結(jié)構(gòu)，分別為DL（Distance List）和SC（Short-Cut）。其中，DL是路網(wǎng)中基于節(jié)點(diǎn)的搜索樹，它的每個(gè)葉節(jié)點(diǎn)被標(biāo)記為該節(jié)點(diǎn)與其所在分區(qū)入口節(jié)點(diǎn)的距離。SC結(jié)構(gòu)是一個(gè)附加邊的集合，每條邊連接該分區(qū)的兩個(gè)入口節(jié)點(diǎn)。

經(jīng)過(guò)分割器和索引器的處理，使用分區(qū)及其相關(guān)的DL和SC結(jié)構(gòu)，能準(zhǔn)確計(jì)算出路網(wǎng)中任何一個(gè)位置到該分區(qū)中任何一個(gè)位置的最短距離。此外，通過(guò)將各入口點(diǎn)作為輸入，NPD-Index還能實(shí)現(xiàn)在整個(gè)路網(wǎng)上執(zhí)行一組Dijkstra算法。

圖1　DISKs系統(tǒng)架構(gòu)

（2）分布式查詢處理器

在NPD-Index被構(gòu)建后，即能在集群中執(zhí)行分布式查詢。將每個(gè)分區(qū)索引分配給一臺(tái)機(jī)器，從而計(jì)算出該分區(qū)的結(jié)果。分布式查詢算法以一個(gè)參數(shù)r和若干關(guān)鍵詞為輸入。對(duì)于每個(gè)關(guān)鍵詞K，節(jié)點(diǎn)集XK包含所有包含K的節(jié)點(diǎn)。對(duì)于每個(gè)分區(qū)P，查詢算法執(zhí)行如下操作：

①對(duì)每個(gè)包含關(guān)鍵詞K的節(jié)點(diǎn)集XK，執(zhí)行如下步驟:

Sub-step 1:查找樹DL查找XK中包含的葉節(jié)點(diǎn)，并遍歷與其距離最大為r的入口節(jié)點(diǎn)。

Sub-step 2：從已遍歷到的入口節(jié)點(diǎn)開(kāi)始，搜索P與SC的并集，并返回P中到XK中任何節(jié)點(diǎn)距離不超過(guò)r的節(jié)點(diǎn)。

②對(duì)所有節(jié)點(diǎn)集中的返回節(jié)點(diǎn)執(zhí)行相交操作。①對(duì)每個(gè)關(guān)鍵詞K計(jì)算了P中到XK的距離不大于r的節(jié)點(diǎn)集。②相交后，找出P中到所有節(jié)點(diǎn)集（即每個(gè)關(guān)鍵詞的相關(guān)節(jié)點(diǎn)）距離不大于r的節(jié)點(diǎn)。

（3）基于Hadoop的DISKs實(shí)現(xiàn)

Hadoop工作階段由map階段和reduce階段組成。在map階段，任務(wù)被分配至不同的機(jī)器，在reduce階段，標(biāo)志相同的map階段的輸出被發(fā)送到一臺(tái)機(jī)器上進(jìn)行下一步操作。

如前所述，以入口節(jié)點(diǎn)為輸入，NPD-Index結(jié)構(gòu)可實(shí)現(xiàn)為一組Dijkstra實(shí)例。在map階段，這些實(shí)例可方便地分布于不同機(jī)器上進(jìn)行計(jì)算。在reduce階段，將map階段的結(jié)果匯總在一起。

綜上即可完成一次分布式的查詢操作。

4　結(jié)語(yǔ)

隨著空間關(guān)鍵詞查詢應(yīng)用的日漸廣泛，需要研究的方面也逐漸增多，尚有一些有待深入研究的開(kāi)放問(wèn)題。例如，可以考慮將關(guān)鍵詞映射到幾何空間中，形成一個(gè)純粹的空間索引；基于關(guān)鍵詞重要程度進(jìn)行查詢等。

本文對(duì)空間關(guān)鍵詞查詢研究現(xiàn)狀進(jìn)行了綜述，分別是從索引技術(shù)、查詢算法及結(jié)果評(píng)估等三方面對(duì)已有研究成果進(jìn)行了闡述，并詳細(xì)介紹了一種分布式空間關(guān)鍵詞查詢系統(tǒng)。最后，指出了空間關(guān)鍵詞查詢研究的一些開(kāi)放問(wèn)題。

[1]K.S.McCurley.Geospatial Mapping and Navigation of the Web.WWW,2001:221~229

[2]I.D.Felipe,V.Hristidis,and N.Rishe.Keyword Search on Spatial Databases.ICDE,2008:656~665

[3]G.Cong,C.S.Jensen,and D.Wu.Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects.PVLDB,2009:337~348

[4]Y.-Y.Chen,T.Suel,and A.Marowetz.Efficient Query Processing in Geographic Web Search Engines.SIGMOD,2006:277~288

[5]R.Hariharan,B.Hore,C.Li,and S.Mehrotra.Processing Spatial-Keyword(SK)Queries in Geographic Information Retrieval(GIR) Systems.SSDBM,2007:1-10

[6]D.Zhang,Y.M.Chee,A.Mondal,A.K.H.Tung,M.Kitsuregawa.Keyword Search in Spatial Databases:Towards Searching by Document.ICDE,2009:688-699

[7]D.Wu,M.L.Yiu,C.S.Jensen,G.Cong.Efficient Continuously Moving Top-k Spatial Keyword Query Processing.ICDE,2011:541~552

[8]X.Cao,G.Cong,C.S.Jensen,B.C.Ooi.Collective Spatial Keyword Querying.SIGMOD,2011:373~384

[9]J.L.Bentley.Multidimensional Binary Search Trees used for Associative Searching.Comm.ACM,1975,18(9):509~517

[10]J.T.Robinson.The K-D-B-Tree:A Search Structure for Large Multidimensional Dynamic Indexes.SIGMOD,1981:10~18

[11]A.Henrich,H.W.Six,P.Widmayer.The LSD Tree:Spatial Access to Multidimensional Point and Nonpoint Objects.VLDB,1989: 45-53

[12]A.Guttman.R-trees:A Dynamic Index Structure for Spatial Searching.SIGMOD,1984:47-57

[13]J.Nievergelt,and H.Hinterberger.The Grid File:An Adaptable,Symmetric Multi-Key File Structure.TODS,1984,9(1):38~71

[14]J.Zobel,and A.Moffat.Inverted Files for Text Search Engines.ACM Comput.Surv.,2006,38(2):6

[15]C.Faloutsos,and S.Christodoulakis.Signature Files:An Access Method for Documents and Its Analytical Performance Evaluation. ACM Transactions on Office Information Systems.1984,2(4):267-288

[16]R.Finkel,and J.L.Bentley.Quad Trees:A Data Structure for Retrieval on Composite Keys.Acta Informatica,1974,4(1):1-9

[17]R.Lee,H.Shiina,H.Takakura,Y.J.Kwon,and Y.Kambayashi.Optimization Range Query Processing.WISEW,2003:9-17

[18]Z.Li,K.C.K.Lee,B.Zheng,W.C.Lee,D.L.Lee,and X.Wang.IR-tree:An Efficient Index for Goegraphic Document Search.TKDE,2011:585-599

[19]W.Wu,F.Yang,C.-Y.Chan,and K.-L.Tan.Finch:Evaluating Reverse k-Nearest Neighbor Queries on Location Data.PVLDB, 2008:1056-1067

[20]Y.Zhou,X.Xie,C.Wang,Y.Gong,and W.Y.Ma.Hybrid Index Structures for Location-Based Web Search.CIKM,2005:155-162

[21]J.B.Rocha-Junior,A.Vlachou,C.Doulkeridis,and K.Norvag.Efficient Processing of Top-k Spatial Preference Queries.PVLDB, 2010:93-104

[22]D.Zhang,B.C.Ooi,A.K.H.Tung.Locating Mapped Resources in Web2.0.ICDE,2010:521~532

[23]G.R.Hjaltason,H.Samet.Distance Browsing in Spatial Databases.ACM Trans.Database Sys.,1999,24(2):265~318

[24]S.Alsubaiee,A.Behm,C.Li.Supporting Location-Based Approximate-Keyword Queries.ACM GIS,2010:61~70

[25]D.Wu,W.L.Yiu,G.Cong,and C.S.Jensen.Joint Top-k Spatial Keyword Query Processing.TKDE,2011:1~15

[26]B.Martins,M.Silva,L.Andrade.Indexing and Ranking in Geo-IR Systems.GIR,2005:31-34

[27]L.Qin,J.X.Yu,L.Chang.Ten Thousand SQLs:Parallel Keyword Queries Computing.In VLDB,volume 3,pages 58~69,2010

[28]Siqiang Luo,Yifeng Luo,Shuigeng Zhou,Gao Cong,Jihong Guan:Distributed Spatial Keyword Querying on Road Networks.EDBT 2014:235-246

[29]Siqiang Luo,Yifeng Luo,Shuigeng Zhou,Gao Cong,Jihong Guan:DISKs:A System for Distributed Spatial Group Keyword Search on !Road Networks.PVLDB 5(12):1966-1969(2012)

Spatial Database;Spatial Keyword Query;Indexing;Distributed Computing

Research on the Survey of Spatial Keyword Query

LI Wei-dan

（Department of Computer Science and Technology，Tongji University，Shanghai 201804）

With the emergence of positioning services,more and more applications associate the physical objects with spatial locations.This situation leads to the prevalence of spatial keyword queries in practice and research.Spatial keyword query processing involves techniques of both spatial query and keyword query processing,and the query results may be impacted by these two aspects.Surveys the state of the art techniques of spatial keyword query processing.Especially,focuses a comparative analysis on indexing mechanisms,query strategies,results ranking and evaluation.In addition,introduces a distributed spatial keyword query system.Highlights open research issues.

1007-1423（2015）12-0034-06

10.3969/j.issn.1007-1423.2015.12.008

李維丹（1991-），男，內(nèi)蒙古自治區(qū)人，碩士研究生，研究方向?yàn)榭臻g關(guān)鍵詞查詢

2015-03-27

2015-04-15