黃偉國

摘 要：互聯(lián)網(wǎng)中沉淀了大量可分析利用的數(shù)據(jù)，如何有效地利用這些海量數(shù)據(jù)，為不同行業(yè)產(chǎn)品制造方提供對新產(chǎn)品的分析，已成為時下的熱點。反向Top-k查詢技術是一種常用的數(shù)據(jù)分析及處理技術，并且已經(jīng)在很多領域得到了應用。研究了已有的基于反向Top-k的查詢算法Skyband-based算法和Branch-and-bound算法，針對很多實際應用領域偏好權重向量會出現(xiàn)改變的情況，提出了一種適用于進行“二次計算”的交互式算法，通過實驗將交互式算法跟效率高的Branch-and-bound算法對比得出，當用戶修改部分偏好權重向量之后，利用交互式算法可以比Branch-and-bound算法更加高效率地計算出結果。

關鍵詞：交互式算法；Skyband-based算法；Branch-and-Bound算法；Top-k查詢

DOI：10.11907/rjdk.172266

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2017）009-0075-04

Abstract：Among the Internet， a large amount of data can be analyzed and utilized. How to effectively use these vast amounts of data， for different industries， manufacturers of products to provide new product analysis， has become a hot topic. Reverse Top-k query technology is a commonly used data analysis and processing technology， and has been applied in many fields. Study of the existing reverse Top-k query algorithm Skyband-based algorithm and Branch-and-bound algorithm based on the preference weight vector in many practical applications will appear to change the situation， a method is presented for the “two” interactive algorithm by experiment that compared to Branch-and-bound algorithm， interactive algorithm with high efficiency， when part of the user to modify the preference weight vector is calculated by the interactive method can be more efficient than Branch-and-bound algorithm results.

Key Words：interactive algorithm； skyband-based algorithm； branch-and-bound algorithm； Top-k queries

0 引言

Top-k查詢作為一種高效的信息對比查詢技術，經(jīng)過多年的發(fā)展，已經(jīng)較為成熟。本文研究的基于Top-k查詢的反向Top-k查詢技術，能夠提供與Top-k不同的查詢角度。反向Top-k查詢算法可以為各行業(yè)提供“影響值”最大的產(chǎn)品參考。產(chǎn)品制造方通過參考這些“影響值”最大的產(chǎn)品，可以制造出更受大眾歡迎的產(chǎn)品，從而為產(chǎn)品制造方帶來更多利益。

1 國內(nèi)外研究現(xiàn)狀

Top-k查詢[1]是指基于用戶的偏好函數(shù)從所有產(chǎn)品集中提取優(yōu)先的k個產(chǎn)品集。比如，知道一個用戶的偏好權重向量，然后用Top-k查詢來查找該用戶喜歡的k個產(chǎn)品。反向Top-k查詢[2]是指基于用戶根據(jù)他們的偏好認為某個產(chǎn)品作為他們的Top-k個產(chǎn)品中的一個來評估一個潛在的產(chǎn)品在市場上的影響。但是根據(jù)反向Top-k查詢?nèi)フ页鰉個最有影響的產(chǎn)品所耗的時間特別多，因為它需要對數(shù)據(jù)庫中的每個產(chǎn)品進行反向Top-k查詢。因此，本文使用文獻[3]中提到的兩個可以提高計算效率的算法。同時，充分考慮現(xiàn)實中的一些情況，也即針對用戶偏好權重發(fā)生改變的情況，提出一種交互式算法，用來進行“二次計算”，以提升“二次計算”效率。

最近，研究產(chǎn)品制造方而不是用戶方的一些創(chuàng)新查詢算法被提出。文獻[4]基于支配關系的分析，幫助制造商完成它們的產(chǎn)品市場定位。文獻[5]中提到了如何創(chuàng)建有競爭力的產(chǎn)品。然而在這兩種方法中，都是將用戶偏好作為數(shù)據(jù)點代表更好的產(chǎn)品，而反向Top-k查詢是根據(jù)權重向量分析出用戶偏好。文獻[6]中提到如何為一個對象的推廣尋找Top-k個最有興趣的區(qū)域。文獻[7]中給出一個查詢點q，反向最近鄰查詢是基于一個相似的函數(shù)，找出那些與q最近鄰的點，這些點描述成被q影響。

2 反向Top-k查詢算法

