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

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

遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

2.1 Top-k 空間關(guān)鍵字查詢

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

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

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

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

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

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

3.1 問題描述

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

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

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

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

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

3.2 算法提出

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

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

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

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

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

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

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

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

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

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

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

（5）返回查詢結(jié)果集H。

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

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

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

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

圖2 一個空間區(qū)域S

表1 特征對象集文本屬性

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

圖3 索引結(jié)構(gòu)

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

首先采用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＞τ（為了便于計算，實例中采用關(guān)鍵字出現(xiàn)的次數(shù)作為文本相關(guān)度，而在實驗部分采用余弦公式計算）。

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

（4）H={o3}。

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

（6）H={o3,o8}。

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

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

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

3.3 算法復(fù)雜度分析

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

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

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

4.2 實驗結(jié)果

實驗從查詢關(guān)鍵字的數(shù)量、查詢結(jié)果數(shù)量k以及數(shù)據(jù)集基數(shù)三方面來衡量IFA 算法和GS-NNA 算法對查詢響應(yīng)時間的影響。實驗參數(shù)具體設(shè)置如表3所示。

表2 實驗數(shù)據(jù)集屬性

表3 實驗參數(shù)設(shè)置

4.2.1 查詢關(guān)鍵字數(shù)量變化對查詢響應(yīng)時間的影響

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

圖4 查詢關(guān)鍵字數(shù)量對查詢響應(yīng)時間的影響

4.2.2 參數(shù)k 變化對查詢響應(yīng)時間的影響

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

圖5 參數(shù)k 對查詢響應(yīng)時間的影響

4.2.3 不同大小的數(shù)據(jù)集對查詢響應(yīng)時間的影響

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

圖6 不同大小的數(shù)據(jù)集對查詢響應(yīng)時間的影響

5 總結(jié)

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