黃金亮，李艷紅，盧航

（中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074）

隨著移動(dòng)終端和位置定位技術(shù)的飛速發(fā)展，越來越多的web 對(duì)象具有位置-文本屬性，基于地理位置的服務(wù)（LBS）逐漸成為了日常所需.在LBS 中，用戶可以發(fā)起一個(gè)查詢，檢索k個(gè)與查詢位置最鄰近且與查詢關(guān)鍵字最相關(guān)的興趣點(diǎn).雖然LBS 在近些年得到了迅猛的發(fā)展，但在查詢結(jié)果可用性上尚有欠缺.例如，用戶想查找周邊5 個(gè)“咖啡店”，卻發(fā)現(xiàn)一家“奶茶店”意外地出現(xiàn)在系統(tǒng)返回的查詢結(jié)果集中（稱為why對(duì)象），于是對(duì)查詢結(jié)果產(chǎn)生質(zhì)疑，提出一個(gè)why 問題，并且想知道要如何修改自己的查詢參數(shù)，才能將why對(duì)象從查詢結(jié)果中剔除.若查詢系統(tǒng)能對(duì)用戶提出的why 問題做出合理解釋，并向用戶提供相對(duì)原始查詢而言只有微小修改的精煉查詢，使why對(duì)象被排除在查詢結(jié)果之外，那將大大提高查詢結(jié)果的可信度，從而進(jìn)一步促進(jìn)LBS 的發(fā)展.

傳統(tǒng)的空間關(guān)鍵字查詢（SKQ）旨在查找與查詢關(guān)鍵字最相似、與查詢點(diǎn)的位置最鄰近的若干個(gè)空間文本對(duì)象.為了加快SKQ的查詢速度，研究者們提出了一系列的查詢技術(shù)及算法.文獻(xiàn)［1］中，用R-tree索引空間對(duì)象的位置信息，用倒排文件索引文本信息，但兩者并無直接聯(lián)系，僅是分別通過兩種索引查找候選對(duì)象，然后將查詢結(jié)果進(jìn)行合并.文獻(xiàn)［2-3］中，IR-tree 在R-tree 的基礎(chǔ)上，為每個(gè)結(jié)點(diǎn)關(guān)聯(lián)了一個(gè)倒排文件，提高了搜索效率.文獻(xiàn)［4］提出一種名為IL-Quadtree 的索引結(jié)構(gòu)，該索引結(jié)構(gòu)是由線性四叉樹和倒排文件組合構(gòu)成，為每一個(gè)關(guān)鍵字維護(hù)一個(gè)線性四叉樹用于存儲(chǔ)包含該關(guān)鍵字的所有對(duì)象.此外，文獻(xiàn)［5］對(duì)不同空間關(guān)鍵字查詢索引和查詢處理技術(shù)進(jìn)行了綜述，為SKQ 的進(jìn)一步研究提供指導(dǎo).

查詢結(jié)果的可用性近幾年也成為研究者們關(guān)注的熱點(diǎn).文獻(xiàn)［6］中指出基于內(nèi)容意料之外的查詢結(jié)果分為兩種：1）用戶想要的對(duì)象（why-not）沒有出現(xiàn)在結(jié)果中；2）用戶不想要的對(duì)象（why）出現(xiàn)在查詢結(jié)果中.現(xiàn)有解決why-not問題的方法主要分為三大類，即操作定位、數(shù)據(jù)庫修改和查詢修改.這三類方法中，查詢修改方法是解決交互性why-not問題的一種絕佳方式.文獻(xiàn)［7］使用查詢修改來回答top-k偏好查詢中的why-not 問題.他們的目的是通過最小限度地修改原始查詢使丟失對(duì)象出現(xiàn)在結(jié)果集中，其中采用了一個(gè)度量修改量的懲罰函數(shù).同時(shí)，查詢修改模型已被應(yīng)用于回答不同查詢和數(shù)據(jù)設(shè)置的why-not 問題，如文獻(xiàn)［8-11］.最近，文獻(xiàn)［12-14］對(duì)空間關(guān)鍵字top-k查詢的why-not問題進(jìn)行了研究，這些文獻(xiàn)中均使用查詢修改來回答空間關(guān)鍵字top-k查詢的why-not 問題，分別通過修改用戶的偏好、修改查詢關(guān)鍵字集以及修改查詢方向來回答用戶的why-not 問題.文獻(xiàn)［15］研究了反向top-k查詢中的why-not 與why 問題，其中why 問題部分采用了與解決why-not問題一樣的方法，即查詢修改.

