孟祥福，王丹丹，張霄雁，賈江浩

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

2.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

隨著GPS定位和移動(dòng)網(wǎng)絡(luò)技術(shù)的不斷發(fā)展以及智能設(shè)備的普及應(yīng)用，Web上出現(xiàn)了大量包含位置信息和文本信息的空間-文本對(duì)象（后文簡稱空間對(duì)象），進(jìn)而使得基于位置的服務(wù)（location based service，LBS）得到了廣泛應(yīng)用。近年來，有學(xué)者提出以一組空間對(duì)象作為空間關(guān)鍵字查詢結(jié)果的基本單元，這組空間對(duì)象的特征聯(lián)合起來以滿足用戶的查詢需求，這種查詢方法稱為集合空間關(guān)鍵字查詢（collective spatial keyword query，CSKQ）[1-5]，該類方法在空間數(shù)據(jù)庫查詢領(lǐng)域逐漸受到關(guān)注。CSKQ的基本思想是，給定一個(gè)空間關(guān)鍵字查詢條件（包括查詢位置和查詢關(guān)鍵字），以最小的代價(jià)查找一組對(duì)象，該組對(duì)象需要滿足如下3個(gè)基本條件：（1）能夠覆蓋所有查詢關(guān)鍵字；（2）組內(nèi)對(duì)象與查詢位置接近；（3）組內(nèi)對(duì)象之間位置相互接近。雖然目前已有一些CSKQ方法，但這些方法存在以下不足：（1）查詢結(jié)果僅提供一組空間對(duì)象，但實(shí)際應(yīng)用中返回top-k組對(duì)象可為用戶提供更多的選擇；（2）沒有考慮組內(nèi)空間對(duì)象之間的關(guān)聯(lián)訪問程度，而在現(xiàn)實(shí)中位置臨近的不同類型對(duì)象之間通常具有密切的關(guān)聯(lián)訪問關(guān)系，例如旅游景點(diǎn)與其周邊的酒店和餐廳經(jīng)常被用戶關(guān)聯(lián)訪問，關(guān)聯(lián)訪問度越大，用戶越有可能同時(shí)訪問這些對(duì)象，得到的結(jié)果也越符合用戶的需求；（3）集合空間關(guān)鍵字精確查詢往往需要枚舉目標(biāo)數(shù)據(jù)集中所有對(duì)象的所有可能組合，這將導(dǎo)致計(jì)算量非常龐大，進(jìn)而影響查詢響應(yīng)速度。針對(duì)上述問題，本文提出一種新的集合空間關(guān)鍵字近似查詢方法，稱為Top-k集合空間關(guān)鍵字近似查詢（Top-kcollective spatial keyword approximate query，Top-kCSKAQ）方法。

下面結(jié)合具體例子說明本文方法的基本思想。

例1圖1給出了8個(gè)空間對(duì)象{O1,O2,…,O8}及它們的描述信息，表1給出了它們的位置信息，表2是用戶歷史訪問記錄，根據(jù)用戶歷史訪問記錄可以挖掘出空間對(duì)象之間的關(guān)聯(lián)訪問度。假設(shè)某個(gè)游客在位置〈5，4〉處提出查詢關(guān)鍵字“Shopping，Restaurant，Hotel”。傳統(tǒng)集合空間關(guān)鍵字查詢方法返回的top-1結(jié)果為{O3,O8,O7}，top-2結(jié)果為{{O3,O8,O7},{O6,O2,O8}}。但如果在考慮距離的同時(shí)考慮組內(nèi)對(duì)象的關(guān)聯(lián)訪問度，即利用本文提出的Top-kCSKAQ方法，則返回的top-1結(jié)果為{O6,O2,O8}，top-2結(jié)果為{{O6,O2,O8},{O3,O8,O7}}。這是因?yàn)楦鶕?jù)歷史用戶訪問記錄，可以觀察到O6,O2,O8被關(guān)聯(lián)訪問的可能性更大。

圖1 空間對(duì)象及其文本描述Fig.1 Spatial objects and their textual descriptions

表1 空間對(duì)象的位置信息Table 1 Location information of spatial objects

表2 空間對(duì)象的用戶歷史訪問記錄Table 2 User check-in records for spatial objects

本文的貢獻(xiàn)總結(jié)如下：

（1）提出了基于Apriori算法的空間對(duì)象關(guān)聯(lián)訪問度評(píng)估方法。

（2）設(shè)計(jì)了一種新的候選空間對(duì)象組合評(píng)分函數(shù)，據(jù)此對(duì)候選對(duì)象組合進(jìn)行排序，選取top-k組近似結(jié)果。

（3）提出了一種基于VP-Tree的剪枝策略，實(shí)現(xiàn)快速鄰域匹配，修剪空間對(duì)象，減少計(jì)算量。

（4）在Yelp真實(shí)數(shù)據(jù)集進(jìn)行了大量的實(shí)驗(yàn)，評(píng)估Top-kCSKAQ方法的效率和有效性。

1 相關(guān)工作

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

傳統(tǒng)的空間關(guān)鍵字查詢將查詢位置和查詢關(guān)鍵字作為參數(shù)，并返回與這些參數(shù)在空間和文本上相關(guān)的空間對(duì)象。文獻(xiàn)[6-27]在研究空間-文本查詢的不同方面做出了一系列的貢獻(xiàn)。傳統(tǒng)的空間關(guān)鍵字查詢主要考慮空間相近性和文本相似性，忽略了用戶偏好和語義近似等方面。針對(duì)該問題，文獻(xiàn)[6-9]研究了空間關(guān)鍵字語義查詢方法，目標(biāo)是找到在空間鄰近性、文本相似性和語義相關(guān)性方面最優(yōu)的對(duì)象。文獻(xiàn)[4]在空間關(guān)鍵字查詢中考慮了用戶偏好，更好地滿足用戶的個(gè)性化需求。已有的研究大多數(shù)集中在歐式空間中如何有效處理空間關(guān)鍵字查詢，但事實(shí)上人們的日常生活是被路網(wǎng)約束的，空間鄰近性應(yīng)該由最短路徑距離而不是歐氏距離來決定，在歐式空間查詢的最優(yōu)結(jié)果在實(shí)際中不一定是最優(yōu)的結(jié)果。所以現(xiàn)在一些工作研究了一個(gè)新的問題，即在路網(wǎng)上進(jìn)行空間關(guān)鍵字查詢[11-13]。與歐式空間相比，基于路網(wǎng)的空間關(guān)鍵字查詢的研究更具有現(xiàn)實(shí)意義和價(jià)值，也給研究者們帶來了更大的挑戰(zhàn)。同時(shí)一些方法研究路線規(guī)劃查詢[14-16]，旨在找到滿足用戶需求的最優(yōu)路線，比如可以利用基于關(guān)鍵字的最優(yōu)路線查詢?yōu)橛脩粢?guī)劃包含用戶所有感興趣的旅游景點(diǎn)并且花費(fèi)較低的一條路線。有一些研究者們沒有考慮上述內(nèi)容，而是關(guān)注于社交網(wǎng)絡(luò)中的查詢。比如，文獻(xiàn)[1]提出了一個(gè)社會(huì)空間組查詢，該查詢選擇一組附近的具有緊密社交關(guān)系的參與者。要求與會(huì)者到集合點(diǎn)的空間距離最小，同時(shí)滿足一定的社會(huì)約束。

