面向不確定文本數(shù)據(jù)的余弦相似性查詢方法*

朱命冬，徐立新，申德榮，寇 月，聶鐵錚

1.河南工學(xué)院 計算機科學(xué)與技術(shù)系，河南 新鄉(xiāng) 453003

2.東北大學(xué) 計算機科學(xué)與工程學(xué)院，沈陽 110819

1 引言

隨著基于位置的服務(wù)、傳感器網(wǎng)絡(luò)、人臉識別、人工智能、數(shù)據(jù)挖掘等技術(shù)的流行，不確定數(shù)據(jù)在現(xiàn)實生活中廣泛存在。例如，溫度傳感器測量出一個地區(qū)溫度70%的概率為26℃，30%的概率為30℃，即一個事件都以一定的概率發(fā)生。而對不確定數(shù)據(jù)的管理中一個不可或缺操作是查詢操作，如查詢一個區(qū)域范圍內(nèi)平均溫度大于30℃的城市。因此不確定性的相似性查詢也被廣泛關(guān)注，如不確定性top-k，不確定性數(shù)據(jù)連接和不確定性最近鄰（nearest neighbor，NN）等[1-6]。隨著云計算技術(shù)的成熟和處理大數(shù)據(jù)需求的加劇，分布式計算和云平臺下算法的研究成為一種趨勢。

隨著數(shù)據(jù)類型多樣化和復(fù)雜化，互聯(lián)網(wǎng)中出現(xiàn)了大量的不確定性文本數(shù)據(jù)。例如對互聯(lián)網(wǎng)中的圖書進行分類時，從不同網(wǎng)站抽取到的同一本書的摘要信息可能是不同的。假設(shè)有一本書Book1,從4個網(wǎng)站抽取到的摘要為A11,從6個網(wǎng)站抽取到的摘要為A12,則這本書的摘要以不確定性的形式可以描述為{＜A11,0.4＞,＜A12,0.6＞}, 即Book1={＜A11,0.4＞,＜A12,0.6＞},可設(shè)第二本書的摘要信息為Book2={＜A21,0.5＞,＜A22,0.5＞}。那么在計算Book1和Book2這兩本書的類別時，不僅僅要計算兩本書的摘要內(nèi)容，還要考慮兩本書的摘要權(quán)重。再如，對圖書網(wǎng)站的評價信息進行抽取時，每一個書評都有其支持度，如圖1是《史蒂夫?喬布斯傳》的一條書評，對應(yīng)每個書評都有“有用”或“喜歡”點擊數(shù)，代表該書評的支持度。每本書都有許多書評，每個書評都有一個支持度，很明顯所有的書及其書評組成一個巨大的不確定性文本數(shù)據(jù)集。同樣的，在微博網(wǎng)站中,每條微博都有點贊數(shù)量和轉(zhuǎn)發(fā)數(shù)量，根據(jù)這些數(shù)量可以計算出某個微博的支持度。這些文本和對應(yīng)的支持度組成了不確定性文本數(shù)據(jù)集。通過這個數(shù)據(jù)集可以查找潛在的朋友，這會比單純比較用戶屬性更全面。類似的應(yīng)用還有通過影評找相似的電影，通過餐館的評價找相似的餐館等。并且面向不確定文本數(shù)據(jù)基于余弦相似度的相似性查詢在組合推薦、實體識別、數(shù)據(jù)集成等領(lǐng)域都具有廣泛應(yīng)用。例如在讀書網(wǎng)站豆瓣網(wǎng)上，人們傾向于閱讀書評，從而獲得有共同愛好的朋友或者找到和自己讀過的書比較類似的書。當(dāng)數(shù)據(jù)集比較大時，這些應(yīng)用都需要一種高效的面向大規(guī)模不確定性文本數(shù)據(jù)集的相似性查詢方法。

Fig.1 Areview and support rate of“Steve Jobs”圖1《史蒂夫?喬布斯傳》的一條書評及其支持度

從信息檢索領(lǐng)域的理論和實踐可知，對文本進行分類（例如網(wǎng)頁分類，評論的情感分類）常用方法是先將文本轉(zhuǎn)化為TF-IDF向量，然后通過計算對應(yīng)向量的余弦距離得出文本之間的相似性[7]。余弦相似度考慮了文本本身的詞頻和全局詞頻等信息，以及信息論對TF-IDF的理論支持[8]，將文本型的相似匹配轉(zhuǎn)化為數(shù)值型的矩陣計算，使其在計算長文本的相關(guān)性和相似性時具有更好的嚴(yán)密性和有效性[9-10]。

本文面向不確定文本數(shù)據(jù)，研究基于余弦相似度的分布式最近鄰查詢方法，目標(biāo)是提出一種解決方案。一方面該方法需要提高查詢準(zhǔn)確度和效率；另一方面該方法需要基于分布式環(huán)境處理大規(guī)模數(shù)據(jù)集?；谟嘞揖嚯x計算不確定性文本的相似性主要優(yōu)勢有：

（1）余弦相似度的計算TF-IDF的理論支持[8]，將文本型的相似匹配轉(zhuǎn)化為數(shù)值型的矩陣計算，在整合計算不確定性數(shù)據(jù)的權(quán)重的過程中，純數(shù)據(jù)的計算比混合數(shù)據(jù)和文本的計算效率更高。

