基于貪心策略的最近鄰Top-k 偏好查詢方法

蔡 盼，李 昕，孟祥福，褚治廣

遼寧工業大學 電子與信息工程學院，遼寧 錦州 121001

1 引言

現有的空間關鍵字查詢技術大多以用戶為中心，返回與用戶位置鄰近、文本相關的興趣對象。然而，用戶希望得到的查詢結果不僅要考慮查詢結果的位置相近性和文本相關性，還要考慮周圍的基礎設施屬性。比如，用戶想要租賃房屋，要求距離房屋500 m 的范圍內存在公交站。此類查詢被定義為Top-k空間關鍵字偏好查詢，其中興趣對象（房屋）周圍的基礎設施（公交站）稱為特征對象。與傳統的空間關鍵字查詢相比，Top-k空間關鍵字偏好查詢關注興趣對象周圍的特征對象對于用戶要求的滿足程度。查詢需要考慮興趣對象與特征對象之間的空間關系以及特征對象與用戶查詢關鍵字的文本相似關系，這使得Top-k空間關鍵字偏好查詢更具有挑戰性。

已有的Top-k空間關鍵字偏好查詢包含范圍約束、最近鄰約束和影響區域約束三種類型的查詢方式。給定一個查詢范圍r，范圍約束根據距離興趣對象范圍r內的特征對象對興趣對象進行評分；最近鄰約束是以距離興趣對象最近的特征對象為依據對興趣對象進行評分。上述兩種查詢方式側重于考慮特征對象與興趣對象之間的位置鄰近，然而這種方式可能會導致查找到的目標對象僅從空間上滿足用戶要求，而在文本上與用戶查詢關鍵字的相關度較低。第三種查詢方式檢索全部空間區域，查找距離與用戶查詢關鍵字最相關的特征對象的最近興趣對象作為候選結果，這種查詢方式有效地避免了查詢結果的遺漏以及與用戶關鍵字要求不匹配的情況。然而，由于影響區域約束需要檢索全部空間區域，在大數據量情況下會導致較低的查詢效率。

針對上述問題，本文研究了影響區域約束的Top-k空間關鍵字偏好查詢解決方法，在此基礎上提出了一種改進算法，主要貢獻如下：

（1）提出了一種有效的剪枝策略，利用貪心思想和最近鄰思想，每次查詢選擇最好的候選對象，有效解決了查詢效率低的問題。

（2）基于剪枝策略提出了一種查詢改進算法——GS-NNA（Greedy Strategy based Nearest Neighbor Algorithm），能夠獲得滿足用戶查詢需求和特征對象偏好的查詢結果。

（3）進行了大量的實驗驗證，從查詢關鍵字、查詢結果數量以及數據集基數三方面評估GS-NNA 算法的性能，并與現有相關算法進行比較。實驗結果表明，提出的GS-NNA 算法在查詢響應時間上比現有相關算法快了一個數量級。

2 相關工作

本文工作涉及Top-k空間關鍵字查詢和基于特征對象屬性的偏好查詢，下面分別從這兩方面介紹相關工作。

2.1 Top-k 空間關鍵字查詢

傳統的Top-k空間關鍵字查詢大多是以用戶為查詢點，根據興趣對象與用戶之間的空間距離以及與查詢關鍵字之間的文本相關度對興趣對象進行評分，返回前k個得分最高的興趣對象給用戶[1-5]。比如在歐式空間下，Felipe等人[1]結合R-tree索引和簽名文件定義了新的索引結構IR2-tree，研究了距離優先的Top-k空間關鍵字查詢。Qian 等人[2]研究了空間Web 對象與查詢關鍵字之間的語義關系，提出了一種基于語義的Top-k空間關鍵字查詢方法。郭帥等人[3]針對多用戶問題研究了協同關鍵字查詢，這種查詢考慮了多用戶問題，返回距離多個查詢位置近、文本與多組查詢關鍵詞相關度高的Topk對象。在路網環境下，Rocha-Junior等人[4]研究了基于路網環境的Top-k空間關鍵字查詢，并提出了有效的查詢處理方法。陳子軍等人[5]提出了基于路網受限的Topk空間關鍵字查詢。給定半徑為r的查詢范圍，基于路網受限的Top-k空間關鍵字查詢，返回靠近查詢位置并且與查詢關鍵字文本相關的Top-k個對象。上述工作中提及的Top-k空間關鍵字查詢都是以用戶為中心，在查詢中僅考慮與用戶位置鄰近和文本相關的興趣對象，忽略了興趣對象周圍的其他特征對象屬性對于查詢結果的重要意義。