1.2 集合空間關(guān)鍵字查詢

通常情況下，只通過單個(gè)空間對(duì)象很難滿足用戶的所有查詢需求，所以進(jìn)而提出集合空間關(guān)鍵字查詢方法。在文獻(xiàn)[28-29]中，提出了一種新的空間關(guān)鍵字查詢，稱為m-最近鄰關(guān)鍵字（mCK）查詢，其目的是找到與m個(gè)用戶指定關(guān)鍵字匹配的空間最近鄰元組。Cao等人[2-3]提出了集合空間關(guān)鍵字查詢問題（collective spatial keyword query problem，CoSKQ），即檢索所有對(duì)象中包含的關(guān)鍵字共同覆蓋查詢關(guān)鍵字的一組對(duì)象。文獻(xiàn)[3]提出高效處理空間關(guān)鍵字組查詢，解決了三個(gè)實(shí)例化的檢索top-k組的問題，設(shè)計(jì)了精確解和具有可證明的近似解，并研究合并對(duì)象權(quán)重的問題的加權(quán)版本。文獻(xiàn)[4]提出新的個(gè)性化空間關(guān)鍵字查詢問題-集合關(guān)鍵字偏好查詢（collective keywords preference query，CKPQ），設(shè)計(jì)了基于訪問歷史和潛在POIs主題的用戶偏好模型，然后根據(jù)集合內(nèi)空間對(duì)象之間的最大距離、集合內(nèi)空間對(duì)象到查詢位置的最大距離以及集合的可達(dá)性（由POI流行度和擁塞度確定，避免在高峰時(shí)間訪問受歡迎的POI）構(gòu)造一個(gè)成本函數(shù)，根據(jù)該模型計(jì)算候選群體的成本，檢索一組結(jié)果。文獻(xiàn)[30]目的是檢索可以覆蓋所有查詢關(guān)鍵字，組內(nèi)對(duì)象接近查詢位置，組內(nèi)對(duì)象距離最小的top-k組對(duì)象。文獻(xiàn)[5]定義了反向集合空間關(guān)鍵字查詢（reverse collective spatial keyword query，RCSKQ）。它是一種新穎的反向空間關(guān)鍵字查詢，用于查找CSKQ中包含查詢對(duì)象的所有用戶。提出了兩種新的過濾策略，一種是利用改進(jìn)的G-Tree索引結(jié)構(gòu)（具有最大距離的反向G-Tree，G-Tree是一種改善最短路徑問題計(jì)算性能的路網(wǎng)指標(biāo)結(jié)構(gòu)）來解決計(jì)算開銷問題的用戶過濾策略。另一種是無索引結(jié)構(gòu)的啟發(fā)式過濾，減少搜索空間。值得一提的是，以往的工作僅針對(duì)歐式空間中的集合空間關(guān)鍵字查詢問題，Gao等人[31]、Su等人[32]研究了路網(wǎng)上的空間關(guān)鍵詞集合查詢處理問題。

綜上可見，空間關(guān)鍵字查詢方法的研究已經(jīng)從多個(gè)方面展開，上述方法重點(diǎn)在于查找單個(gè)空間對(duì)象作為結(jié)果，現(xiàn)有的集合空間關(guān)鍵字方法也大多僅根據(jù)距離關(guān)系檢索結(jié)果。然而，上述集合空間關(guān)鍵字查詢方法忽略了空間對(duì)象之間的關(guān)聯(lián)關(guān)系，這可能使查詢結(jié)果不能讓用戶滿意。針對(duì)上述問題，本文綜合考慮了距離和空間對(duì)象之間的關(guān)聯(lián)訪問度，提出了關(guān)聯(lián)訪問度的評(píng)估方法，設(shè)計(jì)了一種新的評(píng)分函數(shù)，用來度量組合的得分。在此基礎(chǔ)上，提出了一種基于VP-Tree的剪枝策略，以提高索引速度。

2 相關(guān)工作問題定義和總體解決方案

2.1 問題定義

定義1（Top-k集合空間關(guān)鍵字查詢-TkCoSKQ[2-3，33-35]）給定空間對(duì)象集合D，空間關(guān)鍵字查詢q，包含查詢位置q.l，一組查詢關(guān)鍵字q.w和k值，TkCoSKQ返回top-k組空間對(duì)象和每組對(duì)象的最大綜合距離，最大綜合距離由該方法提出的評(píng)分函數(shù)決定，計(jì)算方法如式（1）所示：

其中，β為調(diào)節(jié)參數(shù)，maxdis(q,o)表示組內(nèi)空間對(duì)象到q的最大距離，maxdis(o1,o2)表示組內(nèi)任意兩個(gè)空間對(duì)象之間的最大距離，cost(s)是候選對(duì)象組合s的最大綜合距離。

定義2（Top-kCSKAQ）給定空間對(duì)象集合D，用戶歷史訪問記錄R，空間關(guān)鍵字查詢q，包含查詢位置q.l，一組查詢關(guān)鍵字q.w和k值，Top-kCSKAQ返回綜合距離最小的top-k組空間對(duì)象，綜合距離由評(píng)分函數(shù)決定。

定義3（關(guān)聯(lián)訪問度）給定空間對(duì)象集合D和用戶歷史訪問記錄R，D中的某組對(duì)象經(jīng)常被用戶共同訪問的次數(shù)越高，則該組對(duì)象的關(guān)聯(lián)訪問度越高。

定義4（評(píng)分函數(shù)）給定一組空間對(duì)象，其綜合距離評(píng)分函數(shù)包含距離和關(guān)聯(lián)訪問度兩個(gè)部分，計(jì)算方法如式（2）所示：

其中，h是候選空間對(duì)象組合；α為調(diào)節(jié)參數(shù)，用于平衡距離和關(guān)聯(lián)訪問度在評(píng)分函數(shù)中的作用；maxdis(p1,p2)是空間對(duì)象數(shù)據(jù)集中任意兩個(gè)對(duì)象之間的最大歐式距離，GL是該組空間對(duì)象之間的關(guān)聯(lián)訪問度，maxdis(q,c)表示組內(nèi)空間對(duì)象到q的最大歐式距離，maxdis(o1,o2)表示組內(nèi)任意兩個(gè)空間對(duì)象之間的最大歐式距離。maxdis(q,c)+maxdis(o1,o2)表示評(píng)分函數(shù)中的距離部分，記作距離分?jǐn)?shù)，并對(duì)其進(jìn)行歸一化處理。β是調(diào)節(jié)參數(shù)，用于平衡組內(nèi)空間對(duì)象到q的最大歐式距離和組內(nèi)任意兩個(gè)空間對(duì)象之間的最大歐式距離在距離分?jǐn)?shù)中的作用，本文只考慮β=0.5的情況。

