帶排斥關(guān)鍵字的空間關(guān)鍵字查詢

屠川川

帶排斥關(guān)鍵字的空間關(guān)鍵字查詢

屠川川

定義了一種新的空間關(guān)鍵字查詢模式，即帶排斥關(guān)鍵字的空間關(guān)鍵字查詢，它在普通空間關(guān)鍵字查詢基礎(chǔ)上添加了排斥關(guān)鍵字（即不需要的關(guān)鍵字），提高的查詢的靈活性并使得查詢場景更貼近真實情形。為這種新的關(guān)鍵字查詢模式設(shè)計了混合空間索引以加速查詢處理?；旌峡臻g索引由二叉樹和R-樹組成（文中稱之為BIR樹），并設(shè)計了相應(yīng)的查詢剪枝算法以加速查詢。實驗證明在這種空間關(guān)鍵字查詢模式下，BIR樹有著相當(dāng)高的查詢效率。

關(guān)鍵字查詢；空間索引；排斥關(guān)鍵字；IR-樹；地理信息數(shù)據(jù)

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，越來越多的信息可以從網(wǎng)上獲取，能夠從這大量的數(shù)據(jù)中找到需要信息的搜索引擎變得越來越重要。在另一方面，越來越多的互聯(lián)網(wǎng)服務(wù)商開始提供基于位置信息的服務(wù)，并且專注于地理信息的搜索引擎也已經(jīng)有了很大的發(fā)展。傳統(tǒng)的信息搜索引擎致力于在盡可能短的時間內(nèi)返回用戶所需要的準(zhǔn)確的數(shù)據(jù)，與此類似，地理信息搜索引擎也把在盡可能短的時間內(nèi)找到需要的數(shù)據(jù)作為目標(biāo)。兩者的結(jié)合，基于帶關(guān)鍵字的地理信息查詢的互聯(lián)網(wǎng)服務(wù)已經(jīng)得到初步的發(fā)展。普通的餐館，酒店的查詢僅僅到了地理信息搜索引擎，而現(xiàn)在互聯(lián)網(wǎng)服務(wù)商能夠提供給客戶更多的選擇，比如在查詢餐館的同時指定口味、人氣、以及一系列針對個別客戶的定制化信息，這些信息都需要用到傳統(tǒng)的信息搜索引擎來完成。

但是，僅僅是將信息搜索引擎和地理信息搜索引擎簡單的結(jié)合仍然無法很好地滿足現(xiàn)實生活中的需求，因為，目前的查詢模式只能夠允許用戶輸入他們感興趣的關(guān)鍵字。讓我們看幾個簡單的例子，在外地旅游的時候預(yù)定旅館是一個在互聯(lián)網(wǎng)上被非常頻繁使用的服務(wù)。通?？梢灾付灭^的位置、價格、以及一些額外的信息如全天熱水、無線網(wǎng)絡(luò)、可以攜帶寵物等。在傳統(tǒng)的空間關(guān)鍵字查詢模式中，用戶可以在指定地理位置之后選擇一些自己需要的關(guān)鍵字，然后，服務(wù)器會根據(jù)這新信息為用戶介紹一些合適的旅館。但是，一些特殊的要求無法在這種查詢模式中得到滿足，比如某人對某些動物過敏，因此，不希望在允許攜帶寵物旅館中居住，或者有些人不喜歡煙味，因此，不希望住在一個可以抽煙的旅館。在傳統(tǒng)的空間關(guān)鍵字查詢模式中，由于用戶無法輸入他們不需要的關(guān)鍵字，因此，對于服務(wù)器返回的結(jié)果，他們需要挨個檢查是否滿足他們的特殊需求。因此，本文中提出了一種新的空間關(guān)鍵詞查詢模式，允許用戶輸入他不喜歡的關(guān)鍵字，并根據(jù)這新信息進一步精簡返回給用戶的查詢結(jié)果列表，以節(jié)省用戶挨個檢查的時間。