2.2 基于特征對象屬性的偏好查詢

基于特征對象屬性的偏好查詢，在查詢中考慮了興趣對象周圍的特征對象對于用戶偏好的滿足程度。目前已有不少研究者對此類查詢進行了相關研究[6-9]，根據特征對象的屬性信息，可將相關研究工作分為兩類。

第一類方法考慮了特征對象的空間屬性，為每個特征對象預先定義一個分數（由用戶評論提供，例如http：//www.zagat.com/，用來評定特征對象的等級）。Yiu等人[6]首次定義了Top-k空間偏好查詢并提出了SP算法、GP 算法、BB 算法以及FJ 算法四種查詢算法。Top-k空間偏好查詢根據滿足空間約束關系（范圍約束、最近鄰約束以及影響區域約束）的特征對象的等級分數來評估興趣對象。在此之后，Rocha-Junior等人[7]針對上述查詢提出了改進方法來解決上述算法查詢效率低的問題，該方法定義了一種距離-分數空間，基于此空間提出了一種SFA算法，算法采用Skyline查詢，大量地刪除與查詢結果無關的數據對象，從而有效提高了查詢效率。上述所有研究工作都是針對特征對象的空間屬性，利用特征對象預定義的分數來處理查詢。與上述工作不同，本文研究的Top-k空間關鍵字偏好查詢同時考慮了特征對象的空間屬性和文本屬性。

隨著查詢結果質量的不斷提高，同時考慮位置鄰近性和文本相關性更能夠符合用戶的實際要求，第二類方法同時關注了特征對象的空間屬性和文本屬性。Tsatsanifos等人[8]提出了一種Top-k空間-文本偏好查詢，查詢通過興趣對象與特征對象之間的距離、特征對象與查詢關鍵字之間的文本相關度以及特征對象的分數來計算興趣對象的得分。他們提出的查詢方法雖然與本文研究工作非常相近，但是本文只考慮了特征對象的空間屬性和文本屬性。同時，在實際應用中，特征對象并沒有一個預定義的分數，因此本文研究的查詢更加符合實際應用。De Almeida 等人[9]定義了Top-k空間關鍵字偏好查詢并提出了IFA 算法、SIA 算法和SIA+算法三種查詢處理算法，與本文工作相關性較大。然而需要指出的是，他們只處理了基于范圍約束和最近鄰約束兩種查詢方式的Top-k空間關鍵字偏好查詢，沒有考慮第三種影響區域約束查詢方式。本文研究了基于影響區域約束查詢方式的Top-k空間關鍵字偏好查詢，提出了有效的剪枝策略以及查詢處理方法——GS-NNA算法。

3 基于貪心策略的最近鄰算法

3.1 問題描述

興趣對象集：O={o∈O|o.l=(x,y)},o表示一個興趣對象（例如，旅館），o.l代表空間對象位置，(x,y)表示經緯度。

特征對象集：F={f∈F|f.l=(x,y),f.T},f表示一個特征對象（例如，旅館周圍的餐館、地鐵等基礎設施），擁有空間屬性f.l和文本屬性f.T，其中f.l代表特征對象的位置，f.T代表一組關鍵字集合（例如，餐館提供的菜單）。

Top-k空間關鍵字偏好查詢：Q={O,F,W,φ,k},O代表興趣對象集，F代表特征對象集，W={w1,w2,…,w|W|}代表一組查詢關鍵字集合，φ代表影響區域約束，k代表查詢結果數量。Top-k空間關鍵字偏好查詢根據興趣對象周圍滿足影響區域約束的特征對象來計算興趣對象的分數，返回得分最高的前k個興趣對象。

影響區域約束φ要求查找到的目標對象需滿足以下條件：（1）距離目標對象最近的特征對象擁有最高的文本相關度；（2）查找到的目標對象擁有的分數高于其他興趣對象的分數。根據影響區域約束φ，空間區域中每個興趣對象的得分如式（1）所示：

其中，τφ(o)代表興趣對象o的得分；θ(f.T,Q.W)代表特征對象f與查詢關鍵字集合W之間的文本相關度，采用余弦公式[10]來計算；dist(f,o)代表興趣對象o與特征對象f之間的距離，采用歐氏距離計算；r是由用戶指定的一個范圍，在該函數模型中用來控制興趣對象得分隨距離變化的程度。當給定范圍r時，興趣對象o與特征對象f之間的距離越近，特征對象f與查詢關鍵字集合W之間的文本相關度越高，就表示興趣對象o的得分越高，更符合用戶查詢要求。