定義5（局部鄰域）對(duì)于給定空間對(duì)象集合D及其子集Z，Z?D以及鄰域閾值σ，Z的σ-局部鄰域定義為：

該集合由D中包含的對(duì)象與Z中至少一個(gè)對(duì)象的距離不超過閾值σ的對(duì)象構(gòu)成。

2.2 解決方案

本文的總體解決方案如圖2所示，共分3步。

圖2 解決方案總體框架圖Fig.2 Overall solution framework

步驟1數(shù)據(jù)處理。給定查詢條件，包含查詢位置和一組查詢關(guān)鍵字，刪除不包含任何查詢關(guān)鍵字的空間對(duì)象，將剩余的空間對(duì)象記作相關(guān)空間對(duì)象，根據(jù)到查詢點(diǎn)的歐式距離對(duì)其進(jìn)行升序排序。

步驟2剪枝。循環(huán)選取相關(guān)空間對(duì)象，利用VPTree加速搜索每次選取的空間對(duì)象的局部鄰域，修剪數(shù)據(jù)集中的空間對(duì)象，只保留鄰域內(nèi)的空間對(duì)象，并將每次選取的空間對(duì)象之前的對(duì)象取出與局部鄰域做交集，然后對(duì)交集內(nèi)的空間對(duì)象進(jìn)行組合。

步驟3計(jì)算空間對(duì)象組合的得分，返回top-k組結(jié)果。該步驟分為在線和離線處理兩個(gè)階段，離線處理階段利用Apriori算法對(duì)空間對(duì)象進(jìn)行關(guān)聯(lián)分析，計(jì)算空間對(duì)象之間的關(guān)聯(lián)訪問度。在線處理階段將能夠覆蓋所有查詢關(guān)鍵字的空間對(duì)象組合作為候選組合，并根據(jù)評(píng)分函數(shù)計(jì)算其得分，將得分最?。淳C合距離最?。┑那発個(gè)候選組合作為最終的top-k組結(jié)果。

3 Top-k組查詢結(jié)果的精確選取算法

本章主要闡述如何對(duì)空間對(duì)象之間的關(guān)聯(lián)訪問度進(jìn)行評(píng)估，提出一種top-k組結(jié)果的精確選取算法，并給出精確選取算法的實(shí)現(xiàn)過程。

3.1 空間對(duì)象之間的關(guān)聯(lián)訪問度評(píng)估

Apriori算法使用逐層搜索的迭代方法，其中k項(xiàng)集用于探索(k+1)項(xiàng)集。首先，通過掃描數(shù)據(jù)庫，求出每個(gè)項(xiàng)的計(jì)數(shù)，得到滿足最小支持度的項(xiàng)，找出頻繁1項(xiàng)集的集合，記為L1。然后，使用L1找出頻繁2項(xiàng)集的集合L2，使用L2找出L3，以此類推，直到不能再找到頻繁k項(xiàng)集。在該過程中使用頻繁項(xiàng)集的先驗(yàn)性質(zhì)來壓縮搜索空間，即頻繁項(xiàng)集的所有非空子集也一定是頻繁的。找出滿足最小支持度的項(xiàng)集后，可通過計(jì)算得到滿足最小置信度的強(qiáng)關(guān)聯(lián)規(guī)則，最小置信度和最小支持度可以根據(jù)需求設(shè)置。給定空間對(duì)象集合D和用戶對(duì)空間對(duì)象的歷史訪問記錄R，Apriori算法可以從大量的用戶歷史訪問記錄中發(fā)現(xiàn)空間對(duì)象之間潛在的關(guān)聯(lián)。

本文引言部分的圖1、表1和表2分別給出空間對(duì)象和用戶歷史訪問記錄。假設(shè)對(duì)O2，O6進(jìn)行關(guān)聯(lián)度分析，O6的支持度為1/4；O2的支持度為1/2；O2∩O6的支持度為1/8；關(guān)聯(lián)度為GL(O6|O2)=1/8/1/2=0.25，這表明訪問過O2的用戶中有25%的用戶會(huì)訪問O6。算法1給出了利用Apriori算法對(duì)空間對(duì)象進(jìn)行關(guān)聯(lián)訪問度分析的執(zhí)行過程。

算法1基于Apriori的空間對(duì)象關(guān)聯(lián)訪問度分析算法

Apriori算法首先掃描一遍數(shù)據(jù)集，從中生成一項(xiàng)集C1，然后掃描C1，過濾不滿足最小支持度的項(xiàng)集，得到頻繁1項(xiàng)集L1（第1行）。根據(jù)Apriori原理，非頻繁項(xiàng)集的所有超集也都是非頻繁的，因此，第二輪迭代中，只需要對(duì)上一輪迭代產(chǎn)生的頻繁項(xiàng)集進(jìn)行新的組合即可。然后，檢查新的組合是否滿足最小支持度要求，將不滿足的新組合給過濾，直到?jīng)]有新組合可生成為止（第2～18行）。調(diào)用aprioriGen函數(shù)，通過頻繁項(xiàng)集Lk-1生成無重復(fù)項(xiàng)集Ck（即項(xiàng)數(shù)為k的項(xiàng)集）（第3行）。接下來，迭代掃描R并進(jìn)行候選計(jì)數(shù)（第4～9行），過濾掉不滿足條件的組合，返回項(xiàng)集中不小于最小支持度的項(xiàng)集作為頻繁k項(xiàng)集Lk（項(xiàng)數(shù)為k的頻繁項(xiàng)集）（第10行），集合L包含所有頻繁項(xiàng)集（第12行）。最后，循環(huán)選取L中的每一個(gè)頻繁項(xiàng)集，為其計(jì)算置信度conf（第14行），并判斷conf是否不小于最小置信度minConf，如果conf≥minConf，將該項(xiàng)集作為一個(gè)關(guān)聯(lián)分析結(jié)果，加入到關(guān)聯(lián)規(guī)則集合RL中（第15～17行）。重復(fù)執(zhí)行上述過程，直到所有頻繁項(xiàng)集都被訪問過為止，返回關(guān)聯(lián)規(guī)則RL（第19行）。

3.2 Top-k組結(jié)果精確選取算法（簡稱CSKAQ-E）

