張 豪，朱 睿，宋栿堯，方 鵬，夏秀峰

（沈陽航空航天大學(xué)計(jì)算機(jī)學(xué)院，沈陽 110136）

（?通信作者電子郵箱13623212292@163.com）

0 引言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，基于位置的社交網(wǎng)絡(luò)（Location-Based Social Network，LBSN）服務(wù)應(yīng)用越來越廣泛。許多學(xué)者研究了面向LBSN 的查詢處理問題應(yīng)對不同服務(wù)類型下的業(yè)務(wù)請求。

在眾多查詢處理問題中，面向反k近鄰空間關(guān)鍵字（Reverse Spatial KeywordkNearest Neighbor，RSKkNN）［1］查詢是一類重要問題，在市場分析、決策支持和交通信息等領(lǐng)域具有重要應(yīng)用。具體地，在客戶推薦系統(tǒng)中，該查詢可以幫助商家根據(jù)客戶偏好有針對性地利用短信等手段為客戶推薦商品信息，從而增加營業(yè)收入。在交通信息管理領(lǐng)域，它可以通過分析乘客的用車偏好和位置信息，為乘客推薦車輛。

傳統(tǒng)反k近鄰查詢可分為單色反k近鄰查詢（簡稱單色查詢）和雙色反k近鄰查詢（簡稱雙色查詢）。具體地，給定一組對象o和一個(gè)單色查詢q，查詢返回所有以q作為其k近鄰的對象。與之不同，給定一組用戶U、一組設(shè)施F和一個(gè)雙色查詢設(shè)施q，查詢返回以設(shè)施q為k近鄰的所有用戶。反k近鄰查詢主要應(yīng)用于推薦場景，其中單色反k近鄰查詢主要應(yīng)用于同類型對象之間的推薦。例如，為某位用戶推薦一些與他距離比較近的志趣相投的人。而雙色反k近鄰主要應(yīng)用于兩種不同類型對象之間的推薦，相較于單色反k近鄰查詢的應(yīng)用更加廣泛，比如推薦場景中更多的是為商場提供潛在的消費(fèi)者，為司機(jī)提供潛在的乘客等，這些都是單色反k近鄰查詢無法做到的，所以本文重點(diǎn)研究雙色反k近鄰。接下來本文以k=2 為例簡單說明傳統(tǒng)反k近鄰的查詢規(guī)則，如圖1（a）所示，對象｛o0，o1，o5，o6｝的k近鄰對象包含q，所以對象q的單色反k近鄰查詢返回結(jié)果為｛o0，o1，o5，o6｝；如圖1（b）所示，用戶｛u0，u5，u6，u7，u9｝的k近鄰設(shè)施包含q，所以設(shè)施q的雙色反k近鄰查詢結(jié)果為｛u0，u5，u6，u7，u9｝。本文研究雙色反k近鄰查詢。

圖1 傳統(tǒng)單色和雙色反k近鄰Fig.1 Traditional monochromatic and bicolor reverse k nearest neighbors

傳統(tǒng)反k近查詢不能根據(jù)設(shè)施和用戶需求針對性地返回查詢結(jié)果，而帶關(guān)鍵字約束的反k近鄰查詢可以很好解決此問題。鑒于此類問題的重要性，許多學(xué)者針對此類問題展開研究。例如:Lu 等［1］首次研究了基于關(guān)鍵字約束的反k近鄰查詢問題。給定查詢點(diǎn)q和對象集合D，查詢計(jì)算q和D中對象空間上的距離以及關(guān)鍵字間的相似性。以此為基礎(chǔ)，算法利用打分函數(shù)評價(jià)各對象對于查詢點(diǎn)q的重要性，并返回得分最高的k個(gè)對象。Zhao 等［2］提出了一種相關(guān)反近鄰布爾空間關(guān)鍵字查詢（Ranked Reverse boolean Spatial Keyword Nearest Neighbors，Ranked-RSKNN）問題。該查詢返回一定數(shù)量與查詢點(diǎn)相關(guān)程度最高的對象。

然而，這些研究存在的共性問題是沒有考慮查詢點(diǎn)與查詢結(jié)果的距離對查詢結(jié)果造成的影響，很多距離查詢點(diǎn)很遠(yuǎn)但是關(guān)鍵字相似度較高的對象也將返回給用戶。顯然，和一些距離查詢點(diǎn)較近但關(guān)鍵字相似度較低的對象相比，這些查詢結(jié)果的質(zhì)量較低。

因此，本文研究距離-關(guān)鍵字相似度約束的雙色反k近鄰（Distance-Keyword ReversekNearest Neighbor，DKRkNN）問題。和以往研究不同，DKRkNN 通過引入閾值φr過濾掉一些距離查詢點(diǎn)相對較遠(yuǎn)的用戶。為高效支持此類查詢，本文需面對以下挑戰(zhàn):

1）高效的過濾能力?？臻g文本數(shù)據(jù)同時(shí)具有空間位置和關(guān)鍵字屬性。因此，如何同時(shí)根據(jù)空間位置和關(guān)鍵字對數(shù)據(jù)進(jìn)行篩選是極具挑戰(zhàn)的。

