空間關鍵詞查詢研究綜述

李維丹

空間關鍵詞查詢研究綜述

李維丹

（同濟大學計算機科學與技術系，上海201804）

隨著定位服務技術的出現，越來越多的應用把現實對象與空間位置關聯起來，衍生出應用廣泛的空間關鍵詞查詢，即結合空間查詢和文本查詢以尋求最優結果的混合查詢。對空間關鍵詞查詢領域的研究進展進行總結，特別對各種查詢方法的索引機制、查詢策略、性能評估、適用范圍進行詳細的分析與比較；同時，詳細介紹一種分布式空間關鍵詞查詢系統，并指出空間關鍵詞查詢尚存的開放問題。

空間數據庫；空間關鍵詞查詢；索引結構；分布式計算

0　引言

隨著定位技術的發展，越來越多的對象（如行人）和空間位置緊密關聯起來。此外，Web上包含的位置信息也越來越多。這些變化促進了空間關鍵詞查詢（Spatial Keyword Query，SKQ）[2~5]的發展。

空間關鍵詞查詢主要分為空間查詢和關鍵字查詢。目標是找出包含查詢關鍵詞且距離查詢位置最近的若干對象。例如，用戶通過手機查詢距離當前位置最近的書店。

近年來，快速有效地返回空間關鍵詞查詢結果成為學術界的研究熱點，并提出了各種解決方案。本文基于這些研究成果，對空間關鍵詞查詢的最新進展進行綜述，分析和比較了空間關鍵詞查詢處理關鍵技術，包括索引結構、查詢策略及結果排序與評估等。

1　問題定義與技術挑戰

在一個空間關鍵詞查詢中，給定一個數據集P。設o是P中的一個對象，o=〈o.id，o.s，o.t〉，o.id用于唯一標識對象o；o.s是對象o的空間屬性；o.t是對象o的文本描述。

用q=〈q.s，q.t，q.k〉表示一個空間關鍵詞查詢。其中，q.s是查詢的位置，q.t是查詢關鍵詞，q.k是需要返回的結果數目。

空間關鍵詞查詢q的目標是從數據集P中找出q.k個最優對象。一般，評價函數f（o，q）定義為：

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

下面給出了空間距離計算和文本相關度計算的主要公式：

（1）空間距離（δ）

在空間關鍵詞查詢中，δ一般是歐氏距離，計算公式為：

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

（2）文本相關度（θ）

計算文本相關度的方法很多，應用較廣泛的是計算兩個文本向量的余弦值。使用這種方法，θ可表示為：

其中，Wt，o.t=q+ln（ft，o.t），ft，o.t表示關鍵詞t在文本描述o.t中出現的頻數；，其中|P|表示對象的個數，dft表示包含t的文檔數。根據余弦性質可知計算結果在[0，1]內，這樣就能和距離計算結果的范圍保持一致。

2　空間關鍵詞查詢處理的基本技術

空間關鍵詞查詢主要研究如何提高查詢效率并拓展其實際應用。其中的關鍵問題是如何構建合適的索引結構。此外，還需要對查詢結果進行排序。以下將詳述這些內容。

2.1索引技術

構建高性能的索引是實現高效查詢的有效方法。下面，首先介紹基本的空間索引和文本索引技術，然后評述專門針對空間關鍵詞查詢的索引技術。

（1）空間索引技術

常見的空間索引技術大致可以分為四類，分別是：

①基于二叉樹的索引：基于此索引結構的主要有KD樹[9]、K-D-B樹[10]、LSD樹[11]等。這類空間索引結構適用于點狀對象。

②基于B-樹的索引：此類索引結構中比較典型的是R-樹。R-樹將空間對象及索引空間用最小邊界矩形（Minimum Bounding Rectangle）來近似表示，將空間相鄰的對象組織到同一結點或同一分支，并將一個結點對應成一個或者多個磁盤頁。該索引策略大大減少了I/O訪問。

③基于哈希的網格技術：這類索引將索引空間劃為若干格子，并將每個格子相關聯的空間目標存儲在同一磁盤頁，這樣，查詢時就能通過格子的標號來定位空間對象。具有代表性的便是Grid文件[13]，多用于點狀對象。

④空間目標排序法：此方法將多維對象映射到一維空間中，然后采用一維索引來實現。常見的映射方法有Z-排序、Hilbert曲線等。

（2）文本索引技術