（2）目前大數(shù)據(jù)的應(yīng)用需求普遍存在，通過對余弦相似距離構(gòu)建索引，可以支持面向大規(guī)模數(shù)據(jù)的分布式環(huán)境下的k近鄰(k-nearest neighbor,kNN）、逆向k近鄰(reversek-nearest neighbor,RkNN）等復(fù)雜查詢。

本文提出基于余弦相似度的分布式環(huán)境下的不確定相似性查詢方法及最近鄰查詢算法，并給出面向度量空間的逆向最近鄰查詢算法。本文的主要貢獻(xiàn)可概括如下：

（1）通過分析不確定文本數(shù)據(jù)的余弦相似度計算的特征，提出了高效的相似度計算方法和改進的索引結(jié)構(gòu)sMVP-tree（statistic multiple vantage point tree）。

（2）通過對余弦距離進行轉(zhuǎn)化，提出了一種基于sMVP-tree的相似性查詢方法UnCos（uncertain cosine similarity）。

（3）給出了基于sMVP-tree的查詢過濾方法，然后在UnCos的基礎(chǔ)上提出了分布式kNN查詢算法，以及面向度量空間的RkNN查詢過濾方法。

（4）通過大量實驗驗證了本文算法的有效性。

本文組織結(jié)構(gòu)如下：第2章給出了相關(guān)工作；第3章介紹了預(yù)備知識和本文使用的數(shù)據(jù)模型；第4章詳細(xì)描述了本文提出的查詢方法UnCos；第5章提出了分布式查詢處理算法；第6章給出實驗結(jié)果與分析；第7章對全文進行總結(jié)，并指出進一步的工作方向。

2 相關(guān)研究

近年來，面向不確定數(shù)據(jù)的相似性查詢引起了廣泛的關(guān)注，根據(jù)研究對象大致可將現(xiàn)有研究分為兩類：針對數(shù)值型數(shù)據(jù)的方法[11-16]和針對文本型數(shù)據(jù)的方法[17-21]。

在針對數(shù)值型數(shù)據(jù)的方法中，文獻(xiàn)[11]針對不確定數(shù)值型數(shù)據(jù)進行研究，分別在歐式距離、歐式平方距離和直角距離的條件下提出了查詢期望最近鄰（expected nearest neighbor，ENN）的計算方法，這些方法只需要構(gòu)建線性大小的索引就可以在綜合對數(shù)或次線性時間代價內(nèi)計算出ENN。文獻(xiàn)[12]提出了查詢非零概率最近鄰數(shù)據(jù)對象的高效算法，提出了預(yù)估一個數(shù)據(jù)對象是查詢的最近鄰的概率的方法，分別給出了返回最大似然估計的最近鄰和返回大于一定概率的最近鄰的算法。文獻(xiàn)[13]提出了在歐式距離條件下面向不確定數(shù)據(jù)的相似性查詢方法，該方法可以返回用戶指定概率閾值內(nèi)的kNN查詢。為了處理大規(guī)模高維數(shù)據(jù)，文獻(xiàn)[14]通過將空間和時間信息整合構(gòu)建統(tǒng)一索引的基礎(chǔ)上提出了一種快速的kNN查詢算法。文獻(xiàn)[15]提出了一種概率逆向kNN(probabilistic RkNN,PRkNN)的查詢框架，然后基于已有的空間過濾法給出了有效的概率過濾準(zhǔn)則，將空間過濾、概率過濾和概率確認(rèn)方法整合起來提出了新的PRNN算法和PRkNN算法。文獻(xiàn)[16]對現(xiàn)有的基于歐式距離計算路網(wǎng)kNN查詢方法在內(nèi)存中計算效果進行了詳細(xì)比較，提出了改進的增量歐式限制（incremental Euclidean restriction，IER）方法。但現(xiàn)有方法的RkNN查詢過濾方法多針對歐式空間，不適用于度量空間，本文提出的RkNN算法可以有效處理度量空間的數(shù)據(jù)。

在針對文本型數(shù)據(jù)的方法中，文獻(xiàn)[17]提出了面向無結(jié)構(gòu)文本的相似性查詢方法，該方法通過有效的詞組劃分過濾不相關(guān)的數(shù)據(jù)對象。但該方法需要預(yù)先查詢閾值進行查詢過濾。文獻(xiàn)[18]提出了在編輯距離條件下面向不確定性字符串的相似連接方法。該方法引入了字符串級不確定性模型和字符級不確定性模型，并基于概率q-gram提出了上界過濾器和下界過濾器，從而提高相似字符串識別效率。文獻(xiàn)[19]提出了一種面向近似近鄰查詢的分布式哈希學(xué)習(xí)方法 SparkPQ（spark product quantization）。SparkPQ基于一種按行列劃分的分布式矩陣，采用分布式K-Means算法實現(xiàn)模型求解和碼本訓(xùn)練，利用訓(xùn)練出的碼本模型對分布式數(shù)據(jù)進行編碼和索引，最終通過Spark分布式框架實現(xiàn)近似近鄰查詢系統(tǒng)。Wang等人提出了可以適用于余弦相似度的不確定性文本類型的相似連接方法[20]。該方法通過字符串特征生成策略對候選查詢結(jié)果進行過濾，但該方法需要預(yù)先設(shè)置不確定性閾值，閾值大小很難準(zhǔn)確地設(shè)定使其適合各種場景。現(xiàn)有的針對不確定性文本型數(shù)據(jù)的相似性查詢方法多是集中式方法，文獻(xiàn)[3,21]提出了基于MapReduce的不確定性相似性查詢方法。文獻(xiàn)[3]的方法主要是基于Jaccord距離對兩個集合進行相似性連接。與本文最相關(guān)的是文獻(xiàn)[21]提出的方法，文獻(xiàn)[21]利用Voronoi結(jié)構(gòu)將相似的數(shù)據(jù)對象映射到同一個節(jié)點進行相似性查詢處理，本文在實驗部分和此方法進行了詳細(xì)的比較。

3 預(yù)備知識

本章介紹所使用的基本概念和數(shù)據(jù)結(jié)構(gòu)。

字符串相似度函數(shù)主要用于衡量兩個字符串之間的相似度，可大致分為兩類：面向詞組的相似度方法和面向字符的相似度方法。面向詞組的方法有余弦相似度方法、Dice相似度方法和Jaccard相似度方法等；面向字符的方法有編輯距離方法、Q-gram方法和Smith-Waterman算法等。本文主要分析基于余弦相似度的計算方法。余弦相似度是通過測量兩個向量內(nèi)積空間的夾角的余弦值來度量它們之間的相似性。如果兩個向量的方向是一樣的，則它們之間的余弦相似度是1，如果兩個向量的方向是垂直的，則它們之間的余弦相似度是0。

余弦相似度多用在高維正向量空間中。比如在信息檢索和數(shù)據(jù)挖掘領(lǐng)域，一般一個詞條被認(rèn)為是一個維度，一篇文檔可以被看作一個多維的向量，向量值代表對應(yīng)詞條在這篇文檔中的重要度。已知兩個字符串s1和s2的向量s1和s2，則s1和s2的余弦相似度是[22]：

TF-IDF是將字符串轉(zhuǎn)化為向量的常用方法，TF是指一個詞條t在一篇文檔s中出現(xiàn)的次數(shù)，記為tft,s。直觀地說，一個詞條的頻度越大，該詞條在文檔中的重要性就越高。但是有的詞條在別的文檔中也普遍存在，不具有區(qū)分度。比如一個汽車公司的文檔，幾乎每篇文檔中都有“汽車”這個詞。因此一種衡量一個詞條是否具有區(qū)分度的概率被提出來了。一個詞條t的IDF計算方法是：idft=lb(N/dft),其中dft是指包含詞條t的文檔數(shù)，N是總的文檔數(shù)量。整合兩個概念后，詞條t在文檔s中的TF-IDF為：tfidf(t,s)=tft,s×idft,通過TF-IDF可以計算出詞條在文檔中的權(quán)重。

定義1（度量空間距離函數(shù)）設(shè)D是一個數(shù)據(jù)對象域，任意x,y∈D,如果距離函數(shù)d(x,y)滿足以下條件，則d(x,y)是度量空間距離函數(shù)[23]：

面向度量空間的索引方法是通過數(shù)據(jù)對象之間的距離進行查詢過濾，對于索引方法，數(shù)據(jù)對象的內(nèi)容及距離計算函數(shù)則是黑盒（black-box）。在面向度量空間的索引方法中，MVP-tree（multiple vantage point tree）是較好的常用方法之一[23]。

MVP-tree是一種基于VP-tree的改進索引方法。主要面向如下兩方面進行改進：（1）數(shù)據(jù)空間外部的樞紐點可以對數(shù)據(jù)空間進行劃分，而且在索引中的不同層可以共享樞紐點。這樣，一方面可以減少計算代價，另一方面可以對數(shù)據(jù)空間進行更好的劃分。（2）索引的構(gòu)建過程中，葉子節(jié)點中的數(shù)據(jù)對象保存了從根節(jié)點到該葉子節(jié)點中樞紐的距離。在查詢處理過程中通過這些距離可以減少計算代價，從而提高查詢效率。

根據(jù)文獻(xiàn)[23]，可以得出關(guān)于MPV-tree的一個引理。

引理1構(gòu)建MVP-tree的計算代價是O(nlogmn),其中m是索引節(jié)點的出度，n為數(shù)據(jù)對象的個數(shù)。基于MVP-tree進行等值查詢的計算復(fù)雜度是O(logmn)。

下面給出本文的數(shù)據(jù)模型。

數(shù)據(jù)模型：一個不確定數(shù)據(jù)對象p是由字符串集S={s1,s2,…,sl}和對應(yīng)的一個集合W={w1,w2,…,wl}組成，其中wi是對應(yīng)si的支持度，wi∈[0,1]且。用d表示兩個字符串的余弦距離函數(shù)，即對于任意兩個字符串s1和s2,d(s1,s2)=1-CS(s1,s2),其中s1和s2分別是字符串s1、s2的TF-IDF向量，CS是余弦相似度函數(shù)。給定余弦距離函數(shù)d,兩個不確定數(shù)據(jù)對象p1和p2的期望距離是：

其中，l1和l2分別是數(shù)據(jù)對象p和q中的字符串個數(shù)。

定義2（期望k最近鄰）設(shè)P={p1,p2,…,pn}是包含n個不確定性數(shù)據(jù)對象的數(shù)據(jù)集，對于一個不確定性對象q,q在數(shù)據(jù)集P中的期望最近鄰是ENN(q,P)=argminp∈PED(q,p),q的期望k最近鄰(expectedkNN,EkNN)是本文在不產(chǎn)生歧義的情況下EkNN被簡寫為kNN。

定義3（逆向期望k最近鄰）給定一個不確定性對象q,q的逆向期望k最近鄰(reverse EkNN,REkNN)是REkNN(q,P)={p∈P|q∈EkNN(p,P)}。本文在上下文清晰的情況下REkNN被簡寫為RkNN。

4 查詢方法UnCos

本章分析基于不確定性文本數(shù)據(jù)余弦相似度計算的特性，提出面向不確定性文本數(shù)據(jù)基于余弦相似度的查詢方法UnCos。UnCos的構(gòu)建是基于MVP-tree的改進索引sMVP-tree，在給出UnCos方法之前，首先介紹改進的MVP-tree，稱為sMVP-tree。

sMVP-tree的構(gòu)建過程與MVP-tree的構(gòu)建過程基本類似，主要區(qū)別在于sMVP-tree的構(gòu)建過程中每個索引節(jié)點的分支都保留對應(yīng)孩子節(jié)點所屬數(shù)據(jù)對象的距離統(tǒng)計直方圖，直方圖表示為histogram(Ni),索引節(jié)點Ni是第i個索引節(jié)點。如圖2所示是索引節(jié)點N3中樞紐點p1對孩子節(jié)點N4中數(shù)據(jù)對象的距離直方圖histogram(N4)，其中x軸代表距離的劃分區(qū)間，y軸代表對應(yīng)區(qū)間內(nèi)數(shù)據(jù)對象個數(shù)。sMVP-tree的構(gòu)建過程如算法1所示，首先構(gòu)造一個索引節(jié)點（第1行），從數(shù)據(jù)集中隨機選擇一個數(shù)據(jù)對象，計算出該數(shù)據(jù)對象和其他數(shù)據(jù)對象距離的中位數(shù)，并根據(jù)該中位數(shù)將數(shù)據(jù)集分成兩部分DS1和DS2（第2～4行），用同樣的方法將數(shù)據(jù)集進一步劃分為四部分DS11、DS12、DS21、DS22（第5～9行）。在計算距離中位數(shù)的過程中將四部分的距離直方圖保存在索引節(jié)點中（第10行）。然后對這四部分遞歸調(diào)用構(gòu)建sMVP-tree算法，直到不可再分，并返回結(jié)果（第11～12行）。

Fig.2 Space partition of sMVP-tree圖2 sMVP-tree結(jié)構(gòu)示意圖

算法1sMVP-tree構(gòu)建算法sMVP

輸入：數(shù)據(jù)集DS

輸出：sMVP-tree

1.創(chuàng)建根索引節(jié)點in

2.P1←從數(shù)據(jù)集DS中隨機選擇一個數(shù)據(jù)對象

3.M1←對于所有ds∈D計算距離d(P1,ds)并得出中位數(shù)

4.根據(jù)M1將DS劃分為兩個集合DS1和DS2

5.P2←從數(shù)據(jù)集DS2隨機選擇一個數(shù)據(jù)對象

6.M11←對于所有ds∈DS1計算距離d(P2,ds)并得出中位數(shù)

7.M12←對于所有ds∈DS2計算距離d(P2,ds)并得出中位數(shù)

8.DS1被M11劃分為DS11和DS12

9.DS2被M12劃分為DS21和DS22

10.將樞紐數(shù)據(jù)對象(P1,P2)存入索引節(jié)點in中，并且為集合(P1,P2,DS11),(P1,P2,DS12),(P1,P2,DS21),(P1,P2,DS22)構(gòu)建距離直方圖并存入索引節(jié)點in中

11.遞歸調(diào)用sMVP(DS11),sMVP(DS12),sMVP(DS21),sMVP(DS22)生成索引節(jié)點in的子節(jié)點直到葉子節(jié)點

12.返回in

根據(jù)算法1，sMVP-tree的計算復(fù)雜度同MVP-tree一樣，多了存儲直方圖的空間復(fù)雜度，因此可以得出引理2。

引理2構(gòu)建sMVP-tree的計算復(fù)雜度為O(nlogmn),m是索引節(jié)點的出度，空間復(fù)雜度為

根據(jù)樞紐點的直方圖可以計算出指定距離段的數(shù)據(jù)對象數(shù)量，定義該函數(shù)為NumHist(Ni,dist1,dist2),其中dist1和dist2是距離區(qū)間，Ni是索引節(jié)點i。如果Ni是根節(jié)點，則需要對整個索引樹的直方圖進行計算。

基于sMVP-tree索引結(jié)構(gòu)，提出基于余弦相似度的查詢方法UnCos。UnCos主要分為兩部分：第一部分是索引構(gòu)建部分，在不確定數(shù)據(jù)集上構(gòu)建sMVP-tree。該部分通過分析不確定性余弦相似度計算的理論特征，給出了高效的相似度計算方法。第二部分是查詢處理，基于sMVP-tree進行相似性查詢。該部分給出了有查詢質(zhì)量保證的查詢方法，并給出了計算復(fù)雜度理論分析。下面將對這兩部分分別進行詳細(xì)的介紹。

4.1 索引構(gòu)建

設(shè)P={p1,p2,…,pn},pi={＜si1,wi1＞,＜si2,wi2＞,…,＜sil,wil＞},為了計算不確定字符串間的余弦相似度，將每個字符串視為一個文檔，然后計算該文檔的TF-IDF向量。令pi={＜si1,wi1＞,＜si2,wi2＞,…,＜sil,wil＞},其中s即對應(yīng)字符串s的TF-IDF向量。根據(jù)式（1）即可計算出不確定字符串間的基于余弦相似度的期望距離。通過分析不確定性余弦相似度的特性，可以給出更快的計算方法，見定理1。

定理 1設(shè)，則對于任意pi,pj∈P,

證明根據(jù)式（1），又 因 為因此可以得出ED(pi,pj)=定理1得證。 □

通過定理1，不確定性的余弦相似度計算的復(fù)雜度可以從O(l2d)減少為O(ld),其中d為TF-IDF向量的維度。

sMVP-tree可以有效地適用于度量空間的最近鄰查詢，但余弦相似度的計算不屬于度量空間。為了有效使用sMVP-tree，首先需要將余弦相似度等價轉(zhuǎn)化為角度相似度。兩個字符串s1和s2的角度相似度轉(zhuǎn)化公式如下：

則s1和s2的角度距離可表示為AD(s1,s2)=1-AS(s1,s2)。下面引理3給出了將余弦相似度轉(zhuǎn)化為角度相似度的合理性。

引理3對于任意的不確定對象q∈P,q的角度相似度的最近鄰即為q的余弦相似度最近鄰。

證明使用反證法，已有一個數(shù)據(jù)對象q∈P,設(shè)p*是q的角度相似度的最近鄰，但不是q的余弦相似度最近鄰，則根據(jù)式（1），存在數(shù)據(jù)對象p,使得：

又因為對任意p∈P,ED(q,p*)≤ED(q,p),即：

因此至少有一對字符串使得：

令x=CS(q,p),則因為F(x)是單調(diào)增函數(shù)，所以對?x1＜x2,F(x1)＜F(x2)。根據(jù)式（3），F(xiàn)(CS(q.si,p?.sj))＜F(CS(q.si,p.sk)),這與式（4）沖突，從而引理3成立。 □

參照引理2，在不確定數(shù)據(jù)集上的一個sMVP-tree可以以O(shè)(ndlogmn+ndl)計算復(fù)雜度計算出來，其中d是TF-IDF向量的維度，O(ndl)是計算不確定性數(shù)據(jù)對象期望的計算復(fù)雜度。

4.2 查詢處理

構(gòu)建好sMVP-tree后，當(dāng)有不確定性最近鄰查詢q時，首先計算出q的平均點qˉ，然后在構(gòu)建好的sMVP-tree中查詢qˉ的最近鄰，最后將qˉ的最近鄰返回作為q的查詢結(jié)果。具體算法見算法2。

算法2UnCos查詢算法

輸入：查詢q和sMVP-tree

輸出：q的最近鄰查詢結(jié)果

1.計算出q的平均點qˉ

2.根據(jù)索引節(jié)點中的樞紐數(shù)據(jù)對象，從根節(jié)點開始計算與qˉ距離最小的孩子索引節(jié)點qnode

3.如果qnode不是葉子節(jié)點，迭代查找與qˉ距離最小的孩子索引節(jié)點

4.如果qnode是葉子節(jié)點，則查找葉子節(jié)點中與qˉ距離最小的數(shù)據(jù)對象最近鄰

5.返回最近鄰

為了保證查詢結(jié)果的正確性，提出了引理4。

引理4q為一個不確定性查詢數(shù)據(jù)對象，在sMVP-tree中和qˉ的最近鄰即是數(shù)據(jù)對象q的ENN。

證明根據(jù)定理1和引理3，此引理易得證。 □

因此，可以通過O(ndlogmn+ndl)的計算復(fù)雜度計算出不確定數(shù)據(jù)對象集的sMVP-tree。當(dāng)給定 一個不確定查詢數(shù)據(jù)對象q，以O(shè)(ld)計算出q的 平均點q，因為最近鄰查詢是由兩次范圍查詢組成且 以第二次計算復(fù)雜度高于第一次，所以可以以在sMVP-tree中找出qˉ的最近鄰點并返回結(jié)果。其中m為索引樹的出度，r為查詢的平均選擇度，h為sMVP-tree的高度。因此可以得出定理2。

定理2P為一個不確定性數(shù)據(jù)集，以O(shè)(ndlogmn+ndl)的計算復(fù)雜度在P上構(gòu)建sMVP-tree，從而可以以的時間復(fù)雜度處理基于余弦相似度的不確定性最近鄰查詢。

5 分布式查詢處理算法

當(dāng)數(shù)據(jù)集比較大時，如定理2所示算法的計算復(fù)雜度會比較高，因此為了有效處理大規(guī)模數(shù)據(jù)集，本章將算法擴展到分布式環(huán)境下，提出分布式kNN算法和分布式RkNN算法。

分布式算法是基于分而治之的思想，如圖3所示，P2P分布式系統(tǒng)中各個計算節(jié)點是相互獨立并自治的。設(shè)C是計算節(jié)點的數(shù)量，PV是數(shù)據(jù)集的樞紐點集，PV={pvi},其中1≤i≤pn,pn是樞紐點數(shù)量。PV作為全局信息存儲在各個計算節(jié)點上，每個計算節(jié)點負(fù)責(zé)一個或多個樞紐點，數(shù)據(jù)對象根據(jù)數(shù)據(jù)對象與樞紐點的距離被劃分到各個計算節(jié)點上，然后各個計算節(jié)點在本地構(gòu)建sMVP-tree。

當(dāng)有計算節(jié)點接收一個不確定性數(shù)據(jù)對象為q,查詢范圍為R的查詢后，該計算節(jié)點會充當(dāng)協(xié)調(diào)者，并通過式（5）計算相關(guān)的樞紐點：

Fig.3 Data flow of distributed algorithm圖3 分布式算法的數(shù)據(jù)流圖

其中maxdi是pvi維護的數(shù)據(jù)對象中最大的距離。然后協(xié)調(diào)者會轉(zhuǎn)發(fā)查詢到相關(guān)的樞紐點所在的計算節(jié)點上，各個計算節(jié)點通過本地sMVP-tree計算出查詢結(jié)果并返回給協(xié)調(diào)者。最后協(xié)調(diào)者收集中間查詢結(jié)果并返回最終結(jié)果給用戶。很明顯樞紐點的選擇和查詢算法是系統(tǒng)性能的關(guān)鍵點，接下來具體討論這兩點。

5.1 數(shù)據(jù)劃分樞紐點的選擇

（1）樞紐點的選擇。樞紐點的主要作用是在查詢過程中過濾不相關(guān)的數(shù)據(jù)對象，因此選擇樞紐點的指標(biāo)是盡可能增加查詢的過濾能力。在度量空間中一般選擇較遠(yuǎn)的樞紐點[24]，基于這種啟發(fā)式方法，提出了與文獻(xiàn)[23]類似的樞紐點選擇方案：

①從樣本數(shù)據(jù)集中隨機選擇一個數(shù)據(jù)對象o；

②將樣本數(shù)據(jù)集中距離o最遠(yuǎn)的數(shù)據(jù)對象放到樞紐點集PV中；

③將樣本數(shù)據(jù)集中和PV中樞紐點平均距離最大的數(shù)據(jù)對象加入到PV中；

④重復(fù)上一步工作直到|PV|=pn。

（2）查詢敏感的負(fù)載均衡。在分布式環(huán)境中用一致性哈希對樞紐點進行維護和管理，即樞紐點被劃分在[0,2max]域上，[0,2max]被劃分成多個區(qū)間（token），每個計算節(jié)點負(fù)責(zé)一個或多個區(qū)間，查詢在系統(tǒng)中通過分布式哈希表進行路由。使用較好的哈希方法如SHA1，樞紐點可以均勻地劃分在各個計算節(jié)點上。但是查詢往往不是均勻分布的，而且分布會發(fā)生動態(tài)變化，因此為了達(dá)到系統(tǒng)的負(fù)載均衡，需要一種查詢敏感的調(diào)整方法。首先為負(fù)載均衡設(shè)置閾值t，如果一個計算節(jié)點（NodeA）超過平均負(fù)載的t倍，即NodeA成了查詢熱點，則NodeA與其負(fù)責(zé)區(qū)域相鄰的計算節(jié)點（NodeB）進行通信，減少NodeA負(fù)責(zé)的區(qū)域并增加NodeB負(fù)責(zé)的區(qū)域，并將相應(yīng)的樞紐點從NodeA移動到NodeB上。在這個過程中如果別的計算節(jié)點產(chǎn)生了負(fù)載失衡，則對該計算節(jié)點重復(fù)這個過程直到實現(xiàn)系統(tǒng)的負(fù)載均衡。注意為了避免發(fā)生抖動（thrash）現(xiàn)象，負(fù)載調(diào)整方法要以同一個方向進行。

（3）樞紐點的數(shù)量pn的選擇。查詢處理的計算時間可以分為兩部分：一部分是根據(jù)樞紐點計算相關(guān)計算節(jié)點的時間gt；另一部分是各個計算節(jié)點進行本地查詢的計算時間lt。因此查詢處理的計算時間ct=gt+lt。很明顯，相關(guān)計算節(jié)點的計算時間gt和樞紐點數(shù)量pn成正比，即gt=α×pn,α是系數(shù)比，α的取值和計算節(jié)點的處理性能有關(guān)；而本地查詢的計算時間lt和pn成反比，在平均情況下，其中r是查詢對索引樹孩子節(jié)點的平均選擇度，m是索引樹的出度，N是數(shù)據(jù)集的大小，β是系數(shù)比，β由計算節(jié)點的平均處理性能決定。因此可以得出ct的計算公式：

通過求導(dǎo)并計算極值可以得出，當(dāng)式（7）滿足時：

ct取最小值。通過式（7）可以計算出合適的樞紐點數(shù)量。

5.2 分布式查詢算法

如本章開篇所述，在該分布式查詢模型中利用式（5）易于處理范圍查詢。下面討論兩種復(fù)雜查詢處理算法：最近鄰查詢算法和逆向最近鄰查詢算法。

5.2.1 kNN查詢

先考慮簡單情況，k=1時，即為1NN查詢，當(dāng)一個計算節(jié)點接收到一個數(shù)據(jù)對象為q的1NN查詢后，該計算節(jié)點作為調(diào)度者首先以q為查詢對象，0為查詢半徑發(fā)起查詢，計算相關(guān)的樞紐點，即計算出樞紐點集PS={pni|ED(pni,q)≤maxdi},其中maxdi是樞紐節(jié)點pni與其維護最遠(yuǎn)數(shù)據(jù)對象的距離。然后調(diào)度者將查詢轉(zhuǎn)發(fā)給負(fù)責(zé)PS集中數(shù)據(jù)對象的計算節(jié)點（表示為CS），各個計算節(jié)點計算數(shù)據(jù)對象q在本地的最近鄰并返回給調(diào)度者。調(diào)度者接收到所有候選最近鄰后，計算出與q距離最小的數(shù)據(jù)對象，設(shè)mind是最小距離。之后，調(diào)度者以q為查詢對象，mind為查詢范圍計算出相關(guān)的樞紐點，向負(fù)責(zé)這些樞紐點除了CS集的計算節(jié)點，轉(zhuǎn)發(fā)最近鄰查詢。最后，調(diào)度者收集候選數(shù)據(jù)對象計算出最近鄰，返回給用戶。

下面介紹kNN查詢算法，具體過程如算法3所示。首先根據(jù)統(tǒng)計直方圖預(yù)估出初始查詢距離initR,并計算出相關(guān)的計算節(jié)點（第1行），對于一個查詢對象為q的kNN查詢，q與各個樞紐點的距離是qdisti=ED(pni,q),令：

其中，NumHist是第5章定義的直方圖中數(shù)據(jù)對象計算函數(shù)。然后將查詢轉(zhuǎn)發(fā)給相關(guān)的計算節(jié)點集CS1,各個計算節(jié)點計算出本地的kNN數(shù)據(jù)對象作為候選集返回給調(diào)度者，調(diào)度者從所有的候選數(shù)據(jù)對象中計算出最小的kNN候選數(shù)據(jù)對象的距離mind,并計算出查詢范圍為mind時相關(guān)計算節(jié)點CS2（第2～6行），向計算節(jié)點集CS1-CS2轉(zhuǎn)發(fā)請求，并收集各個計算節(jié)點本地的kNN候選數(shù)據(jù)對象，計算出最終的kNN結(jié)果并返回（第7～11行）。

kNN查詢算法也是使用兩個范圍查詢實現(xiàn)的，但主要區(qū)別是在第一個范圍查詢時，kNN使用樞紐點中sMVP-tree匯總的直方圖信息可以預(yù)估出更好的查詢范圍initR。initR可以對k個最近鄰的數(shù)據(jù)對象有較好的估計，從而有效降低第二次范圍查詢的代價。

根據(jù)算法3的計算過程，kNN查詢算法的通信代價由三部分組成：第一部分是收集預(yù)估initR的信息，通信代價為O(pn),其中pn為樞紐點數(shù)量。第二部分是根據(jù)查詢半徑mind計算出的相關(guān)計算節(jié)點，通信代價為O(pn)。第三部分是各個計算節(jié)點返回的查詢結(jié)果，通信代價為O(k)。因此可得出kNN查詢算法的通信代價為O(2pn+k)。

算法3kNN查詢算法

輸入：查詢q和整數(shù)k

輸出：q的kNN查詢結(jié)果

1.根據(jù)式（8）計算出initR，進而計算出相關(guān)的計算節(jié)點CS1

2.將查詢q和查詢半徑initR轉(zhuǎn)發(fā)給CS1

3.candity←各個計算節(jié)點y∈CS1，計算出本地的k最近鄰

4.candit1←匯總所有candity信息，計算出候選的kNN

5.mind←計算出candit1中數(shù)據(jù)對象與q最遠(yuǎn)的距離

6.CS2←根據(jù)式（5）計算出查詢半徑為mind時的相關(guān)計算節(jié)點

7.將查詢q轉(zhuǎn)發(fā)給計算節(jié)點集{CS2-CS1}

8.candity←各個計算節(jié)點y∈CS2,計算出本地的kNN

9.candit2←匯總所有candity,計算出候選的kNN

10.finalkNN←匯總candit1和candit2,計算出最終的kNN

11.ReturnfinalkNN

5.2.2 RkNN查詢

RkNN也是常用的相似性查詢之一，但需要消耗更多的計算代價。在歐式空間中，可以利用空間劃分的特性[25]對RkNN構(gòu)建索引并進行有效的過濾。但在度量空間中，只能使用數(shù)據(jù)對象之間的距離過濾數(shù)據(jù)對象，而沒有方向性等輔助信息，這使得RkNN查詢代價非常高。一個容易想到的簡單方法（SimM）是：首先對數(shù)據(jù)集進行預(yù)處理，并計算出各個數(shù)據(jù)對象的kNN,對應(yīng)于每個數(shù)據(jù)對象p存儲一個列 表 {＜1,d1＞,＜2,d2＞,…,＜i,di＞,＜2i,d2i＞,…,＜lbn,dlbn＞},其中di是數(shù)據(jù)對象p和iNN之間的距離，n是數(shù)據(jù)集的大小。假設(shè)有一個RkNN查詢q,對于數(shù)據(jù)對象p,如果滿足ED(o,p)≤d2i,其中i=argmini(i＜k≤2i),則p可能是q的查詢結(jié)果，否則p不是q的查詢結(jié)果。SimM需要的空間復(fù)雜度是O(nlbn),過濾過程的計算復(fù)雜度O(n)。很明顯這樣的計算復(fù)雜度過高，下面給出一種基于sMVP-tree直方圖的查詢過濾方法。設(shè)一個RkNN查詢對象q,一個樞紐點p及該樞紐點負(fù)責(zé)的數(shù)據(jù)對象集O。對于任意數(shù)據(jù)對象o∈O,如果滿足式（9），則o不可能是RkNN查詢結(jié)果。

NumHist(p,0,|ED(q,p)-ED(o,p)|-ED(o,p))＞k（9）

用式（9）可以從索引節(jié)點上過濾到大量不相關(guān)的數(shù)據(jù)對象，從而提高查詢效率。如圖4，是樞紐點p維護數(shù)據(jù)對象的直方圖，當(dāng)有一個R3NN查詢q時，根據(jù)三角不等式，任意數(shù)據(jù)對象o和q的距離大于o的3NN的最遠(yuǎn)距離，因此該數(shù)據(jù)對象集不包含R3NN的查詢結(jié)果，可以過濾掉。

基于該過濾方法，提出了RkNN算法，見算法4，根據(jù)式（9）計算出相關(guān)的樞紐點（第1行），將查詢轉(zhuǎn)發(fā)給相關(guān)的計算節(jié)點，各個計算節(jié)點在本地的sMVP-tree上使用式（9）計算出候選數(shù)據(jù)對象（第2～3行），利用kNN查詢算法過濾出真正的RkNN結(jié)果并返回（第4～8行）。

Fig.4 Query filtering ofRkNN圖4RkNN查詢過濾

算法4RkNN查詢算法

輸入：查詢q和整數(shù)k

輸出：q的RkNN查詢結(jié)果

1.根據(jù)式（9）計算相關(guān)的樞紐點和計算節(jié)點集CS

2.將查詢q轉(zhuǎn)發(fā)給計算節(jié)點集CS

3.candity←各個計算節(jié)點y∈CS,計算出候選的數(shù)據(jù)對象

4.For?oi∈candity

5.canditi←利用算法3計算出oi的kNN

6.Ifq∈canditi

7.將oi放入結(jié)果集RS中

8.Endif

9.Endfor

10.ReturnRS

從算法4可以看出，RkNN算法主要由|canditi|次kNN查詢算法組成，因此通信代價為O(|canditi|×(2pn+k))。

6 實驗測試與分析

6.1 實驗設(shè)置

實驗中使用了兩個真實數(shù)據(jù)集，第一個數(shù)據(jù)集抽取自著名的讀書網(wǎng)站豆瓣讀書（http://book.douban.com/），記為Douban，抽取了50萬本書籍信息，平均每本書記錄了30個評價，根據(jù)支持度每個評價被賦予一個概率值。第二個數(shù)據(jù)集抽取自微博網(wǎng)站（http://weibo.com/），記為Weibo，抽取了10萬人的微博信息，平均每個人搜集了45條微博，并且根據(jù)喜歡度給定每條微博一個概率值。去除掉TF-IDF值比較低的詞組并通過LDA（latent Dirichlet allocation）[26]算法將詞組合并，從而使詞組數(shù)小于500。

實驗基于Cassandra實現(xiàn)，分布式集群由20個計算節(jié)點組成，計算節(jié)點的配置為：Red Hat Linux System 6.1操作系統(tǒng)，IntelCore i3 2100 3.1 GHz CPU和8 GB內(nèi)存。本文分布式算法的實現(xiàn)主要基于Cassandra系統(tǒng)中P2P的路由協(xié)議，并不依賴于其他優(yōu)化，因此為了客觀考察算法的性能，不使用緩存技術(shù)和內(nèi)存數(shù)據(jù)庫系統(tǒng)。

目前沒有針對不確定性的基于余弦相似度的相似性查詢算法，本文實驗主要和兩個比較相關(guān)的算法進行比較：一個是簡單法（SimM），使用MVP-tree而不是sMVP-tree，對于kNN查詢使用簡單的兩次范圍查詢，對于RkNN查詢則使用文中所述的簡單策略。另一個較相關(guān)方法是DistV（distributed Voronoi）[21]，該方法是一個基于Voronoi圖的方法，通過Cassandra系統(tǒng)（http://wi了計算方法的近似度，將計算出的最近鄰和ki.apache.org/cassandra/HadoopSupport）的MapReduce擴展實現(xiàn)。本文提出的方法在實驗中簡稱為DistUC（distributed uncertain cosine similarity）。

實驗中參數(shù)默認(rèn)值如表1所示。

如第5章所述，構(gòu)建sMVP-tree的計算復(fù)雜度和構(gòu)建MVP-tree的計算復(fù)雜度一樣，但空間復(fù)雜度要略高于MVP-tree。如表2所示，Weibo中sMVP-tree的空間代價比MVP-tree多28%，Douban數(shù)據(jù)集中sMVP-tree的空間代價比MVP-tree多30%。因為數(shù)據(jù)集大小不同，對于Douban數(shù)據(jù)集的索引空間代價要高于Weibo數(shù)據(jù)集的索引空間代價。而對于Douban數(shù)據(jù)集的索引空間代價在分布式環(huán)境中是可以接受的，即平均每個計算節(jié)點的空間代價約為38.9 MB。

Table 1 Experiment parameters表1 實驗參數(shù)

為了計算方法的近似度，將計算出的最近鄰和人工選出的結(jié)果進行比較。具體地說，對于kNN查詢，設(shè)是真實的結(jié)果，o1,o2,…,om是算法查詢結(jié)果，則近似度為，顯而易見近似度越接近1，性能越好。

Table 2 Space cost of sMVP-tree表2 sMVP-tree的空間代價 MB

6.2 定理1的效果

首先通過1NN查詢驗證定理1對算法性能的影響。在圖5和圖6中比較了使用定理1和不使用定理1時算法的運行時間和準(zhǔn)確度。很明顯圖5顯示了使用定理1時算法的運行時間約是不用時的至圖6顯示了算法在Douban和Weibo數(shù)據(jù)集上的近似度，可以看出在Douban上的近似度要好于在Weibo上的近似度。這是因為Douban的評價長度要比Weibo的更長，包含的信息量更大。本文的算法更適合于Douban數(shù)據(jù)集。

Fig.5 Effect of Theorem 1圖5 定理1改進效果

為了驗證余弦相似度在處理不確定性文本數(shù)據(jù)時的優(yōu)勢，圖7和圖8比較了在Douban和Weibo數(shù)據(jù)集中分別使用余弦相似度計算和Jaccard相似度計算的運行時間和準(zhǔn)確性。從圖7中可以看出，在運算時間方面，因為余弦相似度計算方法的計算過程全是數(shù)值型運算，效率比混合文本匹配和數(shù)值計算的Jaccard相似性計算方法高，進一步通過定理1的優(yōu)化方法，運行時間約是Jaccard相似性計算方法的至同時，從圖8中可以看出，在Douban和Weibo數(shù)據(jù)集上，余弦相似度計算方法的準(zhǔn)確性要優(yōu)于Jaccard相似性計算方法。

Fig.7 Running time:Cosine similarity vs.Jaccard similarity圖7 余弦相似度和Jaccard相似性方法運行時間比較

Fig.8 Accuracy:Cosine similarity vs.Jaccard similarity圖8 余弦相似度和Jaccard相似性方法準(zhǔn)確性比較

6.3 詞組數(shù)的影響

圖9和圖10是在Douban數(shù)據(jù)集上從100到400變化詞組數(shù)時進行1NN查詢時的實驗結(jié)果。在度量空間內(nèi)，查詢通過數(shù)據(jù)對象之間的距離進行過濾，查詢效率和數(shù)據(jù)分布密切關(guān)系。因為通過樞紐點的劃分使得相近的數(shù)據(jù)對象在一個計算節(jié)點上，詞組數(shù)的增加沒有對性能產(chǎn)生很大的影響，如圖所示，查詢的計算代價和數(shù)據(jù)的詞組數(shù)呈線性關(guān)系。圖9顯示出隨著數(shù)據(jù)集的詞組數(shù)增加，各個算法的運行時間也在逐漸增加，可以看出在詞組數(shù)各種取值情況下，DistUC都要比其他兩種算法快。圖10顯示出，隨著數(shù)據(jù)詞組數(shù)的增加，近似度趨于更好。

Fig.9 Effect of tokens number:running time圖9 詞組數(shù)的影響：運行時間

Fig.10 Effect of tokens number:accuracy圖10 詞組數(shù)的影響：近似度

6.4 kNN查詢性能

通過變化參數(shù)k來驗證kNN查詢算法的性能。圖11和圖12顯示了在Douban和Weibo數(shù)據(jù)集上的kNN算法運行時間。本質(zhì)上DistUC是由兩輪最近鄰查詢組成，且可以看出DistUC的執(zhí)行效率要明顯好于DistV。圖13顯示了kNN算法的準(zhǔn)確度，在Douban和Weibo數(shù)據(jù)集上近似值都小于3，說明了算法的有效性。

6.5 RkNN查詢性能

最后通過變化參數(shù)k來驗證RkNN查詢算法的性能。圖14和圖15顯示了在Douban和Weibo數(shù)據(jù)集上的RkNN算法運行時間。從圖14和圖15中可以看出sMVP-tree的過濾方法明顯提高了查詢效率，DistUC方法要比SimM方法快一個數(shù)量級。圖16顯示了RkNN算法的準(zhǔn)確度，本質(zhì)上RkNN算法是由多個并行的最近鄰算法組成，保持了其較好的近似度。

6.6 負(fù)載均衡

Fig.11 Running time ofkNNalgorithm on Douban圖11 kNN算法在Douban上運行時間

Fig.12 Running time ofkNNalgorithm on Weibo圖12 kNN算法在Weibo上運行時間

Fig.13 Accuracy ofkNNalgorithm圖13 kNN算法近似度

Fig.14 Running time ofRkNNalgorithm on Douban圖14 RkNN算法在Douban上運行時間

最后通過包含不同比例的kNN查詢和RkNN查詢的混合查詢?nèi)蝿?wù)驗證系統(tǒng)的負(fù)載均衡情況，主要考察3種kNN查詢和RkNN查詢的比例，分別是（30%，70%）、（50%，50%）、（70%，30%）。實驗中通過計算系統(tǒng)中計算節(jié)點負(fù)載的相對標(biāo)準(zhǔn)差來衡量負(fù)載均衡，即，其中xˉ是各個計算節(jié)點負(fù)載的平均值，δ是各個計算節(jié)點負(fù)載的標(biāo)準(zhǔn)方差。圖17顯示了DistUC算法的負(fù)載均衡情況，得益于一致性哈希的均衡性和查詢敏感的動態(tài)平衡性，DistUC算法在不同的查詢負(fù)載下均表現(xiàn)出良好的負(fù)載均衡，相對標(biāo)準(zhǔn)差維持在0.4以下。