2）高效的驗(yàn)證能力。對每個(gè)用戶進(jìn)行驗(yàn)證都需要遍歷一次設(shè)施集。因此，在驗(yàn)證時(shí)如何盡可能少地遍歷設(shè)施是極具挑戰(zhàn)的。

針對上述挑戰(zhàn)，本文提出了一種基于多分辨率網(wǎng)格樹查詢處理框架支持查詢。本文主要工作如下:

1）提出了一種關(guān)鍵字多分辨率網(wǎng)格矩形樹（Keyword Multiresolution Grid rectangle-Tree，KMG-Tree）索引管理設(shè)施和用戶數(shù)據(jù)。該索引同時(shí)具有以下優(yōu)點(diǎn):①通過對網(wǎng)格中的單元格添加關(guān)鍵字信息，以達(dá)到通過這兩個(gè)屬性批量過濾數(shù)據(jù)的目的；②相對平衡的結(jié)構(gòu)，通過對傳統(tǒng)的多分辨率網(wǎng)格進(jìn)行改進(jìn)，KMG-Tree 用分辨率較高網(wǎng)格劃分?jǐn)?shù)據(jù)密集的區(qū)域；用分辨率較低網(wǎng)格劃分?jǐn)?shù)據(jù)稀疏的區(qū)域。這樣一來，它可以保證索引各節(jié)點(diǎn)維護(hù)的對象數(shù)目大致相同從而保證了索引的平衡性。

2）提出了基于Six-region-optimize 的過濾算法。該算法將整個(gè)空間等分為6 個(gè)區(qū)域，根據(jù)位置關(guān)系定義過濾區(qū)域。這樣一來，被過濾區(qū)域覆蓋的網(wǎng)格節(jié)點(diǎn)可被安全過濾。此外，與查詢點(diǎn)關(guān)鍵字無交集的網(wǎng)格節(jié)點(diǎn)也可被安全過濾。

3）提出了基于Six-region-optimize 的驗(yàn)證算法。在驗(yàn)證用戶時(shí)，只需要訪問該區(qū)域及相鄰區(qū)域的對用戶可能有影響的設(shè)施，這樣可以快速找到用戶的最近鄰及k近鄰，一定程度上提高了驗(yàn)證的效率。

1 相關(guān)工作

LBSN平臺(tái)的數(shù)據(jù)規(guī)模越來越龐大，在做大數(shù)據(jù)查詢時(shí)首先要對大數(shù)據(jù)進(jìn)行分析，例如對于大數(shù)據(jù)分類問題，Xia 等［3］提出了粒度球鄰域粗糙集（Granular Ball Neighborhood Rough Set，GBNRS）分類方法，該方法自適應(yīng)地為每個(gè)對象生成不同的鄰域，從而具有更大的通用性和靈活性，并提高了在公共基準(zhǔn)數(shù)據(jù)集上的分類精度和性能。對于大數(shù)據(jù)“k-均值”問題，Xia 等［4］提出了一種稱為“Ballk-means”的方法，用球來描述每個(gè)簇，減少了點(diǎn)質(zhì)心距離的計(jì)算，提高了算法的性能。對于大數(shù)據(jù)噪聲監(jiān)測問題，Xia 等［5］提出了一種完整有效的隨機(jī)森林方法，通過模擬網(wǎng)格的生成和擴(kuò)展來檢測類噪聲，提高了噪聲監(jiān)測的性能。在這些大數(shù)據(jù)分析的基礎(chǔ)上許多學(xué)者根據(jù)大數(shù)據(jù)推薦問題研究了反k近鄰查詢。

區(qū)域剪枝是處理空間反k近鄰查詢的方法之一，其主要思想是將空間分為幾個(gè)區(qū)域，并針對每塊區(qū)域的空間距離對用戶進(jìn)行剪枝。Stanoi 等［6］提出了一種基于Six-region 剪枝的方法。該方法以查詢點(diǎn)為中心將空間分為6 個(gè)相等的區(qū)域。在每個(gè)區(qū)域中找到查詢點(diǎn)的k近鄰設(shè)施，以該設(shè)施到查詢點(diǎn)距離為半徑定義剪枝區(qū)域。

半空間剪枝法的核心思想是找到查詢對q與設(shè)施對象f的中垂線。以此為基礎(chǔ)，Tao 等［7-8］提出了半空間剪枝的算法，給定一個(gè)設(shè)施f和一個(gè)查詢q，f和q之間的垂直平分線Bf:q將空間分成兩部分。讓Hf:q表示包含f的半空間，Hq:f表示包含q的半空間。Hf:q中的每個(gè)用戶u滿足dist（u，f）＜dist（u，q）。換句話說，位于Hf:q中的每個(gè)用戶u被f剪枝，被k個(gè)這樣的設(shè)施剪枝的用戶可以被過濾。Cheema 等［9-11］提出影響區(qū)概念，影響區(qū)是指當(dāng)且僅當(dāng)用u位于該區(qū)域內(nèi)時(shí)，u為q的RkNN。建造影響區(qū)的方法是繪制所有設(shè)施的半空間，被小于k個(gè)設(shè)施過濾的區(qū)域?yàn)橛绊憛^(qū)。Lee 等［12］提出了相關(guān)反最近鄰查詢，該查詢通過對數(shù)據(jù)對象與查詢對象q的相關(guān)性進(jìn)行排序，返回受查詢對象q影響最大的t個(gè)數(shù)據(jù)對象。