一種找出前m個影響值最大的結果集的樸素方式是用暴力計算方法計算結果集。如對于每一個點p屬于數(shù)據(jù)向量集合S都進行反向Top-k查詢從而得到它的影響分數(shù)fki（p）。但是其效率非常低下，即使是一個中等大小的數(shù)據(jù)庫，也要消耗很多時間。因此，下文主要介紹文獻[3]和文獻[8-9]中可以提高計算效率的算法，分別是Skyband-based算法[10]、Branch-and-Bound算法。

2.1 Skyband-based算法

Skyband-based算法依賴于ComputeSkyband算法和RTA算法，用ComputeSkyband選出點集mSB，這樣就減少了計算RTA的點，從而提升了計算效率。因此，本文首先介紹ComputeSkyband算法和RTA算法。endprint

2.1.1 ComputeSkyband算法

算法思想：計算電影集S中每部電影被支配的數(shù)量，如果被支配的數(shù)量小于m，則將這部電影插入到mSB集合中，否則不進行操作。

2.1.2 RTA算法

作為一種計算向量的反向Top-k集合的算法，RTA算法能夠避免一些重復計算，從而更快速地給出結果集合[11-12]。

該算法的思想是：考慮在整個計算中用戶權重值W的數(shù)量較多，如果用W中的每一個權重去和特定的點計算，那么計算量無疑很大，因此用RTA通過已經(jīng)計算過的Top-k結果集，避免計算那些不可能在Reverse Top-k 結果集中的w向量值，從而能夠避免一些對結果沒有影響的計算過程，進而提高算法效率。

2.1.3 Skyband-based算法

Skyband-based算法簡稱SB算法。算法基本思想：先利用ComputeSkyband算法計算出mSB（S）點集，然后利用RTA算法計算mSB（S）中的所有點集的影響值。在計算點的影響值時，把影響值壓縮進一個從大到小的隊列Q中。當mSB（S）中所有點集的影響值計算完后，取出Q中前m個點，這m個點就是SB算法計算出來的結果集。

2.2 Branch-and-bound算法

上文介紹的Skyband-based算法不是漸增性的，導致當需要擴大或者縮小算法的m值時，該算法不能夠利用上一次的計算結果，而是需要完全重新計算，即Skyband-based算法不是漸進的。與此相對，本節(jié)提出的Branch-and-bound算法是漸增性的，當需要獲得更多的結果值時，即當擴大m值時，并不需要進行全盤的重新計算，只是進行遞增計算即可。因此，面對需要經(jīng)常修改m值的情況，該算法的效率會更高，能夠在更短的時間內(nèi)給出計算結果。

Branch-and-bound算法依賴ComputeBound函數(shù)和RTA算法。RTA算法在上文已介紹過，因此，下文主要介紹ComputeBound函數(shù)。

2.2.1 ComputeBound函數(shù)

ComputeBound函數(shù)的基本思想：輸入一個點q，計算出一個點q的影響值，然后計算出所有點q的影響值集中的反向Top-k值，并且求交集，得到的交集個數(shù)就是影響值的上界。

2.2.2 Branch-and-bound算法

Branch-and-bound算法的基本思想是：先將電影數(shù)據(jù)集S存放在R樹中，之后把R樹根節(jié)點上的MBR加載到從大到小的優(yōu)先隊列Q中；然后用ComputeBound函數(shù)改進每個MBR的上界，并用RTA算法計算出實際影響值。

Branch-and-bound算法詳細描述如下：首先將電影評分數(shù)據(jù)S集加載到R樹上得到一棵樹tree；然后計算tree根節(jié)點的所有子節(jié)點的上界值，并插入到優(yōu)先隊列Q中；接著，做一個循環(huán)，當結果集RES的數(shù)量小于m時循環(huán)一直執(zhí)行。從Q中推出一個MBR為c，判斷c是否為電影數(shù)據(jù)點。如果c是電影數(shù)據(jù)點，而且已經(jīng)計算了它的影響值，則添加到結果集RES中；否則計算它的上界，如果上界變小了，則再次插入到Q中，否則用RTA計算其影響值然后插入Q中。如果c不是產(chǎn)品數(shù)據(jù)點，則計算它的上界值，如果上界值沒有變小，則重新插入到Q中；否則把c的子節(jié)點及其相應的上界值插入到Q中。

3 交互式算法