定義1. 帶排斥關(guān)鍵字的空間關(guān)鍵字查詢是一個信息檢索的問題。所有興趣點以及它們包含的地理位置和關(guān)鍵字是這個問題的數(shù)據(jù)基礎(chǔ)。兩個關(guān)鍵字集合（Wl, Wd）以及一個地理位置p作為問題的輸入，Wl代表用戶需要的關(guān)鍵字，Wd代表用戶不需要的關(guān)鍵字，p由經(jīng)緯度表示。目的是找到距離p最近的一個或幾個帶有Wl中所有關(guān)鍵字并且不帶任何一個Wd中關(guān)鍵字的興趣點。

1 相關(guān)工作

在傳統(tǒng)空間關(guān)鍵字查詢領(lǐng)域已有很多的相關(guān)工作，大多數(shù)相關(guān)論文都使用這樣一個問題模型，用戶提交一個查詢地點以及一組關(guān)鍵詞，服務(wù)器在數(shù)據(jù)庫中找出靠近查詢地點并且滿足用戶提交關(guān)鍵詞的一個或者一組查詢目標(biāo)。針對這個問題模型，一系列論文提出了大量的索引以及算法來優(yōu)化查詢效率。比如論文[1]中提出了一個結(jié)合了倒排文件（inverted file）和R*[2]樹的索引結(jié)構(gòu)以及一整套針對帶關(guān)鍵詞的空間查詢的框架體系，作為這個領(lǐng)域最早的論文之一，整合多種索引的想法具有很大的啟發(fā)性意義。論文[3]沿用了這個索引，并提出了更高效的查詢算法。論文[4]和[5]為傳統(tǒng)搜索引擎優(yōu)化了算法，使得搜索帶有地理信息標(biāo)簽的網(wǎng)頁搜索成為可能。論文[6]提出了IR樹索引，這也是本文提出索引結(jié)構(gòu)參考的的一種高效的帶關(guān)鍵字空間信息的索引結(jié)構(gòu)。還提出了一種IR樹的改進版本，DIR樹，進一步優(yōu)化了空間關(guān)鍵字查詢的效率，由于這種索引是目前在這個領(lǐng)域比較高效并且有代表性的索引結(jié)構(gòu)，因此本文中將它作為了對比算法。論文[7]擴展了IR樹并為它設(shè)計了完整的查詢框架。[8]提出了IR樹的另一種優(yōu)化，W-IR樹。[9]提出了bR*樹，一種將位圖和R*樹結(jié)合在一起的索引結(jié)構(gòu)。論文[10]考慮到了關(guān)鍵詞的分布，認為不同關(guān)鍵詞被查詢到的概率是不同的，這也是本文實驗中作出的一個假設(shè)。論文[11]提出了一種完全基于倒排文件的索引結(jié)果（S2I），而沒有用到R樹等空間索引，并提出了對應(yīng)的查詢算法?？臻g信息和關(guān)鍵詞信息的結(jié)合是一個很熱門的研究方向，在這個領(lǐng)域還有很多相關(guān)工作，由于篇幅所限，很多相關(guān)工作無法在這里一一介紹。

2 對比算法

在這個部分我們將詳細介紹一種名為DIR（document similarity enhanced inverted file R-tree）樹的索引結(jié)構(gòu)以及對于本文提出問題的搜索算法。因為，DIR樹是一種在空間關(guān)鍵詞搜索領(lǐng)域非常高效的索引結(jié)構(gòu)，我們將使用它作為本文實驗的對比算法。