Yiu 等［13］提出了在大型圖上的反k近鄰查詢，并提出了兩種剪枝方法:一種是在網(wǎng)絡(luò)節(jié)點(diǎn)被訪問后立即進(jìn)行修剪的急切算法；另一種是在發(fā)現(xiàn)數(shù)據(jù)點(diǎn)時(shí)對搜索空間進(jìn)行修剪的懶惰算法，實(shí)現(xiàn)了在大型圖上的反k近鄰查詢。李佳佳等［14］提出了面向時(shí)間依賴的路網(wǎng)中的反k近鄰查詢，該查詢提出了計(jì)算節(jié)點(diǎn)到達(dá)時(shí)間的方法，利用該到達(dá)時(shí)間查詢出多個(gè)候選k近鄰結(jié)果。Hidayat 等［15］提出了近似反最近鄰查詢，該查詢將一些不是查詢點(diǎn)的反最近鄰但距離查詢點(diǎn)也很近的點(diǎn)返回到了查詢結(jié)果中。

以上幾個(gè)算法都只是在空間或路網(wǎng)中反k近鄰查詢應(yīng)用很好的算法，并不能夠解決反k近鄰空間關(guān)鍵字查詢問題。Lu 等［1］首次提出了反k近鄰空間關(guān)鍵字查詢問題，將空間位置和關(guān)鍵字通過度量公式結(jié)合在一起，并設(shè)計(jì)了一種空間文本混合索引結(jié)構(gòu)IUR-Tree（Intersection-Union R-Tree）。Zhao等［2］提出了一種相關(guān)反近鄰空間關(guān)鍵字查詢，簡稱Ranked-RSkNN。該查詢可以返回固定數(shù)量的對象，并將這些對象按照查詢相關(guān)程度的大小進(jìn)行排序。該查詢能保證找到一定數(shù)量的結(jié)果返回。

然而，在反k近鄰空間關(guān)鍵字查詢問題中，沒有考慮空間距離太遠(yuǎn)和關(guān)鍵字相似度過低的情況，得到的查詢結(jié)果并非是查詢點(diǎn)所期望的結(jié)果。因此，研究基于距離-關(guān)鍵字相似度約束的反k近鄰空間關(guān)鍵字查詢問題具有重要意義。

2 問題定義

前文已經(jīng)提到現(xiàn)有的空間關(guān)鍵字雙色反k近鄰查詢都沒有考慮查詢點(diǎn)與查詢結(jié)果之間的距離對查詢結(jié)果造成的影響，很多距離查詢點(diǎn)很遠(yuǎn)但是關(guān)鍵字相似度較高的對象也將返回給用戶。顯然，和一些距離查詢點(diǎn)較近但關(guān)鍵字相似度較低的對象相比，這些查詢結(jié)果的質(zhì)量較低。具體地，在商場推銷商品的場景下，通過雙色反k近鄰查詢找到了一些潛在的消費(fèi)者。當(dāng)k≥2 時(shí)，這些消費(fèi)者可能存在這樣一種情況，商場a的位置在城市的中心，但是它的反k近鄰中存在某個(gè)消費(fèi)者u在該城市的郊區(qū)，在該郊區(qū)存在另一個(gè)商場b也可以滿足u的消費(fèi)需求，商場a對于u來說太遠(yuǎn)了，所以消費(fèi)者u一定不會(huì)舍近求遠(yuǎn)，那么查詢返回的消費(fèi)者u對于商場a來說質(zhì)量是非常低的。本文針對該問題設(shè)置了一個(gè)閾值φr，通過閾值φr可以將這些質(zhì)量非常低的對象給過濾掉。下面詳細(xì)介紹本文查詢問題的形式化定義。

在介紹問題之前，本文首先定義一組符號。給定用戶集合U和設(shè)施集合F，任意用戶u∈U、任意設(shè)施f∈F均可用二元組表示。其中，u.l表示了u的位置信息，u.key表示了用戶的關(guān)鍵字信息。給定任意查詢q，它可用五元組表示。φr表示用戶到查詢設(shè)施距離與其到最近鄰設(shè)施距離比值的閾值；φk表示用戶與查詢設(shè)施關(guān)鍵字相似度閾值。給定用戶u和設(shè)施f，本文利用歐氏距離dist（u，f）計(jì)算u與f之間的距離。給定u和其最近鄰NN（f），本文利用式（1）計(jì)算φr，利用式（2）計(jì)算u與q所對應(yīng)關(guān)鍵字的相似程度。接下來介紹關(guān)鍵字-距離約束條件下的雙色反k近鄰查詢。

定義1距離-關(guān)鍵字相似度約束的雙色反k近鄰查詢（DKRkNN）。給定一組帶關(guān)鍵字的用戶U、一組帶關(guān)鍵字的設(shè)施F、一個(gè)帶關(guān)鍵字的查詢設(shè)施q、用戶到查詢設(shè)施距離與到其最近鄰設(shè)施距離的比值閾值φr和關(guān)鍵字相似度閾值φk，返回滿足條件Ratio(q，u) ≤φr和Sim(q，u) ≥φk，并以查詢設(shè)施q為k近鄰的每個(gè)用戶u。