本文算法在計算過程中有大量用戶偏好權重向量，算法計算得到的結果集跟用戶偏好權重向量有關。本文所介紹的Skyband-based算法和Branch-and-bound算法都是批量式的查詢，因此每次計算都需要將所有數(shù)據(jù)計算一次。而當部分用戶偏好權重向量被修改后，不需要重新計算所有數(shù)據(jù)而得到結果集?？梢岳玫谝淮斡嬎愕玫降慕Y果，然后使用增量式的方法進行查詢，即可得到最新的查詢結果集。鑒于此，本文提出交互式算法，也即當部分用戶偏好權重向量改變時，可以用交互式算法快速計算出結果集。

3.1 Top-k集比較算法

因下文介紹的交互式算法需要用到Top-k集比較算法，因此先介紹Top-k集比較算法。

為了在后面的算法過程中描述得更加清楚，在對算法作進一步介紹前，先對交互式算法中用到的一些變量進行定義。變量定義如表1中所示。

Top-k集比較算法的基本思想描述如下：如果一個用戶偏好權重向量w的OldTop-k集中的MtimeId和NewTop-k中的MtimeId相同，則不作任何處理。如果一個MtimeId在OldTop-k集中存在，而在NewTop-k集中不存在，就把OldS中對應MtimeId的電影的影響值減去w的權值；如果一個MtimeId在NewTop-k中存在，而在OldTop-k集中不存在，那么就把OldS中對應的MtimeId的電影的影響值加上w的權值。

3.2 交互式算法介紹

針對改變的用戶偏好權重向量作增量式查詢，為了能夠讓交互式算法對已有的結果做增量式查詢，要在第一次計算時進行一些處理，也即在用Skyband-based算法和Branch-and-bound算法進行結果查詢之后，將查詢出來的每個產(chǎn)品的影響值寫入到存有產(chǎn)品集的文件中，然后針對每個改變的用戶偏好權重向量進行計算。

交互式算法的基本思想是：在用戶修改用戶權重向量之后，系統(tǒng)管理員不定時地將改變的用戶權重向量從Mysql數(shù)據(jù)庫中導出到本地，得到新的用戶偏好權重向量NewW，并根據(jù)得到的NewW讀取文件中的OldW，調(diào)用Top-k算法分別計算OldW集中的每個用戶偏好權重向量的Top-k集稱之為OldWTop-k集，NewW集中的每個用戶偏好權重向量的Top-k集稱之為NewWTop-k集。對OldWTop-k集和NewWTop-k集中的每個OldTop-k集和NewTop-k集都調(diào)用Top-k集比較算法，得到新的電影集NewS。最后將用戶偏好權重向量中的OldW修改為NewW并存于文件中，以保持數(shù)據(jù)庫中用戶偏好權重向量和文件中用戶偏好權重向量的一致性。將計算得到的NewS存于文件中，以記錄最新電影的影響值。endprint

4 反向Top-k查詢算法性能比較

4.1 實驗數(shù)據(jù)獲取及預處理

實驗數(shù)據(jù)獲取包括兩部分：一部分是電影數(shù)據(jù)獲取[13-15]，網(wǎng)絡爬蟲爬取專業(yè)電影網(wǎng)站“時光網(wǎng)”（http：//movie.mtime.com/）中的電影數(shù)據(jù)網(wǎng)頁，之后將電影網(wǎng)頁數(shù)據(jù)用正則表達式進行處理，得到電影的各項評價標準值；另一部分是獲取用戶偏好權重向量，由于用戶偏好權重向量值不是真實值，因此用戶偏好權重向量采用程序生成。

4.2 算法實驗效果

本文中的Branch-and-bound算法和Skyband-based算法都是批量式算法。從文獻[4]中可以看出，在算法所需時間上Branch-and-bound算法（圖中稱BB算法）優(yōu)于Skyband-based算法。因此，在對比批量式算法和交互式算法的效率時，選擇Branch-and-bound算法與交互式算法進行對比。

在對比過程中，如果不加特別說明，各數(shù)據(jù)的默認值如下：k值默認為10，m值默認為100，電影評分的條數(shù)為12 000條，用戶偏好權重向量的條數(shù)為20 000條，電影評分和用戶偏好權重向量的維度是7。兩個算法的計算效率對比有兩個指標，分別是執(zhí)行時間、Top-k計算次數(shù)。