在本節(jié)中，提出一種準(zhǔn)確選取算法，記作CSKAQE，查找覆蓋所有查詢關(guān)鍵字的空間對(duì)象組合，根據(jù)評(píng)分函數(shù)計(jì)算每個(gè)候選組合的綜合距離得分，并選擇得分最低的top-k組對(duì)象作為查詢結(jié)果。CSKAQ-E算法的執(zhí)行過程如圖3所示。

圖3 CSKAQ-E執(zhí)行過程Fig.3 CSKAQ-E execution process

CSKAQ-E算法首先刪除空間對(duì)象集合D中不包含任何查詢關(guān)鍵字的對(duì)象，只保留與查詢關(guān)鍵字相關(guān)的對(duì)象作為相關(guān)空間對(duì)象集合RO；根據(jù)到查詢q的距離對(duì)RO中的對(duì)象進(jìn)行升序排序（第1行）。以順序循環(huán)方式逐個(gè)選取RO中空間對(duì)象，被選取的對(duì)象記為c（第3行），然后將與查詢q的距離小于c到q的距離的空間對(duì)象加入集合S1（第7行），這種情況下，c到q的距離則為組內(nèi)空間對(duì)象到查詢q的最大距離。在此基礎(chǔ)上，將S1中的對(duì)象進(jìn)行組合(o1,o2)（第8行），并將這些組合根據(jù)距離進(jìn)行升序排序。接下來，根據(jù)組合排序結(jié)果順序循環(huán)選取組合，每次選取一對(duì)組合，記為x={c,o1,o2}（第10行），若x能夠覆蓋所有查詢關(guān)鍵字，則將該空間對(duì)象組合視為候選空間對(duì)象組合h，并利用式（2）計(jì)算h的得分score(h)（第11～18行）。最后，檢查結(jié)果集J的大小是否小于k，當(dāng)結(jié)果集中的空間對(duì)象組合的數(shù)量小于k時(shí)，直接將h加入到結(jié)果集J中，得到J中組合的最大得分Jmaxc（第19～23行）；當(dāng)結(jié)果集數(shù)量為k，并且候選組合得分小于Jmaxc時(shí)，將該組合插入到J中，并將J中得分最大的組合刪除，更新Jmaxc（第24～26行），直到所有的組合都被訪問過為止。重復(fù)上述過程，直到結(jié)果集|J|＞k，并且選取的空間對(duì)象到查詢點(diǎn)的距離大于Jmaxc，停止迭代，輸出結(jié)果集J。

算法2 Top-k組結(jié)果精確選取算法CSKAQ-E

例2利用表1、表2和圖1中的信息，給定查詢位置〈5，4〉、查詢關(guān)鍵字為“Shopping，Restaurant，Hotel”。根據(jù)上述查詢條件，首先刪除表1所示空間對(duì)象集合中的不相關(guān)對(duì)象O1，得到相關(guān)對(duì)象集合RO，并對(duì)其進(jìn)行升序排序，排序結(jié)果為：RO={O2,O8,O7,O3,O5,O4,O6}。CSKAQ-E算法獲得top-3結(jié)果的處理過程分析如下：

首先，根據(jù)上述RO中的排序結(jié)果，以順序循環(huán)選取方式，每次從RO中選取一個(gè)空間對(duì)象，記作c。第一次選取O2，即c=O2，然后從RO中計(jì)算與查詢q的距離小于c到q的距離的空間對(duì)象集合S1，S1={O2}，但此時(shí)沒有與之組合的空間對(duì)象。第二次選取，c=O8，得到S1={O8,O2}，將S1中保護(hù)的空間對(duì)象進(jìn)行組合，可以得到(o1,o2)=(O8,O2)。算法CSKAQ-E第10行需得到空間對(duì)象組合x={c,o1,o2}，但此時(shí)x={O8,O2}，可判斷出x包含的對(duì)象不能覆蓋所有查詢關(guān)鍵字，因此沒有候選對(duì)象組合。同理，當(dāng)c=O7時(shí)，所產(chǎn)生的空間對(duì)象組合也不能覆蓋所有查詢關(guān)鍵字，也沒有候選空間對(duì)象組合。c=O3時(shí)，S1={O2,O8,O7,O3}，其中的對(duì)象形成的組合包括(o1,o2)={(O3,O7),(O8,O2),(O3,O8),(O7,O8),(O7,O2),(O3,O2)}，此時(shí)，所有空間對(duì)象組合為x={{O3,O7},{O3,O8,O2},{O3,O8},{O3,O7,O8}，{O3,O7,O2},{O3,O2}}，由此可見，空間對(duì)象組合{O3,O8,O2},{O3,O7,O8}能夠覆蓋查詢關(guān)鍵字，因此將這兩組對(duì)象作為候選對(duì)象組合h，即h={{O3,O8,O2},{O3,O7,O8}}。

接下來，根據(jù)式（2）的評(píng)價(jià)函數(shù)計(jì)算候選對(duì)象組合的排序得分，其中候選空間對(duì)象組合h內(nèi)空間對(duì)象之間的關(guān)聯(lián)訪問度是由Apriori算法獲得的關(guān)聯(lián)規(guī)則RL得到，score({O3,O8,O2})=0.849,score({O3,O7,O8})=0.933。結(jié)果集J中的空間對(duì)象組合的數(shù)量小于3，直接將{O3,O8,O2}加入J，更新Jmaxc=0.849。然后，將{O3,O7,O8}加入到結(jié)果集J中，并更新Jmaxc=0.933。當(dāng)結(jié)果集數(shù)量為3，并且候選組合得分小于Jmaxc時(shí)，將該組合插入到J中，并將J中得分最大的組合刪除，更新Jmaxc，直到所有的候選組合都被訪問過。重復(fù)上述過程，直到結(jié)果集|J|＞k，并且選取的空間對(duì)象到查詢點(diǎn)的距離大于Jmaxc。將J中空間對(duì)象組合根據(jù)得分升序排序，最終CSKAQ-E算法得到的top-3結(jié)果為{{O4,O7,O3},{O6,O8,O2},{O3,O8,O2}}。

3.3 時(shí)間復(fù)雜度分析

CSKAQ-E方法的時(shí)間復(fù)雜度為O(ms(|q.w||RO|+|h|+k))

分析：算法2中首先假設(shè)對(duì)RO中空間對(duì)象進(jìn)行的迭代次數(shù)為m(m≤|RO|)，對(duì)S1內(nèi)空間對(duì)象進(jìn)行任意組合，得到組合(o1,o2)，假設(shè)S1內(nèi)的(o1,o2)組合個(gè)數(shù)記作s。然后，判斷空間對(duì)象組合x是否能覆蓋所有查詢關(guān)鍵字q.w的時(shí)間復(fù)雜度是O(|q.w||RO|)，其中|q.w|代表查詢關(guān)鍵字個(gè)數(shù)。接下來，計(jì)算候選空間對(duì)象組合h的得分score(h),需從關(guān)聯(lián)規(guī)則RL中查找h內(nèi)空間對(duì)象的關(guān)聯(lián)訪問度，查找h中所有組合的關(guān)聯(lián)訪問度的時(shí)間復(fù)雜度為O(|h|)，|h|代表集合h中的空間對(duì)象組合個(gè)數(shù)。最后，再將候選空間對(duì)象組合插入到J中，并將J中得分最大的組合刪除，更新Jmaxc的時(shí)間復(fù)雜度為O(k)，k表示指定的結(jié)果個(gè)數(shù)。綜上，CSKAQ-E算法的時(shí)間復(fù)雜度為O(ms(|q.w||RO|+|h|+k))。