DIR樹作為IR樹的一種拓展，是一種利用倒排文件（inverted file）索引帶權(quán)值關(guān)鍵詞信息，同時，利用R樹的索引空間信息的混合數(shù)據(jù)結(jié)構(gòu)。倒排文件是一種優(yōu)化關(guān)鍵詞查詢的索引結(jié)構(gòu)。一個倒排文件是由多個鏈表組成的，每個鏈表的表頭是一個關(guān)鍵詞，之后的每個鏈表結(jié)點是一個包含這個關(guān)鍵詞的興趣點，通過倒排文件，可以在O(1)得到時間內(nèi)得到包含某個關(guān)鍵詞的所有興趣點。DIR樹中使用的倒排文件進行了簡化，一個R樹結(jié)點，相應(yīng)的倒排文件的每個關(guān)鍵字鏈表中只記錄了該結(jié)點所包含的興趣點中帶有該關(guān)鍵詞并且權(quán)值最大的興趣點信息。本文將關(guān)鍵字查詢的問題做了適當(dāng)簡化，去掉了關(guān)鍵字的權(quán)值，因為，在實驗中使用的DIR樹的倒排文件退化成了類似位圖（bitmap）的結(jié)構(gòu)。

DIR樹的興趣點插入以及結(jié)點分裂規(guī)則都和傳統(tǒng)R樹有著不同。在插入一個興趣點時，普通R樹會通過興趣點的位置信息選擇一個適合的葉子結(jié)點，而DIR樹會同時考慮空間信息以及關(guān)鍵詞信息，找出在空間上和文本相似度上都較高的葉子結(jié)點作為插入結(jié)點。R樹結(jié)點的分裂同樣會考慮到關(guān)鍵詞信息。調(diào)整空間信息和關(guān)鍵詞信息在DIR樹中的比重，就可以適應(yīng)各種應(yīng)用場景。在DIR樹上的搜索過程和傳統(tǒng)R樹非常類似，一個查詢會從DIR樹的根結(jié)點進入，并將所有可能滿足條件的下層結(jié)點加入待查找隊列。這里的條件包括空間位置以及關(guān)鍵詞?？臻g位置可以通過每個結(jié)點的MBR來獲得，關(guān)鍵詞信息則是通過結(jié)點中的倒排文件獲得。假設(shè)一個查詢Q包含以下信息：經(jīng)緯度坐標(biāo)p(x,y)，和關(guān)鍵詞信息Wl(k1,k2,…,kn)以及Wd(k’1,k’2,…,k’m)。當(dāng)訪問到DIR樹中的某個結(jié)點時，我們按照距離查詢點從近到遠依次檢查它的每個孩子結(jié)點的倒排文件。如果倒排文件滿足兩個關(guān)鍵詞集合（包含Wl中所有關(guān)鍵詞并且不包含任意一個Wd中的關(guān)鍵詞），則檢查該結(jié)點是否為葉子結(jié)點，如果是葉子結(jié)點，直接返回作為結(jié)果。如果不是，則將它加入查詢隊列，并取出查詢隊列前端結(jié)點開始下一次迭代。

由于R樹結(jié)點上的倒排文件只能記錄該結(jié)點上出現(xiàn)過哪些關(guān)鍵詞，并不能很好的代表結(jié)點上所有興趣點，我們可以看一個例子：當(dāng)訪問到DIR樹中某個結(jié)點N時，我們檢查它的倒排文件，如果Wl中出現(xiàn)了倒排文件中沒有的關(guān)鍵詞，那么這個結(jié)點可以從待查找隊列中去除，但是我們卻不能根據(jù)Wd集合與倒排文件的關(guān)系將結(jié)點從候選中去除，因為即使倒排文件中包含了某個不需要的關(guān)鍵詞，該結(jié)點中仍可能存在滿足Wd集合條件的興趣點。這會導(dǎo)致查詢空間的變大，從而導(dǎo)致查詢效率低下。

3 BIR樹

在這個部分我們將詳細介紹一種新的數(shù)據(jù)，二叉樹與IR樹的混合索引，該索引改進了IR樹的結(jié)構(gòu)，從而避免上面提出DIR樹在處理Wd集合時的缺點，同時為關(guān)鍵詞增加一個二叉樹索引，進一步提高了帶關(guān)鍵詞空間查詢的效率。本章節(jié)將會分為兩部分，第一部分介紹BIR樹的結(jié)構(gòu)以及構(gòu)建過程，第二部分介紹查詢的處理過程。