然而，到目前為止，尚無研究者對(duì)空間關(guān)鍵字top-k查詢的why 問題展開研究，也沒有提出相關(guān)研究成果.為此，本文首次定義并研究了空間關(guān)鍵字top-k查詢的why 問題.由于能使why 對(duì)象被排除在查詢結(jié)果集之外的精煉查詢數(shù)量巨大，找出代價(jià)最小的精煉查詢的時(shí)間成本過高.為了加速空間關(guān)鍵字top-k查詢的why 問題處理過程，本文設(shè)計(jì)了一種名為WIR-tree 的混合索引，以在訪問一個(gè)非葉子結(jié)點(diǎn)下的子樹前，先估算此結(jié)點(diǎn)索引的所有對(duì)象與查詢之間的空間距離和文本相似性的上限值，進(jìn)而作相應(yīng)的剪枝操作.此外，還提出了一個(gè)WSKQK 算法，通過編輯距離遞增方式枚舉候選關(guān)鍵字集，并結(jié)合查詢處理提早結(jié)束策略，加速枚舉候選關(guān)鍵字集的整個(gè)過程，以達(dá)到算法效率提升的目的.

1 問題描述

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

用D表示空間中的對(duì)象集合，任意o∈D都有兩個(gè)屬性（o.loc，o.doc），其中o.loc 和o.doc 分別表示對(duì)象的位置和描述對(duì)象的文本信息.一個(gè)空間關(guān)鍵字top-k查詢q=（loc，doc，k，α）包含四個(gè)參數(shù)，其中，q.loc表示查詢位置，q.doc表示查詢關(guān)鍵字集，q.k表示檢索的對(duì)象個(gè)數(shù)，q.α表示用戶的偏好.空間關(guān)鍵字top-k查詢根據(jù)一個(gè)同時(shí)考慮空間距離和文本相似度的得分函數(shù)檢索出k個(gè)得分最高的對(duì)象.為了提高普適性，本文采用一個(gè)較為廣泛使用的得分函數(shù)［12-14］，具體如下：

其中，α表示用戶對(duì)空間距離和文本相似度的相對(duì)偏好.SDist（o，q）表示歸一化后的o.loc與q.loc之間的歐式空間距離，可由D中兩點(diǎn)之間最大距離對(duì)o.loc與q.loc之間的歐式距離進(jìn)行歸一化而獲得.TSim（o，q）表示歸一化后的o.doc和q.doc的文本相似度，可通過信息檢索模型來計(jì)算，本文選擇Jaccard 相似度模型，具體如下：

其中，|o.doc∩q.doc|表示o.doc與q.doc 交集的關(guān)鍵字個(gè)數(shù)，|o.doc∪q.doc|表示o.doc 與q.doc 并集的關(guān)鍵字個(gè)數(shù).通過上述得分函數(shù)計(jì)算對(duì)象的得分，得分越高的對(duì)象其排名越高.對(duì)象o的排名具體如下：

定義1空間關(guān)鍵字top-k查詢.空間關(guān)鍵字top-k查詢返回來自D的k個(gè)對(duì)象的集合RS，其中，?o∈RS（?o′∈D-RS，ST（o，q）≥ST′（o′，q））.

1.2 空間關(guān)鍵字top-k查詢的why問題