文本索引主要是用于關鍵詞查詢。關鍵詞查詢中常用的索引結構主要是倒排索引（Inverted Index）[14]和簽名文件（Signature File）[15]。

①倒排索引

倒排索引是一種簡單高效的文本索引，它列出了每個關鍵詞以及包含該關鍵詞的所有對象，如表1所示。

表1　倒排索引

當需查詢包含關鍵詞k1和k4的對象時，就相交這兩個關鍵詞的對象集合，得到的{o1，o6}即為結果。

（2）簽名文件

簽名文件也是一種常見的文本索引方式，它為每個關鍵詞分配一個固定大小的向量，稱為簽名（signature）。對一個空間對象的所有關鍵詞的簽名進行OR運算，就形成了該對象的簽名。

在查詢時，首先生成查詢關鍵詞的簽名，然后通過AND操作進行檢索。

（3）基于空間關鍵詞查詢的索引技術

按照構建索引方式的不同，現有針對空間關鍵詞查詢的索引結構可分為兩類，一類是獨立索引[1，4]；另一類是混合索引[2~3，5~6]。

①獨立索引

針對空間關鍵詞查詢的獨立索引將傳統的文本索引技術和具有空間過濾功能的Quad樹[16]、R樹[12]、網格索引（grid index）[13]等空間索引獨立地用于查詢。

例如，文獻[3]中采用倒排索引來索引關鍵詞，用網格索引來索引空間位置；而文獻[17]使用Quad樹和R樹來進行空間索引。

基于獨立索引的空間關鍵詞查詢的效率很低，不適合數據規模較大、查詢時間要求較高的情況。

②混合索引

目前，空間關鍵詞查詢處理大多采用混合索引，即將空間索引和文本索引結合成統一的索引結構。混合索引可以分為松散混合索引[19]和緊密混合索引[2~3，5~7]。

●松散混合索引

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

本質上，松散混合索引還未擺脫空間索引和文本索引順序檢索的特點，查詢效率波動較大。

●緊密混合索引

緊密混合索引結合了空間索引和文本索引，在查詢過程中可同時訪問空間索引和文本索引。

采用R-樹作為空間索引的緊密混合索引本質上是在R樹的結點中加入子結點的文本信息，從而盡早實現對不合理路徑的剪枝。

同時進行空間和文本的索引，避免了過多的數據訪問，基于此類索引結構的空間關鍵詞查詢可有效提高效率。

2.2查詢算法

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

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

SK算法基于KR*樹索引結構實現。該算法以查詢Q和KR*樹的根結點N為輸入，Q=〈Q.r，Q.t，Q.k〉，給出查詢區域、查詢關鍵詞和需返回的對象個數。首先，算法檢查當前結點的所有子結點，若子結點包含所有的查詢關鍵詞，則加入列表。然后檢測結點是否與查詢區域相交，若相交，且該結點是葉子結點，則將滿足條件的對象加入候選集；若相交，但其不是葉子結點，則重復以上計算；若不相交，則剪掉該結點及其子結點。最后，算法返回一個候選集，該候選集里的所有對象都與查詢區域相交且包含查詢關鍵詞。若要進行top-k查詢，則需對候選集進行排序，并取最優的k個對象。

該算法較早實現對空間數據和文本數據的同時處理，能大大減小I/O開銷。由于需要在算法結束后進行排序，候選集較大時性能較差。

（2）距離優先IR2樹算法[2]

距離優先IR2樹算法基于IR2樹索引結構實現。該算法中，查詢關鍵詞只用于過濾，即只考慮包含全部查詢關鍵詞的對象。最后，算法返回包含查詢關鍵詞的前k個距離查詢點最近的對象，并按與查詢點的距離排序。

該算法查詢效率很高，I/O開銷較少。缺點在于只能實現關鍵詞的布爾查詢。

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

LkT算法主要用于基于位置的top-k空間關鍵詞查詢，采用的索引結構是IR-樹。

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

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

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

表2　空間關鍵詞查詢算法比較

2.3查詢結果的排序與評估

空間關鍵詞查詢一般要返回多個對象。這就需要合適的排序策略。現有研究中，排序方式可分兩類，一類是直接由查詢算法返回排序好的結果；另一類是在查詢算法結束后進行排序。

此外，還需評估查詢結果的好壞。評估方法主要考慮返回的候選對象的數目和最終結果與查詢要求的匹配程度。

2.4空間關鍵詞查詢的變體

還有空間關鍵詞查詢的變體，如移動空間關鍵詞查詢、多目標空間關鍵詞查詢等。