3.1 BIR樹結(jié)構(gòu)

定義2. Binary R樹（簡稱BIR樹）是一棵基于一組關(guān)鍵詞集合和(W)建立的平衡二叉樹。第i層上所有結(jié)點Rs保證如下性質(zhì)：Wi是W中第i個關(guān)鍵字，BIR樹第i層上所有左結(jié)點中只存在包含Wi關(guān)鍵字的興趣點，右結(jié)點中只存在不包含Wi關(guān)鍵字的興趣點。二叉樹一共k層，每一個葉子結(jié)點都是一棵改進后的IR樹（將在后面詳細介紹）。對于一個給定興趣點以及一棵已經(jīng)建立的BIR樹，根據(jù)興趣點包含關(guān)鍵字的信息，它會屬于二叉樹唯一一個葉子結(jié)點。一棵兩層BIR樹的簡單例子，有兩個關(guān)鍵詞被索引在二叉樹中如圖1所示：

圖1 BIR樹例子

所有興趣點最終落在二叉樹的葉子結(jié)點內(nèi)，并組成若干棵R樹。由于二叉樹的存儲開銷是和高度程指數(shù)增長的，因此，在二叉樹中能夠索引的關(guān)鍵詞數(shù)量是很有限的。通常熱門的關(guān)鍵詞會被優(yōu)先索引在二叉樹中，使得二叉樹索引能夠在大多數(shù)查詢中都起到剪枝的作用。

在二叉樹的葉子結(jié)點時一系列的R樹。為了能夠處理關(guān)鍵字查詢，我們對R樹進行了一些改進。和IR樹類似，我們首先為R樹加上了兩個倒排文件IF1和IF2。IF1與IR樹上的相同，記錄了每個結(jié)點中包含的興趣點的關(guān)鍵詞出現(xiàn)情況。IF2記錄了該結(jié)點包含的興趣點中共同擁有的關(guān)鍵詞信息。也就是說，如果某個R樹結(jié)點中包含了以下幾個興趣點（I1,I2,…,In），僅當(dāng)某個關(guān)鍵詞ki出現(xiàn)在所有這些興趣點中時，這個倒排文件才會記錄這個關(guān)鍵詞。

由于我們在傳統(tǒng)R樹上添加了兩個倒排文件，按照原來完全按空間位置的插入和結(jié)點分裂算法，這兩個倒排文件的性能無法得到完全發(fā)揮。這是因為一般情況下，一個小區(qū)域內(nèi)的興趣點共同包含的興趣點數(shù)量是很少的，反映在R樹上就是，上層結(jié)點的IF1會非常大，而IF2則很可能是空集。這對提高查詢剪枝的效率是非常不利的。因此我們需要改進R樹的插入和結(jié)點分裂算法，以適應(yīng)我們對R樹結(jié)構(gòu)的改進。

當(dāng)一個興趣點插入一棵BIR樹時，首先會比較那些被二叉樹索引的關(guān)鍵詞，這個結(jié)果是確定的。因此我們只考慮將一個興趣點插入R樹的過程。首先我們重新需要定義一個興趣點o到一個R樹結(jié)點M的距離，并把關(guān)鍵字的信息也考慮在內(nèi)。距離公式如下：

其中distk是興趣點與R樹結(jié)點關(guān)鍵詞距離，定義如下

于曉明一行參觀了法律服務(wù)所的黨員活動室、接待大廳、人民調(diào)解委員會辦公室等場所，聽取了黨建、法律援助、普法等工作情況的介紹，并與前來進行法律咨詢的群眾進行了親切交流。