用戶通常很難找到最能描述其查詢意圖的關(guān)鍵字.因此，確定合適的查詢關(guān)鍵字集可以說是發(fā)起空間關(guān)鍵字top-k查詢的主要挑戰(zhàn).當(dāng)用戶發(fā)起一個(gè)查詢q=（loc，doc0，k0，α）并接收到結(jié)果后，可能會(huì)發(fā)現(xiàn)一個(gè)或多個(gè)非期望的對(duì)象出現(xiàn)在結(jié)果集中（稱為why 對(duì)象）.然后，用戶提出一組why 對(duì)象集W=｛w1，w2，…，wn｝，要求系統(tǒng)返回一個(gè)精煉查詢q′=（loc，doc′，k′，α），以使why 對(duì)象被排除在結(jié)果集之外.通過對(duì)查詢關(guān)鍵字集q.doc0和查詢對(duì)象個(gè)數(shù)q.k0的修改，可能會(huì)產(chǎn)生許多能排除掉why 對(duì)象的合格查詢.為獲得對(duì)原始查詢修改最小的精煉查詢，本文對(duì)文獻(xiàn)［7，15］采用的代價(jià)函數(shù)進(jìn)行微調(diào)整，以量化精煉查詢相對(duì)原始查詢的修改量，具體如下：

其中，三個(gè)偏好系數(shù)β、γ和（1-β-γ）取值范圍均為（0，1），分別表示用戶對(duì)修改q.doc0、修改q.k0和失準(zhǔn)度（后續(xù)將給出失準(zhǔn)度的說明）的偏好.對(duì)于精煉查詢q′，why 對(duì)象的排名q′），查詢個(gè)數(shù)k′=R′（W，q′）-1，k的修改量Δk=|min（0，k′-k0）|，用k0-R（W，q）+1對(duì)Δk進(jìn)行歸一化.為簡單起見，編輯距離僅考慮插入和刪除這兩種編輯操作，查詢關(guān)鍵字修改量Δdoc 為將doc0轉(zhuǎn)化成doc′所需最小編輯操作數(shù).類似地，用將doc0修改為doc′所需的最大編輯操作數(shù)對(duì)Δdoc 進(jìn)行歸一化.除此之外，本文將失準(zhǔn)度ΔcntN作為結(jié)果集對(duì)象變化的度量，ΔcntN具體表示精煉查詢結(jié)果集相對(duì)原始查詢結(jié)果集新加入對(duì)象的個(gè)數(shù)，即ΔcntN=|RS′-RS|，用原始查詢的k0對(duì)其歸一化.

圖1給出原始查詢q和四個(gè)不同對(duì)象的位置、文本信息，其中，q.doc0=｛t1，t2｝，k0=3，α=0.5.表1列出每個(gè)對(duì)象歸一化后的1-SDist（o，q）值、TSim（o，q）值，以及對(duì)象的最終得分ST（o，q）.根據(jù)這些得分值，why對(duì)象w排名第2，它出現(xiàn)在原始結(jié)果集中.表2列出了幾個(gè)精煉查詢的詳細(xì)信息，Δk、Δdoc 和ΔcntN已歸一化.由于精煉查詢的q′.loc 和3 個(gè)偏好系數(shù)與原始查詢保持不變，表中沒有將其列出.本例中，β=0.4，γ=0.3，k0-R（W，q）+1=2，|doc0∪W.doc|=3，由式（4）計(jì)算出精煉查詢的修改代價(jià)，如表2 中Penalty 欄所示，q4的修改代價(jià)最小，所以q4為最優(yōu)的精煉查詢.

表1 四個(gè)空間對(duì)象的得分詳情Tab.1 Score details of the four spatial objects

表2 精練查詢示例Tab.2 An example of refined query

圖1 原始查詢及四個(gè)空間對(duì)象的信息Fig.1 The information of origin query and four spatial objects