3.2 算法提出

現有相關研究工作中，只有De Almeida 等人提出的IFA 算法[9]經過改造后可以用來處理本文提出的問題。IFA算法需要檢索空間區域中的全部興趣對象，對于每一個興趣對象，需要通過文本相關的所有特征對象來計算它的分值，然后選擇分值最大的作為興趣對象的最終得分，最后將空間區域中分數最高的k個興趣對象返回。然而采用IFA 算法處理Top-k空間關鍵字偏好查詢存在以下三個問題：

（1）IFA 算法需要檢索和計算空間區域中所有的興趣對象；

（2）IFA算法每次只訪問一個興趣對象；

（3）與查詢關鍵字文本相關的所有特征對象都需要參與計算，如果興趣對象和文本相關的特征對象數量均很大，IFA算法會產生昂貴的計算代價和I/O成本，導致較低的查詢效率。

針對上述IFA算法的不足，本文算法重點考慮如何設計有效的剪枝策略，將與查詢結果無關的興趣對象和特征對象進行剪枝。由于Top-k空間關鍵字偏好查詢根據特征對象的屬性對興趣對象評分，特征對象與查詢關鍵字之間的文本相關度越高，則距離該特征對象最近的興趣對象得分就越高。因此GS-NNA 算法的基本思想是采用一種貪心策略，每次選擇與給定查詢關鍵字最相關的特征對象，然后根據該特征對象，從興趣對象集合中查找距離該特征對象最近的興趣對象，將它加入到候選結果集中。具體來講，GS-NNA算法通過倒排文件對特征對象進行文本過濾，然后預先計算倒排文件中所有特征對象與查詢關鍵字之間的文本相關度，并按照相關程度由高到低對它們進行排序。其次，設置閾值判定條件，用來剪枝與查詢結果無益的興趣對象和特征對象。最后，利用最近鄰方法查找與文本相關度最高的特征對象距離最近的興趣對象。通過上述方式查找到的興趣對象將擁有最高的分數。

因為Top-k空間關鍵字偏好查詢需要處理兩種數據對象：興趣對象和特征對象，所以針對兩種數據對象的屬性特征，本文算法采用不同索引結構來索引它們。算法采用R*-tree[11-12]索引興趣對象，將距離彼此接近的興趣對象存儲到同一個節點中。采用倒排文件[13-15]索引特征對象，過濾掉與查詢關鍵字不相關的特征對象。倒排文件中每個倒排列表對應一個查詢關鍵字w，列表中存儲包含w的特征對象的id以及w在該特征對象文本中出現的頻率ft。同時，為了便于計算特征對象與興趣對象之間的距離，在倒排列表中存儲了特征對象的位置信息f.l。

圖1給出了GS-NNA算法查詢處理流程圖，算法具體執行過程如下：

