空間關鍵字top-k查詢的why問題

黃金亮，李艷紅，盧航

（中南民族大學 計算機科學學院，武漢 430074）

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

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

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

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

1 問題描述

1.1 空間關鍵字top-k查詢

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

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

其中，|o.doc∩q.doc|表示o.doc與q.doc 交集的關鍵字個數，|o.doc∪q.doc|表示o.doc 與q.doc 并集的關鍵字個數.通過上述得分函數計算對象的得分，得分越高的對象其排名越高.對象o的排名具體如下：

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

1.2 空間關鍵字top-k查詢的why問題

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

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

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

表1 四個空間對象的得分詳情Tab.1 Score details of the four spatial objects

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

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

定義2空間關鍵字top-k查詢的why 問題.給定原始空間關鍵字查詢q=（loc，doc0，k0，α），原始查詢返回的結果集RS，why 對象集W.根據式（4）定義的代價方程，查詢系統將返回一個代價最小、且why對象均被排除在結果集RS′之外的精煉查詢q′=（loc，doc′，k′，α）.

2 WIR-tree索引結構

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

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

定理1給定查詢q=（loc，doc，k，α），WIR-tree中的非葉子結點N，N索引的對象集合S，記MDist（q.loc，N.MBR）為q.loc 和N.MBR 的最小距離，N∪和N∩分別表示結點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）成立，

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

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

3 WSKQK算法

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

接下來，需要解決的一個重要問題是獲取可能的查詢關鍵字集.由于對象集D中不同關鍵字的總數可能很大，所以可能的查詢關鍵字集個數會很多.因此為每一組關鍵字執行空間關鍵字top-k查詢是不現實的，為此，提出了以下解決方案.

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

3.1 編輯距離遞增方式枚舉關鍵字集

候選關鍵字集的枚舉順序對算法的性能起到關鍵性作用.候選關鍵字集的枚舉過程中，應該優先考慮更有可能成為最優精煉查詢的關鍵字集，因為對于原始查詢關鍵字集編輯距離越小的精煉查詢關鍵字集，其修改代價越小，因而越有可能成為最優精煉查詢的關鍵字集.首先考慮編輯距離為0的基本精煉查詢q′=（q.loc，q.doc′，k′，α），其中基本精煉查詢的關鍵字集與原始查詢的關鍵字集完全相同，即q′.doc′=q.doc，查詢個數縮小為q′.k′=R（W，q）-1，由式（4）計算得出基本精煉查詢的代價為：

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

關鍵字部分的修改代價已大于pmin，通過代價公式（4）知，剩余的候選關鍵字集的修改代價絕不會小于pmin，此時，整個候選關鍵字集枚舉過程結束，pmin為最優精練查詢的修改代價.

3.2 候選關鍵字查詢處理提早結束策略

對于精煉查詢q′（loc，doc′，k′，α），若其為最優精煉查詢，由式（4）、（8）得：

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

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

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

4 實驗與分析

以基于SetR-tree 索引結構的BS 算法［13］作為對照算法，通過一系列對比實驗來驗證本文提出的基于WIR-tree索引的WSKQK算法的性能.

4.1 實驗設置

4.1.1 實驗設備及評估指標

所有實驗均在同一臺PC 上進行，PC 的配置為Intel Core i7，2.20 GHz CPU 和8 GB 內存.所有算法皆使用Java實現，運行在Windows10操作系統上.本文采用查詢時間作為算法性能的評估指標，對每一組實驗，隨機生成500 個查詢取其平均查詢時間作為查詢時間結果.

4.1.2 數據集

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

表3 數據集詳情Tab.3 Datasets information

4.1.3 參數

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

表4 參數設置Tab.4 Parameters setting

4.2 實驗結果及分析

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

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

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

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

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

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

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

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

（5）查詢關鍵字個數對算法性能的影響.關鍵字的數量會在兩個方面影響到算法的性能：?。┎樵冴P鍵字的增多使候選關鍵字集的規模增大；ⅱ）關鍵字數量的增加使計算對象文本與查詢關鍵字的文本相似度所花費的時間有所增加.實驗結果如圖7所示，候選關鍵字集規模的增大，使BS 算法的運行時間隨關鍵字數量的增多而顯著增加.相比之下，WSKQK 算法的性能隨著關鍵字數量的增多越來越優于BS算法.

圖7 查詢關鍵字個數對算法性能的影響Fig.7 Impact of query keyword numbers on algorithm performance

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

圖8 數據集大小對算法性能的影響Fig.8 Impact of dataset size on algorithm performance

5 結論

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