反向Top—k查詢算法研究

黃偉國(guó)

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

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

DOI：10.11907/rjdk.172266

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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查詢作為一種高效的信息對(duì)比查詢技術(shù)，經(jīng)過(guò)多年的發(fā)展，已經(jīng)較為成熟。本文研究的基于Top-k查詢的反向Top-k查詢技術(shù)，能夠提供與Top-k不同的查詢角度。反向Top-k查詢算法可以為各行業(yè)提供“影響值”最大的產(chǎn)品參考。產(chǎn)品制造方通過(guò)參考這些“影響值”最大的產(chǎn)品，可以制造出更受大眾歡迎的產(chǎn)品，從而為產(chǎn)品制造方帶來(lái)更多利益。

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

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

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

2 反向Top-k查詢算法

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

2.1 Skyband-based算法

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

2.1.1 ComputeSkyband算法

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

2.1.2 RTA算法

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

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

2.1.3 Skyband-based算法

Skyband-based算法簡(jiǎn)稱SB算法。算法基本思想：先利用ComputeSkyband算法計(jì)算出mSB（S）點(diǎn)集，然后利用RTA算法計(jì)算mSB（S）中的所有點(diǎn)集的影響值。在計(jì)算點(diǎn)的影響值時(shí)，把影響值壓縮進(jìn)一個(gè)從大到小的隊(duì)列Q中。當(dāng)mSB（S）中所有點(diǎn)集的影響值計(jì)算完后，取出Q中前m個(gè)點(diǎn)，這m個(gè)點(diǎn)就是SB算法計(jì)算出來(lái)的結(jié)果集。

2.2 Branch-and-bound算法

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

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

2.2.1 ComputeBound函數(shù)

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

2.2.2 Branch-and-bound算法

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

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

3 交互式算法

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

3.1 Top-k集比較算法

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

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

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

3.2 交互式算法介紹

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

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

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

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

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

4.2 算法實(shí)驗(yàn)效果

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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] 夏冰，高軍，王騰蛟，等.一種高效的動(dòng)態(tài)腳本網(wǎng)站有效頁(yè)面獲取方法[C].中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議，2009.

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

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

（責(zé)任編輯：孫 娟）endprint