Fig.15 Running time ofRkNNalgorithm on Weibo圖15 RkNN算法在Weibo上運行時間

Fig.16 Accuracy ofRkNNalgorithm圖16 RkNN算法近似度

Fig.17 Load balance圖17 負(fù)載均衡

7 結(jié)束語

隨著大數(shù)據(jù)的應(yīng)用急速增長，面向大規(guī)模數(shù)據(jù)的分布式查詢處理成為研究熱點。本文研究了分布式環(huán)境下基于余弦相似度的不確定最近鄰查詢的問題。首先分析了不確定性余弦相似度計算的特性，并給出了高效的計算方法，提出了基于sMVP-tree的查詢方法。然后將算法擴展到分布式環(huán)境中，介紹了分布式環(huán)境下的kNN查詢算法，并首次提出了面向度量空間的RkNN查詢和過濾方法。最后通過真實數(shù)據(jù)上的實驗驗證了算法的有效性。

[1]Zhang Peiwu,Cheng R,Mamoulis N,et al.Voronoi-based nearest neighbor search for multi-dimensional uncertain databases[C]//Proceedings of the 29th International Conference on Data Engineering,Brisbane,Apr 8-12,2013.Washington:IEEE Computer Society,2013:158-169.

[2]Peng Liping,Diao Yanlei,Liu Anna.Optimizing probabilistic query processing on continuous uncertain data[C]//Proceedings of the 37th International Conference on Very Large Data Bases,Seattle,Aug 29-Sep 3,2011.New York:ACM,2011:1169-1180.