接下來，通過如下實(shí)例詳細(xì)說明DKRkNN 查詢。通過設(shè)施和用戶來區(qū)分不同的數(shù)據(jù)類型。圖1（b）為每個(gè)對象在二維空間中的位置。圖中五角星q表示商場在空間中的位置，正方形fi表示其他商場在空間中的位置，圓形ui表示用戶在空間中的位置（后文圖中的正方形點(diǎn)代表設(shè)施，圓形點(diǎn)代表用戶）。表1 分別為用戶以及用戶與商場q的關(guān)鍵字相似度、用戶到商場q的空間距離。給定查詢q，假設(shè)查詢值k=2、φr=2、φk=0.3，關(guān)鍵字集合為｛water，egg，meat，coffee，banana，milk｝，q的R2NN 為｛u0，u5，u6，u7，u9｝（見圖1（b））。u0的最近鄰為f0，u9的最近鄰為f1，通過計(jì)算發(fā)現(xiàn)Ratio(q，u0)=3.05 ＞2，Ratio(q，u9)=3.47 ＞2（見表1）。因此，u0和u9不滿足要求。進(jìn)一步地，通過相似度計(jì)算發(fā)現(xiàn)用戶｛u5，u6，u7｝的關(guān)鍵字信息與商場q的關(guān)鍵字的信息相似度分別為｛0.09，0.71，0.50｝，顯然Sim（q，u5）＜0.3，最終，查詢結(jié)果為｛u6，u7｝。

表1 用戶與設(shè)施之間的關(guān)系Tab.1 Relationship between users and facilities

3 基于多分辨率網(wǎng)格樹的查詢處理框架

3.1 框架概述

本文利用基于Six-region 改進(jìn)的Six-region-optimize 過濾-驗(yàn)證框架支持基于距離-關(guān)鍵字相似度約束的雙色反k近鄰查詢問題。為支持高效查詢，本文首先提出了一種基于數(shù)據(jù)依賴的多分辨率網(wǎng)格樹索引實(shí)現(xiàn)數(shù)據(jù)的高效管理，隨后本文提出了一種基于Six-region-optimize 過濾算法實(shí)現(xiàn)對用戶和設(shè)施的過濾，最后本文提出了一種基于Six-region-optimize 的驗(yàn)證算法實(shí)現(xiàn)對候選用戶的驗(yàn)證。

給定n個(gè)帶關(guān)鍵字的用戶，首先，根據(jù)用戶空間位置將空間等分為個(gè)帶關(guān)鍵字信息的單元格。然后，根據(jù)單元格中數(shù)據(jù)的密度對單元格進(jìn)行合并和分裂操作，從而得到一個(gè)多分辨率網(wǎng)格結(jié)構(gòu)。最后，通過多叉樹維護(hù)網(wǎng)格之間的空間位置關(guān)系。該索引可以利用網(wǎng)格的特性降低維護(hù)代價(jià)，保證索引的平衡性，并在訪問過程中根據(jù)單元格的關(guān)鍵字信息對用戶實(shí)現(xiàn)批量過濾。

根據(jù)過濾算法得到候選用戶集R和用于驗(yàn)證用戶的設(shè)施集V，根據(jù)驗(yàn)證算法對候選集R中的每個(gè)用戶進(jìn)行驗(yàn)證。驗(yàn)證每個(gè)候選用戶需要遍歷設(shè)施集V，將滿足查詢要求的用戶存儲(chǔ)到結(jié)果集Result中。

3.2 多分辨率網(wǎng)格樹索引KMG-Tree

本文提出了基于關(guān)鍵字多分辨率網(wǎng)格矩形樹（KMGTree）索引分別管理用戶和設(shè)施。該索引是一種以多分辨率網(wǎng)格為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。它對數(shù)據(jù)密集的區(qū)域使用分辨率較高的單元格進(jìn)行劃分，對數(shù)據(jù)稀疏的區(qū)域使用分辨率較低的單元格進(jìn)行劃分，從而保證每個(gè)單元格存儲(chǔ)用戶或設(shè)施數(shù)量基本相同。

首先，介紹一組KMG-Tree 索引用到的符號。KMG-Tree索引的每個(gè)節(jié)點(diǎn)t使用一個(gè)5 元組表示。KMG-Tree每個(gè)節(jié)點(diǎn)t唯一標(biāo)識(shí)用t.id表示；t.c是一個(gè)數(shù)組，用來存儲(chǔ)節(jié)點(diǎn)t的所有孩子節(jié)點(diǎn)；t.leaf是一個(gè)標(biāo)記，它標(biāo)記節(jié)點(diǎn)t是否為KMG-Tree 索引的葉子節(jié)點(diǎn)，值為true 表示為該索引的葉子節(jié)點(diǎn)，值為false 表示為該索引的非葉子節(jié)點(diǎn)；t.k用來存儲(chǔ)每個(gè)節(jié)點(diǎn)中所有對象的關(guān)鍵字信息，該關(guān)鍵字信息是一個(gè)基于哈夫曼樹構(gòu)造的一個(gè)bit串。算法可以根據(jù)每個(gè)節(jié)點(diǎn)t存儲(chǔ)的bit 串快速過濾對象。使用哈夫曼編碼表示關(guān)鍵字信息可以有效地降低空間代價(jià)。與直接使用節(jié)點(diǎn)存儲(chǔ)關(guān)鍵字方式相比，基于哈夫曼編碼的bit串存儲(chǔ)策略可以有效壓縮存儲(chǔ)空間。