需要指出的是，由于這種方法需要將所有包含查詢關(guān)鍵字的空間對(duì)象互相組合，并且計(jì)算所有候選組合的得分，算法復(fù)雜度高，計(jì)算量大，查詢效率較低。因此，需要設(shè)計(jì)一種近似查詢匹配方法，在確保準(zhǔn)確性的情況下提高執(zhí)行效率。

4 Top-k組查詢結(jié)果的近似選取算法

本章提出一種基于VP-tree的剪枝策略，在此基礎(chǔ)上提出一種top-k近似查詢匹配算法。

4.1 VP-Tree結(jié)構(gòu)

VP-Tree[36]是一種二元空間劃分樹，其基本思想是選取某個(gè)空間對(duì)象作為制高點(diǎn)，然后計(jì)算其他對(duì)象到制高點(diǎn)的距離，并根據(jù)距離對(duì)空間對(duì)象數(shù)據(jù)集進(jìn)行劃分。利用VP-Tree可快速進(jìn)行給定空間對(duì)象的近鄰查詢和范圍查詢。

對(duì)于給定的相關(guān)空間對(duì)象集合RO，VP-Tree從根節(jié)點(diǎn)以自頂向下方式構(gòu)建，構(gòu)建時(shí)需選取制高點(diǎn)，指定一個(gè)距離函數(shù)和一個(gè)閾值。首先根據(jù)文獻(xiàn)[36]的思想，在RO中隨機(jī)抽樣選取一組對(duì)象作為候選制高點(diǎn)，利用剩下的對(duì)象對(duì)其進(jìn)行評(píng)估，最終選取能夠構(gòu)建出高度平衡的VP-Tree的對(duì)象作為制高點(diǎn)。然后以該制高點(diǎn)作為依據(jù)，將數(shù)據(jù)集中與制高點(diǎn)的歐式距離不高于給定閾值的對(duì)象劃分到左子樹，與制高點(diǎn)的歐式距離高于給定閾值的對(duì)象劃分到右子樹。左右子樹以遞歸方式再進(jìn)行劃分，直到節(jié)點(diǎn)僅包含一個(gè)對(duì)象（即葉子節(jié)點(diǎn)）。VPTree的構(gòu)造時(shí)間復(fù)雜度是O(|RO|lg|RO|)。

圖4給出了構(gòu)建VP-Tree的實(shí)例。假設(shè)選取點(diǎn)＜5，6＞為制高點(diǎn)，分別計(jì)算其余四個(gè)對(duì)象到制高點(diǎn)的歐式距離，將距離制高點(diǎn)小于給定閾值（設(shè)為4）的對(duì)象劃分到左子樹。

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

4.2 局部鄰域搜索

給定鄰域閾值σ，對(duì)于空間對(duì)象數(shù)據(jù)集中的任一對(duì)象r∈RO，根據(jù)式（3）計(jì)算可得到{r}的σ-局部鄰域L({r},D,σ)，但為每個(gè)空間對(duì)象都計(jì)算其σ-局部鄰域耗時(shí)較長，因此為了提高空間對(duì)象的σ-局部鄰域搜索的效率，本文使用VP-Tree加速對(duì)空間對(duì)象的σ-局部鄰域搜索。

給定相關(guān)空間對(duì)象集合RO中一個(gè)對(duì)象，利用VP-Tree搜索該對(duì)象的σ-局部鄰域的過程為：自頂向下比較VP-Tree中各節(jié)點(diǎn)與給定對(duì)象之間的歐式距離，如果VP-Tree中某個(gè)中間節(jié)點(diǎn)在該對(duì)象的σ-局部鄰域中，那么該節(jié)點(diǎn)的所有后繼對(duì)象都在該對(duì)象的局部鄰域當(dāng)中。理想情況下，VP-tree搜索的時(shí)間復(fù)雜度是O(lg|RO|)。由此可見，利用VP-Tree，可以快速得到與給定空間對(duì)象位置接近的其他空間對(duì)象，從而為快速獲取top-k組對(duì)象提供了支持。

4.3 Top-k組結(jié)果近似選取算法（簡稱CSKAQ-A）

本節(jié)提出一種基于剪枝策略的CSKAQ-A方法，該方法通過VP-Tree需要搜索每個(gè)空間對(duì)象的局部鄰域，修剪空間對(duì)象，進(jìn)而只保留鄰域內(nèi)的空間對(duì)象，減少組合可能性和計(jì)算量，最后選擇綜合距離最低的top-k組作為近似查詢結(jié)果。CSKAQ-A算法的執(zhí)行過程如圖5所示。

圖5 CSKAQ-A執(zhí)行過程Fig.5 CSKAQ-A execution process

CSKAQ-A算法首先刪除空間對(duì)象集合D中不包含任何查詢關(guān)鍵字的空間對(duì)象，只保留與查詢關(guān)鍵字相關(guān)的空間對(duì)象作為相關(guān)空間對(duì)象集合RO；根據(jù)到查詢q的距離對(duì)RO中的空間對(duì)象進(jìn)行升序排序（第1行）。然后，對(duì)J、h、x、Jmaxc等進(jìn)行初始化，并將相關(guān)空間對(duì)象集合RO構(gòu)建成VP-Tree（第2行）。接下來，將與查詢q的距離小于c到q的距離的空間對(duì)象加入集合S1（第7行），并利用VP-Tree對(duì)每次選取的對(duì)象c進(jìn)行局部鄰域搜索，得到c的σ-局部鄰域集合S2（第8行），在此基礎(chǔ)上計(jì)算S1∩S2=M，并對(duì)M進(jìn)行升序排序（第9～10行），這種情況下，c到q的距離則為組內(nèi)空間對(duì)象到查詢q的最大距離，該策略可以避免重復(fù)計(jì)算。然后，對(duì)M內(nèi)空間對(duì)象進(jìn)行任意組合，得到組合(o1,o2)，后續(xù)步驟與CSKAQ-E方法相同。

算法3 Top-k組對(duì)象近似選取算法CSKAQ-A

利用S1∩S2=M，減少組合可能性和計(jì)算量，可以避免重復(fù)計(jì)算。