目前，針對移動查詢的研究主要采用安全區域（safe zone）的思想，若用戶在安全區域內，查詢結果不變。若用戶離開該區域，則重新提交查詢，計算新的結果和新的安全區域。

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

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

3　空間關鍵詞查詢的分布式處理

隨著實際應用越來越廣，在集中式環境下處理空間關鍵詞查詢已不能滿足對性能和效率的需求。

首先，實際的查詢系統往往基于C/S或B/S架構，若用戶規模極大，服務端將承擔巨大的負荷；其次，移動終端的日益普及導致移動查詢日益普及，對于移動查詢，用戶行進過程中不斷向服務端提交查詢，服務端不斷進行繁重的計算；再次，實際的空間關鍵詞查詢往往并不基于歐氏距離，而是基于道路網絡（以下簡稱路網），因為在現實中，從一個地方并不能通過直線路徑抵達另一地方，而必須經過道路路徑，相比歐氏空間，路網結構更復雜，數據量級更大，查詢效率難免降低。

綜上，在集中式環境下進行空間關鍵詞查詢已不能滿足現實應用的需求。于是，在分布式環境中進行處理已逐漸成為空間關鍵詞查詢問題的研究方向。如文獻[27]提出了一種基于多核平臺的平行處理技術，能對SQL語句執行分布處理，文獻[28]提出了一種分布式處理基于路網的空間關鍵詞查詢技術，文獻[29]提出了一種分布式空間關鍵詞查詢系統，以下將介紹一個具有代表性的分布式系統。

3.1DISKs(Distribured Spatial Keyword Search)

文獻[29]第一次提出基于分布式處理空間關鍵詞查詢問題，并提出了能有效處理基于路網的空間關鍵詞查詢的分布式系統，即DISKs。

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

（1）分割器和索引器

分割器以一個路網為輸入，輸出N個小的節點不相交的分區，并將連接各分區的邊的終點作為后續步驟的入口節點。

索引器以分割器輸出的分區及入口節點為參數，輸出名為NPD-Index（Node Partition Distance Index）的索引結構。NPD-Index由N個部分組成，每部分與一個分區關聯，并包含兩個結構，分別為DL（Distance List）和SC（Short-Cut）。其中，DL是路網中基于節點的搜索樹，它的每個葉節點被標記為該節點與其所在分區入口節點的距離。SC結構是一個附加邊的集合，每條邊連接該分區的兩個入口節點。

經過分割器和索引器的處理，使用分區及其相關的DL和SC結構，能準確計算出路網中任何一個位置到該分區中任何一個位置的最短距離。此外，通過將各入口點作為輸入，NPD-Index還能實現在整個路網上執行一組Dijkstra算法。

圖1　DISKs系統架構

（2）分布式查詢處理器

在NPD-Index被構建后，即能在集群中執行分布式查詢。將每個分區索引分配給一臺機器，從而計算出該分區的結果。分布式查詢算法以一個參數r和若干關鍵詞為輸入。對于每個關鍵詞K，節點集XK包含所有包含K的節點。對于每個分區P，查詢算法執行如下操作：

①對每個包含關鍵詞K的節點集XK，執行如下步驟:

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

Sub-step 2：從已遍歷到的入口節點開始，搜索P與SC的并集，并返回P中到XK中任何節點距離不超過r的節點。

②對所有節點集中的返回節點執行相交操作。①對每個關鍵詞K計算了P中到XK的距離不大于r的節點集。②相交后，找出P中到所有節點集（即每個關鍵詞的相關節點）距離不大于r的節點。

（3）基于Hadoop的DISKs實現

Hadoop工作階段由map階段和reduce階段組成。在map階段，任務被分配至不同的機器，在reduce階段，標志相同的map階段的輸出被發送到一臺機器上進行下一步操作。

如前所述，以入口節點為輸入，NPD-Index結構可實現為一組Dijkstra實例。在map階段，這些實例可方便地分布于不同機器上進行計算。在reduce階段，將map階段的結果匯總在一起。

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

4　結語

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

本文對空間關鍵詞查詢研究現狀進行了綜述，分別是從索引技術、查詢算法及結果評估等三方面對已有研究成果進行了闡述，并詳細介紹了一種分布式空間關鍵詞查詢系統。最后，指出了空間關鍵詞查詢研究的一些開放問題。

[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-），男，內蒙古自治區人，碩士研究生，研究方向為空間關鍵詞查詢

2015-03-27

2015-04-15