定義2空間關(guān)鍵字top-k查詢的why 問題.給定原始空間關(guān)鍵字查詢q=（loc，doc0，k0，α），原始查詢返回的結(jié)果集RS，why 對(duì)象集W.根據(jù)式（4）定義的代價(jià)方程，查詢系統(tǒng)將返回一個(gè)代價(jià)最小、且why對(duì)象均被排除在結(jié)果集RS′之外的精煉查詢q′=（loc，doc′，k′，α）.

2 WIR-tree索引結(jié)構(gòu)

為了有效地處理空間關(guān)鍵字top-k查詢的why問題，本文提出了一種混合索引以同時(shí)估算空間距離和文本相似度，該索引結(jié)構(gòu)支持Jaccard 相似模型.這種索引名為WIR-tree，是IR-tree［3］的一種變體.WIR-tree 的葉子結(jié)點(diǎn)的結(jié)構(gòu)為（o，mbr，pks），其中，o表示空間中的一個(gè)對(duì)象，mbr 表示對(duì)象的最小邊界矩形，pks則表示指向?qū)ο髈的關(guān)鍵字的指針.WIR-tree的非葉子結(jié)點(diǎn)的結(jié)構(gòu)為（pc，mbr，pku，pki），其中，pc表示指向其孩子結(jié)點(diǎn)的指針，mbr表示其子樹的最小邊界矩形，pku 表示指向其索引的所有對(duì)象的關(guān)鍵字并集的指針，pki則表示指向其索引的所有對(duì)象的關(guān)鍵字交集的指針.圖2 為WIR-tree 的示例，非葉子結(jié)點(diǎn)R3，它的并集（交集）為R1和R2下所有對(duì)象的關(guān)鍵字的并集（交集）.

圖2 WIR-tree示例Fig.2 An example of WIR-tree

定理1給定查詢q=（loc，doc，k，α），WIR-tree中的非葉子結(jié)點(diǎn)N，N索引的對(duì)象集合S，記MDist（q.loc，N.MBR）為q.loc 和N.MBR 的最小距離，N∪和N∩分別表示結(jié)點(diǎn)N下的所有對(duì)象的關(guān)鍵字的并集和交集，則下式（5）成立.

證明：由于o被N.MBR 包含，故o.loc 和q.loc 之間的距離一定大于MDist（q.loc，N.MBR），則下式（6）成立，

又因o.doc∈N∪且N∩∈o.doc，得出o.doc∩q.doc∈N∪∩q.doc和N∩∪q.doc ∈o.doc∪q.doc，故下式（7）成立，

結(jié)合得分函數(shù)ST（o，q）=α·（1-SDist（o，q））+（1-α）TSim（o，q），式（5）中不等式右邊的兩項(xiàng)都分別大于得分函數(shù)中的兩項(xiàng).因此，定理1成立.

定理1 能夠利用WIR-tree 來同時(shí)估算空間距離和文本相似性的上界，在訪問非葉子節(jié)點(diǎn)的子樹前，先估算其子樹下所有空間對(duì)象的得分上界，若得分上界小于當(dāng)前排名為k的對(duì)象，則該非葉子結(jié)點(diǎn)及其子樹可安全地剪枝，這有助于搜索出top-k個(gè)最相關(guān)的對(duì)象.

3 WSKQK算法

基于上述WIR-tree，本文提出了WSKQK 算法，具體思路如下：首先，通過原始查詢確定why對(duì)象的排名；接著，通過編輯距離遞增方式，依次枚舉所有可能的查詢關(guān)鍵字集；算法執(zhí)行過程中，始終維護(hù)一個(gè)當(dāng)前最優(yōu)的精煉查詢及其修改代價(jià)，并結(jié)合查詢處理提早結(jié)束策略，加速枚舉候選關(guān)鍵字集的整個(gè)過程.最后，返回一個(gè)代價(jià)最小的精煉查詢.