分析：c的σ-局部鄰域是L({c},RO,σ)，近似算法CSKAQ-A僅保留距離c較近的空間對(duì)象，可減少可組合的空間對(duì)象數(shù)量，進(jìn)而減少計(jì)算量。假設(shè)c1是c的σ-局部鄰域L({c},RO,σ)內(nèi)的空間對(duì)象，利用VP-Tree搜索c1的σ-局部鄰域集合L({c1},RO,σ)。將L({c},RO,σ)內(nèi)的空間對(duì)象進(jìn)行任意組合，再循環(huán)選取組合，將其與c共同形成空間對(duì)象組合，此時(shí)c和c1將進(jìn)行一次組合。當(dāng)循環(huán)選取相關(guān)空間對(duì)象到c的局部鄰域內(nèi)的對(duì)象c1時(shí)，L({c1},RO,σ)內(nèi)將包含c，然后將c1與其鄰域內(nèi)的任意對(duì)象的組合形成空間對(duì)象組合，此時(shí)c和c1將可能出現(xiàn)重復(fù)組合。通過計(jì)算S1∩S2=M可以避免該情況，因?yàn)楦鶕?jù)S1集合的特性，S1集合包含到q的距離小于c到q的距離的空間對(duì)象，L({c},RO,σ)內(nèi)的對(duì)象c1到q的距離若大于c到q的距離，則它不會(huì)出現(xiàn)在c的M集合中，并且當(dāng)循環(huán)選取到c的局部鄰域內(nèi)空間對(duì)象c1時(shí)，c則會(huì)出現(xiàn)在c1的M集合中，此時(shí)c與其局部鄰域內(nèi)的對(duì)象只需要組合和計(jì)算一次，可避免重復(fù)計(jì)算。

例3利用表1、表2和圖1中的信息，給定查詢位置〈5，4〉、查詢關(guān)鍵字為“Shopping，Restaurant，Hotel”。根據(jù)上述查詢條件，首先刪除表1所示空間對(duì)象集合中的不相關(guān)對(duì)象O1，得到相關(guān)對(duì)象集合RO，并對(duì)其進(jìn)行升序排序，排序結(jié)果為RO={O2,O8,O7,O3,O5,O4,O6}。CSKAQ-A算法獲得top-3結(jié)果的處理過程分析如下：

對(duì)于得到的相關(guān)對(duì)象集合RO={O2,O8,O7,O3,O5,O4,O6}，CSKAQ-A算法先將RO中的空間對(duì)象構(gòu)建成VP-Tree，然后根據(jù)順序循環(huán)方式，每次選取RO中的一個(gè)空間對(duì)象，記作c。與CSKAQ-E算法相比，CSKAQ-A算法除了獲取與q的距離小于c到q的距離的空間對(duì)象集合S1，還利用VP-Tree加速c的σ-局部鄰域搜索，得到c的σ-局部鄰域集合S2，并做S1∩S2=M操作，在此基礎(chǔ)上對(duì)M內(nèi)的空間對(duì)象進(jìn)行組合，也就是組合(o1,o2)從集合M中獲得，該策略能夠使得距離c較遠(yuǎn)的空間對(duì)象被剪枝，進(jìn)而|(o1,o2)|的數(shù)量大大減少。

根據(jù)前述討論，c=O2、O8、O7的情況下沒有產(chǎn)生候選對(duì)象組合。當(dāng)c=O3時(shí)，S1={O2,O8,O7,O3}，利用VP-tree可獲得c的σ-局部鄰域?yàn)镾2={O8,O7,O3}，S1∩S2=M={O8,O7,O3}，此時(shí)可能的組合有(o1,o2)={(O3,O7),(O3,O8),(O7,O8)}，即空間對(duì)象組合為x={{O3,O7},{O3,O8},{O3,O7,O8}}，據(jù)此可判斷{O3,O7,O8}能夠覆蓋查詢關(guān)鍵字，因此將其作為候選對(duì)象組合h，即，h={{O3,O7,O8}}，score({O3,O7,O8})=0.933。結(jié)果集J中的空間對(duì)象組合的數(shù)量小于3，將{O3,O7,O8}直接加入結(jié)果集J中，并更新Jmaxc=0.933；當(dāng)結(jié)果集數(shù)量為3，并且候選組合得分小于Jmaxc時(shí)，將該組合插入到J中，并將J中得分最大的組合刪除，更新Jmaxc，直到所有的候選組合都被訪問過（該過程與CSKAQ-E算法相同）。重復(fù)上述過程，直到結(jié)果集|J|＞k，并且選取的空間對(duì)象到查詢點(diǎn)的距離大于Jmaxc。將J中空間對(duì)象組合根據(jù)得分升序排序，最終CSKAQ-A算法得到的top-3結(jié)果為{{O6,O8,O2},{O3,O7,O8},{O4,O7,O5}}。

4.4 時(shí)間復(fù)雜度分析

CSKAQ-A方法的時(shí)間復(fù)雜度為O(|RO|lg|RO|+m(lg|RO|+|S1||S2|+ss(|q.w||RO|+|h|+k)))

分析：算法3首先對(duì)相關(guān)空間對(duì)象集合RO構(gòu)建VP-Tree的時(shí)間復(fù)雜度為O(|RO|lg|RO|)，然后利用VPTree對(duì)選取的對(duì)象c進(jìn)行局部鄰域搜索，獲得集合S2的時(shí)間復(fù)雜度為O(lg|RO|)，S1∩S2=M的時(shí)間復(fù)雜度為O(|S1||S2|)。然后對(duì)M內(nèi)空間對(duì)象進(jìn)行任意組合，得到組合(o1,o2)，令(o1,o2)組合個(gè)數(shù)記作ss。接下來，判斷空間對(duì)象組合x是否能覆蓋所有查詢關(guān)鍵字q.w的時(shí)間復(fù)雜度是O(|q.w||RO|)。計(jì)算候選空間對(duì)象組合h的得分score(h)，需從關(guān)聯(lián)規(guī)則RL中查找h內(nèi)空間對(duì)象關(guān)聯(lián)訪問度，查找h中所有組合的關(guān)聯(lián)訪問度的時(shí)間復(fù)雜度為O(|h|)，|h|代表集合h中的空間對(duì)象組合個(gè)數(shù)。最后，再將該組合插入到J中，并將J中得分最大的組合刪除，更新Jmaxc的更新階段時(shí)間復(fù)雜度為O(k)，k表示指定的結(jié)果個(gè)數(shù)。綜上，CSKAQ-A算法的時(shí)間復(fù)雜度為O(|RO|lg|RO|+m(lg|RO|+|S1||S2|+ss(|q.w||RO|+|h|+k)))，其中m為對(duì)RO中空間對(duì)象進(jìn)行的迭代次數(shù)(m≤|RO|)。

綜上可見，相比于CSKAQ-E算法，CSKAQ-A算法中|(o1,o2)|,|x|,|h|數(shù)量均減少，因此計(jì)算量減小，查詢速度加快。