接下來，舉一個(gè)例子詳細(xì)說明索引的構(gòu)建過程。本文首先指定一個(gè)閾值m用來表示每個(gè)單元格存儲(chǔ)對象數(shù)量的最大值。以m=2時(shí)為例，整個(gè)空間存在10個(gè)對象，將整個(gè)空間劃分為個(gè)單元格，根據(jù)每個(gè)單元格中對象的數(shù)量判斷單元格是否需要進(jìn)行合并或者分裂。合并和分裂的條件如下:

1）當(dāng)單元格中對象數(shù)量大于m時(shí)進(jìn)行分裂；

2）當(dāng)單元格中對象數(shù)量小于m時(shí)進(jìn)行合并。

經(jīng)過合并與分裂之后得到的邏輯空間如圖2（a）所示，C0包含四個(gè)節(jié)點(diǎn)C1、C2、C3和C4；C1包含兩個(gè)對象u1和u2；C2包含兩個(gè)節(jié)點(diǎn)C5和C6；C3包含一個(gè)對象u0；C4包含兩個(gè)節(jié)點(diǎn)C7和C8；C5包含一個(gè)對象u3；C6包含兩個(gè)對象u4和u6；C7包含兩個(gè)對象u5和u7；C8包含兩個(gè)對象u8和u9。這時(shí)所有單元格都滿足對象數(shù)量的限制。將C1、C3、C5、C6、C7和C8的leaf值設(shè)置為true。構(gòu)建完成后的KMG-Tree 索引結(jié)構(gòu)如圖2（b）所示，索引中每個(gè)節(jié)點(diǎn)以及每個(gè)單元格集成對應(yīng)的關(guān)鍵字集合存儲(chǔ)在t.k中。

圖2 索引結(jié)構(gòu)示意圖Fig.2 Schematic diagram of index structure

接下來，介紹構(gòu)建KMG-Tree時(shí)間復(fù)雜度。構(gòu)建KMG-tree索引需要遍歷所有的對象，構(gòu)建用戶索引首先遍歷所有用戶時(shí)間代價(jià)為O(|U|)，遍歷過程需要將用戶存儲(chǔ)到網(wǎng)格節(jié)點(diǎn)中。根據(jù)網(wǎng)格劃分得到個(gè)單元格，索引的高度為分裂與合并的時(shí)間代價(jià)為所以構(gòu)建用戶KMG-Tree 索引的總代價(jià)為O(|U|+同理構(gòu)建設(shè)施KMG-Tree索引的總代價(jià)為

3.3 基于Six-region-optimize的過濾算法

Six-region 算法在處理雙色反k查詢時(shí)，不僅沒有考慮關(guān)鍵字因素，而且只是對用戶進(jìn)行了過濾，這樣在驗(yàn)證用戶時(shí)需要遍歷整個(gè)設(shè)施R-tree。針對以上問題本文提出了基于Sixregion 改進(jìn)的過濾算法Six-region-optimize，該算法結(jié)合設(shè)施空間位置與關(guān)鍵字結(jié)合對用戶和設(shè)施進(jìn)行過濾。在介紹算法之前先介紹一個(gè)引理和一個(gè)定理。

引理1以查詢點(diǎn)q為中心將空間劃分為6 個(gè)相等區(qū)域，在區(qū)域i(i=0，1，…，5)中，找到距離設(shè)施q第k近的設(shè)施fk。以q為圓心、ri=dist(q，fk)為半徑做一個(gè)扇形seci，位于seci外面的用戶可以被過濾。

證明 在區(qū)域i(i=0，1，…，5)中，位于seci外面的任意用戶u的kNN一定不包含q，因?yàn)樵趕eci里面一定存在k個(gè)設(shè)施滿足dist(u，f) ＜dist(u，q)。

定理1以查詢點(diǎn)q為中心將空間劃分為6 個(gè)相等區(qū)域，在區(qū)域i(i=0，1，…，5)中，以q為圓心、2Ri為半徑做一個(gè)扇形SECi，位于SECi外面的設(shè)施可以被過濾。其中Ri為區(qū)域i及其相鄰區(qū)域中r的最大值。r是根據(jù)引理1 得到的每個(gè)區(qū)域的seci的半徑。

證明 在區(qū)域i(i=0，1，…，5)中，位于SECi外面的任意設(shè)施f一定不會(huì)影響查詢點(diǎn)q成為任何候選用戶u的kNN。因?yàn)槊總€(gè)區(qū)域中的任意候選用戶u一定滿足dist(q，u) ≤Ri，而位于i區(qū)域SECi外面的任意設(shè)施f一定滿足dist(f，u) ≥Ri。