[3]Ma Youzhong,Meng Xiaofeng.Set similarity join on massive probabilistic data using MapReduce[J].Distributed and Parallel Databases,2014,32(3):447-464.

[4]Ye Mao,Lee W C,Lee D L,et al.Distributed processing of probabilistictop-Kqueries in wireless sensor networks[J].IEEE Transactions on Knowledge&Data Engineering,2013,25(1):76-91.

[5]Yi Ke,Li Feifei,Kollios G,et al.Efficient processing oftop-Kqueries in uncertain databases with X-relations[J].IEEE Transactions on Knowledge&Data Engineering,2008,20(12):1669-1682.

[6]Dallachiesa M,Palpanas T,Ilyas I F.Top-knearest neighbor search in uncertain data series[J].Proceedings of the VLDB Endowment,2014,8(1):13-24.

[7]Huang Chenghui,Yin Jian,Hou Fang.A text similarity measurement combining word semantic information with TF-IDF method[J].Chinese Journal of Computers,2011,34(5):856-864.

[8]Robertson S.Understanding inverse document frequency:on theoretical arguments for IDF[J].Journal of Documentation,2004,60(5):503-520.

[9]Han Min,Tang Changjie,Duan Lei,et al.TF-IDF similarity based method for tag clustering[J].Journal of Frontiers of Computer Science and Technology,2010,4(3):240-246.