接下來，需要解決的一個(gè)重要問題是獲取可能的查詢關(guān)鍵字集.由于對(duì)象集D中不同關(guān)鍵字的總數(shù)可能很大，所以可能的查詢關(guān)鍵字集個(gè)數(shù)會(huì)很多.因此為每一組關(guān)鍵字執(zhí)行空間關(guān)鍵字top-k查詢是不現(xiàn)實(shí)的，為此，提出了以下解決方案.

考慮到添加一個(gè)和原始查詢結(jié)果集不相關(guān)的關(guān)鍵字可能會(huì)使非why 對(duì)象也被排除在結(jié)果集之外，同時(shí)會(huì)加入更多新的結(jié)果對(duì)象，因此候選關(guān)鍵字只考慮原始查詢結(jié)果集中存在的關(guān)鍵字.將原始查詢結(jié)果集中所有對(duì)象的關(guān)鍵字劃分為3 個(gè)子集，即SW、Sc和S！W.其中，SW表示僅why 對(duì)象包含而其他結(jié)果對(duì)象不包含的關(guān)鍵字集合，Sc表示why 對(duì)象和其他結(jié)果對(duì)象均包含的關(guān)鍵字集合，S！W表示why對(duì)象不包含而其他結(jié)果對(duì)象包含的關(guān)鍵字集合.為了在最小程度影響原有結(jié)果集的前提下去除why 對(duì)象，候選關(guān)鍵字集可以通過將S！W添加到q.doc0或從q.doc0中刪除SW、Sc而獲得.

3.1 編輯距離遞增方式枚舉關(guān)鍵字集

候選關(guān)鍵字集的枚舉順序?qū)λ惴ǖ男阅芷鸬疥P(guān)鍵性作用.候選關(guān)鍵字集的枚舉過程中，應(yīng)該優(yōu)先考慮更有可能成為最優(yōu)精煉查詢的關(guān)鍵字集，因?yàn)閷?duì)于原始查詢關(guān)鍵字集編輯距離越小的精煉查詢關(guān)鍵字集，其修改代價(jià)越小，因而越有可能成為最優(yōu)精煉查詢的關(guān)鍵字集.首先考慮編輯距離為0的基本精煉查詢q′=（q.loc，q.doc′，k′，α），其中基本精煉查詢的關(guān)鍵字集與原始查詢的關(guān)鍵字集完全相同，即q′.doc′=q.doc，查詢個(gè)數(shù)縮小為q′.k′=R（W，q）-1，由式（4）計(jì)算得出基本精煉查詢的代價(jià)為：

接著根據(jù)編輯距離遞增的原則，依次枚舉編輯距離為n（n=1，2，…，|doc0∪W.doc|）的候選關(guān)鍵字集，具有相同編輯距離的關(guān)鍵字集枚舉順序具體如下：?。脑疾樵冴P(guān)鍵字集中刪除n個(gè)關(guān)鍵字，記為dn（Ew=Sw∩q.doc，Ec=Sc∩q.doc，?dn∈Ew∪Ec）；ⅱ）在原始查詢關(guān)鍵字集基礎(chǔ)上插入n個(gè)關(guān)鍵字，記為in（?in∈S！W）.其中，每個(gè)候選關(guān)鍵字集將通過執(zhí)行一個(gè)空間關(guān)鍵字top-k查詢獲得R′（W，q′）.最后，由式（4）計(jì)算該關(guān)鍵字集對(duì)應(yīng)的精煉查詢的修改代價(jià)，始終維護(hù)當(dāng)前最優(yōu)精煉查詢最小代價(jià)pmin.隨著編輯距離n的遞增，若出現(xiàn)下式情況：

關(guān)鍵字部分的修改代價(jià)已大于pmin，通過代價(jià)公式（4）知，剩余的候選關(guān)鍵字集的修改代價(jià)絕不會(huì)小于pmin，此時(shí)，整個(gè)候選關(guān)鍵字集枚舉過程結(jié)束，pmin為最優(yōu)精練查詢的修改代價(jià).

3.2 候選關(guān)鍵字查詢處理提早結(jié)束策略

