• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    一種高效的不確定圖上k步可達(dá)查詢處理算法

    2021-07-27 04:59:16周軍鋒
    新一代信息技術(shù) 2021年5期
    關(guān)鍵詞:結(jié)點(diǎn)頂點(diǎn)概率

    仲 悅,杜 明,周軍鋒

    (東華大學(xué),上海 201620)

    0 引言

    k步可達(dá)查詢用于研究在給定的數(shù)據(jù)圖上,起始點(diǎn)u是否能在路徑長度不大于k的前提下到達(dá)目標(biāo)頂點(diǎn)v。該研究有著廣泛的用途[1-3],例如在人際關(guān)系網(wǎng)絡(luò)圖[4]中,查詢兩個(gè)人能否通過 k個(gè)中間好友構(gòu)成熟人關(guān)系;道路網(wǎng)絡(luò)[5]中,用以查詢用戶是否可以從一個(gè)起點(diǎn)經(jīng)過k條道路到達(dá)目的地等。

    目前已有的 k步可達(dá)查詢研究都是基于確定圖[6-10],然而不確定圖[11]在實(shí)際生活中隨處可見,此時(shí)兩個(gè)實(shí)體之間的聯(lián)系的強(qiáng)弱程度表現(xiàn)為邊上的概率權(quán)值。例如,在道路網(wǎng)絡(luò)中時(shí)常會(huì)出現(xiàn)擁堵的情況,而擁堵的嚴(yán)重程度可以用概率來刻畫,從而導(dǎo)致本來可達(dá)的路徑暫時(shí)性不可達(dá);以及路由網(wǎng)絡(luò)中,傳感器測量誤差導(dǎo)致兩個(gè)路由之間的信號(hào)不穩(wěn)定也會(huì)產(chǎn)生不確定的邊。當(dāng)給定一個(gè)不確定圖,k步可達(dá)查詢不但要求兩點(diǎn)間可達(dá),而且還要求出可達(dá)的概率。最樸素的方法是枚舉所有的可能世界及其出現(xiàn)概率,接著計(jì)算每一個(gè)可能世界上u到v的可達(dá)情況,將結(jié)果相加。而每一個(gè)可能世界由于邊的出現(xiàn)情況不同,無法用預(yù)先處理的索引對(duì)不同的可能世界進(jìn)行查詢。一個(gè)n條邊的不確定圖有2n個(gè)可能世界,呈指數(shù)級(jí)。因此,即使該方法能得到最精確的結(jié)果,當(dāng)數(shù)據(jù)圖達(dá)到比較大的規(guī)模后,這種枚舉法顯然無法進(jìn)行,不具有擴(kuò)展性。

    針對(duì)上述問題,本文提出一種兩階段查詢方法,用于加速不確定圖上k步可達(dá)查詢的處理。其基本思想是:對(duì)可達(dá)和不可達(dá)的查詢基于不同索引分別處理。對(duì)不可達(dá)查詢,提出基于頂點(diǎn)覆蓋的高效索引來快速檢測是否k步不可達(dá)。對(duì)可達(dá)查詢,構(gòu)建位向量索引提前存儲(chǔ)可能世界來加速判斷。其總體思想是根據(jù)大數(shù)定律用抽樣近似法進(jìn)行計(jì)算,再用較小的內(nèi)存提前存儲(chǔ)抽樣結(jié)果。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文提出的索引和查詢方法 kRP的高效性。

    1 問題定義及相關(guān)工作

    1.1 問題定義

    給定一個(gè)有向無環(huán)不確定圖G=(V,E,P),其中V是圖中所有頂點(diǎn)的集合,E是圖中邊的集合,(u,v)表示從頂點(diǎn)u出發(fā)到頂點(diǎn)v有一條邊,在有向圖中(u,v)和(v,u)是兩條不同的邊,P是所有邊上概率的集合,且P={pi|0<pi≤1,pi為第i條邊上的概率權(quán)值}。

    以下介紹不確定圖、可能世界等相關(guān)定義及問題的定義。

    定義 1 不確定圖在圖中,邊上有權(quán)值,權(quán)值范圍在(0,1)區(qū)間內(nèi),且權(quán)值表達(dá)的含義為該邊出現(xiàn)的概率,將這樣的圖表示為G=(V,E,P),如圖1。

    圖1 不確定圖GFig. 1 Uncertain graph G

    定義2 可能世界對(duì)于不確定圖G=(V,E,P),若一個(gè)確定圖 G′=(V′,E′)滿足:(1)V′?V;(2)E′?E,則G′為G的一個(gè)可能世界。當(dāng)V′=V且E′=E的時(shí)候,G′稱為 G的完全圖。圖2是圖1的兩個(gè)可能世界。

    圖2 不確定圖G的兩個(gè)可能世界Fig.2 Possible Worlds of Uncertain Graph G

    定義3 k步可達(dá)在一個(gè)確定圖上,給定頂點(diǎn)u和頂點(diǎn)v,存在一條從u到v的路徑且路徑上的邊數(shù)不大于k,則稱u到v在k步以內(nèi)可達(dá),結(jié)果為TRUE或FALSE。

    問題定義 給定一個(gè)不確定圖G、頂點(diǎn)u和頂點(diǎn)v,以及步數(shù)約束k,求u到v在k步以內(nèi)可達(dá)的概率值。

    1.2 相關(guān)算法

    1.2.1 確定圖上k步索引

    確定圖上的 k步可達(dá)研究目前已經(jīng)有不少算法,文獻(xiàn)[7]提出了一種在頂點(diǎn)覆蓋集上建立路徑信息的索引?;舅枷胧请S機(jī)選取一條邊,將邊兩端的頂點(diǎn)都加入到覆蓋集C中,刪除這兩個(gè)頂點(diǎn)的所有出邊和入邊,再重新隨機(jī)選取一條邊,重復(fù)以上操作直到圖中沒有剩余的邊,然后在覆蓋集上建立k步以內(nèi)的路徑傳遞閉包。

    由于索引是在覆蓋集的基礎(chǔ)上構(gòu)建的,因此查詢可以分為三種情況,分別是(1)u和v都是覆蓋集C中的頂點(diǎn),此時(shí)只要查詢索引中u到v是否 k步可達(dá)就能直接得出結(jié)果;(2)起始點(diǎn) u是覆蓋集C中的頂點(diǎn)而目標(biāo)頂點(diǎn)v不在覆蓋集內(nèi),這種情況下把問題轉(zhuǎn)換為是否存在一個(gè)頂點(diǎn)w,且w是v的入結(jié)點(diǎn),滿足u到w的距離不大于k-1(u不在覆蓋集中且 v在覆蓋集中的情況類似,不再贅述);(3)u、v都不在覆蓋集里,此時(shí)查詢能否存在w1和w2,且w1是u的出結(jié)點(diǎn),w2是v的入結(jié)點(diǎn),滿足w1到w2的距離不大于k-2。

    這種索引方法存在規(guī)模大、效率低兩個(gè)問題,覆蓋集的大小直接影響了索引的大小和性能,然而對(duì)于覆蓋集的選取過于隨機(jī)性,導(dǎo)致生成的索引每次都不同。并且,該方法沒有考慮邊的不確定性,只能運(yùn)用在確定圖上。

    1.2.2 MC抽樣法

    在不確定圖中進(jìn)行蒙特卡洛(Monte Carlo)抽樣[12-13]是求解可達(dá)性問題的一種基本方法,主要思想如下:從起始點(diǎn)u出發(fā)BFS遍歷進(jìn)行不同可能世界的抽樣,只有當(dāng)邊(u,w)存在時(shí),才把頂點(diǎn)w加入BFS的運(yùn)算隊(duì)列中。在隊(duì)列為空前,如果找到了目標(biāo)頂點(diǎn)v,則該可能世界中兩者可達(dá),繼續(xù)下一次的圖抽樣和可達(dá)判斷。最終的結(jié)果為

    1.2.3 其他方法

    YILDIRIM在文獻(xiàn)[1]中提出GRAIL算法進(jìn)行可達(dá)性查詢,首先用不同遍歷方式生成d個(gè)區(qū)間標(biāo)簽加速不可達(dá)判斷,對(duì)于使用標(biāo)簽會(huì)產(chǎn)生誤判的查詢對(duì),提出使用特例列表進(jìn)行記錄,減少查詢時(shí)的遍歷操作。

    文獻(xiàn)[2]提出的 BFSI-B將查詢分為可達(dá)和不可達(dá)進(jìn)行處理,先構(gòu)建深度優(yōu)先生成樹,再基于樹利用區(qū)間標(biāo)簽判斷可達(dá)性,如果滿足區(qū)間包含要求,則計(jì)算兩頂點(diǎn)在樹中的層數(shù)差是否不大于k,從而得出k步可達(dá)查詢結(jié)果。

    Yano等人在文獻(xiàn)[9]中提出 PLL算法,該方法為每個(gè)頂點(diǎn) u建立inLabel和outLabel兩組標(biāo)簽,分別用來記錄能到達(dá)u的頂點(diǎn)和距離以及從u出發(fā)可達(dá)的頂點(diǎn)和距離。當(dāng)查詢時(shí)只需要求起始點(diǎn)的 outLabel與目標(biāo)頂點(diǎn)的 inLabel中的交集頂點(diǎn),通過判斷兩段距離相加之和與k的大小關(guān)系進(jìn)行判斷。

    2 兩階段求解算法

    對(duì)于給定兩點(diǎn)u和v的k步可達(dá)查詢,基本方法是從u出發(fā),進(jìn)行N次抽樣,統(tǒng)計(jì)這些可能世界中既滿足可達(dá)又滿足k步的樣本個(gè)數(shù),除以N值得到結(jié)果。這種方法存在大量冗余計(jì)算。例如,在圖3給定的有向無環(huán)不確定圖中求頂點(diǎn)v0到頂點(diǎn)v1的3步可達(dá)概率,按照以上方法,需要從頂點(diǎn) v0出發(fā)對(duì)邊依次進(jìn)行抽樣。然而從頂點(diǎn)v0出發(fā),無論怎么抽樣都不可能到達(dá)頂點(diǎn)v1。事實(shí)上,在這種無法k步可達(dá)的情況下直接抽樣毫無意義。對(duì)于該問題,本文提出結(jié)點(diǎn)覆蓋索引快速判斷不可達(dá)情況,從而能夠避免抽樣的昂貴代價(jià)。另外,對(duì)于可能到達(dá)的情況,本文提出高效的索引來加速查詢處理。下面分別進(jìn)行介紹。

    圖3 有向無環(huán)不確定圖Fig.3 Directed Acyclic Uncertain Graph G

    2.1 頂點(diǎn)覆蓋索引

    本文首先在不確定圖對(duì)應(yīng)的完全圖上構(gòu)建頂點(diǎn)覆蓋集,接著基于覆蓋集中的頂點(diǎn)構(gòu)建k步索引,用來判斷給定查詢是否能在確定圖上k步可達(dá)。只有在確定圖上k步可達(dá)的前提下,才需要計(jì)算它的可達(dá)概率,否則無需進(jìn)行抽樣操作。和k-reach算法構(gòu)造覆蓋集的方法不同:k-reach是通過隨機(jī)選邊的方式來構(gòu)造覆蓋集,然后計(jì)算覆蓋集中兩兩頂點(diǎn)之間的最短路徑。

    本文在構(gòu)建索引時(shí)選用的邊并非隨機(jī)抽取,而是優(yōu)先選擇度較大的頂點(diǎn)加入到覆蓋集。因?yàn)殡S機(jī)取邊的操作不僅會(huì)導(dǎo)致每次生成的頂點(diǎn)覆蓋集和索引都不一樣,索引效果也無法保證。

    例如,用 k-reach算法對(duì)圖 3中不確定圖 G的完全圖進(jìn)行頂點(diǎn)覆蓋計(jì)算的可能情況如下。假設(shè)第一次隨機(jī)取邊結(jié)果為 v1->v2,將頂點(diǎn) v1和頂點(diǎn)v2加入結(jié)點(diǎn)覆蓋集C,刪除頂點(diǎn)v1和頂點(diǎn)v2的所有鄰邊,即邊 v1->v4、v0->v2、v2->v3和v2->v4。第二次隨機(jī)取邊 v4->v7,相應(yīng)的將頂點(diǎn)v4和頂點(diǎn)v7加入覆蓋集C,并刪除鄰邊v4->v6。若第三次和第四次隨機(jī)取到的邊分別為 v6->v8和v5->v9,那么此次求解覆蓋集的過程如表1所示??梢钥吹阶罱K求得的覆蓋集C仍有8個(gè)頂點(diǎn),對(duì)圖的壓縮效果較差。

    表1 求解覆蓋集過程Tab.1 The progress of computing vertex cover

    但是如果按照大度頂點(diǎn)進(jìn)行求解的話,能獲得更小的頂點(diǎn)覆蓋集,生成的索引在查詢時(shí)也更高效,具體操作如下。首先選取度最大的頂點(diǎn),即頂點(diǎn) v2,刪除 v2的鄰邊。然后選取當(dāng)前度最大的頂點(diǎn) v4,刪除 v4的鄰邊。第三步選擇剩余圖中度最大的v8,最后選擇頂點(diǎn)v5??梢?,用這四個(gè)頂點(diǎn)就能構(gòu)成原圖的頂點(diǎn)覆蓋集,比隨機(jī)選邊的方式減少了一半的頂點(diǎn)規(guī)模。

    圖4 完全圖的kR+索引Fig.4 The kR+ index

    關(guān)于索引構(gòu)建的具體代碼設(shè)計(jì)如下。

    算法1kR+(完全圖G=(V,E))

    輸入:完全圖G=(V,E)

    輸出:基于頂點(diǎn)覆蓋集VC的索引kR+

    算法1用來構(gòu)建完全圖上的索引,加速判斷k步不可達(dá)的情況。第 1~7行按照上述大度頂點(diǎn)的方法構(gòu)建頂點(diǎn)覆蓋集,第1行初始化頂點(diǎn)覆蓋集VC為空集,第2行判斷是否有剩余邊,|E|表示邊數(shù),第 3行選擇當(dāng)前度最大的頂點(diǎn)賦給 u,在第4行加入覆蓋集VC,第5~6行刪除u的所有鄰邊并將鄰接點(diǎn)的度都減去一。第8~11行基于頂點(diǎn)覆蓋集構(gòu)造k步索引,對(duì)于頂點(diǎn)u和頂點(diǎn)v,若u能在k步以內(nèi)到達(dá)v,則給邊(u,v)賦予權(quán)值,表示路徑步數(shù),否則不建立邊。最后生成kR+索引。

    查詢時(shí),如查詢頂點(diǎn)v1到頂點(diǎn)v5是否3步可達(dá),由于v1不在覆蓋集內(nèi)而v5在覆蓋集內(nèi),則問題轉(zhuǎn)換為查詢頂點(diǎn)v1的出結(jié)點(diǎn)到頂點(diǎn)v5是否2步可達(dá)。頂點(diǎn)v1的出結(jié)點(diǎn)為v2和v4,由kR+索引查詢可知v2到v5在2步內(nèi)可達(dá),因此得出結(jié)論v1到v5可以3步到達(dá)。

    2.2 基于路徑的提前抽樣

    本文采用文獻(xiàn)[14]中提出的離線抽樣思想,把N個(gè)可能世界提前進(jìn)行抽樣并且以位向量[15]的索引形式存放在邊上。邊存在時(shí)記為 1,不存在記為0,第i個(gè)值表示在第i個(gè)可能世界上該邊的存在與否,每一條邊都有一個(gè)N大小的位向量,如[01100]可以看作5個(gè)抽樣圖中某一條邊的出現(xiàn)情況,該邊在第二、第三個(gè)可能世界上存在。由于該索引只需要0和1兩種值,因此可以采用C++中STL容器bitset或者二進(jìn)制int的存儲(chǔ)方式,從而節(jié)省索引所占內(nèi)存,時(shí)間復(fù)雜度為O(K|E| ),其中N是抽樣個(gè)數(shù),|E|是邊數(shù)。

    求解不確定圖上兩點(diǎn)間 k步可達(dá)概率的一個(gè)重要前提是它們之間能夠可達(dá),而這一點(diǎn)可以用完全圖上的頂點(diǎn)覆蓋索引進(jìn)行判斷。倘若在完全圖上無法滿足k步可達(dá),那么在任何一個(gè)可能世界中都不存在符合要求的路徑,此時(shí)查詢結(jié)果為0.如果完全圖的查詢結(jié)果為TRUE,再通過路徑枚舉剪枝可能世界中的邊,縮小查詢范圍。

    例如,在圖3上求v2->v8在3步內(nèi)可達(dá)概率,有 v2->v3->v8 和 v2->v4->v6->v8 兩條路徑。此時(shí)看 v2->v3和 v3->v8這兩條邊的第 1位,只有兩者都為 1的時(shí)候這條路徑才完整存在并且滿足 3步可達(dá),此時(shí)不再需要驗(yàn)證 v2->v4->v6->v8 路徑,只有在前一條路徑不符合要求時(shí)才進(jìn)行第二條路徑的查詢。

    本文提出枚舉路徑的時(shí)候可以采用 kDFS的方式,求解的如果是k步可達(dá)問題,則用一個(gè)大小為k+1的棧,把起始點(diǎn)壓入棧中,如果存在未被訪問過的鄰居頂點(diǎn)就依次入棧。與DFS不同的是該棧有固定大小,如果棧滿時(shí)還未到達(dá)目標(biāo)頂點(diǎn),則需先彈出棧頂元素后再入棧其余頂點(diǎn),直到??铡DFS的過程中若遇到了目標(biāo)頂點(diǎn),就把棧中所有元素記錄下來,作為一條可能路徑,該方法的時(shí)間復(fù)雜度為O(|Gk(u) |),即從源頂點(diǎn) u 出發(fā)k步內(nèi)可以到達(dá)的頂點(diǎn)個(gè)數(shù)。

    2.3 查詢算法

    算法2給出了在不確定圖G上查詢兩點(diǎn)間k步可達(dá)概率的kRP方法,設(shè)計(jì)代碼如下。

    算法2 kRP(u,v,k,N)

    輸入:起始點(diǎn)u,目標(biāo)頂點(diǎn)v,步數(shù)k,抽樣個(gè)數(shù)N

    輸出:u到v在k步內(nèi)可達(dá)的概率

    第一行中success用來計(jì)數(shù)可能世界里k步可達(dá)的數(shù)量。第2行是在生成的頂點(diǎn)覆蓋索引上進(jìn)行查詢,若u不在覆蓋集內(nèi),則轉(zhuǎn)換為u的出結(jié)點(diǎn)與v的k-1步查詢,v不在覆蓋集內(nèi)的情況不再贅述。如果該步驟判斷結(jié)果為 TRUE,則用固定大小的棧執(zhí)行深度優(yōu)先遍歷kDFS枚舉u到v的k步路徑。第5~9行,在預(yù)先存儲(chǔ)的N個(gè)可能世界中進(jìn)行查詢,當(dāng)路徑存在且查詢結(jié)果為TRUE時(shí),給計(jì)數(shù)器 success的值增加1。第10行用可達(dá)的抽樣圖個(gè)數(shù)除以總的個(gè)數(shù)N,即可得到概率結(jié)果。

    3 實(shí)驗(yàn)分析

    3.1 實(shí)驗(yàn)環(huán)境

    本文實(shí)驗(yàn)所使用的硬件平臺(tái)是Intel Core i7,主頻為2.60 GHz的CPU,RAM內(nèi)存為8 GB,操作系統(tǒng)為 Windows10 64位系統(tǒng)。代碼用 C++實(shí)現(xiàn),使用基礎(chǔ)BFS抽樣法進(jìn)行比較。查詢的距離k取值為3,抽樣個(gè)數(shù)N為1000個(gè),查詢對(duì)數(shù)100對(duì),其中3步內(nèi)可達(dá)的頂點(diǎn)對(duì)數(shù)和不可達(dá)的頂點(diǎn)對(duì)數(shù)各占一半。

    3.2 數(shù)據(jù)集

    本文使用8個(gè)數(shù)據(jù)集對(duì)實(shí)驗(yàn)進(jìn)行驗(yàn)證,Amaze和 Kegg都是與生物基因相關(guān)的網(wǎng)絡(luò)圖;Human和 Pubmed描述的是蛋白質(zhì)網(wǎng)絡(luò);Nasa是 XML文檔的數(shù)據(jù)集;Yago用來描述語義庫中的關(guān)系結(jié)構(gòu);Arxiv來自文獻(xiàn)[16];Web-Google是 Google網(wǎng)頁相關(guān)的數(shù)據(jù)集,具體信息見表 2,|V|表示頂點(diǎn)數(shù),|E|表示邊數(shù)。邊上的概率權(quán)值用隨機(jī)數(shù)生成,取值為(0,1)的左開右閉區(qū)間。查詢集用完全圖隨機(jī)生成 100對(duì)查詢對(duì),3步可達(dá)與不可達(dá)的比例為1∶1。

    表2 數(shù)據(jù)集Tab.2 Dataset

    3.3 性能比較分析

    3.3.1 索引大小

    表 3展示了在不同數(shù)據(jù)集上構(gòu)造的索引大小,單位均為MB。其中,kR+是本文提出的用頂點(diǎn)覆蓋集構(gòu)造的k步路徑索引,bitEdge是提前抽樣N個(gè)可能世界后存儲(chǔ)在邊上的索引,此處N值是1000,total表示兩個(gè)索引相加后的大小??梢钥闯鏊饕嫉膬?nèi)存都較小,即使是在幾十萬頂點(diǎn)的圖上,也僅要117.553 MB。

    表3 索引大小/MBTab.3 Inde x Size/MB

    3.3.2 索引構(gòu)建時(shí)間

    如表4所示,列出了構(gòu)造對(duì)應(yīng)索引所需的時(shí)間。在構(gòu)造bitEdge位向量索引時(shí)耗時(shí)較長,因?yàn)樵摬襟E相當(dāng)于對(duì)每一條邊都預(yù)先抽樣了N次,優(yōu)點(diǎn)是在后續(xù)的查詢時(shí),不論查詢對(duì)是多少,都無需再進(jìn)行額外的抽樣,且在查詢時(shí)可以直接得出結(jié)果?;陧旤c(diǎn)覆蓋構(gòu)造的 kR+索引不僅消耗時(shí)間少,還能加快處理不可達(dá)查詢。

    表4 索引構(gòu)建時(shí)間/msTab.4 Index Building Time/ms

    3.3.3 查詢時(shí)間

    由于樸素抽樣法中,對(duì)于每一組查詢對(duì),都需要從起始點(diǎn)開始向外BFS尋找目標(biāo)頂點(diǎn),且找到后還需要判斷兩個(gè)頂點(diǎn)之間的最短距離是否滿足 k步可達(dá),消耗了極大的時(shí)間。如果u不可達(dá)v或者可達(dá)步數(shù)超過k時(shí),更是浪費(fèi)了N次的BFS遍歷。

    而本文提出的kRP算法先判斷了查詢是否滿足可達(dá)和k步兩個(gè)條件,又枚舉出路徑縮小了需要查詢的邊數(shù),剪枝了不在路徑上的邊,查詢的時(shí)候通過讀取位向量就可以直接得出結(jié)果。當(dāng)一條邊在多次查詢中用到的時(shí)候,也不需要進(jìn)行重復(fù)抽樣,極大地縮短了查詢時(shí)間。查詢100對(duì)頂點(diǎn)對(duì)的時(shí)間結(jié)果如表5所示,可見樸素的抽樣法耗費(fèi)了大量時(shí)間在冗余遍歷上,只有在數(shù)據(jù)集nasa上,使用本文所提方法的構(gòu)建索引時(shí)間超出了樸素方法的時(shí)間,原因是該數(shù)據(jù)集的出度較小。而其余7個(gè)數(shù)據(jù)集中,構(gòu)建索引的時(shí)間都遠(yuǎn)遠(yuǎn)小于直接抽樣所耗費(fèi)的時(shí)間,實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出的kRP算法的有效性。

    表5 查詢時(shí)間/msTab.5 Query Time/ms

    4 結(jié)論

    本文分析了不確定圖上的 k步可達(dá)近似算法,即樸素抽樣的BFS方法,并針對(duì)該方法中直接抽樣過于耗時(shí)的問題,提出將查詢分為兩種情況進(jìn)行不同的處理。首先基于完全圖的頂點(diǎn)覆蓋集構(gòu)建了k步可達(dá)索引,其中在求解覆蓋集時(shí)按照頂點(diǎn)度從大到小的順序選擇頂點(diǎn)加入覆蓋集,從而縮小覆蓋集的規(guī)模。用索引判斷出無法k步可達(dá)的頂點(diǎn)對(duì),直接得出可達(dá)概率為 0,對(duì)這些查詢不再進(jìn)行后續(xù)抽樣計(jì)算。對(duì)于可以k步可達(dá)的查詢,本文提出基于路徑來減少抽樣時(shí)的邊數(shù),再用位向量的索引方式提前存儲(chǔ)抽樣圖例。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提方法的高效性。

    猜你喜歡
    結(jié)點(diǎn)頂點(diǎn)概率
    第6講 “統(tǒng)計(jì)與概率”復(fù)習(xí)精講
    過非等腰銳角三角形頂點(diǎn)和垂心的圓的性質(zhì)及應(yīng)用(下)
    第6講 “統(tǒng)計(jì)與概率”復(fù)習(xí)精講
    概率與統(tǒng)計(jì)(一)
    概率與統(tǒng)計(jì)(二)
    關(guān)于頂點(diǎn)染色的一個(gè)猜想
    Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
    基于Raspberry PI為結(jié)點(diǎn)的天氣云測量網(wǎng)絡(luò)實(shí)現(xiàn)
    基于DHT全分布式P2P-SIP網(wǎng)絡(luò)電話穩(wěn)定性研究與設(shè)計(jì)
    數(shù)學(xué)問答
    国产美女午夜福利| 少妇丰满av| 亚洲国产精品专区欧美| 久久久国产一区二区| 亚洲色图综合在线观看| 精品99又大又爽又粗少妇毛片| 另类亚洲欧美激情| 日韩av不卡免费在线播放| 在线观看三级黄色| 大香蕉97超碰在线| 国产大屁股一区二区在线视频| 亚洲欧美日韩东京热| 亚洲精品乱码久久久久久按摩| 七月丁香在线播放| 一区二区三区乱码不卡18| av女优亚洲男人天堂| 特大巨黑吊av在线直播| 欧美激情国产日韩精品一区| 亚洲熟女精品中文字幕| 深爱激情五月婷婷| 国产人妻一区二区三区在| av在线app专区| 一个人看视频在线观看www免费| 亚洲av国产av综合av卡| 91久久精品国产一区二区三区| 在现免费观看毛片| 欧美一级a爱片免费观看看| 亚洲av二区三区四区| 日本色播在线视频| 亚洲色图综合在线观看| 如何舔出高潮| 国产精品人妻久久久久久| 久久久久久九九精品二区国产| 各种免费的搞黄视频| 王馨瑶露胸无遮挡在线观看| 国产大屁股一区二区在线视频| 国产黄片美女视频| 国产一区二区在线观看日韩| 丝袜美腿在线中文| 亚洲av不卡在线观看| 日韩成人伦理影院| 午夜福利在线在线| 久久99热这里只频精品6学生| 人妻系列 视频| 一级毛片aaaaaa免费看小| 午夜福利在线观看免费完整高清在| 国产精品秋霞免费鲁丝片| 国精品久久久久久国模美| 日韩一区二区三区影片| 国产毛片在线视频| 少妇丰满av| 69人妻影院| 国产v大片淫在线免费观看| 中文资源天堂在线| av国产免费在线观看| 深爱激情五月婷婷| 欧美丝袜亚洲另类| 高清视频免费观看一区二区| 只有这里有精品99| 久久6这里有精品| 国产精品久久久久久久久免| 网址你懂的国产日韩在线| 又大又黄又爽视频免费| 美女内射精品一级片tv| 久久久久久久久久久丰满| 五月开心婷婷网| 日韩伦理黄色片| 少妇猛男粗大的猛烈进出视频 | av国产免费在线观看| 视频中文字幕在线观看| 精品99又大又爽又粗少妇毛片| 成人高潮视频无遮挡免费网站| 亚洲成人中文字幕在线播放| 亚洲高清免费不卡视频| 国产精品麻豆人妻色哟哟久久| 亚洲成人av在线免费| 精品国产三级普通话版| 日韩免费高清中文字幕av| 久久精品国产鲁丝片午夜精品| 国产黄片美女视频| 一级片'在线观看视频| 一本一本综合久久| 久热这里只有精品99| 久久精品人妻少妇| 女人久久www免费人成看片| 国内少妇人妻偷人精品xxx网站| 精品久久国产蜜桃| 国产精品国产三级国产专区5o| 免费av观看视频| 2021天堂中文幕一二区在线观| 99九九线精品视频在线观看视频| 成年免费大片在线观看| 人妻制服诱惑在线中文字幕| 免费不卡的大黄色大毛片视频在线观看| 婷婷色综合www| 国产成人精品一,二区| 制服丝袜香蕉在线| a级毛片免费高清观看在线播放| 亚洲精品第二区| 日韩在线高清观看一区二区三区| 日本午夜av视频| 一区二区三区四区激情视频| 中文字幕免费在线视频6| 看十八女毛片水多多多| 又粗又硬又长又爽又黄的视频| 乱系列少妇在线播放| kizo精华| 亚洲精品成人久久久久久| 欧美激情在线99| 熟妇人妻不卡中文字幕| 国产免费福利视频在线观看| 国产黄a三级三级三级人| 最近的中文字幕免费完整| 97超碰精品成人国产| 国产一区二区三区av在线| 女人十人毛片免费观看3o分钟| 免费黄网站久久成人精品| 色网站视频免费| 各种免费的搞黄视频| 亚洲成人久久爱视频| 亚洲精品一二三| 欧美日韩在线观看h| 丝袜美腿在线中文| 成人综合一区亚洲| 深夜a级毛片| 天天躁日日操中文字幕| 成人一区二区视频在线观看| 免费观看a级毛片全部| 卡戴珊不雅视频在线播放| 午夜精品国产一区二区电影 | 国产视频首页在线观看| 国产精品伦人一区二区| 国内精品美女久久久久久| 97在线视频观看| 免费看av在线观看网站| 欧美xxⅹ黑人| 97在线视频观看| 又爽又黄无遮挡网站| .国产精品久久| av又黄又爽大尺度在线免费看| 国产人妻一区二区三区在| 亚洲国产精品999| 日韩伦理黄色片| 高清欧美精品videossex| 久久精品熟女亚洲av麻豆精品| 秋霞伦理黄片| 亚洲av中文av极速乱| 在线观看美女被高潮喷水网站| 亚洲av不卡在线观看| 你懂的网址亚洲精品在线观看| 大码成人一级视频| 国产人妻一区二区三区在| 高清视频免费观看一区二区| 亚洲国产欧美在线一区| 免费看av在线观看网站| 国产精品一区二区性色av| 久久久精品欧美日韩精品| 日韩一区二区三区影片| 肉色欧美久久久久久久蜜桃 | 成人免费观看视频高清| 亚洲欧洲日产国产| 久久精品国产a三级三级三级| 欧美三级亚洲精品| 在线观看美女被高潮喷水网站| 日日啪夜夜爽| av网站免费在线观看视频| 亚洲av电影在线观看一区二区三区 | 美女被艹到高潮喷水动态| av播播在线观看一区| 天天躁日日操中文字幕| 尾随美女入室| 少妇人妻 视频| 男插女下体视频免费在线播放| 国产色婷婷99| 婷婷色麻豆天堂久久| 午夜福利视频精品| 久久亚洲国产成人精品v| 又大又黄又爽视频免费| 亚洲精品成人av观看孕妇| 成人高潮视频无遮挡免费网站| 亚洲精品乱久久久久久| 女的被弄到高潮叫床怎么办| 高清午夜精品一区二区三区| 国产视频首页在线观看| 最近最新中文字幕大全电影3| 2022亚洲国产成人精品| 禁无遮挡网站| 亚洲人成网站高清观看| 自拍偷自拍亚洲精品老妇| 91久久精品国产一区二区成人| 国产亚洲av片在线观看秒播厂| 男的添女的下面高潮视频| 亚洲精品久久午夜乱码| 男女那种视频在线观看| 97人妻精品一区二区三区麻豆| 嫩草影院入口| 可以在线观看毛片的网站| 自拍偷自拍亚洲精品老妇| 18禁在线无遮挡免费观看视频| 成人综合一区亚洲| 成人综合一区亚洲| 亚洲天堂av无毛| 国语对白做爰xxxⅹ性视频网站| 亚洲丝袜综合中文字幕| 搡女人真爽免费视频火全软件| 好男人在线观看高清免费视频| 特级一级黄色大片| 亚洲内射少妇av| 91精品国产九色| 全区人妻精品视频| 久久6这里有精品| 成人欧美大片| 国产一区二区在线观看日韩| a级毛色黄片| 国产有黄有色有爽视频| 听说在线观看完整版免费高清| 日本三级黄在线观看| av天堂中文字幕网| 一级毛片 在线播放| 少妇熟女欧美另类| 岛国毛片在线播放| 国内揄拍国产精品人妻在线| 欧美丝袜亚洲另类| av在线蜜桃| 亚洲,一卡二卡三卡| 国产探花在线观看一区二区| 国产精品一及| 欧美丝袜亚洲另类| 在线观看av片永久免费下载| 一区二区三区乱码不卡18| av在线亚洲专区| 五月玫瑰六月丁香| 亚洲av不卡在线观看| 欧美精品人与动牲交sv欧美| 男插女下体视频免费在线播放| 在线精品无人区一区二区三 | 高清欧美精品videossex| 特级一级黄色大片| 国产一区二区亚洲精品在线观看| 高清毛片免费看| 亚洲激情五月婷婷啪啪| 亚洲av免费高清在线观看| 伊人久久精品亚洲午夜| 国产亚洲最大av| 97在线人人人人妻| 精品久久久久久久久亚洲| 日韩亚洲欧美综合| 少妇高潮的动态图| 我要看日韩黄色一级片| 久久精品熟女亚洲av麻豆精品| 视频区图区小说| 亚洲人与动物交配视频| 国产精品一区二区性色av| 国产免费视频播放在线视频| 中国美白少妇内射xxxbb| 中国三级夫妇交换| 女的被弄到高潮叫床怎么办| 亚洲av中文av极速乱| 禁无遮挡网站| 色综合色国产| 男女国产视频网站| 日韩电影二区| 久久久久久久久大av| 超碰97精品在线观看| 两个人的视频大全免费| 亚洲综合精品二区| 一个人看的www免费观看视频| 偷拍熟女少妇极品色| 天堂网av新在线| 视频区图区小说| 人妻系列 视频| 大话2 男鬼变身卡| 婷婷色综合www| 99久久九九国产精品国产免费| 久久久精品欧美日韩精品| 免费少妇av软件| 亚洲国产av新网站| 中文字幕亚洲精品专区| 亚洲自拍偷在线| 黄色视频在线播放观看不卡| 国产免费福利视频在线观看| 亚洲欧美清纯卡通| 久久久久久久久久人人人人人人| 女人十人毛片免费观看3o分钟| 欧美高清成人免费视频www| 亚洲精品色激情综合| 丝瓜视频免费看黄片| 国产精品国产三级专区第一集| 99久国产av精品国产电影| 网址你懂的国产日韩在线| 国产精品精品国产色婷婷| 成人一区二区视频在线观看| 午夜激情久久久久久久| 国产免费又黄又爽又色| xxx大片免费视频| 欧美成人午夜免费资源| 视频区图区小说| 成人鲁丝片一二三区免费| 纵有疾风起免费观看全集完整版| 日本一二三区视频观看| 日本免费在线观看一区| 一本久久精品| 五月开心婷婷网| 综合色丁香网| kizo精华| 男女边吃奶边做爰视频| 老司机影院毛片| 国产综合精华液| 赤兔流量卡办理| 777米奇影视久久| 久久精品国产a三级三级三级| 哪个播放器可以免费观看大片| 99热6这里只有精品| 国产精品一区二区性色av| 插阴视频在线观看视频| 在线天堂最新版资源| 国产精品久久久久久av不卡| 国产精品一区二区三区四区免费观看| 国产高清国产精品国产三级 | 男的添女的下面高潮视频| 免费观看的影片在线观看| 成人免费观看视频高清| 欧美成人a在线观看| 搞女人的毛片| 深爱激情五月婷婷| 欧美人与善性xxx| 久久影院123| 成人欧美大片| 高清av免费在线| 国产 一区 欧美 日韩| 最新中文字幕久久久久| 亚洲精品乱码久久久v下载方式| 欧美日韩在线观看h| 青春草国产在线视频| 22中文网久久字幕| 久久久久国产精品人妻一区二区| 亚洲精品日韩在线中文字幕| 国产亚洲精品久久久com| 亚洲,欧美,日韩| 日韩欧美精品v在线| 欧美老熟妇乱子伦牲交| 成人毛片a级毛片在线播放| 日韩av免费高清视频| 中文乱码字字幕精品一区二区三区| 黄色日韩在线| 欧美一区二区亚洲| 精品亚洲乱码少妇综合久久| 男女边摸边吃奶| 97热精品久久久久久| 91精品一卡2卡3卡4卡| 亚洲av.av天堂| 婷婷色综合www| 人妻一区二区av| 黑人高潮一二区| 国产一级毛片在线| 永久免费av网站大全| 综合色丁香网| 欧美一级a爱片免费观看看| 亚洲成人中文字幕在线播放| 男人爽女人下面视频在线观看| 黄色配什么色好看| 日本猛色少妇xxxxx猛交久久| videos熟女内射| 久久精品人妻少妇| 18禁在线无遮挡免费观看视频| av专区在线播放| 国内揄拍国产精品人妻在线| 久久久久性生活片| 亚洲第一区二区三区不卡| 国产精品久久久久久av不卡| 亚洲人成网站在线观看播放| 91午夜精品亚洲一区二区三区| 亚洲色图综合在线观看| 国产精品麻豆人妻色哟哟久久| 黄片无遮挡物在线观看| 亚洲av电影在线观看一区二区三区 | 97精品久久久久久久久久精品| 久久久久久久久久久免费av| 亚洲内射少妇av| 别揉我奶头 嗯啊视频| av在线观看视频网站免费| 亚洲四区av| 少妇高潮的动态图| 在线观看国产h片| 国产一区有黄有色的免费视频| 欧美日韩在线观看h| 简卡轻食公司| 网址你懂的国产日韩在线| 免费大片18禁| 99久久精品一区二区三区| 色吧在线观看| 欧美 日韩 精品 国产| 男人舔奶头视频| 一本一本综合久久| 人人妻人人澡人人爽人人夜夜| 亚洲欧洲日产国产| 成人亚洲精品av一区二区| 人妻夜夜爽99麻豆av| 欧美另类一区| 久热久热在线精品观看| 国产女主播在线喷水免费视频网站| 国产男女内射视频| 水蜜桃什么品种好| 人人妻人人看人人澡| 欧美亚洲 丝袜 人妻 在线| 青青草视频在线视频观看| 一级av片app| 少妇高潮的动态图| www.色视频.com| 国产亚洲av嫩草精品影院| 国产精品麻豆人妻色哟哟久久| 亚洲av日韩在线播放| 97在线视频观看| 国产亚洲一区二区精品| 精品熟女少妇av免费看| 高清av免费在线| 成人鲁丝片一二三区免费| 免费av不卡在线播放| 成人无遮挡网站| 全区人妻精品视频| 国产成人aa在线观看| 免费高清在线观看视频在线观看| 中文字幕亚洲精品专区| 色吧在线观看| 亚洲丝袜综合中文字幕| 久久人人爽av亚洲精品天堂 | 国产精品福利在线免费观看| 亚洲人成网站在线播| 国产精品久久久久久精品电影| 真实男女啪啪啪动态图| 成人特级av手机在线观看| 欧美老熟妇乱子伦牲交| 卡戴珊不雅视频在线播放| 国产av码专区亚洲av| 成年人午夜在线观看视频| 午夜日本视频在线| 欧美日韩亚洲高清精品| 少妇人妻久久综合中文| 成人一区二区视频在线观看| 久久综合国产亚洲精品| 欧美最新免费一区二区三区| 好男人在线观看高清免费视频| 亚洲精品视频女| 色视频www国产| 五月伊人婷婷丁香| 观看免费一级毛片| av一本久久久久| 99re6热这里在线精品视频| 一个人观看的视频www高清免费观看| 国产老妇女一区| 好男人在线观看高清免费视频| 男人舔奶头视频| 极品教师在线视频| 97超视频在线观看视频| 欧美高清成人免费视频www| 久久99热这里只频精品6学生| .国产精品久久| 能在线免费看毛片的网站| 亚洲av日韩在线播放| 亚洲精品第二区| av国产免费在线观看| 伊人久久国产一区二区| 亚洲欧洲日产国产| 久久久久久久久久成人| 午夜老司机福利剧场| av在线蜜桃| 日产精品乱码卡一卡2卡三| 蜜桃亚洲精品一区二区三区| 少妇人妻久久综合中文| a级一级毛片免费在线观看| 视频中文字幕在线观看| 插逼视频在线观看| 午夜激情福利司机影院| 亚洲精品成人久久久久久| av黄色大香蕉| 综合色av麻豆| 亚洲经典国产精华液单| 丝袜脚勾引网站| 国产精品偷伦视频观看了| 久久久久久久大尺度免费视频| 中国三级夫妇交换| 日韩在线高清观看一区二区三区| 欧美成人a在线观看| 成人毛片60女人毛片免费| 色视频www国产| 菩萨蛮人人尽说江南好唐韦庄| 国产探花在线观看一区二区| 亚洲精品久久午夜乱码| 亚洲电影在线观看av| 秋霞在线观看毛片| 日韩不卡一区二区三区视频在线| 成人一区二区视频在线观看| 久久精品久久精品一区二区三区| 99精国产麻豆久久婷婷| 99热6这里只有精品| 视频区图区小说| 欧美97在线视频| 99九九线精品视频在线观看视频| 在线a可以看的网站| 亚洲欧美一区二区三区国产| 99热国产这里只有精品6| 国产色婷婷99| 久久99热这里只频精品6学生| 在线天堂最新版资源| 一级黄片播放器| 国内揄拍国产精品人妻在线| 成人一区二区视频在线观看| 亚洲色图综合在线观看| 国产免费一级a男人的天堂| 超碰97精品在线观看| 成人国产av品久久久| 国产亚洲最大av| 亚洲经典国产精华液单| 狂野欧美激情性bbbbbb| 国产精品av视频在线免费观看| 可以在线观看毛片的网站| av在线播放精品| 人妻夜夜爽99麻豆av| 国产一级毛片在线| 国产男人的电影天堂91| 欧美激情国产日韩精品一区| 国产亚洲精品久久久com| 亚洲欧美精品专区久久| 又黄又爽又刺激的免费视频.| 日韩强制内射视频| 色网站视频免费| 久久人人爽人人片av| 少妇人妻 视频| 人妻 亚洲 视频| 女人十人毛片免费观看3o分钟| 1000部很黄的大片| 中文字幕制服av| 久久久国产一区二区| 日韩,欧美,国产一区二区三区| 99久久精品国产国产毛片| 自拍偷自拍亚洲精品老妇| 国产亚洲av片在线观看秒播厂| 成人漫画全彩无遮挡| 99视频精品全部免费 在线| 亚洲成人久久爱视频| 亚洲av成人精品一二三区| 成人午夜精彩视频在线观看| 亚洲高清免费不卡视频| 亚洲精品视频女| 新久久久久国产一级毛片| 国产精品爽爽va在线观看网站| 成人亚洲欧美一区二区av| 国产精品国产三级国产专区5o| av免费在线看不卡| 久久久久久久久久成人| 五月天丁香电影| 精品久久久久久久久亚洲| 可以在线观看毛片的网站| 午夜福利视频精品| 亚洲av国产av综合av卡| 国产亚洲av片在线观看秒播厂| 免费大片18禁| av在线蜜桃| 中文字幕免费在线视频6| 国产一区二区亚洲精品在线观看| .国产精品久久| 免费在线观看成人毛片| 亚洲精品乱久久久久久| 天天一区二区日本电影三级| 亚洲国产精品成人久久小说| 日韩不卡一区二区三区视频在线| 免费av观看视频| 日本一二三区视频观看| 五月伊人婷婷丁香| 日韩欧美一区视频在线观看 | 亚洲精品久久午夜乱码| 国产高潮美女av| 久久久久久久国产电影| 国产一区二区亚洲精品在线观看| 三级男女做爰猛烈吃奶摸视频| 成年免费大片在线观看| 亚洲av福利一区| 少妇高潮的动态图| 亚洲精品成人av观看孕妇| 亚洲一级一片aⅴ在线观看| 人人妻人人爽人人添夜夜欢视频 | 日本猛色少妇xxxxx猛交久久| 成人亚洲精品一区在线观看 | 国产日韩欧美亚洲二区| 成人漫画全彩无遮挡| 在线看a的网站| 高清毛片免费看| 18禁在线播放成人免费| 成人毛片60女人毛片免费| 高清毛片免费看| 欧美性猛交╳xxx乱大交人| 身体一侧抽搐| 亚洲久久久久久中文字幕| 激情 狠狠 欧美| 国产成人精品久久久久久| 久久久久久久大尺度免费视频| 亚洲精品国产成人久久av| 欧美三级亚洲精品| 精品99又大又爽又粗少妇毛片| 嫩草影院精品99| 人妻夜夜爽99麻豆av| 亚洲精品一区蜜桃| 视频中文字幕在线观看| 国产永久视频网站| av在线app专区| 免费观看性生交大片5| 亚洲一区二区三区欧美精品 | 免费大片18禁| 中文天堂在线官网| 国产日韩欧美亚洲二区| 久久精品久久精品一区二区三区| 亚洲精品乱码久久久久久按摩| 亚洲人成网站高清观看| 午夜福利视频精品| 黄片无遮挡物在线观看|