[10]Wu H C,Luk R W P,Wong K F,et al.Interpreting TF-IDF term weights as making relevance decisions[J].ACM Transactions on Information Systems,2008,26(3):55-59.

[11]Agarwal P K,Efrat A,Sankararaman S,et al.Nearest-neighbor searching under uncertainty[C]//Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,Scottsdale,May 20-24,2012.New York:ACM,2012:225-236.

[12]Agarwal P K,Aronov B,Har-Peled S,et al.Nearest neighbor searching under uncertainty II[C]//Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,New York,Jun 22-27,2013.New York:ACM,2013:115-126.

[13]Zheng Kai,Fung G P C,Zhou Xiaofang.K-nearestneighbor search for fuzzy objects[C]//Proceedings of the 2010 International Conference on Management of Data,Indianapolis,Jun 6-10,2010.New York:ACM,2010:699-710.

[14]Li Chen,Shen Derong,Zhu Mingdong,et al.kNNquery processing approach for content with location and time tags[J].Journal of Software,2016,27(9):2278-2289.

[15]Bernecker T,Emrich T,Kriegel H P,et al.Efficient probabilistic reverse nearest neighbor query processing on uncertain data[C]//Proceedings of the 37th International Conference on Very Large Data Bases,Seattle,Aug 29-Sep 3,2011.New York:ACM,2011:669-680.