對(duì)于精煉查詢q′（loc，doc′，k′，α），若其為最優(yōu)精煉查詢，由式（4）、（8）得：

上式成立則必須滿足Δk′＜Δk，即

因此，在執(zhí)行空間關(guān)鍵字top-k查詢過程中，若why 對(duì)象的排名不滿足式（11），則該候選關(guān)鍵字集的查詢處理過程可提早結(jié)束，且可安全地排除.若當(dāng)前查詢到的最相關(guān)對(duì)象個(gè)數(shù)等于k0時(shí)，why 對(duì)象還未出現(xiàn)，該關(guān)鍵字集的空間關(guān)鍵字top-k查詢處理過程也可提早結(jié)束.取k′=k0，此時(shí)Δk=0，該關(guān)鍵字集對(duì)應(yīng)的精煉查詢代價(jià)最小，p′為式（4）的后兩項(xiàng)關(guān)鍵字修改代價(jià)和失準(zhǔn)度之和，即

算法1 為WSKQK 算法的偽代碼.ⅰ）首先確定why 對(duì)象在原始查詢結(jié)果集中的排名，使用基本精煉查詢初始化最優(yōu)精煉查詢，由式（8）知，此時(shí)的pmin為β（第1～2 行）；ⅱ）然后，根據(jù)候選關(guān)鍵字集枚舉順序，取出下一組關(guān)鍵字ks（第5行），執(zhí)行空間關(guān)鍵字top-k查詢（第10 行），執(zhí)行過程中每查詢到一個(gè)top-k對(duì)象，判斷是否符合提早結(jié)束條件（第20～23行）；ⅲ）若符合，則結(jié)束本輪的空間關(guān)鍵字top-k 查詢，否則確定why 對(duì)象的排名，進(jìn)而計(jì)算其代價(jià)p′，并判斷是否更新當(dāng)前最優(yōu)精煉查詢及pmin（第12-15行）.不斷從候選關(guān)鍵字集中取出下一組關(guān)鍵字，重復(fù)步驟ii）和iii），直至算法結(jié)束條件成立，算法結(jié)束（第6～7行），返回最優(yōu)精煉查詢（第17行）.

4 實(shí)驗(yàn)與分析

以基于SetR-tree 索引結(jié)構(gòu)的BS 算法［13］作為對(duì)照算法，通過一系列對(duì)比實(shí)驗(yàn)來驗(yàn)證本文提出的基于WIR-tree索引的WSKQK算法的性能.

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)設(shè)備及評(píng)估指標(biāo)

所有實(shí)驗(yàn)均在同一臺(tái)PC 上進(jìn)行，PC 的配置為Intel Core i7，2.20 GHz CPU 和8 GB 內(nèi)存.所有算法皆使用Java實(shí)現(xiàn)，運(yùn)行在Windows10操作系統(tǒng)上.本文采用查詢時(shí)間作為算法性能的評(píng)估指標(biāo)，對(duì)每一組實(shí)驗(yàn)，隨機(jī)生成500 個(gè)查詢?nèi)∑淦骄樵儠r(shí)間作為查詢時(shí)間結(jié)果.

4.1.2 數(shù)據(jù)集

實(shí)驗(yàn)選取了EURO和GN兩個(gè)真實(shí)數(shù)據(jù)集，EURO是一個(gè)興趣點(diǎn)數(shù)據(jù)集，興趣點(diǎn)包含ATMs，hotels 和stores.GN 是來自US Board on Geographic Names 提供的公開數(shù)據(jù)集，包含大量的地理對(duì)象.這兩個(gè)數(shù)據(jù)集常用于空間關(guān)鍵字的相關(guān)研究，它們都包含了許多由一個(gè)空間位置和一組關(guān)鍵字表示的對(duì)象，更多詳情信息見表3.

表3 數(shù)據(jù)集詳情Tab.3 Datasets information

4.1.3 參數(shù)