接下來，介紹基于Six-region-optimize 的過濾算法。該算法過濾過程分為批量過濾和局部過濾。針對用戶的批量過濾，在遍歷用戶KMG-Tree 過程中根據(jù)定理1 對用戶在空間位置上進(jìn)行過濾，在區(qū)域i(i=0，1，…，5)中位于seci外面的網(wǎng)格節(jié)點(diǎn)可以直接被過濾。然后，根據(jù)關(guān)鍵字信息對用戶進(jìn)行過濾，沒有被直接過濾的網(wǎng)格節(jié)點(diǎn)t需要檢查該節(jié)點(diǎn)的關(guān)鍵字信息，如果t滿足t.k∩q.k=?，則t可以被直接過濾。針對用戶的局部過濾，訪問那些沒有被直接過濾網(wǎng)格節(jié)點(diǎn)的用戶，根據(jù)定理1 過濾掉那些在區(qū)域i(i=0，1，…，5)中位于seci外面的用戶。

例如圖3（a）所示，以查詢q為中心的整個(gè)空間被劃分為六個(gè)相等的扇形區(qū)域S0～S5。在區(qū)域S1和S2中，查詢點(diǎn)q的2近鄰設(shè)施分別為f4和f0，所以基于這兩個(gè)設(shè)施定義了這兩個(gè)區(qū)域的過濾空間，如圖中陰影部分。被陰影部分完全覆蓋的網(wǎng)格節(jié)點(diǎn)可以直接被過濾；被部分覆蓋的網(wǎng)格節(jié)點(diǎn)將訪問所包含的網(wǎng)格節(jié)點(diǎn)或用戶，并將位于過濾空間中的網(wǎng)格節(jié)點(diǎn)或用戶過濾。這樣一來，算法無需要遍歷所有用戶便可批量過濾掉不滿足要求的用戶。

針對設(shè)施的批量過濾，在遍歷設(shè)施KMG-Tree過程中根據(jù)定理1 對設(shè)施在空間位置上進(jìn)行過濾，在區(qū)域i(i=0，1，…，5)中位于SECi外面的網(wǎng)格節(jié)點(diǎn)可以直接被過濾。針對設(shè)施的局部過濾，訪問那些沒有被直接過濾網(wǎng)格節(jié)點(diǎn)的設(shè)施，根據(jù)定理1過濾掉那些在區(qū)域i(i=0，1，…，5)中位于SECi外面的設(shè)施。

例如圖3（b）所示，在區(qū)域S1和與其相鄰的兩區(qū)域S0與S2中，f4、f5和f0分別在各子區(qū)域中為查詢q的2 近鄰。它們滿足不等式dist(q，f0) ＞dist(q，f4) ＞dist(q，f5)。設(shè)R1=dist(q，f0)，在區(qū)域S1中以R1為半徑做扇形SEC1，SEC1定義了過濾空間，如圖中陰影部分。被陰影部分完全覆蓋的網(wǎng)格節(jié)點(diǎn)可以直接過濾；被部分覆蓋的網(wǎng)格節(jié)點(diǎn)將訪問所包含的網(wǎng)格節(jié)點(diǎn)或設(shè)施，并將位于過濾空間中的網(wǎng)格節(jié)點(diǎn)或設(shè)施進(jìn)行過濾。這樣一來，算法無需要遍歷所有設(shè)施便可批量過濾掉不影響候選用戶的設(shè)施。

圖3 空間屬性過濾用戶和設(shè)施Fig.3 Spatial attributes filtering users and facilities

基于Six-region-optimize 的過濾算法見算法1。利用兩個(gè)隊(duì)列分別緩存用戶節(jié)點(diǎn)和設(shè)施節(jié)點(diǎn)如算法1第2）行。對用戶進(jìn)行過濾，不能被過濾的用戶存儲(chǔ)到候選用戶集合R中如算法1的第2）～7）行。對設(shè)施進(jìn)行過濾，不能被過濾的設(shè)施存儲(chǔ)到驗(yàn)證集合V中如算法1中第8）～13）行。

算法1 基于Six-region-optimize的過濾算法。

輸入 查詢設(shè)施q，k值，用戶樹u?root和設(shè)施樹f?root，每個(gè)區(qū)域扇形半徑r；

輸出 集合R，集合V。

接下來，介紹Six-region-optimize 算法過濾階段的時(shí)間復(fù)雜度。該階段首先需要訪問設(shè)施KMG-Tree 索引進(jìn)行空間劃分，劃分需要的時(shí)間代價(jià)為O(log|V|)。然后，再同時(shí)訪問用戶和設(shè)施KMG-Tree索引，根據(jù)劃分空間對用戶和設(shè)施進(jìn)行過濾，該階段的時(shí)間代價(jià)為O(log|V|+log|U|)。整個(gè)過濾階段的總代價(jià)為O(2log|V|+log|U|)。

3.4 基于Six-region-optimize的驗(yàn)證算法

Six-region-optimize 的驗(yàn)證算法通過過濾得到候選集R中的每個(gè)用戶u進(jìn)行驗(yàn)證，如果用戶u同時(shí)滿足條件1）～3）時(shí)將用戶存儲(chǔ)到最終的結(jié)果集Result中。

1）用戶u與查詢設(shè)施q的關(guān)鍵字相似度Sim（q，u）≥φk。

2）以用戶u為圓心、dist（q，u）為半徑做一個(gè)圓，遍歷集合V中的設(shè)施，圓中的設(shè)施數(shù)量小于k。

3）dist（u，q）與dist（u，NN（u））的比值Ratio（q，u）≤φr。