其中分子指興趣點與M中所有關(guān)鍵詞的并集大小，即興趣點與IF1的并集。分母是興趣點關(guān)鍵詞和IF1的交集大小。這個距離越小表示插入興趣點和R樹結(jié)點內(nèi)興趣點關(guān)鍵詞相似度越大。而距離公式中歐氏距離部分是o與M最短距離和M內(nèi)距離o最遠的興趣點o’的距離的乘積，同樣這個距離也隨著o與M的距離增大而增大。將這兩個距離加權(quán)平均之后得到綜合距離，這個距離將歐氏距離和關(guān)鍵詞相似度整合到一起，通過調(diào)整兩邊的權(quán)值，就可以應(yīng)對各種情況。

完成了距離函數(shù)的定義，我們可以利用原有的R樹的插入算法將一個興趣點插入R樹。當(dāng)R樹某個結(jié)點到達存儲上限時，將會發(fā)生分裂。傳統(tǒng)R樹的分裂算法也是完全按照歐氏距離，將互相靠近的子結(jié)點分到同一邊。但在這里我們會考慮關(guān)鍵詞的信息。我們的目標(biāo)是，在完成結(jié)點分裂之后，得到的兩個新的結(jié)點中IF1盡可能小，而IF2盡可能大。因此在分裂時，考慮所有分裂可能性，并找出IF1盡可能小同時IF2盡可能大的結(jié)果，作為分裂結(jié)果。用重新定義的距離函數(shù)以及分裂算法得到的R樹會與傳統(tǒng)R樹有較大區(qū)別，同一個結(jié)點中的興趣點將會在關(guān)鍵詞信息上更加相近，這樣的結(jié)構(gòu)非常符合本文提出的查詢模式。

3.2 BIR樹上的查詢算法

完成了R樹的構(gòu)建，我們將在這節(jié)中介紹BIR樹的查詢算法。BIR樹的查詢主要分為兩個步驟，第一步是在二叉樹上進行查詢，這一步將會得到一組葉子結(jié)點。也就是一組R樹的根結(jié)點作為輸出。第二步是在以這些結(jié)點為根的R樹上進行搜索，利用一個最小堆，能夠以很小的代價完成查詢搜索。

對于一個查詢，按照本文查詢模式的定義，會有一個經(jīng)緯度p(x,y)，兩個關(guān)鍵詞集合Wl和Wd。首先來看第一步。由于二叉樹只對幾個最熱門的關(guān)鍵詞進行了索引，因此，我們也只需關(guān)注這些關(guān)鍵詞有沒有出現(xiàn)在Wl和Wd中即可。如果某個被索引關(guān)鍵詞出現(xiàn)在Wl中，按照二叉樹定義，索引該關(guān)鍵詞的層的所有右結(jié)點可以從候選中刪去，因為，根據(jù)定義該層中所有右結(jié)點包含的興趣點都不會包含該關(guān)鍵詞，與查詢要求相反。同樣，如果該關(guān)鍵詞出現(xiàn)在Wd中，則所有左結(jié)點可以被刪去。完成了二叉樹上的查詢之后，我們得到了一組R樹根結(jié)點。將這些結(jié)點放入一個最小堆，鍵值為結(jié)點和查詢點的最小距離。每次從最小堆中取出一個R樹結(jié)點，檢查它的每個孩子結(jié)點的兩個倒排文件。如果滿足，IF1中包含Wl中所有關(guān)鍵詞并且IF2和Wd交集為空，則將它作為候選結(jié)點加入最小堆，否則直接拋棄。重復(fù)這個過程直到找到第一個（根據(jù)查詢要求可能為第k個）興趣點。將找到的興趣點作為結(jié)果返回后一次查詢就結(jié)束了。

4 實驗部分