本文通過改變查詢的對(duì)象個(gè)數(shù)k0、why 對(duì)象的排名R（w，q）、用戶對(duì)空間距離與文本相似度的偏好α、代價(jià)函數(shù)的偏好系數(shù)（β，γ）及查詢關(guān)鍵字個(gè)數(shù)來評(píng)估所提方法的性能.這些參數(shù)及其默認(rèn)值（粗體）如表4所示.

表4 參數(shù)設(shè)置Tab.4 Parameters setting

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

（1）k0對(duì)算法性能的影響.選取排名為當(dāng)前k0的一半（即R（o，q）=k0/2）的對(duì)象為why 對(duì)象，以驗(yàn)證不同的k0取值對(duì)算法性能的影響.例如，當(dāng)原始查詢由top-4 變化到top-10 時(shí)，相應(yīng)的why 查詢中，why 對(duì)象相應(yīng)為排名第2 的對(duì)象和排名第5 的對(duì)象.實(shí)驗(yàn)結(jié)果如圖3 所示，由于BS 算法為每一個(gè)候選關(guān)鍵字集執(zhí)行一個(gè)空間關(guān)鍵字top-k查詢，因此，隨k0取值的增長，候選關(guān)鍵字集增大，從而使執(zhí)行空間關(guān)鍵字top-k查詢的時(shí)間增大，故BS算法性能對(duì)k0的變化非常敏感.然而，WSKQK 算法得益于編輯距離遞增方式枚舉關(guān)鍵字集和查詢處理提早結(jié)束策略，它對(duì)k0取值的變化敏感降低.如k0=100 時(shí)，WSKQK 算法的運(yùn)行時(shí)間約為BS算法的1/3.

圖3 k0對(duì)算法性能的影響Fig.3 Impact of k0 on algorithm performance

（2）why對(duì)象排名對(duì)算法性能的影響.由于原始查詢?yōu)榭臻g關(guān)鍵字top-10 查詢，此組實(shí)驗(yàn)發(fā)起了why 對(duì)象的排名分別為1、3、5、7 和9 的5 個(gè)why 查詢，以驗(yàn)證不同的why 對(duì)象排名對(duì)算法性能的影響.實(shí)驗(yàn)結(jié)果如圖4 所示，因其候選關(guān)鍵字集的規(guī)模并未發(fā)生變化，BS 算法的運(yùn)行時(shí)間幾乎不受why 對(duì)象排名變化的影響.而WSKQK 算法的運(yùn)行時(shí)間隨著why 對(duì)象的排名增大而減小.具體的原因是，why 對(duì)象的排名與k0更接近時(shí)，當(dāng)前最優(yōu)精煉查詢的代價(jià)pmin會(huì)更小，算法初始的剪枝能力會(huì)更強(qiáng)，能夠更早地結(jié)束查詢處理過程.

圖4 R（w，q）對(duì)算法性能的影響Fig.4 Impact of R（w，q）on algorithm performance

（3）α對(duì)算法性能的影響.根據(jù)空間關(guān)鍵字topk查詢的得分公式（1）可知，α越小意味著文本相似性的權(quán)重更高，這就降低了空間距離的重要性，因此，基于R-tree及其變體設(shè)計(jì)的索引，其剪枝能力會(huì)降低，可能需要訪問更多的樹結(jié)點(diǎn)以查找到最相關(guān)的k個(gè)對(duì)象.若α越大，則空間近鄰度的權(quán)重越高，從而降低了文本維度的裁剪能力.實(shí)驗(yàn)結(jié)果如圖5所示，正如以上分析，當(dāng)α取中間值時(shí)，BS和WSKQK算法的運(yùn)行時(shí)間都更短.

圖5 α對(duì)算法性能的影響Fig.5 Impact of α on algorithm performance