以φk=0.3、φr=2 和k=2 為例說明一下。首先，計(jì)算候選用戶ui（i=0，1，…，3）與查詢設(shè)施q的關(guān)鍵字相似度Sim（q，ui），如表2 所示，Sim（q，u0）=0.71、Sim（q，u1）=0.63、Sim（q，u2）=0.09 和Sim（q，u3）=0.67，所以u2不是查詢結(jié)果。然后，檢查滿足關(guān)鍵字相似度要求的候選用戶的kNN是否包含查詢設(shè)施q，例如圖4所示，以u1為中心、dist（q，u1）為半徑的圓中有兩個(gè)設(shè)施f1和f6，所以u1不是查詢結(jié)果。u0和u3為q的R2NN。最后，計(jì)算dist（q，u0）與dist（u0，NN（u0））比值Ratio（q，u0）=0.7和dist（q，u3）與dist（u3，NN（u3））比值Ratio（q，u3）=2.5。u3不滿足條件，u0為查詢結(jié)果。

圖4 空間范圍驗(yàn)證用戶Fig.4 Spatial scope authenticating users

表2 關(guān)鍵字相似度和最近鄰距離比值Tab.2 Keyword similarity and nearest neighbor distance ratio

基于Six-region-optimize 的驗(yàn)證算法見算法2。訪問候選用戶集合R如算法2 中的第2）～3）行。驗(yàn)證關(guān)鍵字相似度是否滿足查詢條件如算法2 的第4）行。驗(yàn)證用戶的RkNN 是否包含查詢設(shè)施q，并計(jì)算是否滿足距離約束如算法2 的第5）～11）行。

算法2 基于Six-region-optimize的驗(yàn)證算法。

輸入 集合R和集合V，查詢設(shè)施q，k值，閾值φr和φk；

輸出 集合Result。

接下來，介紹Six-region-optimize 算法驗(yàn)證階段的時(shí)間復(fù)雜度。在算法的過濾階段已經(jīng)得到了候選集R和驗(yàn)證集V。假設(shè)候選集的大小為K，驗(yàn)證集的大小為2K。可以明確的是K?U，并且2K?V。驗(yàn)證階段需要或每個(gè)候選用戶發(fā)出一個(gè)布爾范圍查詢，每個(gè)布爾范圍查詢大概需要訪問2/3的驗(yàn)證集中的設(shè)施，所以該階段的時(shí)間復(fù)雜度為

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

4.1 實(shí)驗(yàn)準(zhǔn)備

實(shí)驗(yàn)的配置環(huán)境為:64 位Windows 10、操作系統(tǒng)，Java 編程語言，實(shí)驗(yàn)內(nèi)存為8 GB，CPU 為Intel Core i5-4460 處理器。采用的數(shù)據(jù)集如表3 所示，包括兩個(gè)真實(shí)數(shù)據(jù)集德國（GE）的部分地理位置信息和北京（BJ）的部分地理信息以及一個(gè)模擬地理位置的數(shù)據(jù)集（SD）。

表3 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息Tab.3 Statistical information of experimental datasets

4.2 結(jié)果分析

首先，對本文提出的DKRkNN 查詢與Ranked-RSKNN 查詢的返回結(jié)果進(jìn)行比較驗(yàn)證該查詢返回結(jié)果的有效性。然后，使用不同大小的數(shù)據(jù)集對本文提出的基于Six-regionoptimize的過濾驗(yàn)證算法進(jìn)行實(shí)驗(yàn)分析，將它與最基本的簡稱baseline 的算法和Stanoi 等［6］提出的Six-region 算法進(jìn)行對比，驗(yàn)證算法高效性。最后，通過改變參數(shù)的大小驗(yàn)證本文所提算法的穩(wěn)定性。

4.2.1 DKRkNN查詢的有效性分析

通過比較DKRkNN 查詢和Ranked-RSkNN 查詢在三個(gè)數(shù)據(jù)集上的返回結(jié)果數(shù)量分析DKRkNN查詢結(jié)果的有效性。如圖5 所示，設(shè)閾值φr=2 和φk=0.5，設(shè)置不同的k值為｛5，10，15，20，25｝。

圖5 不同k值時(shí)Ranked-RSKNN和DKRkNN返回用戶數(shù)量Fig.5 Number of returned users by Ranked-RSKNN and DKRkNN with different k values

通過圖5 可以發(fā)現(xiàn)，在不同數(shù)據(jù)集上，k值越大兩個(gè)算法返回對象數(shù)量差距越大，表明DKRkNN 查詢過濾掉的無效的對象越多，從而驗(yàn)證了DKRkNN查詢返回結(jié)果的有效性。

4.2.2 Six-region-optimize算法的效率分析