[16]Abeywickrama T,Cheema M A,Taniar D.k-nearestneighbors on road networks:a journey in experimentation and inmemory implementation[J].Proceedings of the VLDB Endowment,2016,9(6):492-503.

[17]Wang Pei,Xiao Chuan,Qin Jianbin,et al.Local similarity search for unstructured text[C]//Proceedings of the 2016 International Conference on Management of Data,San Francisco,Jun 26-Jul1,2016.New York:ACM,2016:1991-2005.

[18]Jestes J,Li Feifei,Yan Zhepeng,et al.Probabilistic string similarity joins[C]//Proceedings of the 2010 International Conference on Management of Data,Indianapolis,Jun 6-10,2010.New York:ACM,2010:327-338.

[19]Wen Qingfu,Wang Jianmin,Zhu Han,et al.Distributed learning to hash for approximate nearest neighbor search[J].Chinese Journal of Computers,2017,40(1):192-206.

[20]Wang Jiannan,Li Guoliang,Feng Jianhua.Extending string similarity join to tolerant fuzzy token matching[J].ACM Transactions on Database Systems,2014,39(1):7.

[21]Akdogan A,Demiryurek U,Kashani F B,et al.Voronoibased geospatial query processing with MapReduce[C]//Proceedings of the 2nd International Conference on Cloud Computing,Indianapolis,Nov 30-Dec 3,2010.Washington:IEEE Computer Society,2010:9-16.