（4）β和γ對(duì)算法性能的影響.這兩個(gè)參數(shù)為用戶在修改查詢關(guān)鍵字、修改查詢個(gè)數(shù)及失準(zhǔn)度這三者之間的偏好.實(shí)驗(yàn)結(jié)果如圖6 所示，由于β和γ只用于在執(zhí)行空間關(guān)鍵字查詢確定why 對(duì)象的排名后，計(jì)算候選關(guān)鍵字集的代價(jià)，所以β和γ對(duì)BS算法的性能幾乎沒有影響.然而，在WSKQK 算法中，使用基本精煉查詢初始化最優(yōu)精煉查詢，且始終維護(hù)目前最優(yōu)精煉查詢及其代價(jià)，以便盡早結(jié)束查詢處理過程，因而算法性能受β的影響.根據(jù)式（6），基本精煉查詢的代價(jià)為β，較小的β使得初始的pmin較小，這可以提高算法效率，因此，WSKQK 算法的查詢時(shí)間隨著β的增大而增大.

圖6 β和γ對(duì)算法性能的影響Fig.6 Impact of β and γ on algorithm performance

（5）查詢關(guān)鍵字個(gè)數(shù)對(duì)算法性能的影響.關(guān)鍵字的數(shù)量會(huì)在兩個(gè)方面影響到算法的性能：ⅰ）查詢關(guān)鍵字的增多使候選關(guān)鍵字集的規(guī)模增大；ⅱ）關(guān)鍵字?jǐn)?shù)量的增加使計(jì)算對(duì)象文本與查詢關(guān)鍵字的文本相似度所花費(fèi)的時(shí)間有所增加.實(shí)驗(yàn)結(jié)果如圖7所示，候選關(guān)鍵字集規(guī)模的增大，使BS 算法的運(yùn)行時(shí)間隨關(guān)鍵字?jǐn)?shù)量的增多而顯著增加.相比之下，WSKQK 算法的性能隨著關(guān)鍵字?jǐn)?shù)量的增多越來越優(yōu)于BS算法.

圖7 查詢關(guān)鍵字個(gè)數(shù)對(duì)算法性能的影響Fig.7 Impact of query keyword numbers on algorithm performance

（6）數(shù)據(jù)集大小對(duì)算法性能的影響.為驗(yàn)證算法的可擴(kuò)展性，本組實(shí)驗(yàn)從GN 數(shù)據(jù)集中隨機(jī)選擇不同數(shù)量的空間對(duì)象（從0.1 M 到1.7 M），執(zhí)行空間關(guān)鍵字top-10 查詢，以評(píng)估不同數(shù)據(jù)集大小下的算法性能.實(shí)驗(yàn)結(jié)果如圖8 所示，隨數(shù)據(jù)集基數(shù)的增加，兩種算法的執(zhí)行時(shí)間幾乎呈線性增長.具體原因是，這兩種算法中候選關(guān)鍵字集的大小不會(huì)隨著數(shù)據(jù)集大小的增加而增加.這意味著本文提出的WSKQK算法的性能在不同的數(shù)據(jù)集下呈平穩(wěn)趨勢.

圖8 數(shù)據(jù)集大小對(duì)算法性能的影響Fig.8 Impact of dataset size on algorithm performance

5 結(jié)論

本文首次定義并研究了空間關(guān)鍵字top-k查詢的why 問題，為用戶提供了更能描述他們查詢意圖的關(guān)鍵字集.設(shè)計(jì)了一種名為WIR-tree 的索引結(jié)構(gòu)，旨在訪問非葉子結(jié)點(diǎn)下的子樹前完成剪枝操作.基于WIR-tree 索引，提出了WSKQK 算法，通過編輯距離遞增方式枚舉關(guān)鍵字集，并結(jié)合查詢處理提早結(jié)束策略，來加速整個(gè)候選關(guān)鍵字集的枚舉過程.最后，采用兩個(gè)真實(shí)數(shù)據(jù)集，通過WSKQK 與BS 算法的一系列對(duì)比實(shí)驗(yàn)，驗(yàn)證了所提方法的高效性和可擴(kuò)展性.未來將探討不同的文本相似模型及處理多個(gè)why對(duì)象的情形.