通過評估Six-region-optimize 算法、baseline 算法和Sixregion 算法在數(shù)據(jù)集大小不同時(shí)CPU 處理時(shí)間的消耗分析算法的效率。數(shù)據(jù)集的大小不同時(shí)實(shí)驗(yàn)結(jié)果如圖6 所示。由圖6可以看出，在德國（GE）數(shù)據(jù)集的大小為6 105時(shí)每個(gè)算法在時(shí)間上的消耗都非常低，Six-region 和Six-region-optimize 算法表現(xiàn)得都不是很優(yōu)秀。隨著數(shù)據(jù)集的大小不斷增加，例如在北京（BJ）數(shù)據(jù)集的大小為312 349 和模擬（SD）數(shù)據(jù)集的大小為600 000 時(shí)，很明顯baseline 算法在時(shí)間上的消耗明顯增加，而Six-region 和Six-region-optimize 算法時(shí)耗增加都不是很明顯，而Six-region-optimize 算法時(shí)間消耗是最小的，驗(yàn)證了Six-region-optimize算法的高效性。

圖6 數(shù)據(jù)集大小對不同算法時(shí)間消耗的影響Fig.6 Influence of dataset size on time consumption of different algorithms

4.2.3 Six-region-optimize算法的穩(wěn)定性分析

接下來，通過改變參數(shù)的值比較Six-region-optimize 算法、baseline 算法和Six-region 算法在三個(gè)不同數(shù)據(jù)集上的變化，分析各個(gè)參數(shù)對于每個(gè)算法的影響。

1）k值對各算法的影響。

該組實(shí)驗(yàn)設(shè)閾值φr=2 和閾值φk=0.5，設(shè)置不同的k值為｛5，10，15，20，25｝，三個(gè)算法分別在數(shù)據(jù)集GE、BJ 和SD 上的變化情況如圖7 所示。由圖7 可以看出，隨著k值增加三個(gè)算法在CPU 時(shí)間上的消耗都在增加，這是因?yàn)閗值越大滿足條件的用戶越多，從而過濾掉的數(shù)據(jù)就越少，需要驗(yàn)證的數(shù)據(jù)就越多。但是在數(shù)據(jù)集較大時(shí)，k值對Six-region 和Six-regionoptimize 算法的影響很小，表明了k值對這兩個(gè)算法影響很小，驗(yàn)證了算法的穩(wěn)定性。

圖7 k值對不同算法時(shí)間消耗的影響Fig.7 Influence of k value on time consumption of different algorithms

2）閾值φr對各算法的影響。

該組實(shí)驗(yàn)設(shè)k=5 和閾值φk=0.5，設(shè)置不同的φr值為｛1.5，2.0，2.5，3.0，3.5｝，三個(gè)算法分別在數(shù)據(jù)集GE、BJ 和SD 上的變化情況如圖8 所示。由圖8（a）可以看出，三個(gè)算法在數(shù)據(jù)集GE上都基本不受影響，這是因?yàn)閿?shù)據(jù)集GE非常小，距離閾值φr的變化對驗(yàn)證過程影響非常小，從而三個(gè)算法在CPU 時(shí)間上的消耗也比較穩(wěn)定。由圖8（b）～（c）可以看出，baseline 算法和Six-region 算法隨著閾值φr的增加在CPU 時(shí)間上的消耗也有較明顯增加，這是因?yàn)檫@兩個(gè)算法在過濾階段沒有將大量設(shè)施過濾掉，這樣使閾值φr增加時(shí)需要訪問的設(shè)施也會(huì)大量增加。Six-region-optimize 算法不會(huì)存在這樣的情況，該算法在過濾階段已經(jīng)把大量不影響結(jié)果的設(shè)施給過濾掉了，表明了Six-region-optimize 算法在CPU 時(shí)間消耗上的穩(wěn)定性。

圖8 閾值φr對不同算法時(shí)間消耗的影響Fig.8 Influence of threshold φr on time consumption of different algorithms

3）閾值φk對各算法的影響。

該組實(shí)驗(yàn)設(shè)k=5 和閾值φd=9 000，設(shè)置φk值為（0.2，0.3，0.4，0.5，0.6），三個(gè)算法分別在數(shù)據(jù)集GE、BJ和SD上的CPU時(shí)間消耗變化情況如圖9所示。

由圖9可以看出，隨著φk值的增加，三個(gè)算法的CPU 時(shí)間消耗基本無變化，這是因?yàn)殛P(guān)鍵字相似度只需要在驗(yàn)證階段計(jì)算一次。所以φk對三個(gè)算法都沒什么影響，表明三個(gè)算法都是非常穩(wěn)定的。

圖9 閾值φk對不同算法時(shí)間消耗的影響Fig.9 Influence of threshold φk on time consumption of algorithms

5 結(jié)語

本文研究了距離-關(guān)鍵字相似度約束的雙色反k近鄰查詢（DKRkNN）問題，并提出了一種基于多分辨率網(wǎng)格樹索引查詢處理框架。該框架根據(jù)區(qū)域劃分規(guī)定過濾區(qū)域，訪問多分辨率網(wǎng)格樹，得到用戶候選集和影響用戶成為查詢結(jié)果的設(shè)施，對候選用戶進(jìn)行驗(yàn)證，得到最終的結(jié)果集?；趦蓚€(gè)真實(shí)數(shù)據(jù)集和一個(gè)模擬數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性和高效性，表明所提框架能夠有效處理該查詢。但是隨著社會(huì)的發(fā)展，查詢的需求會(huì)越來越復(fù)雜，空間文本信息可能不再是以關(guān)鍵字的方式存在，有可能是一段文字。因此，未來的研究需要對空間文本做語義分析從而為用戶提供更高質(zhì)量的查詢體驗(yàn)。