在這章節(jié)中，我們通過實驗證明了本文提出的索引結(jié)構(gòu)和查詢算法的高效性。所有實驗都只關(guān)注運行時間因為我們認為在內(nèi)存容量越來越大的現(xiàn)在，I/O性能瓶頸已經(jīng)可以由擴大內(nèi)存的手段彌補。我們使用了倫敦的地圖數(shù)據(jù)作為數(shù)據(jù)來源，一共包括34,162個興趣點，以及1035個互相不同的關(guān)鍵詞。由于建立二叉樹時需要關(guān)鍵詞的熱門程度而我們又無法得到現(xiàn)實生活中各關(guān)鍵詞的被查詢頻度，我們隨機了每個關(guān)鍵詞的被查詢頻率，并利用換這個頻率建立了二叉樹。之后隨機生成查詢時，關(guān)鍵詞的選取仍然會按照這次隨機得到的概率分布。我們按照分布為每個關(guān)鍵詞分配了出現(xiàn)頻率，并取了α=1作為基礎(chǔ)值，也就是說大概有20%的關(guān)鍵詞占據(jù)了80%的概率，我們認為這是符合現(xiàn)實生活中用戶的查詢習(xí)慣的，因為熱門的關(guān)鍵詞只占總關(guān)鍵詞的少數(shù)但是會頻繁得被查詢。在一組實驗中，我們將的值從0調(diào)整到1.33，來考察α值，也就是說查詢關(guān)鍵詞分布情況對我們提出的索引的影響。就像之前已經(jīng)介紹過的，我們將DIR樹作為了基準(zhǔn)算法，除了對二叉樹層數(shù)的實驗，其他所有實驗都是與DIR樹做對比得到的。

4.1 實驗結(jié)果圖及說明

在實驗結(jié)果圖之前，我們先用一個表格說明實驗的基本設(shè)定，如表1所示：

表1 實驗參數(shù)設(shè)定

其中帶下劃線的參數(shù)設(shè)定是我們在實驗中使用的默認值。實驗結(jié)果圖如圖2所示：

圖2 vs. Layer

每一幅圖都對應(yīng)了表格中一個參數(shù)。為了避免特殊情況的影響，提高實驗的代表性，在圖2中所有數(shù)據(jù)都是100個隨機查詢消耗時間的平均值。

首先，我們給出二叉樹不同層數(shù)情況下查詢效率的比較，如圖3所示：

圖3 實驗結(jié)果

在圖3中我們可以看到，隨著二叉樹層數(shù)的增加，查詢時間先減少后增加，然后保持在了一個中等水平。這是因為，隨著二叉樹層數(shù)增加，更多熱門關(guān)鍵詞被索引，大多數(shù)查詢在二叉樹中就可以極大減少搜索空間，這對查詢效率的提升是很明顯的。但是二叉樹的存儲空間是指數(shù)增加的，而層數(shù)過多也會影響下層的R樹結(jié)構(gòu)，造成在R樹上查詢效率下降，因此，當(dāng)層數(shù)到達4之后，查詢效率并沒有繼續(xù)提高，而是下降然后保持在一個中等水平?？梢灶A(yù)見，如果層數(shù)繼續(xù)增加，查詢效率反而會緩慢下降，因此，在其他實驗中，我們使用三層二叉樹為熱門關(guān)鍵詞做索引。

在圖3中的4幅圖分別是表1中剩下4個參數(shù)的實驗結(jié)果圖。在針對某一個參數(shù)進行研究時，我們保持剩下的參數(shù)都取默認值。從圖3中我們可以看到，大多數(shù)情況下，BIR樹的查詢效率都要高于DIR樹。在調(diào)整|Wl|大小的實驗中，BIR樹表現(xiàn)出了和DIR樹相反的趨勢，因為隨著|Wl|的增大，BIR樹的二叉樹部分能夠提供更好的剪枝效果，而兩種索引的R樹部分都會因為比較次數(shù)的增加而效率有所降低，最終得到圖中的結(jié)果。在調(diào)整|Wd|的實驗中，兩種索引的效率都隨著|Wd|增大而下降，因為，不需要的關(guān)鍵詞對R樹的查詢效率影響很大，雖然BIR樹在二叉樹層可以利用Wd中的關(guān)鍵詞進行剪枝，但是，仍然比不上R樹上查詢的效率損失。α的變化對DIR樹的查詢效率并沒有明顯的影響，而隨著用戶查詢關(guān)鍵詞的集中，DIR樹的效率有很明顯的提高，因為，越多的被查詢關(guān)鍵詞被二叉樹索引到，那么DIR樹的查詢效率就能越高。最后，一幅是調(diào)整查詢中需要興趣點個數(shù)的實驗圖，從圖中可以看到BIR樹受到k的影響遠遠小于DIR樹。

