【論文精讀】《Random Sampling over Joins Revisited》
最近閱讀了一些報(bào)告，同時(shí)對(duì)相應(yīng)內(nèi)容進(jìn)行了復(fù)現(xiàn)，B站的markdown排版太不友好了，有目錄的細(xì)致排版的版本可以看我的博客園博客：https://www.cnblogs.com/zekaiblogs/p/16342935.html
《Random Sampling over Joins Revisited》論文閱讀報(bào)告
主要論文地址：https://www.cs.utah.edu/~lifeifei/papers/samplejoin.pdf
目錄
對(duì)計(jì)算問(wèn)題的概述
背景
隨著社會(huì)進(jìn)入大數(shù)據(jù)時(shí)代，計(jì)算機(jī)需要處理的數(shù)據(jù)成爆炸性增長(zhǎng)。將需要處理的數(shù)據(jù)全部存儲(chǔ)在硬盤(pán)中并進(jìn)行精確處理變得不現(xiàn)實(shí)。在計(jì)算機(jī)的日常應(yīng)用中，經(jīng)常需要進(jìn)行的任務(wù)之一為連接操作。直觀的說(shuō)，其目的常常為了把兩個(gè)相關(guān)的表連接起來(lái)，獲取其相同的特征。通常情況下，我們常常需要連接3張以上的表，才能獲取想要的信息，比如知道一個(gè)用戶(hù)購(gòu)買(mǎi)的商品的供應(yīng)商供應(yīng)的其它產(chǎn)品，就需要用戶(hù)表，購(gòu)買(mǎi)表，商品表，供應(yīng)商表，商品表的多重連接操作，這類(lèi)操作的結(jié)果往往是數(shù)億級(jí)別的，這種結(jié)果即使能得出來(lái)，也很難放到訓(xùn)練模型中進(jìn)行訓(xùn)練。我們做的就是進(jìn)行隨機(jī)采樣的方法，從連接的結(jié)果中均勻獨(dú)立的抽樣，以獲取一致的結(jié)果用于訓(xùn)練。實(shí)際表面，這種抽樣策略往往能訓(xùn)練出合格的模型用于項(xiàng)目中。
本篇論文在前人方法的基礎(chǔ)上，提出了一個(gè)統(tǒng)一的求Join Sample的算法，以高效的求出采樣的數(shù)據(jù)。
問(wèn)題概述
在訓(xùn)練模型時(shí)，常常需要將多個(gè)表做自然連接，來(lái)獲取整體的樣本特征；而在大數(shù)據(jù)的樣本下，如果直接做自然連接得到的結(jié)果數(shù)量和時(shí)間復(fù)雜度往往是不可以接受的（樣本數(shù)太大，很難用梯度下降之外的方法進(jìn)行l(wèi)oad訓(xùn)練）。這時(shí)候就需要一種join sample策略，假設(shè)我們join得到的結(jié)果數(shù)目為n,則我們希望每次抽到一個(gè)join結(jié)果的樣本，使得抽到這個(gè)樣本的概率是1/n,即我們總是希望獲取一個(gè)均勻抽樣的join結(jié)果。
問(wèn)題定義
在這一節(jié)中給出Random Sampling over Joins問(wèn)題的精確定義。
對(duì)于全部的
的結(jié)果U，我們希望獲得一組隨機(jī)抽樣結(jié)果S，使得抽樣結(jié)果S中的每個(gè)元素e均勻獨(dú)立等可能的出現(xiàn)在結(jié)果U中。
算法及其理解
前人的工作總結(jié)
在介紹本論文實(shí)現(xiàn)方法之前，我想先介紹下前人對(duì)join sample的工作，分別是Olken et al.和Chaudhuri et al [sigmod 99]在兩表之間的join；和Acharya et al.[sigmod 99]基于外鍵的多表join;
Olken和Chaudhuri et al的工作（2-table joins）
首先是Olken的工作，他的策略如下：
如果要對(duì)R1和R2做自然連接，需要先對(duì)R1做均勻采樣，再對(duì)與R1選中的那個(gè)元組在R2中連接的那些元組做均勻采樣，再以一個(gè)概率α接受這個(gè)采樣；
我們舉個(gè)例子來(lái)說(shuō)明這樣為什么是可行的。
如上圖所示，我們對(duì)R1和R2做自然連接操作，肉眼可以看出結(jié)果是10個(gè)元組，下面我們證明用以上方法進(jìn)行隨機(jī)抽樣，接受一個(gè)樣本的條件下，抽到正確的結(jié)果的概率是1/10；
首先計(jì)算選擇到t1和t2并且被接受的概率；在R1上做均勻采樣，那么我抽到t1的概率就是1/7，通過(guò)索引，我們可以快速找到t1對(duì)應(yīng)的t2的元組有兩個(gè)，則均勻在R2上抽取，獲得t2的概率就是1/2了。最后我們以概率α拒絕這個(gè)采樣，首先分子的計(jì)算方法就是t2的B屬性的值在R2表上投影的個(gè)數(shù)，結(jié)果為2；分母就是對(duì)R2的B屬性進(jìn)行分組操作（Group by），取分組后個(gè)數(shù)的最大值，顯然是B=3時(shí)候的分組，為4；所以α就是2/4為1/2；
隨后我們計(jì)算一組結(jié)果被接受的概率；首先若在R1中抽到B的值為1時(shí)，概率為3/7，而α為0（因?yàn)镽2中沒(méi)有對(duì)應(yīng)的結(jié)果元組）；同理選中2并且接受的概率是3/7*2/4；選中3并且被接受的概率是1/7+4/4；所以加起來(lái)就是接受的概率，為10/28；
最后利用條件概率公式，如圖所示，我們計(jì)算在接受的條件下，抽到t1t2的概率是1/10；由此驗(yàn)證了正確性；
然后是和Chaudhuri et al的工作。他的步驟和操作更簡(jiǎn)單，不需要進(jìn)行拒絕抽樣樣本，節(jié)省了時(shí)間，直接通過(guò)每個(gè)R1中元組的比例和的概率進(jìn)行R1的采樣，在R2中采樣的方式和之前一樣；
我們同樣用例子說(shuō)明結(jié)果的正確性；
還是以上圖為例子，R1中B=1占在R2的比例是0；B=2在R2的比例是2+2+2=6；B=3在R2中占的比例是4；一共比例就是10；那么抽到t1的概率是用R2中B=2的個(gè)數(shù)除以10，就是2/10；抽到t2的概率就是1/2，這個(gè)元組是一定接收的；因此抽樣的概率就是2/10*1/2是1/10；符合我們的要求。
Acharya et al.的工作（有外鍵條件下的連接）
他定義了一種特殊的連接條件的操作，就是如果一組連接中任意兩個(gè)關(guān)系，他們的公共屬性一定是靠前那個(gè)關(guān)系的外鍵，同時(shí)參考于后一個(gè)關(guān)系的主鍵；同時(shí)除了最后一個(gè)關(guān)系，前面的關(guān)系一定會(huì)找到一個(gè)關(guān)系和它配對(duì)，同時(shí)滿(mǎn)足前面的條件。
如下圖所示，左邊的就是muliti-way foreign-key joins，右邊則不是。
那么如果滿(mǎn)足這種情況的化，抽樣就很簡(jiǎn)單了，因?yàn)閮蓚€(gè)相鄰的關(guān)系之間，總是一對(duì)一連接的，直接抽樣就行了。如下圖所示。均勻抽取t1后，后面的t2和t3一定被抽中。
作者的想法
模型分為抽樣部分和權(quán)重的上界估計(jì)部分，其中抽樣模型是統(tǒng)一的，即根據(jù)權(quán)重進(jìn)行隨機(jī)抽樣；權(quán)重上界估計(jì)模型的方法有許多，權(quán)重越精確，抽樣時(shí)接受率越高，速度越快；權(quán)重不精確則計(jì)算權(quán)重時(shí)候更快；換句話(huà)說(shuō)，精確權(quán)重的代價(jià)是計(jì)算權(quán)重的時(shí)間長(zhǎng)；不精確的權(quán)重的代價(jià)是抽樣時(shí)的拒絕率增加，速度緩慢；如何設(shè)計(jì)這兩部分，是算法的關(guān)鍵。
抽樣模型
可以看出，上面兩種連接方案，一個(gè)是只能進(jìn)行兩表的連接；另一個(gè)則是對(duì)多表連接中的一種特殊情況進(jìn)行討論；而本作者對(duì)上面的論文進(jìn)行了研究，提出了自己的一種普適性的多表連接方案。
首先對(duì)一個(gè)鏈?zhǔn)降亩啾磉B接，我們引出權(quán)重的概念，這個(gè)權(quán)重的意義就是用來(lái)表示一個(gè)連接操作的規(guī)模大小的，即一個(gè)元組的權(quán)重是這個(gè)元組和后續(xù)所有表做自然連接得到的結(jié)果數(shù)總和，即
而一個(gè)表的權(quán)重，則是這個(gè)表上所有元組的權(quán)重之和。同時(shí)我們?cè)谧铋_(kāi)頭的表之前加一個(gè)頭，用來(lái)記錄第一個(gè)表R的W(R),一個(gè)例子如圖所示，可以看出t0的權(quán)重其實(shí)就是連接結(jié)果的總個(gè)數(shù)。
但是對(duì)于自然連接的抽樣，想得出每個(gè)元組精確的權(quán)重的代價(jià)是很高的，我們希望得出一個(gè)對(duì)于連接規(guī)模上界的估計(jì)，即得出W的上界，這樣的話(huà)時(shí)間開(kāi)銷(xiāo)就很小了，同時(shí)需要以一個(gè)概率拒絕這個(gè)采樣，這樣來(lái)保持抽樣的正確性。
論文中提到的，我們拒絕這個(gè)采樣的概率是
，我們來(lái)證明這個(gè)拒絕率的正確性（假設(shè)w(t0)=|J|，即連接的結(jié)果總數(shù)為|J|），邏輯和思路和上面Olken的思路類(lèi)似，如下圖所示：
具體的算法流程如圖所示：
同樣的為了方便理解，我們用一個(gè)例子來(lái)說(shuō)明抽樣的過(guò)程是怎么樣的：
如上圖所示，每個(gè)元組的權(quán)重上界標(biāo)記在圖中了，如果我們?cè)赗1中進(jìn)行抽樣，抽到第三個(gè)元組的概率就是5/（5+5+5）是1/3；拒絕率就是1-[(1+1+1)/5]就是2/5；
估計(jì)權(quán)重上界的方法
我們上面提到了每個(gè)元組的拒絕率的概念，若|J|是這條元組和后續(xù)關(guān)系做自然連接的結(jié)果數(shù)總和，那么對(duì)于每個(gè)元組的拒絕率就是
，我們需要讓這個(gè)上界盡可能的接近|J|，以達(dá)到拒絕率盡量小，一直接受的情況（這樣效率最高）。
那么下面就是對(duì)W上界的計(jì)算。作者對(duì)Olken、Chaudhuri和Acharya的方法進(jìn)行了泛化，此后又提出了另一種基于random walk的方法對(duì)W的值進(jìn)行估計(jì)和計(jì)算。值得注意的是，提出的四種方法中僅僅是計(jì)算W的方法不一樣，進(jìn)行抽樣均使用上面提到的方法。下面對(duì)這四種方法進(jìn)行闡述：
Exact Weight方法
這種方法是對(duì)Chaudhuri的方法進(jìn)行了推廣和泛化，把該方法從兩個(gè)關(guān)系推廣到多個(gè)關(guān)系。該方法被命名為Exact Weight(EW)方法。其實(shí)主要思想就是動(dòng)態(tài)規(guī)劃的思想，對(duì)每一個(gè)關(guān)系中的每一個(gè)元組精確計(jì)算其值。對(duì)于join關(guān)系中的最后一個(gè)表，將其初始化為1。再?gòu)暮笙蚯坝?jì)算每一個(gè)表中的結(jié)果，對(duì)于滿(mǎn)足連接條件的元組，將這些元組進(jìn)行累加，就是前一個(gè)表中對(duì)應(yīng)元組的權(quán)重的精確值。
這樣Chaudhuri的方法就進(jìn)行了拓展，從兩個(gè)表泛化到多個(gè)表中。
這種方法的好處就是，結(jié)果是非常準(zhǔn)確的，但是時(shí)間效率可能不高，它需要反復(fù)掃描各表中符合連接條件的元組進(jìn)行賦值。
Reverse Sampling方法
這種方法是對(duì)Acharya的方法進(jìn)行了移植，簡(jiǎn)稱(chēng)RS方法，這就直接是一種特殊情況，因?yàn)槊總€(gè)元組的權(quán)重都一定是1，直接1to1的采樣就行了。
Extended Olken方法
這種方法對(duì)Olken中的方法進(jìn)行了泛化和改進(jìn)。論文中將其命名為Extended Olken (EO)方法。作者定義了一個(gè)頻率的概念，即這個(gè)表種度最大的元組的權(quán)重就是這個(gè)表中所有元組的權(quán)重，即
。舉個(gè)例子如下圖所示：
綠色是估計(jì)的權(quán)重，紅色是準(zhǔn)確的權(quán)重，這樣算權(quán)重肯定是大于準(zhǔn)確值的，是準(zhǔn)確權(quán)重的一個(gè)上界，同時(shí)我們只需要從上到下掃描一遍這個(gè)表找到度最大的元組，將這個(gè)元組的權(quán)重作為所有元組的權(quán)重就行了，效率是高于EW算法的。
可以看出，如果只用olken_bound估計(jì)的話(huà)，和真實(shí)值的代價(jià)差距很大，代價(jià)就是，我們總是會(huì)被拒絕！
所以，作者還引入了AGM Bound。在chain join的情況下，作者給出了AGM Bound的簡(jiǎn)化形式如下：
這兩種方法在不同的情況下的優(yōu)劣程度也不一樣。如果某個(gè)表的最大頻率很小，那么Olken的方法得到的上界可能更小一些。而當(dāng)表的最大頻率很大時(shí)（比如接近表本身的大小），Olken方法得到的上界可能很大。因此此時(shí)選用AGM Bound可以使得整體的上界更小?；谶@樣的觀察，作者提出整合兩種方法的混合方法。
該混合方法通過(guò)一個(gè)閾值h統(tǒng)計(jì)每個(gè)表R上頻率大于h的元素和小于h的元素，并將該表分為RH（heavy部分）和RL（light部分）兩部分，并在計(jì)算中對(duì)這兩部分使用不同的方法進(jìn)行計(jì)算，得到整體較低的上界。對(duì)于RH傾向于使用AGM方法，對(duì)于RL部分傾向于使用Olken方法。
Online Exploration方法
這種方法被命名為Online Exploration(OE)方法。該方法在該join關(guān)系上進(jìn)行大量基于自然連接的隨機(jī)游走（在每一個(gè)參與連接的表上，在下一個(gè)表中可以與當(dāng)前元組進(jìn)行連接的元組中均勻隨機(jī)的選取一個(gè)），得到大量隨機(jī)游走的結(jié)果序列，并在這個(gè)過(guò)程中保存得到每一個(gè)序列的概率。
此后對(duì)于每一個(gè)表上的每一個(gè)元組，設(shè)置一個(gè)閾值。其中在random walk中到達(dá)該元組達(dá)到該閾值次數(shù)的，使用wander join estimator對(duì)上界進(jìn)行估計(jì)。對(duì)于未到達(dá)該閾值的，使用Exact Weight中的動(dòng)態(tài)規(guī)劃方法進(jìn)行計(jì)算。
對(duì)于random walk，我們隨機(jī)選擇一條通路，從后往前通過(guò)選中這條通路的概率，來(lái)計(jì)算當(dāng)前通路上各個(gè)元組的權(quán)值。
同樣的，用一個(gè)例子說(shuō)明隨機(jī)游走的算法是怎么樣的，如下圖所示的三個(gè)關(guān)系的鏈?zhǔn)竭B接操作：
首先最后一個(gè)表的元組權(quán)重全部賦值為1，其它表的初始權(quán)值設(shè)置為空（或?yàn)?），對(duì)于我隨機(jī)選中的這條通路，從后往前運(yùn)動(dòng)，先看R2表中對(duì)應(yīng)的元組，這個(gè)元組是唯一指向R3的，所以權(quán)重更新為1；再看R1中的元組這個(gè)元組以1/3的概率指向R2選中的元組，因此它的權(quán)重更新為1除以1/3，更新為3；再看t0的權(quán)重，它是以1/7的概率指向通路的那條元組的，因此它的權(quán)重更新為3除以1/7，更新為21；
實(shí)際上我們得到估計(jì)值的期望后，需要給予一定的置信度，利用上(α+1)/2-分位數(shù)計(jì)算置信區(qū)間。此后，使用期望+置信區(qū)間/2作為最終的W估計(jì)值。對(duì)于具體的計(jì)算公式，由于W函數(shù)應(yīng)為數(shù)據(jù)庫(kù)函數(shù)中的COUNT函數(shù)。給定如下的函數(shù)定義：
由以上公式得到期望和方差的值后，我們給定置信區(qū)間α，使用如下公式計(jì)算置信區(qū)間的大?。?/span>
其中zα是均值為0，方差為1的正態(tài)分布函數(shù)的(α+1)/2-分位數(shù)。
除了鏈?zhǔn)竭B接的其它連接形態(tài)
通過(guò)以上的兩個(gè)抽樣模型和計(jì)算權(quán)重模型，我們已經(jīng)可以求出任意的鏈?zhǔn)竭B接的抽樣結(jié)果了，而對(duì)于更多復(fù)雜的情況，我們還有樹(shù)形連接、有環(huán)連接和帶有選擇的連接，如下圖所示。
Acyclic Join
對(duì)于樹(shù)形的連接，對(duì)于權(quán)重計(jì)算模型，我們修正計(jì)算方法為：一個(gè)結(jié)點(diǎn)的權(quán)重等于他所有孩子結(jié)點(diǎn)的上界的乘積，這是因?yàn)楹⒆咏Y(jié)點(diǎn)的計(jì)算都是互相獨(dú)立的，所有孩子結(jié)點(diǎn)計(jì)算過(guò)程中并不依賴(lài)其它結(jié)點(diǎn)。
而抽樣模型則是采用遞歸的方式進(jìn)行抽樣，對(duì)于根節(jié)點(diǎn)的抽樣結(jié)果，我們要先對(duì)所有孩子結(jié)點(diǎn)進(jìn)行抽樣，然后將抽樣結(jié)果進(jìn)行合并即可，這就是一個(gè)遞歸的程序過(guò)程，而拒絕率我們則修正為以下情況。
Cyclic Join
而對(duì)于一個(gè)循環(huán)連接的情況，我們可以把任意一個(gè)帶有循環(huán)的連接，拆為鏈?zhǔn)降暮蜆?shù)形的連接，如圖所示，我們可以將以下連接的R3或者R5拿出來(lái)變成鏈?zhǔn)胶蜆?shù)形的連接。
特殊的，我們要對(duì)每個(gè)循環(huán)進(jìn)行驗(yàn)證，就是我們雖然將他們拆分成兩個(gè)連接，但是對(duì)于公共的屬性，我們要保證兩個(gè)連接的屬性對(duì)應(yīng)的值相同，如果不相同，我們就拒絕這個(gè)采樣。
帶有選擇的Join
對(duì)于有選擇的情況非常簡(jiǎn)單，我們只需要先對(duì)表加一個(gè)選擇過(guò)濾器就行了，可以采用必要的選擇下推技術(shù)，讓表盡早的變小，這樣反而能加速連接的速度。
作者實(shí)驗(yàn)的結(jié)果分析
抽樣時(shí)間對(duì)比
在TCP-H和推特關(guān)系兩個(gè)數(shù)據(jù)集進(jìn)行連接測(cè)試，對(duì)于特定的采樣RS算法是最快的；對(duì)于EO它在抽樣數(shù)比較小的時(shí)候，采樣時(shí)間很短，但是隨著抽樣數(shù)的增加，它在后面拒絕的概率越來(lái)越高，時(shí)間就會(huì)快速增加；而EW和OE算法，則由于上界估計(jì)的比較準(zhǔn)確，抽樣時(shí)間保持穩(wěn)定的提示（注意，雖然圖里面看起來(lái)抽樣個(gè)數(shù)隨著時(shí)間的變化情況是平的，變化不明顯；但是這是因?yàn)榭v坐標(biāo)是不是均勻的，是一個(gè)取對(duì)數(shù)才均勻變化的的坐標(biāo)軸）
延展性對(duì)比
若抽樣個(gè)數(shù)不變，隨著表規(guī)模的增大，EO算法在抽樣時(shí)，拒絕率總是很大，所以抽樣時(shí)間很長(zhǎng)；而對(duì)于計(jì)算權(quán)重時(shí)間，EO算法的預(yù)計(jì)算時(shí)間很低，所以基本不受表規(guī)模的影響；EW和OE算法與之相反。
對(duì)論文實(shí)驗(yàn)過(guò)程復(fù)現(xiàn)與設(shè)計(jì)方案
大致設(shè)計(jì)思路
由于計(jì)算資源和時(shí)間的限制，我們?cè)谙鄬?duì)原論文中的數(shù)據(jù)集較小的數(shù)據(jù)集上進(jìn)行試驗(yàn)。我們?cè)谙嗤膓uery上采樣不同規(guī)模的的sample，并記錄其運(yùn)行時(shí)間，同時(shí)我們用EO，EW,OE三種方法來(lái)估計(jì)權(quán)重，因?yàn)镽S方法需要連接條件是外鍵的情況。我們來(lái)通過(guò)實(shí)驗(yàn)比較這三種方法的時(shí)間效率。除此之外，我們比較三種方法在輸出第一個(gè)采樣結(jié)果時(shí)間的比較，以分析三種方法計(jì)算W值的效率。
根據(jù)原論文中的設(shè)置，我們?cè)O(shè)定如下查詢(xún)的query：
Query1: popular user, twitter user的2-join query。
Query2: twitter user，popular user, twitter user的3表循環(huán)鏈?zhǔn)絡(luò)oin query。
Query3: popular user, twitter user，popular user, twitter user，popular user的五表循環(huán)鏈?zhǔn)竭B接
實(shí)驗(yàn)的必要性分析
對(duì)于兩表連接
對(duì)于Query1僅僅進(jìn)行兩表的連接，使用如下sql語(yǔ)句：
結(jié)果如下圖所示：
如圖所示，結(jié)果就已經(jīng)達(dá)到3億級(jí)別了，這種級(jí)別的數(shù)據(jù)，很難全部放入后續(xù)的訓(xùn)練集中進(jìn)行訓(xùn)練，需要抽樣才行。
對(duì)于少量多表連接
對(duì)于Query2，使用如下sql語(yǔ)句進(jìn)行自然連接，結(jié)果如圖所示，運(yùn)行了1小時(shí)還沒(méi)算出來(lái)，已經(jīng)不可能先算出來(lái)全部結(jié)果再抽樣了。
對(duì)于大量多表連接
對(duì)于Query3，更不必說(shuō)，結(jié)果呈指數(shù)級(jí)別上升，普通的fulljoin已經(jīng)不可能計(jì)算出全部的結(jié)果了。甚至權(quán)重估計(jì)也變的緩慢，需要策略進(jìn)行優(yōu)化。
代碼部分的編寫(xiě)
整體設(shè)計(jì)思路是，針對(duì)論文提出的三種主要的估計(jì)權(quán)重上界的方法（省去了RS方法，因?yàn)镽S方法比較簡(jiǎn)單（只需要1 to 1 map），而且需要特定的數(shù)據(jù)集（外鍵連接的情況），就沒(méi)進(jìn)行實(shí)驗(yàn)）,在1，10，100，200的sample num上進(jìn)行實(shí)驗(yàn)，分別計(jì)算產(chǎn)生sample需要的時(shí)間和從開(kāi)始到產(chǎn)生第一個(gè)sample需要準(zhǔn)備的時(shí)間。
EW方法
就說(shuō)從最后一個(gè)表向前面掃描，最后一個(gè)表中元組的權(quán)重都是1，前面的表利用數(shù)據(jù)庫(kù)的倒敘查找操作進(jìn)行動(dòng)態(tài)規(guī)劃賦值即可。
關(guān)鍵代碼如圖所示：
EO方法
首先是對(duì)于EO方法，Olken bound需要獲得當(dāng)前表的最大頻率主鍵的頻率。在原論文中，作者提出在數(shù)據(jù)庫(kù)大規(guī)模查詢(xún)的過(guò)程中，最大主鍵頻率一般是會(huì)被統(tǒng)計(jì)和保存的。
然而在本次實(shí)驗(yàn)中，是直接將數(shù)據(jù)集中的數(shù)據(jù)加載到數(shù)據(jù)庫(kù)中做各種操作，因此不可能獲得這樣的統(tǒng)計(jì)數(shù)據(jù)，因此，我們顯式統(tǒng)計(jì)所有元組的頻率，然后記錄最大頻率元組的頻率。同時(shí)我在統(tǒng)計(jì)生成第一個(gè)sample準(zhǔn)備時(shí)間時(shí)，剪掉了這個(gè)過(guò)程所需的時(shí)間。
對(duì)于EO方法，需要將AGM bound 和 Olken bound結(jié)合使用。該思路的思想是當(dāng)表的最大頻率較大時(shí)（例如接近表的頻率），Olken bound可能會(huì)過(guò)大，此時(shí)適合使用AGM bound。否則適合使用Olken bound。因此將每一個(gè)表利用一個(gè)閾值頻率，將其分為Heavy和Light部分。我們將除第一個(gè)表外所有的表區(qū)分為Heavy和Light部分，并分別給出AGM bound和Olken bound下的結(jié)果，取其中較小的結(jié)果，最后相加。實(shí)驗(yàn)中我們?cè)O(shè)置閾值為400進(jìn)行heavy和light的區(qū)分?；诂F(xiàn)有計(jì)算能力，我們分別抽取1，10，100，200個(gè)sample進(jìn)行實(shí)驗(yàn)。
關(guān)鍵代碼如下圖所示：
OE方法
首先我們進(jìn)行random walk，記錄每個(gè)元組被游走的次數(shù)；隨后對(duì)于游走次數(shù)大于一定值的元組，我們認(rèn)為它是關(guān)鍵結(jié)點(diǎn)，這時(shí)候?qū)@個(gè)元組使用wanderJoin進(jìn)行估計(jì)，否則使用動(dòng)態(tài)規(guī)劃進(jìn)行估計(jì)，對(duì)于Online Exploration方法，我們?cè)O(shè)置random walk次數(shù)為2000000次，其中經(jīng)過(guò)次數(shù)大于200次的利用estimator進(jìn)行估計(jì)，小于200次的使用動(dòng)態(tài)規(guī)劃進(jìn)行估計(jì)。
關(guān)鍵代碼如圖所示。
對(duì)復(fù)現(xiàn)的實(shí)驗(yàn)結(jié)果的理解
實(shí)驗(yàn)環(huán)境
運(yùn)行環(huán)境
CPU: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz 1.99 GHz
RAM: 8GB
OS: Windows 10 64bit
程序環(huán)境
編譯環(huán)境：Python 3.8
IDE:Pycharm
數(shù)據(jù)庫(kù)：Sqlite3數(shù)據(jù)庫(kù)引擎
數(shù)據(jù)
我的筆記本無(wú)法對(duì)原論文中提供的數(shù)據(jù)集1進(jìn)行試驗(yàn)。正如論文所說(shuō)，經(jīng)過(guò)統(tǒng)計(jì)，發(fā)現(xiàn)整個(gè)數(shù)據(jù)集共有36G，超過(guò)19億條數(shù)據(jù)。且原論文中使用的popular user關(guān)系并未直接提供，需要進(jìn)行預(yù)處理（繪制粉絲關(guān)系圖，找到popular user）。而這個(gè)過(guò)程對(duì)于我現(xiàn)有的計(jì)算資源很難完成。因此，我選擇了相對(duì)適合當(dāng)前實(shí)驗(yàn)的數(shù)據(jù)集予以替代。
我找到了斯坦福SNAP提供的推特用戶(hù)關(guān)系數(shù)據(jù)集。該數(shù)據(jù)集2的數(shù)據(jù)規(guī)模在百萬(wàn)級(jí)別，大小約為100MB.我們使用SNAP for python工具建立該數(shù)據(jù)集的關(guān)系圖，并從中提取入度超過(guò)一定閾值的節(jié)點(diǎn)作為popular user，提取與這些節(jié)點(diǎn)有關(guān)的記錄組成popular user表，用做實(shí)驗(yàn)的join query。
經(jīng)過(guò)斯坦福提供的SNAP工具處理后，我們的twitter user人數(shù)為2420766個(gè)，popular user的人數(shù)為937159個(gè)；盡管如此，僅僅twitter user和popular user做連接操作，結(jié)果數(shù)就達(dá)到了315300960個(gè)，可以進(jìn)行算法的驗(yàn)證實(shí)驗(yàn)。
實(shí)驗(yàn)結(jié)果
利用以上設(shè)置，對(duì)于我們?cè)O(shè)置的Query，我們有如下運(yùn)行時(shí)間結(jié)果：
Query1 2-join sample產(chǎn)生的速度數(shù)據(jù)和圖表：
time=[[1.40625, 19.796875, 137.703125, 276.265625], [2.140625, 21.171875, 148.65625, 282.421875], [1.75, 19.40625, 141.375, 276.046875]]
Query2 3循環(huán)join sample產(chǎn)生的速度數(shù)據(jù)和圖表：
time=[[5.609375, 58.9375, 481.328125, 937.46875], [3.5625, 90.5625, 731.90625, 1655.0625], [2.734375, 50.84375, 396.15625, 786.53125]]
[1] ???數(shù)據(jù)集地址：http://twitter.mpi-sws.org/data-icwsm2010.html
[2] ???數(shù)據(jù)集地址：http://snap.stanford.edu/data/ego-twitter.html
Query3 5循環(huán)join sample產(chǎn)生的速度數(shù)據(jù)和圖表
time=[[1.984375, 29.75, 163.53125, 314.453125], [14.609375, 89.859375, 869.984375, 1629.109375], [1.890625, 27.140625, 154.9375, 280.53125]]
三種算法準(zhǔn)備時(shí)間對(duì)比
我們通過(guò)多次運(yùn)行sample，同時(shí)對(duì)不同方法準(zhǔn)備時(shí)間做了些優(yōu)化（數(shù)據(jù)量過(guò)少，分布過(guò)于密集，frequency的維護(hù)問(wèn)題），得出不同的方法在query中獲得第一個(gè)sample所需時(shí)間來(lái)比較三種方法進(jìn)行sample的準(zhǔn)備所需的時(shí)間。統(tǒng)計(jì)結(jié)果如下：
實(shí)驗(yàn)結(jié)果及分析
Sample分析
限于計(jì)算資源和時(shí)間，我們選用的抽取數(shù)量與原文中不完全相同。但根據(jù)論文中的實(shí)驗(yàn)結(jié)果和復(fù)現(xiàn)后的實(shí)驗(yàn)結(jié)果，運(yùn)行時(shí)間的走勢(shì)有一定相似:
首先由于OE方法和EW方法都會(huì)在某種情況下使用動(dòng)態(tài)規(guī)劃算法，只是OE算法對(duì)EW算法中關(guān)鍵結(jié)點(diǎn)進(jìn)行了優(yōu)化（使用隨機(jī)游走）則其W值相似度可能較高，且是比較準(zhǔn)確的，因此抽樣時(shí)候的通過(guò)率比較高，因此OE和EW在產(chǎn)生sample時(shí)間方面是近似且時(shí)間短的。
對(duì)于EO方法，可以看到在3個(gè)表以上的情況下其時(shí)間復(fù)雜度隨sample數(shù)增加很快。這是因?yàn)椋槿颖緮?shù)較少時(shí)，該方法計(jì)算得到的bound不如EW精確，仍可以以相對(duì)較快的速度進(jìn)行sample。然而當(dāng)sample數(shù)量迅速增加時(shí)，由于W上界計(jì)算的不精確性導(dǎo)致sample的拒絕率較高，因此sample所需時(shí)間迅速上升。
兩個(gè)表直接連接時(shí)，三種方法的時(shí)間大致相同，這是因?yàn)閹缀醪粫?huì)拒絕，權(quán)重不會(huì)影響到采樣的效率。
準(zhǔn)備時(shí)間分析
對(duì)于產(chǎn)生第一個(gè)sample所需時(shí)間的統(tǒng)計(jì)結(jié)果可以印證上述的推斷。根據(jù)統(tǒng)計(jì)結(jié)果，三種方法所需的準(zhǔn)備時(shí)間EO是最少的，OE方法次之，EW方法最高。
由于EO方法在計(jì)算W值的過(guò)程中不需要額外的準(zhǔn)備時(shí)間只需要通過(guò)最高的frequency進(jìn)行賦值即可，因此時(shí)間最短。
對(duì)于OE方法，具體的準(zhǔn)備時(shí)間與random walk次數(shù)有關(guān)系。OE在random walk過(guò)程中需要進(jìn)行下一個(gè)結(jié)點(diǎn)的選擇和概率的記錄，在所有random walk結(jié)束后才開(kāi)始計(jì)算W值，因此所花時(shí)間較長(zhǎng)。而對(duì)于遍歷次數(shù)比較多的元組，能迅速用wanderjoin估計(jì)權(quán)重，其余的才用EW估計(jì)。
EW對(duì)每一個(gè)節(jié)點(diǎn)使用動(dòng)態(tài)規(guī)劃精確計(jì)算W值，因此所需時(shí)間最長(zhǎng)。
反思
可以看到，盡管在相同的sample數(shù)量下實(shí)驗(yàn)取得和原論文中相同量級(jí)的結(jié)果，但實(shí)際上復(fù)現(xiàn)模型效果仍與原論文中的結(jié)果有很大差距。主要是OE算法的隨機(jī)游走時(shí)間好像過(guò)于緩慢；同時(shí)EW算法又有點(diǎn)偏快了，這一點(diǎn)比較讓人困擾。
首先是因?yàn)閺?fù)現(xiàn)選用的數(shù)據(jù)集相比原論文中使用的數(shù)據(jù)集小了很多，EO算法和EW算法在準(zhǔn)備時(shí)間上，沒(méi)有像論文那樣拉開(kāi)差距，如果數(shù)據(jù)量達(dá)到他的19億級(jí)別，EO算法在有frequency直接維護(hù)的前提下，速度應(yīng)該很快，直接賦值權(quán)重就可以進(jìn)行權(quán)重上界的估計(jì)。
本次復(fù)現(xiàn)中同時(shí)使用Sqlite3數(shù)據(jù)庫(kù)引擎進(jìn)行索引操作和用python進(jìn)行查找操作，數(shù)據(jù)庫(kù)層面進(jìn)行查找肯定是更快的，但是進(jìn)行隨機(jī)游走的時(shí)候，不得不用python手動(dòng)實(shí)現(xiàn)，這就導(dǎo)致了橫向?qū)Ρ壬?，OE算法好像慢了許多；而EW算法完全用數(shù)據(jù)庫(kù)索引查找，然后賦值，速度上快了一些。
論文中有大量未交代清楚的實(shí)現(xiàn)細(xì)節(jié)，因此復(fù)現(xiàn)結(jié)果可能有所差距。而且模型在不同的處理器上運(yùn)行，并行運(yùn)算方面我們也沒(méi)有考慮，因此算力不同導(dǎo)致實(shí)驗(yàn)結(jié)果相對(duì)較差。
論文閱讀的心得體會(huì)
第一次復(fù)現(xiàn)這種比較復(fù)雜的論文，首先感謝一位前輩的博客對(duì)這篇論文的學(xué)習(xí)筆記（https://zhuanlan.zhihu.com/p/328576706），結(jié)合自己的理解收益匪淺；
受到水平的限制，或者筆記本性能的限制，我在處理大數(shù)據(jù)集的時(shí)候常常會(huì)報(bào)錯(cuò)（論文里面10億級(jí)別的數(shù)據(jù)庫(kù)實(shí)在吃不消），經(jīng)過(guò)和朋友的交流溝通，還有請(qǐng)教了一位學(xué)長(zhǎng)，最后使用了另外一個(gè)數(shù)據(jù)集（數(shù)據(jù)集地址：http://snap.stanford.edu/data/ego-twitter.html），從而完成了本次實(shí)驗(yàn)；
大數(shù)據(jù)的代碼調(diào)試工作還是比較復(fù)雜的，有時(shí)候花30分鐘跑出來(lái)一個(gè)錯(cuò)誤的代碼，所以一定要有良好的代碼書(shū)寫(xiě)習(xí)慣，做好提前設(shè)計(jì)和模塊分塊，能盡量減少代碼錯(cuò)誤的可能。
總結(jié)來(lái)說(shuō)，本次實(shí)驗(yàn)較為準(zhǔn)確地理解論文的思想，復(fù)現(xiàn)了論文提出的對(duì)于chain join的sample算法和三種計(jì)算w值上界（W值）的方法。同時(shí)進(jìn)行試驗(yàn)，復(fù)現(xiàn)了論文有關(guān)Social graph數(shù)據(jù)集的相關(guān)實(shí)驗(yàn)。根據(jù)實(shí)驗(yàn)環(huán)境的實(shí)際情況，對(duì)原有的數(shù)據(jù)集進(jìn)行更換，對(duì)原有的部分實(shí)驗(yàn)方案進(jìn)行等價(jià)代替（例如頻率的統(tǒng)計(jì)），使得實(shí)驗(yàn)得以正常進(jìn)行。最后進(jìn)了反思，分析了實(shí)驗(yàn)中出現(xiàn)相關(guān)時(shí)間統(tǒng)計(jì)結(jié)果和與原文論文不一致的可能原因。
請(qǐng)輸入正文