5 實(shí)驗(yàn)

5.1 數(shù)據(jù)和實(shí)驗(yàn)設(shè)置

5.1.1 數(shù)據(jù)

實(shí)驗(yàn)測試數(shù)據(jù)采用Yelp數(shù)據(jù)集，Yelp包含了20 290個(gè)空間對(duì)象，74 773條用戶評(píng)論，每個(gè)空間對(duì)象都包含ID、名稱、經(jīng)緯度和類別等屬性，每條評(píng)論數(shù)據(jù)集都包含用戶ID、空間對(duì)象ID和評(píng)論內(nèi)容。

5.1.2 參數(shù)設(shè)置

表3給出了本文算法的參數(shù)默認(rèn)值。在實(shí)驗(yàn)過程中，通過改變一個(gè)參數(shù)的值、固定其他參數(shù)的值來討論該參數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響。所有實(shí)驗(yàn)都采用Java實(shí)現(xiàn)，電腦配置為主頻3.7 GHz的CPU，32.0 GB內(nèi)存，Windows10操作系統(tǒng)。

表3 參數(shù)的默認(rèn)值Table 3 Default values for parameters

5.1.3 算法對(duì)比

將本文提出的精確選取方法（CSKAQ-E）和近似選取方法（CSKAQ-A）分別與文獻(xiàn)[30]提出的TkCoSKQ方法中的RC算法（記作TkCoSKQ-RC）和最新的相關(guān)研究工作文獻(xiàn)[4]提出的CKPQ中的RKD-Search算法（記作CKPQ-RKD-Search）進(jìn)行對(duì)比。

TkCoSKQ-RC的基本思想是，選取候選組合時(shí)，對(duì)任意空間對(duì)象的組合，計(jì)算其歐式距離并設(shè)置上下邊界條件，修剪不滿足條件的組合，減少組合的可能性和計(jì)算量。最后將滿足所有查詢關(guān)鍵字的候選組合，根據(jù)評(píng)分函數(shù)計(jì)算其得分，返回得分（即綜合距離）最小的top-k組結(jié)果。需要指出的是，在選取組對(duì)象時(shí)，該算法只考慮空間對(duì)象與查詢位置之間的距離關(guān)系而沒有考慮組內(nèi)對(duì)象之間的關(guān)聯(lián)訪問度。

CKPQ-RKD-Search的基本思想是，針對(duì)每個(gè)查詢關(guān)鍵字，都從查詢區(qū)域中找到一個(gè)包含該查詢關(guān)鍵字同時(shí)最接近查詢位置的一個(gè)空間對(duì)象，然后將查找到的所有空間對(duì)象進(jìn)行組合，根據(jù)評(píng)分函數(shù)計(jì)算該組合的綜合得分。評(píng)分函數(shù)綜合考慮了用戶對(duì)空間對(duì)象的偏好程度、組內(nèi)空間對(duì)象之間的最大距離、組內(nèi)空間對(duì)象到查詢位置的最大距離以及組內(nèi)對(duì)象的可達(dá)性。

5.1.4 評(píng)價(jià)標(biāo)準(zhǔn)

本文設(shè)置5組空間關(guān)鍵字查詢條件，針對(duì)每個(gè)查詢條件，每個(gè)算法獲取top-10組查詢結(jié)果，進(jìn)而每個(gè)算法最終得到50組查詢結(jié)果，對(duì)每個(gè)算法獲得的50組查詢結(jié)果取平均測量結(jié)果。本文使用近似比[3，30]衡量查詢效果，近似比的計(jì)算方法如下：

其中，AVG(distance)表示CSKAQ-E、CSKAQ-A和CKPQRKD-Search方法獲得的距離分?jǐn)?shù)的平均值；AVG(Cost)表示TkCoSKQ-RC獲得的平均綜合距離。近似比的結(jié)果等于或小于1，說明結(jié)果越好。

5.2 實(shí)驗(yàn)結(jié)果分析

本節(jié)主要研究在相同數(shù)據(jù)集上，表3中各參數(shù)分別對(duì)CKPQ-RKD-Search、TkCoSKQ-RC、CSKAQ-E和CSKAQ-A在查詢效果和查詢效率上的評(píng)估。

（1）結(jié)果集個(gè)數(shù)k值變化對(duì)查詢效果和響應(yīng)時(shí)間影響

將k的值分別設(shè)置為2～10。圖6（a）顯示了不同k值下各算法的查詢響應(yīng)時(shí)間。CSKAQ-E方法需要獲取候選組合內(nèi)空間對(duì)象之間的關(guān)聯(lián)訪問度，所以查詢響應(yīng)時(shí)間略大于TkCoSKQ-RC方法。CKPQ-RKD-Search方法在遍歷索引結(jié)構(gòu)時(shí)采用了剪枝策略，所以其查詢響應(yīng)時(shí)間要小于TkCoSKQ-RC和CSKAQ-E方法。CSKAQA方法每次對(duì)距離所選取的空間對(duì)象較遠(yuǎn)的空間對(duì)象進(jìn)行修剪，減少組合的可能性和計(jì)算量，所以查詢響應(yīng)時(shí)間最短。在k值較小時(shí)，CSKAQ-E、CSKAQ-A以及CKPQ-RKD-Search方法的近似比結(jié)果要略大于1，因?yàn)橄啾萒kCoSKQ-RC，CSKAQ-E和CSKAQ-A方法還考慮了組內(nèi)空間對(duì)象之間的關(guān)聯(lián)訪問度。但隨著k值增大，CSKAQ-A、CSKAQ-E的近似比結(jié)果越來越接近1，甚至CSKAQ-E方法要小于1，說明在所需查詢結(jié)果增多時(shí)，CSKAQ-E方法的性能更好一些，也更符合用戶的需求。CSKAQ-A方法始終略大于1，因?yàn)镃SKAQ-A方法使用了修剪策略，生成的是近似查詢結(jié)果。

圖6 k值變化對(duì)查詢效果和響應(yīng)時(shí)間的影響Fig.6 Effect of k value change on query effect and response time

（2）Keywords數(shù)量變化對(duì)查詢效果和響應(yīng)時(shí)間的影響