如圖1所示，當不同數(shù)量的用戶偏好權重向量發(fā)生改變時，Branch-and-bound算法的時間都為250，Top-k計算次數(shù)都為20 000，即沒有發(fā)生變化。這是因為Branch-and-bound算法不能根據(jù)已有結果作增量式查詢，因此當用戶偏好權重向量改變時，需要對全部數(shù)據(jù)進行計算。而采用交互式算法，當用戶偏好權重向量改變時，只需要對改變的向量作增量式查詢就可以得到結果集。由圖1可以看到，當不同數(shù)量用戶偏好權重向量發(fā)生改變時，交互式算法執(zhí)行的時間不一樣。在交互式算法中，花費時間最多的是計算改變的用戶偏好權重向量的Top-k集和對硬盤上數(shù)據(jù)的讀取。當改變的用戶偏好權重向量數(shù)為500時，為了作增量式查詢，需要計算改變前的用戶偏好權重向量的Top-k集和改變后的用戶偏好權重向量的Top-k集。因此，一共計算了兩倍改變的用戶偏好權重向量的數(shù)量，也即當改變的用戶偏好權重向量的數(shù)量為500時，計算1 000次Top-k集。因此，隨著改變的用戶偏好權重向量的增加，交互式算法所花時間和計算Top-k集的次數(shù)也在不斷增加。由此可見，當用戶修改部分偏好權重向量之后，用交互式算法可以比Branch-and-bound算法更加高效率地計算出結果。

5 結語

本文對已有的基于反向Top-k查詢的算法進行研究，其中包括Skyband-based算法和Branch-and-bound算法，并針對這兩種算法的不足，提出交互式算法以提高“二次計算”效率。本文的重點是用批量式算法中效率較高的算法進行第一次計算，當用戶偏好權重向量發(fā)生改變時，用交互式算法針對第一次計算得到的結果做增量式計算，以提高系統(tǒng)效率。

參考文獻：

[1] IIYAS IF， BESKALES G， SOLIMAN MA.A survey of top-k query processing techniques in relational database systems[J]. ACM Computing Surveys，2008，40（4）：1-58.

[2] VLACHOU A， DOULKERIDIS C，KOTIDIS Y，et al.Reverse top-k queries[J]. IEEE International Conference on Data Engineering， 2010，41（3）：365-376.

[3] VLACHOU A， DOULKERIDIS C. Identifying the most influential data objects with reverse top-k queries[J]. Proceedings of The VLDB Endowment，2010，3（1-2）：364-372.

[4] LI C， OOI BC， TUNG AKH， et al. DADA：a data cube for dominant relationship analysis[J]. In Proc. of SIGMOD，2006：659-670.

[5] QIAN W， WONG CW， IIYAS IF， YU P. Creating competitive products[J]. PVLDB，2009，2（1）：898-909.

[6] WU T， LI C， HAN J. Region-based online promotion analysis[J]. In Proc. of EDBT，2010：63-74.

[7] KORN F， MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries[J]. In Proc. of SIGMOD，2000，29（2）：201-212.

[8] LAWLER EL， WOOD DE. Branch-and-Bound methods： a survey[J]. Informs，1966，14（4）：699-719.

[9] NARENDRA， FUKUNAGA.A branch and bound algorithm for feature subset selection[J]. IEEE，2006（9）：917-922.

[10] PAPADIAS D， TAO Y， FU G， et al. Progressive skyline computation in database systems[J].ACM Transactions on Database Systems，2005，30（1）：41-82.

[11] WANG B， DAI Z， LI C， CHEN H.Efficient computation of monochromatic reverse top-k queries[J].Fuzzy Systems And Knowledge Discovery （FSKD），2010，4：1788-1792.

[12] LIAN X， CHEN L. Monochromatic and bichromatic reverse skyline search over uncertain databases[C].Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，2008：213-226.

[13] 夏冰，高軍，王騰蛟，等.一種高效的動態(tài)腳本網(wǎng)站有效頁面獲取方法[C].中國數(shù)據(jù)庫學術會議，2009.

[14] 羅剛，王振東.自己動手寫網(wǎng)絡爬蟲[M].北京：清華大學出版社，2010：17-84.

[15] 許笑，張偉哲，張宏莉，等.廣域網(wǎng)分布式Web 爬蟲[J].軟件學報，2010，21（5）：1067-1082.

（責任編輯：孫 娟）endprint