（1）訪問倒排文件。按照id順序訪問和計算每個特征對象f與查詢關鍵字W之間的文本相關度，并按照相關程度將特征對象f存儲在堆U中。U中每個節點存儲特征對象f的id、位置信息f.l以及與查詢關鍵字之間的文本相關度θ(fi.T,Q.W）。

（2）訪問堆U。每次從U中取出與查詢關鍵字相關度最高的特征對象fθmax，根據式（1）計算Tφ(fθmax)。其中取距離值為 0，Tφ(fθmax)=θ(fθmax.T,Q.W) 。比較Tφ(fθmax)與閾值τ：如果Tφ(fθmax)＞τ，執行步驟 3；否則結束查詢，執行步驟5。

（3）訪問R*-tree。如果是首次訪問R*-tree，則查找特征對象fθmax的k個最近鄰興趣對象oj(j=1,2,…,k),計算它們的得分τφ(oj)。然后比較τφ(oj)和閾值τ,如果τφ(oj)＞τ，將oj按照分值降序存儲到結果集H中，更新H和τ；否則執行步驟2。

（4）如果不是首次訪問R*-tree，則查找fθmax的最近鄰興趣對象oNN，計算τφ(oNN)。比較τφ(oNN)與閾值τ：如果τφ(oNN)＞τ，將oNN按照分值降序添加到H中，更新結果集H和閾值τ，然后繼續查找fθmax的下一個最近鄰oNN，直到τφ(oNN)≤τ時，結束當前查詢，返回步驟（2）。

（5）返回查詢結果集H。

圖1 GS-NNA算法處理流程圖

這里對更新查詢結果集H和閾值τ進行簡要說明。如果 |H|＜k且τφ(oj)＞τ，則將興趣對象oj按照分數降序添加到H中；如果 |H|≥k且τφ(oj)＞τ，則刪除H中第k個對象，將oj按照分數降序添加到H中，并用當前H中第k個對象的得分更新閾值τ。

由上述查詢流程得出GS-NNA算法：

為了更清楚地解釋GS-NNA算法的查詢過程，本文將結合實例對算法進行說明。圖2 所示的是一個空間區域S，其中黑點表示興趣對象（旅館）oj∈O(j=1,2,…,8)，白點表示特征對象fi∈F(i=1,2,…,6)，用二維坐標(x,y)表示它們的地理位置信息。表1記錄了每個特征對象fi的詳細信息，包括名稱Name以及關鍵字信息f.T。

圖2 一個空間區域S

表1 特征對象集文本屬性

假設一名游客想要查找一家旅館，要求附近存在提供“Coffee”和“WiFi”的餐館。這是一個Top-k空間關鍵字偏好查詢，其中“Coffee”和“WiFi”為查詢關鍵字。圖3是根據圖2 中的數據所創建的索引結構，圖3（a）是R*-tree 索引，圖3（b）是為查詢關鍵字“Coffee”和“WiFi”創建的倒排列表。

圖3 索引結構

本文分別采用GS-NNA 算法和IFA 算法執行該示例中的Top-k空間關鍵字偏好查詢。

首先采用GS-NNA 算法進行查詢，指定r=1.7，具體查詢步驟如下：

（1）訪問倒排列表，則U={f3,f1,f4,f6}。

（2）初始閾值τ=0 ，訪問U，從U中取出fθmax，即f3,Tφ(fθmax)=Tφ(f3)=θ(f3.T,Q.W)=2＞τ（為了便于計算，實例中采用關鍵字出現的次數作為文本相關度，而在實驗部分采用余弦公式計算）。

（3）如果執行Top-1查詢，則f3的最近鄰oNN為o3，返回步驟（2），繼續訪問U，從U中取出下一個fθmax，即f1,Tφ(f1)=θ(f1.T,Q.W)=1＜τ=1.124 ，因此查詢結束，返回結果集H。

（4）H={o3}。

（5）如果執行Top-2 查詢，f3的最近鄰為o3和o8，重復執行步驟2，結束查詢，理由同上，返回結果集H。

（6）H={o3,o8}。

采用IFA 算法執行Top-k空間關鍵字偏好查詢。算法需要檢查空間區域S中所有的興趣對象，對于每一個興趣對象oi(i=1,2,…,8)，需要訪問倒排文件，取出所有的特征對象存儲到U中，U={f1,f3,f4,f6}。然后按照id順序計算每個特征對象的文本相關度，以及它們與oi之間的距離，最后根據式（1），計算每個興趣對象oi的分數3,4,6。經過計算，每個興趣對象oi的分數分別為：

經過比較τφ(oi)和τ，查詢返回o3作為Top-1結果，o8作為Top-2結果。

結合上述實例發現，采用IFA 算法執行查詢時，需要檢索和計算空間區域中每一個興趣對象的得分，從而導致較高的計算代價和I/O 成本，使得查詢效率較低。相比之下，采用GS-NNA 算法執行查詢時，因為每次只查找文本相關度最高的特征對象的最近鄰作為候選結果，大量與查詢結果無關的興趣對象和特征對象被剪枝，所以有效減少了計算成本，提高了查詢效率。通過上述實例可以明顯看出GS-NNA算法更具優勢。

3.3 算法復雜度分析

本節主要對GS-NNA 算法和IFA 算法的復雜度進行簡要分析，兩種算法的復雜度主要從需要檢索的特征對象數量和興趣對象數量兩方面進行考慮。假設興趣對象集中興趣對象的數量為 |O|，特征對象集中特征對象的數量為 |F|。對于IFA 算法，由于采用倒排文件過濾了與查詢關鍵字不相關的特征對象，并計算了空間數據集中所有的興趣對象，因此IFA 算法的復雜度為O(|O|× |F′|)，其中F′?F。對于GS-NNA算法，由于算法每次從倒排列表中選取文本相關度最高的特征對象，通過該特征對象查找距離它最近的興趣對象，并利用閾值判定條件，將不滿足閾值條件的特征對象和興趣對象進行剪枝，有效減少了需要訪問和計算的特征對象和興趣對象的數量，因此GS-NNA 算法的復雜度為O(|O′|×|F′|)，其中O′?O，F"?F′?F。

4 實驗結果與分析

4.1 實驗設置

實驗在三個真實數據集Venice、London 和North America 上進行，數據集的相關屬性如表2 所示。本文所有算法均采用Java 語言實現，實驗在Windows 10 系統上進行，系統配置為8 GHz 內存的Intel?CoreTMi3-6100 CPU@3.70 GHz處理器。

4.2 實驗結果

實驗從查詢關鍵字的數量、查詢結果數量k以及數據集基數三方面來衡量IFA 算法和GS-NNA 算法對查詢響應時間的影響。實驗參數具體設置如表3所示。

表2 實驗數據集屬性

表3 實驗參數設置

4.2.1 查詢關鍵字數量變化對查詢響應時間的影響

圖4 展示了當固定查詢結果數量為5、數據集為Venice 時，不同查詢關鍵字數量對查詢響應時間的影響。從圖4中可以看出，GS-NNA算法查詢響應時間比IFA算法要快，并且隨著查詢關鍵字數量的增加，IFA算法和GS-NNA算法都有所增加，但是GS-NNA算法增加幅度微小。由于IFA 算法僅能通過倒排文件對特征對象進行文本過濾，當查詢關鍵字數量增加時，文本相關的特征對象數量將會增加，導致剪枝效果較差，從而導致查詢時間增加。而GS-NNA 算法采用倒排文件和閾值判定條件對特征對象進行剪枝，只有同時滿足文本相關和閾值判定條件的特征對象才能參與計算，因此GS-NNA算法查詢響應時間增加的程度要小于IFA算法。

圖4 查詢關鍵字數量對查詢響應時間的影響

4.2.2 參數k 變化對查詢響應時間的影響

圖5 展示了當固定查詢關鍵字數量為3、數據集為Venice時，查詢結果數量k變化對于查詢響應時間的影響。從圖5 中可以看出，當k增加時，兩種算法的查詢響應時間受到的影響非常小，而GS-NNA算法仍然保持優勢。這是因為IFA 算法已經訪問和計算了所有的興趣對象，當k值增加時，只需要從候選結果集中返回前k個興趣對象即可，所以并不會影響查詢響應時間。而對于GS-NNA算法，因為查詢結果從文本相關度最高的特征對象的最近鄰中選擇，所以當k值增加時，需要搜索特征對象最近鄰的時間增加，從而導致整體查詢時間增加。但是由于GS-NNA算法采用了有效的剪枝策略，相對于整體查詢時間，搜索最近鄰的時間具有微小的影響。

圖5 參數k 對查詢響應時間的影響

4.2.3 不同大小的數據集對查詢響應時間的影響

圖6 展示了當固定查詢關鍵字數量為3、查詢結果數量k為5時，不同大小的數據集對于查詢響應時間的影響。從圖6 中可以看出，隨著數據集基數的增大，兩種算法的查詢響應時間也隨之增加。主要原因是當數據集基數增加時，表示興趣對象和特征對象的數量均增加。其中特征對象數量的增加并不會影響到查詢效果，因為參與查詢的特征對象數量只與查詢關鍵字數量的變化相關。而興趣對象數量的增加將會影響兩種算法的查詢響應時間，尤其是IFA算法受到的影響更大。這是因為IFA 算法需要訪問和計算所有的興趣對象，而GS-NNA 算法僅搜索和計算滿足閾值判定條件的特征對象的最近鄰，所以查詢響應時間上要快于IFA算法。

圖6 不同大小的數據集對查詢響應時間的影響

5 總結

本文提出了一種基于貪心策略的最近鄰查詢算法GS-NNA，該算法結合R*-tree 索引和倒排文件索引，有效解決了基于影響區域偏好約束的Top-k空間關鍵字偏好查詢方式下，訪問和計算代價大的問題。具體地，算法利用貪心思想，每次選擇與用戶查詢需求最匹配的特征對象，然后通過最近鄰方法遍歷R*-tree，查找距離該特征對象最近的興趣對象，將此興趣對象作為候選結果返回。GS-NNA算法為了更進一步提高查詢效率，設置了閾值判定條件，將不滿足閾值判定條件的特征對象和興趣對象進行剪枝，減少了需要訪問和計算的數據量。最后，通過與IFA算法進行實驗比較，證明了GS-NNA算法比IFA算法在查詢響應時間上快了一個數量級，有效提高了查詢效率。