通過圖7（a）給出了不同查詢關(guān)鍵字?jǐn)?shù)量情況下不同算法的查詢響應(yīng)時(shí)間變化情況。從圖中可以觀察到，四種方法的查詢響應(yīng)時(shí)間都會(huì)隨著查詢關(guān)鍵詞的數(shù)量增加而增加，并且TkCoSKQ-RC和CSKAQ-E與CSKAQ-A的差距越來越大，因?yàn)椴樵冴P(guān)鍵字越多，需要計(jì)算的空間對(duì)象越多。CKPQ-RKD-Search和CSKAQ-A方法均采用了剪枝策略，因此查詢相應(yīng)時(shí)間較短。CKPQ-RKD-Search查詢響應(yīng)時(shí)間大于CSKAQ-A，是因?yàn)镃KPQ-RKD-Search不僅考慮距離部分，還要計(jì)算用戶偏好程度和組內(nèi)對(duì)象的可達(dá)性；通過圖7（b）還可以觀察到，CSKAQ-A方法的近似比結(jié)果也僅略大于1，這說明本文近似方法在確保選取結(jié)果準(zhǔn)確率的情況下，同時(shí)具有較高的執(zhí)行效率。CSKAQ-E方法的距離分?jǐn)?shù)要小于TkCoSKQ-RC，因?yàn)镃SKAQ-E不僅考慮距離上的得分，還考慮組內(nèi)空間對(duì)象的關(guān)聯(lián)訪問度，同時(shí)，TkCoSKQRC在考慮組合的上下邊界條件時(shí)，一些較好的組合結(jié)果可能被剪枝掉。CSKAQ-A和CKPQ-RKD-Search方法近似比結(jié)果略大于1，因?yàn)樗鼈兙捎昧思糁Σ呗?，生成近似查詢結(jié)果。

圖7 Keywords數(shù)量變化對(duì)查詢效果和響應(yīng)時(shí)間的的影響Fig.7 Effect of change of number of keywords on query effect and response time

（3）|D|值變化對(duì)查詢效果和響應(yīng)時(shí)間的影響

通過圖8可以觀察到，隨著數(shù)據(jù)集增大，四種方法的查詢響應(yīng)時(shí)間都隨之增長，因?yàn)閿?shù)據(jù)集越大，相關(guān)空間對(duì)象越多，計(jì)算量越大。數(shù)據(jù)集較小的情況下，TkCoSKQ-RC方法的查詢響應(yīng)時(shí)間最小，因?yàn)樵摲椒ú恍枰紤]組內(nèi)空間對(duì)象之間的關(guān)聯(lián)訪問度，也不需要構(gòu)建索引結(jié)構(gòu)。但隨著數(shù)據(jù)集的增大，CSKAQ-A方法的查詢響應(yīng)時(shí)間明顯小于CSKAQ-E和TkCoSKQ-RC方法，并且差距也越來越大，同時(shí)也可以觀察到CSKAQ-A方法的查詢響應(yīng)時(shí)間也小于CKPQ-RKD-Search方法。并且，隨著數(shù)據(jù)集的增大，CSKAQ-E方法的近似比小于1，說明該方法的距離分?jǐn)?shù)要小于TkCoSKQ-RC方法，CSKAQ-A方法得到的距離分?jǐn)?shù)也僅略大于TkCoSKQRC。這說明本文提出的近似方法在結(jié)果準(zhǔn)確率較高的情況下，同時(shí)具有較高的執(zhí)行效率。

圖8 數(shù)據(jù)集大小對(duì)查詢效果和響應(yīng)時(shí)間的影響Fig.8 Impact on query efficiceny and response time when dataset size varied

（4）閾值σ取值范圍的影響

通過圖9可以看到，隨著σ的增大，CSKAQ-A方法查詢響應(yīng)時(shí)間越來越大，近似比逐漸減小。原因是隨著σ增大，搜索到的局部鄰域內(nèi)的空間對(duì)象的數(shù)量增多，被剪枝的空間對(duì)象減少，組合的可能性變多，計(jì)算量變大，所以查詢響應(yīng)時(shí)間增大。但隨著σ增大，查詢效果得到了提升，查詢到的結(jié)果更準(zhǔn)確。

圖9 閾值σ的影響Fig.9 Effect of threshold σ

（5）參數(shù)α值的變化對(duì)查詢效果和響應(yīng)時(shí)間的影響

從圖10可以看出，α的變化對(duì)本文所提出的兩種算法的查詢響應(yīng)時(shí)間幾乎沒影響。CSKAQ-A的響應(yīng)時(shí)間明顯小于CSKAQ-E方法，因?yàn)镃SKAQ-A利用VPTree搜索空間對(duì)象的局部鄰域，減少了相關(guān)空間對(duì)象，組合的可能性變少，計(jì)算量減小，查詢響應(yīng)時(shí)間小。通過圖10（b）可以觀察到，隨著α的增大，CSKAQ-E方法的近似比結(jié)果小于1，得到的結(jié)果效果更好。

圖10 參數(shù)α的影響Fig.10 Effect of parameter α value on query effect and response time

為了進(jìn)一步驗(yàn)證本文所提出方法的查詢效果，在50名用戶中進(jìn)行了以下實(shí)驗(yàn)。針對(duì)5組空間關(guān)鍵字查詢條件Q1～Q5，各個(gè)方法均生成top-3結(jié)果。并讓所有測試者對(duì)4個(gè)方法得到的查詢結(jié)果進(jìn)行投票，通過這50名用戶的投票結(jié)果來衡量查詢效果，圖11展示其投票結(jié)果。由圖11可以明顯地觀察出本文所提出的CSKAQ-A方法得到的查詢結(jié)果，最受用戶歡迎。相比其他兩種方法，CSKAQ-E方法更受用戶歡迎，所以本文提出的方法更能讓用戶滿意。

圖11 用戶投票結(jié)果Fig.11 User voting results

6 結(jié)束語

本文提出了一種新的集合空間關(guān)鍵字近似查詢方法，記作Top-kCSKAQ，該方法研究了一種新的空間關(guān)鍵字查詢問題，即空間對(duì)象之間的關(guān)聯(lián)訪問度，并通過Apriori算法對(duì)其進(jìn)行評(píng)估。此外，提出基于VP-Tree的剪枝策略來優(yōu)化解決方案，實(shí)現(xiàn)近似查詢。最后在真實(shí)數(shù)據(jù)集中驗(yàn)證了本文所提出的算法的性能，同時(shí)實(shí)驗(yàn)結(jié)果表明，本文提出的算法不僅考慮是否能夠覆蓋所有查詢關(guān)鍵字和組內(nèi)空間對(duì)象到查詢的距離以及組內(nèi)空間對(duì)象之間的距離，還考慮了組內(nèi)空間對(duì)象的關(guān)聯(lián)訪問度，這樣的查詢結(jié)果更符合用戶的查詢要求，并在一定程度上提高了用戶的體驗(yàn)和滿意度。但是查詢到的一組對(duì)象可能會(huì)重復(fù)出現(xiàn)某個(gè)關(guān)鍵字，忽略了組內(nèi)對(duì)象的多樣性。因此未來工作中，在選取空間對(duì)象進(jìn)行組合時(shí)，應(yīng)該避免選取具有相同關(guān)鍵字的空間對(duì)象作為一組；或在最終選取查詢結(jié)果時(shí)，考慮組內(nèi)空間對(duì)象之間的多樣性對(duì)結(jié)果排序的影響。