5 總結(jié)

本文提出了一種帶關(guān)鍵詞空間查詢的新查詢模式，提出了高效的索引結(jié)構(gòu)和查詢算法，并通過大量的實驗證明了索引和算法的高效性。我們打算在路網(wǎng)數(shù)據(jù)中進一步研究這個新的查詢模式，同時我們也將考慮將搜索引擎中常見的排序算法（如Page Rank）結(jié)合到這個查詢中，使得查詢返回的結(jié)果能夠更貼合實際生活中的應(yīng)用場景。

[1]Zhou Y., Xie X., Wang C., Gong Y., and Ma W.-Y.. Hybrid index structures for location-based web search [J].In CIKM, ACM, 2005:155-162.

[2]Beckmann N., Kriegel H.-P., Schneider R., and Seeger B.. The R*-tree: an efficient and robust access method for points and rectangles [M].ACM, 1990(19).

[3]Hariharan R., Hore B., Li C., and Mehrotra S.. Processing spatial-keyword (sk) queries. geographic information retrieval (gir) systems [C].In SSDBM. IEEE, 2007.

[4]Chen Y.-Y., Suel T., and Markowetz A.. Efficient query processing in geographic web search engines [C]. In SIGMOD. ACM, 2006:277-288.

[5]Cong G., Jensen C. S., and Wu D.. Efficient retrieval of the top-k most relevant spatial web objects [J]. VLDB, 2009,2(1):337-348.

[6]Wu D., Cong G., and Jensen C. S.. A framework for efficient spatial web object retrieval [J]. VLDBJ, 2012,21(6):797-822.

[7]Wu D., Yiu M. L., Cong G., and Jensen C. S.. Joint top-k spatial keyword query processing [J]. IEEE TKDE, 2012,24(10):1889-1903.

[8]Zhang D., Chee Y. M., A. Mondal, A. Tung, and M.Kitsuregawa. Keyword search in spatial databases:Towards searching by document [C]. In ICDE,IEEE,2009: 688-699.

[9]G¨obel R., Henrich A., Niemann R., and Blank D.. A hybrid index structure for geo-textual searches[C]. CIKM, ACM, 2009:1625-1628.

[10]Rocha-Junior J. B., Gkorgkas O., Jonassen S., and N?rv°ag K.. Efficient processing of top-k spatial keyword queries. In Advances in Spatial and Temporal Databases [C].Springer, 2011: 205-222.

[11]M. Christoforaki, J. He, C. Dimopoulos, A. Markowetz, and T. Suel. Text vs. space: efficient geo-search query processing. CIKM [J].ACM, 2011:423-432.

Exclusive Spatial Keyword Query

Tu Chuanchuan

(Fudan University, Shanghai200433, China)

This paper identifies a new mode of spatial keyword query, which is the spatial keyword query with keyword exclusion. It adds keyword exclusion (the keywords which are not essential) on basis of the normal spatial keyword query, so as to improve the querying flexibility and make the querying scenario draw to the real-world situation. The paper desires a hybrid space index for this new mode to accelerate the query process. The hybrid space index is made up of binary tree and R tree (called as BIR tree in the paper), it meanwhile desires relevant query Alpha-Beta pruning to boost the query. The experiment demonstrates that BIR tree is high efficiency under this spatial keyword query mode.

earch; Spatial Index; Exclude Keyword; IR-tree; Geo-information

TP393

A

2015.02.02）

1007-757X(2015)04-0019-04

屠川川（1989-），男，復(fù)旦大學(xué)，碩士研究生，研究方向：空間數(shù)據(jù)庫，上海，200433