[22]Manning C D,Raghavan P,Schtze H.Introduction to information retrieval[M].New York:Cambridge University Press,2008:113-133.

[23]Bozkaya T,Ozsoyoglu M.Indexing large metric spaces for similarity search queries[J].ACM Transactions on Database Systems,1999,24(3):361-404.

[24]Bustos B,Navarro G,Chávez E.Pivot selection techniques for proximity searching in metric spaces[J].Pattern Recognition Letters,2003,24(14):2357-2366.

[25]Yang Shiyu,Cheema M A,Lin Xuemin,et al.Reverseknearest neighbors query processing:experiments and analysis[J].Proceedings of the VLDB Endowment,2015,8(5):605-616.

[26]Shu Liangcai,Long Bo,Meng Weiyi.A latent topic model for complete entity resolution[C]//Proceedings of the 25th International Conference on Data Engineering,Shanghai,Mar 29-Apr 2,2009.Washington:IEEE Computer Society,2009:880-891.

附中文參考文獻(xiàn)：

[7]黃承慧,印鑒,侯昉.一種結(jié)合詞項語義信息和TF-IDF方法的文本相似度量方法[J].計算機學(xué)報,2011,34(5):856-864.

[9]韓敏,唐常杰,段磊,等.基于TF-IDF相似度的標(biāo)簽聚類方法[J].計算機科學(xué)與探索,2010,4(3):240-246.

[14]李晨,申德榮,朱命冬,等.一種對時空信息的kNN查詢處理方法[J].軟件學(xué)報,2016,27(9):2278-2289.

[19]文慶福,王建民,朱晗,等.面向近似近鄰查詢的分布式哈希學(xué)習(xí)方法[J].計算機學(xué)報,2017,40(1):192-206.