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

    有向圖上k步可達(dá)查詢(xún)處理

    2021-07-11 10:56:10杜明林鏗周軍鋒
    關(guān)鍵詞:有向圖

    杜明 林鏗 周軍鋒

    摘 要:給定一個(gè)有向圖,一個(gè)k步可達(dá)查詢(xún)u→?kv用來(lái)回答在該圖中是否存在一條從頂點(diǎn)u到頂點(diǎn)v且長(zhǎng)度不大于k的有向路徑。k步可達(dá)查詢(xún)是一種基本的圖操作并在過(guò)去十年間被廣泛地研究。已有的k步可達(dá)查詢(xún)算法仍存在許多弊端,例如不可達(dá)查詢(xún)效率低,索引規(guī)模大和索引構(gòu)建時(shí)間長(zhǎng)等。本文針對(duì)上述問(wèn)題提出了2種優(yōu)化方法,分別是基于互逆拓?fù)湫蛱?hào)以及基于等價(jià)頂點(diǎn)的圖壓縮方法.前者提高了不可達(dá)查詢(xún)的效率,后者減少了索引規(guī)模和索引構(gòu)建時(shí)間。實(shí)驗(yàn)結(jié)果表明,本文提出的方法可以有效地處理k步可達(dá)查詢(xún),并支持大規(guī)模數(shù)據(jù)的處理。

    關(guān)鍵詞: 有向圖;k步可達(dá)查詢(xún);圖壓縮

    文章編號(hào): 2095-2163(2021)01-0008-07?中圖分類(lèi)號(hào):TP301.6?文獻(xiàn)標(biāo)志碼:A

    【Abstract】Given a directed graph, a k-hop reachability query u→?kv is used to answer whether there is a directed path from vertex u to vertex v and the length of the path is not greater than k. The k-hop reachability query is a basic graph operation and has been extensively studied in the past years. Existing algorithms still have many drawbacks, such as being inefficient for unreachability queries, large index size and long index construction time. This paper proposes two optimization approaches to make improvements, i.e., the mutual reversed topological order and the graph compression based on equivalent vertices. The former improves the efficiency of unreachability queries, and the latter reduces the index size and index construction time. The experimental results show that the proposed method can effectively improve the performance of k-hop reachability queries processing and support large-scale graph processing.

    【Key words】directed graph; k-hop reachability query; graph compression

    0?引?言

    隨著互聯(lián)網(wǎng)的快速發(fā)展,各種數(shù)據(jù)的規(guī)模日益龐大。圖是一種常見(jiàn)的數(shù)據(jù)表示模型,其中每個(gè)實(shí)體被簡(jiǎn)單地抽象成圖中的一個(gè)頂點(diǎn),實(shí)體間的關(guān)系被抽象成2個(gè)頂點(diǎn)之間的一條邊。圖被廣泛地應(yīng)用于各類(lèi)領(lǐng)域,如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等等[1-3]。在圖模型上的一個(gè)基本操作是回答2個(gè)頂點(diǎn)之間的可達(dá)性查詢(xún),即判斷在圖中是否存在一條從源頂點(diǎn)u出發(fā)到目標(biāo)頂點(diǎn)v結(jié)束的一條有向路徑??蛇_(dá)性查詢(xún)?cè)谶^(guò)去被廣泛地研究[4-8],然而在實(shí)際應(yīng)用中,可達(dá)性查詢(xún)僅能回答2個(gè)實(shí)體之間是否存在某種關(guān)系,而無(wú)法回答這種關(guān)系的強(qiáng)弱程度。

    另一種更有價(jià)值的操作是回答2個(gè)頂點(diǎn)之間的k步可達(dá)查詢(xún)[9-10],即判斷在圖中是否存在一條從源頂點(diǎn)u出發(fā)到目標(biāo)頂點(diǎn)v結(jié)束的一條有向路徑,并且滿(mǎn)足該路徑的長(zhǎng)度不超過(guò)k。k步可達(dá)查詢(xún)相較于可達(dá)性查詢(xún)能提供更多關(guān)于2個(gè)頂點(diǎn)之間的信息,本質(zhì)上,可達(dá)性查詢(xún)是一種特殊的k步可達(dá)查詢(xún),即當(dāng)k取∞時(shí)。k步可達(dá)查詢(xún)?cè)诂F(xiàn)實(shí)生活中有很多實(shí)際的應(yīng)用。比如在交通網(wǎng)絡(luò)中,經(jīng)常需要回答在2個(gè)地點(diǎn)之間是否存在一條路程不超過(guò)某個(gè)閾值的路線(xiàn)。又比如在社交網(wǎng)絡(luò)中,通過(guò)2個(gè)實(shí)體之間的距離來(lái)判斷這2個(gè)實(shí)體產(chǎn)生關(guān)聯(lián)的可能性。

    現(xiàn)有k步可達(dá)查詢(xún)算法大多只能運(yùn)行在有向無(wú)環(huán)圖上,而有向圖上的k步可達(dá)查詢(xún)的相關(guān)研究卻寥寥無(wú)幾。在有向圖上回答k步可達(dá)查詢(xún)的基本方法是BFS[11]或者DFS [12]?;诒闅v的方法因?yàn)椴痪邆淞己玫臄U(kuò)展性,因而查詢(xún)效率低下。另一個(gè)簡(jiǎn)單的實(shí)現(xiàn)方法是將任意2個(gè)頂點(diǎn)之間的最短路徑信息預(yù)先通過(guò)鄰接矩陣的方式存儲(chǔ)起來(lái),回答查詢(xún)時(shí)僅需要O(1)的時(shí)間內(nèi)即可返回結(jié)果。但是這種方法需要的空間代價(jià)過(guò)大,無(wú)法應(yīng)用于大規(guī)模數(shù)據(jù)圖。

    針對(duì)上述算法存在的問(wèn)題,文獻(xiàn)[9]提出了一種基于2-hop索引PLL。PLL的基本思想是通過(guò)為每個(gè)頂點(diǎn)預(yù)先建立一組出標(biāo)簽和一組入標(biāo)簽,這2組標(biāo)簽分別保存了部分頂點(diǎn)與該頂點(diǎn)之間的最短路徑信息,這些部分頂點(diǎn)被稱(chēng)為hop點(diǎn)。2個(gè)頂點(diǎn)之間的k步可達(dá)查詢(xún)問(wèn)題可以被轉(zhuǎn)化為判斷兩點(diǎn)間最短路徑的長(zhǎng)度是否小于等于k的問(wèn)題。

    PLL算法本身也存在低效性的問(wèn)題。首先,如果一個(gè)查詢(xún)頂點(diǎn)對(duì)之間是不可達(dá)的,那么PLL算法需要遍歷源頂點(diǎn)的所有出標(biāo)簽以及目標(biāo)頂點(diǎn)的所有入標(biāo)簽才能判斷出這對(duì)查詢(xún)頂點(diǎn)對(duì)是不可達(dá)的。其次,PLL算法在所有的頂點(diǎn)上構(gòu)建索引,因此導(dǎo)致構(gòu)建的索引的時(shí)間較長(zhǎng),同時(shí)構(gòu)建的索引規(guī)模也較大。

    針對(duì)PLL算法存在的以上2種問(wèn)題,本文提出了2種針對(duì)性的優(yōu)化方法。第一種是基于互逆拓?fù)湫蛱?hào)來(lái)加快不可達(dá)查詢(xún)的效率,第二種是基于等價(jià)頂點(diǎn)的圖壓縮方法,通過(guò)去除圖中的冗余頂點(diǎn)和冗余邊,使得圖盡可能地小。實(shí)驗(yàn)結(jié)果表明,本文提出的優(yōu)化方法可以顯著改善索引的構(gòu)建速度,索引規(guī)模更小。

    1?相關(guān)工作

    1.1?問(wèn)題定義

    給定一個(gè)有向圖G=(V,E),其中V={v1,v2,…,vn}是圖中頂點(diǎn)的集合,E={(u,v)|u,v∈V}是圖中邊的集合。當(dāng)一條邊e=(u,v)∈E時(shí),表示存在一條從頂點(diǎn)u指向頂點(diǎn)v的有向邊。對(duì)于每個(gè)頂點(diǎn)u,本文使用scc(u)來(lái)表示頂點(diǎn)u所在的強(qiáng)連通分量。同時(shí)使用outG(u)={v|(u,v)∈E}來(lái)表示頂點(diǎn)u的出鄰居集合以及使用inG(u)={v|(v,u)∈E}表示頂點(diǎn)u的入鄰居集合。用degout(u)=|outG(u)|表示頂點(diǎn)u的出度,degin(u)=|inG(u)|表示頂點(diǎn)u的入度。

    在一個(gè)有向無(wú)環(huán)圖中,拓?fù)渑判蚴菍D中頂點(diǎn)從偏序狀態(tài)轉(zhuǎn)化為全序狀態(tài)。一個(gè)頂點(diǎn)u的拓?fù)湫蛱?hào)是頂點(diǎn)全序關(guān)系的序號(hào),拓?fù)湫蛱?hào)大的頂點(diǎn)與拓?fù)湫蛱?hào)小的頂點(diǎn)之間不存在有向路徑。

    如果2個(gè)頂點(diǎn)u,v滿(mǎn)足outG(u)=outG(v)并且inG(u)=inG(v),即頂點(diǎn)u和頂點(diǎn)v存在相同的出鄰居集合以及相同的入鄰居集合,則稱(chēng)這2個(gè)頂點(diǎn)互為等價(jià)頂點(diǎn)。直觀上,2個(gè)頂點(diǎn)等價(jià)意味著二者可達(dá)相同的頂點(diǎn)集合,且可達(dá)二者的頂點(diǎn)集合也相同。

    問(wèn)題定義?給定一個(gè)有向圖G和一個(gè)k步可達(dá)查詢(xún)u→?kv,如果在G中存在一條從u出發(fā)到v的有向路徑,并且該路徑的長(zhǎng)度不超過(guò)k,則返回TRUE,否則返回FALSE。

    1.2?相關(guān)算法

    1.2.1?PLL算法

    PLL(Pruned Landmark Labeling)算法的基本思想是為圖中的每一個(gè)頂點(diǎn)u預(yù)先構(gòu)建2組標(biāo)簽Lout(u)={(h1,d1),…,(hi,di)}和Lin(u)={(h1,d1),…,(hj,dj)}。其中,Lout(u)保存了從頂點(diǎn)u可以到達(dá)的部分頂點(diǎn)以及頂點(diǎn)u到這些頂點(diǎn)之間的距離,類(lèi)似地,Lin(u)保存了從部分可以到達(dá)頂點(diǎn)u的頂點(diǎn)以及這些頂點(diǎn)到頂點(diǎn)u之間的距離。每個(gè)頂點(diǎn)標(biāo)簽中的每一對(duì)元素(h,d)表示hop點(diǎn)h以及h和該頂點(diǎn)之間的最短距離d。

    PLL算法將2個(gè)查詢(xún)頂點(diǎn)對(duì)之間的k步可達(dá)查詢(xún)轉(zhuǎn)化為了判斷源頂點(diǎn)u和目標(biāo)頂點(diǎn)v的最短距離是否小于等于k的問(wèn)題。由于標(biāo)簽中的hop點(diǎn)序號(hào)是以升序排列的,因此判斷2個(gè)標(biāo)簽中是否存在一個(gè)公共的hop點(diǎn)的時(shí)間復(fù)雜度為O(n+m),其中n,m分別表示出標(biāo)簽和入標(biāo)簽中元素的個(gè)數(shù)。

    PLL算法使用剪枝策略保證了建立的索引中盡可能地減少冗余的最短路徑信息。具體的做法是在對(duì)每一個(gè)hop點(diǎn)進(jìn)行BFS遍歷的過(guò)程中,如果已經(jīng)建立的2-hop索引能夠回答該hop點(diǎn)到當(dāng)前遍歷的頂點(diǎn)之間的最短路徑信息,則PLL算法不會(huì)將該hop點(diǎn)加入到當(dāng)前遍歷的頂點(diǎn)的2-hop標(biāo)簽中,同時(shí)不再?gòu)漠?dāng)前遍歷的頂點(diǎn)執(zhí)行BFS遍歷。

    1.2.2?K-Reach算法

    K-Reach算法[9,13]的基本思想是首先求解有向圖G的最小頂點(diǎn)覆蓋集C,然后在求解得到的C上建立傳遞閉包,這個(gè)傳遞閉包只包含了C中各個(gè)頂點(diǎn)之間的可達(dá)信息。

    當(dāng)回答一個(gè)k步可達(dá)查詢(xún)u→?kv時(shí),根據(jù)查詢(xún)頂點(diǎn)對(duì)u,v是否屬于C分為如下3種情況:

    (1)頂點(diǎn)u和頂點(diǎn)v都屬于最小頂點(diǎn)覆蓋集,此時(shí)可以直接通過(guò)建立的傳遞閉包來(lái)回答查詢(xún)。

    (2)頂點(diǎn)u和頂點(diǎn)v中只有一個(gè)屬于C,在這種情況下需要通過(guò)遍歷那個(gè)非最小頂點(diǎn)覆蓋集頂點(diǎn)的出鄰居集合的傳遞閉包或者入鄰居集合的傳遞閉包來(lái)回答查詢(xún)。

    (3)頂點(diǎn)u和頂點(diǎn)v中都不屬于C,這是最壞的情況,需要遍歷頂點(diǎn)u的出鄰居集合的傳遞閉包以及v的入鄰居集合的傳遞閉包來(lái)回答查詢(xún)。

    K-Reach算法存在如下問(wèn)題:首先該算法構(gòu)建的傳遞閉包索引只能用于回答k等于特定值的k步可達(dá)查詢(xún)。其次,當(dāng)查詢(xún)頂點(diǎn)對(duì)不屬于最小頂點(diǎn)覆蓋集時(shí),需要遍歷查詢(xún)頂點(diǎn)對(duì)的所有鄰居頂點(diǎn)的傳遞閉包。最后,隨著k值的增大,每個(gè)頂點(diǎn)的傳遞閉包數(shù)量將呈指數(shù)上升,因此該算法將無(wú)法有效地?cái)U(kuò)展到大圖上。

    2?優(yōu)化方法

    2.1?基于互逆拓?fù)湫蛱?hào)的查詢(xún)優(yōu)化方法

    在有向無(wú)環(huán)圖中,一個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)是該頂點(diǎn)在拓?fù)渑判蛑斜惶幚淼捻樞?。如果一個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)大于另一個(gè)頂點(diǎn)的拓?fù)湫蛱?hào),則前者必然不可達(dá)后者,反之不成立。因此,在一個(gè)有向無(wú)環(huán)圖中,可以通過(guò)判斷2個(gè)頂點(diǎn)的拓?fù)湫蛱?hào)大小來(lái)快速地回答2個(gè)頂點(diǎn)間的不可達(dá)情況。

    但是在有向圖中,由于可能存在強(qiáng)連通分量,而拓?fù)渑判虮仨氃跓o(wú)環(huán)圖中才能進(jìn)行,因此必須對(duì)有向圖進(jìn)行一定的變換。在本文中采取的解決方案是將每一個(gè)強(qiáng)連通分量(SCC)壓縮成一個(gè)超級(jí)頂點(diǎn),從而將有向圖轉(zhuǎn)換成有向無(wú)環(huán)圖。Tarjan算法是用來(lái)求解強(qiáng)連通分量的經(jīng)典算法,該算法可以在線(xiàn)性時(shí)間內(nèi)求解出每個(gè)頂點(diǎn)所屬的強(qiáng)連通分量。對(duì)于屬于同一個(gè)強(qiáng)連通分量中的頂點(diǎn),將為其賦予相同的拓?fù)湫蛱?hào)。

    在拓?fù)渑判蛑?,?duì)于一個(gè)頂點(diǎn)來(lái)說(shuō),不同的處理順序可以生成不同的拓?fù)湫蛱?hào),一個(gè)直觀的想法就是為每個(gè)頂點(diǎn)設(shè)置多個(gè)拓?fù)湫蛱?hào)從而過(guò)濾掉等多的不可達(dá)查詢(xún)。然而,每個(gè)拓?fù)湫蛱?hào)都需要一個(gè)整型的存儲(chǔ)空間,過(guò)多的拓?fù)湫蛱?hào)會(huì)導(dǎo)致索引規(guī)模增長(zhǎng)。因此,本文提出構(gòu)建互逆的拓?fù)湫蛱?hào)來(lái)達(dá)到最佳的查詢(xún)效率以及較小的空間開(kāi)銷(xiāo)。

    互逆拓?fù)湫蛱?hào)的大致思想是為每個(gè)頂點(diǎn)建立2個(gè)拓?fù)湫蛱?hào)。如果建立頂點(diǎn)u的第一個(gè)拓?fù)湫蛱?hào)要先于建立頂點(diǎn)v的第一個(gè)拓?fù)湫蛱?hào),則在建立第二個(gè)拓?fù)湫蛱?hào)時(shí),要優(yōu)先處理頂點(diǎn)v的拓?fù)湫蛱?hào)。這種機(jī)制保證了每個(gè)頂點(diǎn)的2個(gè)拓?fù)湫蛱?hào)構(gòu)成的區(qū)間盡可能地大,從而可以判斷等多的不可達(dá)情況。至此,研究可得算法1、算法2的代碼設(shè)計(jì)詳見(jiàn)如下。

    算法1?genTopo(G=(V,E))

    輸入:G=(V,E)

    輸出:所有頂點(diǎn)的互逆拓?fù)湫蛱?hào)

    1?G' ← tarjan(G)

    2?construct(G',X)

    3?construct(G',Y)

    4?return (X,Y)

    算法2?construct(G=(V,E),T)

    1?將入度為0的頂點(diǎn)按照特定的順序入棧S

    2?topNum ← 0

    3?while S≠ do

    4?u ← pop(S)

    5?Tu ← topNum

    6?topNum ← topNum + 1

    7?for each v ∈outG(u) do

    8?degin(v) ← degin(v)-1

    9?if degin(v) = 0 do

    10?push(S,v)

    算法1展示了在一個(gè)有向圖上求解互逆拓?fù)湫蛱?hào)的過(guò)程。算法的輸入是G,輸出是G上所有頂點(diǎn)的互逆拓?fù)湫蛱?hào)。第1行首先調(diào)用Tarjan算法將G中的強(qiáng)連通分量壓縮成超級(jí)頂點(diǎn)。第2~3行分別調(diào)用construct方法建立拓?fù)湫蛱?hào)。

    在算法2的construct方法中,第1行將入度為0的頂點(diǎn)按照特定的順序入棧S,第2行設(shè)置一個(gè)計(jì)數(shù)器topNum,用來(lái)記錄每個(gè)頂點(diǎn)的處理順序。第3行當(dāng)棧S不為空時(shí),執(zhí)行第4~10行的操作。第4行先彈出棧首頂點(diǎn)v,并在第5行將頂點(diǎn)v的拓?fù)湫蛱?hào)設(shè)置為topNum,同時(shí)第6行更新topNum。第7~10行按照特定的順序處理頂點(diǎn)v的所有出鄰居,將其入度均做減一處理,如果減后的入度為0,則將該出鄰居頂點(diǎn)入棧。

    對(duì)于在同一個(gè)強(qiáng)連通分量中的每個(gè)頂點(diǎn),各頂點(diǎn)的互逆拓?fù)湫蛱?hào)都等于相應(yīng)頂點(diǎn)所在的超級(jí)頂點(diǎn)的互逆拓?fù)湫蛱?hào)。Tarjan算法和construct方法的時(shí)間復(fù)雜度都為O(m), 其中m為有向圖G的邊數(shù),因此整個(gè)genTopo方法的時(shí)間復(fù)雜度為O(m)。

    2.2?基于等價(jià)頂點(diǎn)的圖壓縮方法

    在1.1節(jié)中給出了等價(jià)頂點(diǎn)的相關(guān)定義。對(duì)于任意2個(gè)相互等價(jià)的頂點(diǎn)u、v,在回答可達(dá)性查詢(xún)時(shí)(除查詢(xún)頂點(diǎn)對(duì)為(u,v)這種特殊情況,稍后討論)可以相互替換。例如當(dāng)回答從頂點(diǎn)u到頂點(diǎn)w(其中w≠v)的k步可達(dá)查詢(xún)時(shí),可以替換成從頂點(diǎn)v到頂點(diǎn)w的k步可達(dá)查詢(xún)。

    根據(jù)該特性,可以實(shí)現(xiàn)基于等價(jià)頂點(diǎn)的圖壓縮算法。具體的做法是對(duì)于互為等價(jià)頂點(diǎn)的一組頂點(diǎn),只保留其中的一個(gè)頂點(diǎn),同時(shí)刪除與該頂點(diǎn)等價(jià)的其他頂點(diǎn)。當(dāng)需要回答涉及被刪除頂點(diǎn)的k步可達(dá)查詢(xún)信息時(shí),可以通過(guò)與查詢(xún)頂點(diǎn)等價(jià)的那個(gè)保留頂點(diǎn)來(lái)判斷可達(dá)性。在對(duì)圖建立2-hop索引之前,通過(guò)先對(duì)圖進(jìn)行基于等價(jià)頂點(diǎn)的圖壓縮,能有效減小圖的規(guī)模,從而降低構(gòu)建索引的時(shí)間和索引大小。

    本文采用文獻(xiàn)[14]中提出的基于分治思想的求解等價(jià)頂點(diǎn)方法。該方法的基本思路是首先將頂點(diǎn)集V中的所有頂點(diǎn)視為可能相互等價(jià)的,再將集合V分成2個(gè)集合,這2個(gè)集合中的頂點(diǎn)可能互相等價(jià),但不同集合中的頂點(diǎn)不可能等價(jià)。接下來(lái)繼續(xù)對(duì)2個(gè)集合進(jìn)行類(lèi)似的分割,直到每個(gè)集合都無(wú)法再繼續(xù)分割下去。最后每個(gè)集合中存儲(chǔ)的頂點(diǎn)都是相互等價(jià)的,而集合之間的頂點(diǎn)是不可能等價(jià)的,該算法的時(shí)間復(fù)雜度是O(m),其中m是圖中邊的個(gè)數(shù)。

    對(duì)于2個(gè)等價(jià)頂點(diǎn)u、v,當(dāng)查詢(xún)頂點(diǎn)對(duì)為(u,v)時(shí),根據(jù)頂點(diǎn)u和頂點(diǎn)v是否位于同一個(gè)強(qiáng)連通分量中,會(huì)存在2種不同的情況,具體如圖1所示。在圖1(a)中,即頂點(diǎn)u和頂點(diǎn)v不在同一個(gè)SCC并且頂點(diǎn)u和頂點(diǎn)v互為等價(jià)頂點(diǎn),此時(shí)頂點(diǎn)u必然不可達(dá)頂點(diǎn)v、并且頂點(diǎn)v也不可達(dá)頂點(diǎn)u,因此查詢(xún)結(jié)果返回FALSE。在圖1(b)中,頂點(diǎn)u和頂點(diǎn)v位于同一個(gè)SCC、并且頂點(diǎn)u和頂點(diǎn)v互為等價(jià)頂點(diǎn),則u和v可能是k步可達(dá)的(取決于k值是否大于或等于這2個(gè)頂點(diǎn)之間的最短路徑長(zhǎng)度),此時(shí)可能就需要通過(guò)遍歷或者額外的索引來(lái)處理這種特殊情況。為了處理這種不常見(jiàn)但又確實(shí)存在的查詢(xún),導(dǎo)致每一次回答查詢(xún)時(shí)都要進(jìn)行額外的判斷,這顯然是十分繁瑣又低效的操作。

    為了解決該問(wèn)題,本文提出了一種新的策略,對(duì)于不在同一個(gè)SCC中的等價(jià)頂點(diǎn),將對(duì)其進(jìn)行壓縮操作。而對(duì)于處于同一個(gè)SCC中的等價(jià)頂點(diǎn),則將其視為不等價(jià)的,因此無(wú)需進(jìn)行壓縮,等價(jià)頂點(diǎn)之間的k步可達(dá)查詢(xún)可以直接通過(guò)建立的2-hop標(biāo)簽回答。該策略能有效地避免在這種特殊條件下的冗長(zhǎng)而低效的條件分支判斷以及遍歷圖的操作。

    2.3?查詢(xún)方法

    算法3給出了在2種優(yōu)化方法下的PLL算法的查詢(xún)方法,設(shè)計(jì)代碼依次展開(kāi)如下。

    算法3?query(u,v,k)

    輸入:源頂點(diǎn)u,目標(biāo)頂點(diǎn)v,查詢(xún)距離k

    輸出:TRUE/FALSE

    1?if Xu > Xv or Yu > Yv

    2?return FALSE

    3?ue ← Eu, ve ← Ev

    4?if ue = ve

    5?return FALSE

    6?ui ← 0, vi ← 0

    7?while ui < Lout(ue).size and vi < Lin(ve).size

    8?hu = Lout(ue)[ui].hop, hv = Lin(ve)[vi].hop

    9?du = Lout(ue)[ui].dist, dv = Lin(ve)[vi].dist

    10?if hu = hv do

    11?if du +?dv <= k do

    12?return TRUE

    13?else

    14?ui ← ui + 1, vi ← vi + 1

    15?else if hu < hv do

    16?ui ← ui + 1

    17?else

    18?vi ← vi + 1

    19?return FLASE

    算法3中,第1行先判斷頂點(diǎn)u的拓?fù)湫蛱?hào)X是否大于頂點(diǎn)v的拓?fù)湫蛱?hào)X以及頂點(diǎn)u的拓?fù)湫蛱?hào)Y是否大于頂點(diǎn)v的拓?fù)湫蛱?hào)Y。如果任意一個(gè)條件成立,表明頂點(diǎn)u不可達(dá)頂點(diǎn)v,因此第2行直接返回FALSE。第3行將頂點(diǎn)u和頂點(diǎn)v轉(zhuǎn)換成對(duì)應(yīng)的等價(jià)頂點(diǎn)ue和ve。數(shù)組E保存了每個(gè)頂點(diǎn)與其對(duì)應(yīng)的等價(jià)頂點(diǎn)的關(guān)系,該數(shù)組由2.2節(jié)中所描述的方法求出。第4行如果轉(zhuǎn)換后的等價(jià)頂點(diǎn)相等,則查詢(xún)結(jié)果返回FALSE。否則第6~19行通過(guò)PLL算法構(gòu)建的2-hop標(biāo)簽來(lái)回答查詢(xún)。

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

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

    本文實(shí)驗(yàn)中所使用的硬件平臺(tái)為Intel(R)Core(TM) i5-4200M @ 2.5GHz CPU,16G雙通道內(nèi)存,操作系統(tǒng)為Ubuntu 18.04.3 LTS。本次實(shí)驗(yàn)算法采用C++語(yǔ)言實(shí)現(xiàn),并且查詢(xún)距離k均取值為10。實(shí)驗(yàn)首先比較了PLL算法和PLL算法在分別使用2種優(yōu)化算法的情況下的索引構(gòu)造時(shí)間、索引大小以及查詢(xún)時(shí)間。隨后比較了PLL算法與同時(shí)使用2種優(yōu)化算法的索引構(gòu)造時(shí)間、索引大小以及查詢(xún)時(shí)間。

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

    本次研究中所使用的10個(gè)數(shù)據(jù)集見(jiàn)表1。這10個(gè)數(shù)據(jù)集都來(lái)自斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集(snap.stanford.edu/data/)。這些圖數(shù)據(jù)集都是有向有環(huán)圖,表1中標(biāo)注了每個(gè)數(shù)據(jù)集的頂點(diǎn)數(shù)V以及邊數(shù)E。本文將頂點(diǎn)數(shù)大于100000的數(shù)據(jù)集稱(chēng)為大數(shù)據(jù)集,因此本次實(shí)驗(yàn)中共有5個(gè)大數(shù)據(jù)集以及5個(gè)小數(shù)據(jù)集。本次實(shí)驗(yàn)使用的查詢(xún)集大小為1000000,其中可達(dá)頂點(diǎn)對(duì)和不可達(dá)頂點(diǎn)對(duì)的比例為1:1。

    3.3?性能比較分析

    3.3.1?2種優(yōu)化技術(shù)的比較

    PLL算法和PLL算法在分別使用了2種優(yōu)化方法之后的索引大小見(jiàn)表2。從表2中可以看到,互逆拓?fù)湫蛱?hào)所需的存儲(chǔ)空間最多,因?yàn)樾枰~外的2個(gè)整型值來(lái)存儲(chǔ)拓?fù)湫蛱?hào)(即PLL+Topo)。其次是PLL算法,最優(yōu)的是使用了基于等價(jià)頂點(diǎn)壓縮的PLL算法(即PLL+GC),因?yàn)閮H在部分點(diǎn)上建立2-hop索引,從而具有最小的索引大小。

    PLL算法和PLL算法在分別使用了2種優(yōu)化方法之后的索引構(gòu)造時(shí)間見(jiàn)表3。從表3中可以得到與在索引大小中類(lèi)似的結(jié)論,由于需要額外計(jì)算2個(gè)互逆拓?fù)湫蛱?hào),因此PLL+Topo的時(shí)間開(kāi)銷(xiāo)最多,但由于求解拓?fù)湫蛱?hào)是線(xiàn)性時(shí)間復(fù)雜度,因此差距并不明顯。其次,雖然PLL+GC方法花費(fèi)了線(xiàn)性時(shí)間來(lái)計(jì)算等價(jià)頂點(diǎn),但是由于進(jìn)行了圖壓縮,因此整個(gè)索引構(gòu)造時(shí)間相較于PLL算法減少了。

    PLL算法和PLL算法在分別使用了2種優(yōu)化方法之后的查詢(xún)時(shí)間見(jiàn)表4。其中,查詢(xún)距離k取10。從表4中可以看出在應(yīng)用了互逆拓?fù)湫蛱?hào)后的查詢(xún)效率有了明顯的提升,在一些數(shù)據(jù)集上有2~3倍左右的提升。PLL算法在回答不可達(dá)查詢(xún)時(shí)的時(shí)間消耗要大于回答可達(dá)的查詢(xún)頂點(diǎn)對(duì)所花費(fèi)的時(shí)間,而互逆拓?fù)湫蛱?hào)能在O(1)的時(shí)間內(nèi)回答絕大部分的不可達(dá)查詢(xún),因此提高了查詢(xún)的效率。對(duì)于PLL+GC方法來(lái)說(shuō),由于進(jìn)行了圖壓縮,因此建立的索引大小更小,從而使得查詢(xún)時(shí)需要遍歷的hop頂點(diǎn)數(shù)更少,因此也在一定程度上提高了查詢(xún)效率。

    3.3.2?PLL算法與PLL-O方法的比較

    PLL算法和PLL算法同時(shí)應(yīng)用了2種優(yōu)化方法(即PLL-O)之后的索引大小見(jiàn)表5。從表5中可以看出在絕大多數(shù)的數(shù)據(jù)集上,PLL-O方法的索引大小要優(yōu)于PLL算法。只有在極個(gè)別圖上(如HepTh),圖壓縮方法對(duì)索引大小帶來(lái)的收益沒(méi)能抵消2個(gè)拓?fù)涮?hào)帶來(lái)的空間開(kāi)銷(xiāo),此時(shí)PLL-O方法的索引規(guī)模會(huì)略大于PLL算法。

    PLL算法和PLL算法同時(shí)應(yīng)用了2種優(yōu)化方法之后的索引構(gòu)造時(shí)間見(jiàn)表6。由于綜合了圖壓縮方法的優(yōu)點(diǎn),PLL-O算法在整體上的性能都優(yōu)于PLL算法。

    PLL算法和PLL算法同時(shí)應(yīng)用了2種優(yōu)化方法之后的查詢(xún)時(shí)間見(jiàn)表7,其中查詢(xún)距離k取10。從表7中可以看出PLL-O方法相比于只應(yīng)用了圖壓縮的方法的查詢(xún)效率要高,然而相對(duì)于僅應(yīng)用互逆拓?fù)湫蛱?hào)的方法來(lái)說(shuō)性能差距不大。但綜合考慮索引大小以及索引構(gòu)造時(shí)間后,PLL-O方法較PLL算法以及僅使用一種優(yōu)化方法的PLL方法仍具有較大的優(yōu)勢(shì)。

    4?結(jié)束語(yǔ)

    本文針對(duì)已有k步可達(dá)查詢(xún)算法存在的不可達(dá)查詢(xún)效率低,索引構(gòu)造時(shí)間長(zhǎng),索引規(guī)模大等問(wèn)題提出了2種優(yōu)化的方法,分別是基于等價(jià)頂點(diǎn)的圖壓縮方法以及基于互逆拓?fù)湫蛱?hào)的不可達(dá)查詢(xún)優(yōu)化方法。實(shí)驗(yàn)結(jié)果表明,在同時(shí)應(yīng)用了這2種算法之后,PLL算法的查詢(xún)效率、索引大小以及索引構(gòu)造時(shí)間都有了明顯的提升。

    參考文獻(xiàn)

    [1]Van HELDEN J, NAIM A, MANCUSO R, et al. Representing and analysing molecular and cellular function using the computer[J]. Biological chemistry, 2000, 381(9-10): 921-935.

    [2]STANN F, HEIDEMANN J. RMST: Reliable data transport in sensor networks[C]//Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications. Anchorage,AK, USA:IEEE, 2003: 102-112.

    [3]KUMAR R, TUZHILIN A, FALOUTSOS C, et al. Social networks: Looking ahead[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Las Vegas, USA:ACM, 2008: 1060.

    [4]CHEN Yangjun, CHEN Yibin. An efficient algorithm for answering graph reachability queries[C]//2008 IEEE 24th International Conference on Data Engineering. Cancun,Mexico:IEEE, 2008: 893-902.

    [5]YU J X, CHENG Jiefeng. Graph reachability queries: A survey[M]//Managing and Mining Graph Data. Boston, MA:Springer, 2010: 181-215.

    [6]CHENG J, HUANG Silu, WU Huanhuan, et al. TF-Label: A topological-folding labeling scheme for reachability querying in a large graph[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2013: 193-204.

    [7]WANG H, HE H, YANG J, et al. Dual labeling: Answering graph reachability queries in constant time[C]//22nd International Conference on Data Engineering (ICDE'06). Atlanta, Georgia:IEEE, 2006: 75.

    [8]WEI Hao, YU J X, LU C,et al. Reachability querying: An independent permutation labeling approach[J]. The VLDB Journal, 2018,27:1-26.

    [9]YANO Y, AKIBA T, IWATA Y, et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. San Francisco, CA,USA:ACM, 2013: 1601-1606.

    [10]CHENG J, SHANG Zechao, CHENG Hong, et al. K-reach: Who is in your small world[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1292-1303.

    [11]BUNDY A, WALLEN L. Breadth-first search [M]// Catalogue of Artificial Intelligence Tools.Symbolic Computation (Artificial Intelligence). Berlin /Heidelberg: Springer , 1984:13.

    [12]STEIER D M, ANDERSON A P. Depth-first search [M]// Algorithm synthesis: A Comparative Study. US:Springer, 1989:47-62.

    [13]YANO Y, AKIBA T, IWATA Y, et al. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths[C]//Proceedings of the 22nd ACM international conference on Information & Knowledge Management. San Francisco, CA,USA:ACM, 2013: 1601-1606.

    [13]TANG Xian, CHEN Ziyang, LI Kai, et al. Efficient computation of the transitive closure size[J]. Cluster Computing,2019,22: 6517-6527.

    [14]ZHOU Junfeng, ZHOU Shijie, YU J X, et al. DAG reduction: Fast answering reachability queries[C]//Proceedings of the 2017 ACM International Conference on Management of Data. Raleigh:ACM, 2017: 375-390.

    猜你喜歡
    有向圖
    串并有向圖的判定算法及應(yīng)用實(shí)例
    科技資訊(2023年21期)2023-11-22 08:35:46
    廣義棱柱中的超歐拉有向圖
    極大限制弧連通有向圖的度條件
    有向圖的Roman k-控制
    依賴(lài)于團(tuán)數(shù)的有向圖弧連通度的下界
    超歐拉和雙有向跡的強(qiáng)積有向圖
    關(guān)于超歐拉的冪有向圖
    一個(gè)特殊本原有向圖的廣義competition及scrambling指數(shù)
    本原有向圖的scrambling指數(shù)和m-competition指數(shù)
    一類(lèi)含三個(gè)圈的本原有向圖的m-competition指數(shù)
    在线精品无人区一区二区三| 美女午夜性视频免费| 18+在线观看网站| 捣出白浆h1v1| 看十八女毛片水多多多| kizo精华| 国产精品无大码| 最黄视频免费看| 在线观看三级黄色| 国产精品欧美亚洲77777| 亚洲国产精品一区三区| 午夜91福利影院| 春色校园在线视频观看| 国产 精品1| 国产精品久久久久久精品古装| 如何舔出高潮| 久久狼人影院| 亚洲经典国产精华液单| 电影成人av| 久久精品国产亚洲av高清一级| 亚洲精品,欧美精品| 视频区图区小说| 可以免费在线观看a视频的电影网站 | 亚洲久久久国产精品| 在线免费观看不下载黄p国产| 最近最新中文字幕免费大全7| 久久99一区二区三区| 国产成人午夜福利电影在线观看| 久久精品国产亚洲av涩爱| 熟女av电影| 人人妻人人爽人人添夜夜欢视频| 国产精品一区二区在线观看99| 久久女婷五月综合色啪小说| 欧美精品一区二区大全| 黄片无遮挡物在线观看| 国产一区二区在线观看av| av在线播放精品| 热re99久久精品国产66热6| 少妇被粗大的猛进出69影院| 视频在线观看一区二区三区| 成人18禁高潮啪啪吃奶动态图| 亚洲一区中文字幕在线| 精品国产一区二区三区四区第35| 免费观看av网站的网址| 日韩av免费高清视频| 亚洲综合精品二区| 精品一区二区三卡| 欧美精品一区二区大全| 久久午夜综合久久蜜桃| 国产无遮挡羞羞视频在线观看| 国产精品国产av在线观看| 国产福利在线免费观看视频| 午夜久久久在线观看| 99久久精品国产国产毛片| 精品亚洲乱码少妇综合久久| 日韩一区二区视频免费看| 水蜜桃什么品种好| 国产亚洲欧美精品永久| 爱豆传媒免费全集在线观看| www.精华液| 青春草亚洲视频在线观看| 国产精品免费大片| 国产精品免费大片| 制服人妻中文乱码| 一二三四中文在线观看免费高清| 我要看黄色一级片免费的| 97精品久久久久久久久久精品| 如何舔出高潮| 亚洲经典国产精华液单| 可以免费在线观看a视频的电影网站 | 免费av中文字幕在线| 久久久久精品性色| 亚洲精华国产精华液的使用体验| 国产精品无大码| 国产综合精华液| 建设人人有责人人尽责人人享有的| 国产av一区二区精品久久| 纵有疾风起免费观看全集完整版| 国产精品 欧美亚洲| 亚洲国产色片| 久久亚洲国产成人精品v| 丝袜人妻中文字幕| 91久久精品国产一区二区三区| 国产精品免费视频内射| 一本一本久久a久久精品综合妖精 国产伦在线观看视频一区 | 久久青草综合色| 国产精品久久久久久精品古装| 欧美人与善性xxx| 黄片无遮挡物在线观看| 丝袜美足系列| 日韩电影二区| 欧美精品人与动牲交sv欧美| 黑人欧美特级aaaaaa片| 婷婷成人精品国产| 黑丝袜美女国产一区| 久久久精品国产亚洲av高清涩受| 在现免费观看毛片| 热99久久久久精品小说推荐| 久久精品国产自在天天线| 亚洲,一卡二卡三卡| 观看美女的网站| 黄色 视频免费看| 飞空精品影院首页| 欧美97在线视频| 黄色配什么色好看| 亚洲av日韩在线播放| 欧美精品一区二区免费开放| 99热网站在线观看| 欧美日韩av久久| 人妻 亚洲 视频| 日韩一本色道免费dvd| 91久久精品国产一区二区三区| 一边摸一边做爽爽视频免费| 精品人妻熟女毛片av久久网站| 制服诱惑二区| 亚洲国产欧美网| 999久久久国产精品视频| 欧美变态另类bdsm刘玥| 叶爱在线成人免费视频播放| 另类精品久久| 天天躁狠狠躁夜夜躁狠狠躁| 不卡视频在线观看欧美| 亚洲一区二区三区欧美精品| 黄片无遮挡物在线观看| 国产精品三级大全| 欧美日韩国产mv在线观看视频| 免费观看无遮挡的男女| 91久久精品国产一区二区三区| 丰满少妇做爰视频| 久久人人97超碰香蕉20202| 免费在线观看完整版高清| 2022亚洲国产成人精品| 伦理电影免费视频| 亚洲国产最新在线播放| 亚洲精品成人av观看孕妇| 一二三四在线观看免费中文在| 欧美av亚洲av综合av国产av | 亚洲精华国产精华液的使用体验| 免费观看av网站的网址| 日韩精品有码人妻一区| 青春草亚洲视频在线观看| www日本在线高清视频| 久热久热在线精品观看| 久久精品aⅴ一区二区三区四区 | 自拍欧美九色日韩亚洲蝌蚪91| 国产1区2区3区精品| 日韩中文字幕欧美一区二区 | 亚洲婷婷狠狠爱综合网| 建设人人有责人人尽责人人享有的| 久久国产精品男人的天堂亚洲| 久久精品人人爽人人爽视色| 青草久久国产| av片东京热男人的天堂| 91在线精品国自产拍蜜月| 1024视频免费在线观看| 边亲边吃奶的免费视频| 日本色播在线视频| 亚洲av成人精品一二三区| 亚洲精品视频女| 欧美精品高潮呻吟av久久| 日韩视频在线欧美| 久久亚洲国产成人精品v| 美女大奶头黄色视频| 国产97色在线日韩免费| 校园人妻丝袜中文字幕| 欧美日韩精品网址| 天天影视国产精品| 老鸭窝网址在线观看| 制服人妻中文乱码| 十八禁高潮呻吟视频| 午夜福利网站1000一区二区三区| 久久97久久精品| 日韩制服丝袜自拍偷拍| 亚洲激情五月婷婷啪啪| 高清不卡的av网站| av在线老鸭窝| 五月伊人婷婷丁香| 9热在线视频观看99| 在线精品无人区一区二区三| 中文精品一卡2卡3卡4更新| 最近的中文字幕免费完整| 91精品三级在线观看| 色婷婷av一区二区三区视频| 国产亚洲一区二区精品| 亚洲精品美女久久av网站| 少妇人妻久久综合中文| 亚洲一区中文字幕在线| 久久久国产精品麻豆| 国产一区亚洲一区在线观看| 晚上一个人看的免费电影| 中文字幕另类日韩欧美亚洲嫩草| 人人澡人人妻人| 国产日韩欧美亚洲二区| 国产精品一国产av| 啦啦啦中文免费视频观看日本| 99热全是精品| 精品亚洲乱码少妇综合久久| 欧美人与善性xxx| 久久免费观看电影| 国产精品免费大片| 男人爽女人下面视频在线观看| 免费黄频网站在线观看国产| 肉色欧美久久久久久久蜜桃| 国产精品秋霞免费鲁丝片| 在线观看美女被高潮喷水网站| 欧美日韩精品成人综合77777| 国产高清国产精品国产三级| 亚洲精品日本国产第一区| 黄网站色视频无遮挡免费观看| 久热这里只有精品99| 精品国产露脸久久av麻豆| 一级毛片 在线播放| av国产久精品久网站免费入址| 久久久久久久大尺度免费视频| 日本欧美视频一区| 国产不卡av网站在线观看| 亚洲欧美中文字幕日韩二区| 性色av一级| 亚洲精华国产精华液的使用体验| av有码第一页| 飞空精品影院首页| 国产亚洲av片在线观看秒播厂| 波野结衣二区三区在线| 日韩一本色道免费dvd| 午夜激情久久久久久久| 嫩草影院入口| 黄网站色视频无遮挡免费观看| 91成人精品电影| 国产精品av久久久久免费| 视频区图区小说| 久久国产亚洲av麻豆专区| 999久久久国产精品视频| www.av在线官网国产| 欧美日韩一级在线毛片| 欧美成人午夜精品| 高清黄色对白视频在线免费看| 久久99热这里只频精品6学生| 国产又爽黄色视频| 男人操女人黄网站| 老司机亚洲免费影院| 亚洲在久久综合| 亚洲成国产人片在线观看| 久久久精品区二区三区| 天天躁夜夜躁狠狠久久av| 国产精品久久久久久av不卡| 国产伦理片在线播放av一区| 国产男女内射视频| 91成人精品电影| 街头女战士在线观看网站| 咕卡用的链子| 久久精品国产a三级三级三级| 中文天堂在线官网| 丝袜美足系列| 久久久久国产网址| 亚洲欧洲日产国产| 涩涩av久久男人的天堂| 成人手机av| 欧美国产精品va在线观看不卡| 在线天堂中文资源库| 日本wwww免费看| 国产亚洲最大av| 精品一区二区免费观看| 国产片内射在线| 一本大道久久a久久精品| 999久久久国产精品视频| 欧美人与性动交α欧美软件| 中文字幕亚洲精品专区| 国产精品一区二区在线观看99| 2022亚洲国产成人精品| 激情五月婷婷亚洲| 日韩中文字幕视频在线看片| 久久这里只有精品19| 国产亚洲最大av| 九色亚洲精品在线播放| 日本欧美视频一区| 国产女主播在线喷水免费视频网站| 免费久久久久久久精品成人欧美视频| av女优亚洲男人天堂| 午夜免费男女啪啪视频观看| 国产精品国产三级专区第一集| 国产综合精华液| av女优亚洲男人天堂| 日日爽夜夜爽网站| 亚洲美女搞黄在线观看| 大话2 男鬼变身卡| 欧美另类一区| 国产精品久久久久久久久免| www.av在线官网国产| 日本色播在线视频| 国产1区2区3区精品| 亚洲少妇的诱惑av| 电影成人av| 青青草视频在线视频观看| 自线自在国产av| 国产精品一区二区在线观看99| 18禁裸乳无遮挡动漫免费视频| 激情五月婷婷亚洲| 久久久精品国产亚洲av高清涩受| 天美传媒精品一区二区| 啦啦啦啦在线视频资源| 9热在线视频观看99| 国产日韩欧美在线精品| 丝袜人妻中文字幕| 久久国产亚洲av麻豆专区| 久久久a久久爽久久v久久| 在线看a的网站| 亚洲欧洲日产国产| a级毛片黄视频| 另类亚洲欧美激情| 国产欧美日韩综合在线一区二区| 超碰成人久久| 国产伦理片在线播放av一区| 性少妇av在线| 久久人人爽人人片av| 老司机影院毛片| 国产男女内射视频| 99久国产av精品国产电影| 久久久欧美国产精品| 国产精品无大码| 欧美人与性动交α欧美软件| 少妇的逼水好多| 久久这里只有精品19| 曰老女人黄片| 久久鲁丝午夜福利片| 大码成人一级视频| 一级黄片播放器| 国产av精品麻豆| 国产高清国产精品国产三级| 新久久久久国产一级毛片| 九草在线视频观看| 最近最新中文字幕免费大全7| www日本在线高清视频| 男人添女人高潮全过程视频| 久久免费观看电影| 日本爱情动作片www.在线观看| 波多野结衣av一区二区av| 日韩一本色道免费dvd| 国产av国产精品国产| 午夜精品国产一区二区电影| 国产有黄有色有爽视频| 多毛熟女@视频| 女的被弄到高潮叫床怎么办| 狠狠婷婷综合久久久久久88av| 亚洲综合色网址| 性色av一级| 欧美日韩一区二区视频在线观看视频在线| 各种免费的搞黄视频| 一本久久精品| 日韩欧美一区视频在线观看| 久久99精品国语久久久| 9色porny在线观看| 黄色 视频免费看| 五月开心婷婷网| 多毛熟女@视频| 久久久久久人人人人人| 亚洲精品久久成人aⅴ小说| 国产精品 国内视频| 91久久精品国产一区二区三区| 国产日韩欧美视频二区| 捣出白浆h1v1| 亚洲精品乱久久久久久| 国产亚洲一区二区精品| 熟女电影av网| 午夜久久久在线观看| www.自偷自拍.com| freevideosex欧美| 午夜老司机福利剧场| 午夜福利在线免费观看网站| 国语对白做爰xxxⅹ性视频网站| 国产成人精品在线电影| 日韩欧美精品免费久久| 亚洲成人av在线免费| 免费观看无遮挡的男女| 人人妻人人澡人人爽人人夜夜| 国产1区2区3区精品| 国产成人精品福利久久| 色播在线永久视频| 在线天堂最新版资源| 精品久久久精品久久久| 人体艺术视频欧美日本| 国产精品熟女久久久久浪| 成年美女黄网站色视频大全免费| 亚洲精品日本国产第一区| 最近最新中文字幕大全免费视频 | 亚洲av欧美aⅴ国产| 国产精品久久久久久精品电影小说| 国产福利在线免费观看视频| 人妻少妇偷人精品九色| 这个男人来自地球电影免费观看 | 欧美激情 高清一区二区三区| av天堂久久9| 免费看不卡的av| 久久久久人妻精品一区果冻| 成人免费观看视频高清| 精品卡一卡二卡四卡免费| 欧美最新免费一区二区三区| 又黄又粗又硬又大视频| 久久99一区二区三区| 在线 av 中文字幕| 1024视频免费在线观看| 欧美成人午夜精品| 亚洲色图 男人天堂 中文字幕| 老汉色∧v一级毛片| 日本色播在线视频| 韩国精品一区二区三区| 18禁裸乳无遮挡动漫免费视频| 欧美av亚洲av综合av国产av | 亚洲成人手机| 在线天堂最新版资源| 日本av手机在线免费观看| 欧美97在线视频| 熟女少妇亚洲综合色aaa.| 午夜福利乱码中文字幕| 丰满乱子伦码专区| 久久av网站| 熟女少妇亚洲综合色aaa.| 免费黄网站久久成人精品| 婷婷色综合大香蕉| 自线自在国产av| 精品国产乱码久久久久久男人| av网站在线播放免费| 哪个播放器可以免费观看大片| 一本大道久久a久久精品| 人人妻人人爽人人添夜夜欢视频| 男女边摸边吃奶| 国语对白做爰xxxⅹ性视频网站| 欧美人与善性xxx| 可以免费在线观看a视频的电影网站 | 日韩av免费高清视频| 午夜福利视频在线观看免费| 亚洲综合色惰| 熟妇人妻不卡中文字幕| 日韩av不卡免费在线播放| 精品久久久精品久久久| 午夜免费观看性视频| 汤姆久久久久久久影院中文字幕| 国语对白做爰xxxⅹ性视频网站| 亚洲第一青青草原| 免费在线观看完整版高清| 午夜福利在线观看免费完整高清在| 日韩成人av中文字幕在线观看| 日韩电影二区| 国产97色在线日韩免费| 久久精品久久久久久久性| 亚洲国产精品一区二区三区在线| 最近手机中文字幕大全| 国产在线免费精品| 成人漫画全彩无遮挡| 99热全是精品| 久久久欧美国产精品| 成人手机av| 亚洲色图综合在线观看| 日日啪夜夜爽| 亚洲熟女精品中文字幕| 美女福利国产在线| 亚洲精华国产精华液的使用体验| 可以免费在线观看a视频的电影网站 | 哪个播放器可以免费观看大片| 侵犯人妻中文字幕一二三四区| 国产男女超爽视频在线观看| 在线观看美女被高潮喷水网站| 两个人免费观看高清视频| 亚洲精品乱久久久久久| 久久久a久久爽久久v久久| 国产男女内射视频| 亚洲成av片中文字幕在线观看 | 尾随美女入室| 啦啦啦视频在线资源免费观看| 国产精品av久久久久免费| 亚洲一区中文字幕在线| 国产精品成人在线| 熟妇人妻不卡中文字幕| 国产 一区精品| 秋霞在线观看毛片| 男女下面插进去视频免费观看| 色播在线永久视频| 1024香蕉在线观看| 中文字幕色久视频| 自线自在国产av| 国产一区二区三区av在线| 亚洲一区中文字幕在线| 黄色配什么色好看| 色哟哟·www| 丝瓜视频免费看黄片| 最新的欧美精品一区二区| 超碰成人久久| 欧美激情高清一区二区三区 | 十分钟在线观看高清视频www| av女优亚洲男人天堂| 伦理电影大哥的女人| 欧美精品国产亚洲| 18禁观看日本| 久久99蜜桃精品久久| 在现免费观看毛片| 久久女婷五月综合色啪小说| 啦啦啦中文免费视频观看日本| 99国产精品免费福利视频| 成人漫画全彩无遮挡| 欧美变态另类bdsm刘玥| 成人国产av品久久久| 女的被弄到高潮叫床怎么办| 香蕉丝袜av| 亚洲国产欧美网| 欧美激情极品国产一区二区三区| 人人妻人人添人人爽欧美一区卜| kizo精华| 国产人伦9x9x在线观看 | av又黄又爽大尺度在线免费看| 久久婷婷青草| 亚洲 欧美一区二区三区| av.在线天堂| 人妻系列 视频| 亚洲美女视频黄频| 日韩精品免费视频一区二区三区| 精品少妇久久久久久888优播| 国产av码专区亚洲av| 黄色视频在线播放观看不卡| 国产精品国产三级专区第一集| 免费黄色在线免费观看| 欧美精品人与动牲交sv欧美| 久久久久国产精品人妻一区二区| 日韩精品免费视频一区二区三区| 日韩一本色道免费dvd| av女优亚洲男人天堂| 亚洲精品视频女| 一边摸一边做爽爽视频免费| 欧美日韩视频精品一区| 亚洲精品第二区| 永久免费av网站大全| 亚洲色图综合在线观看| 国产午夜精品一二区理论片| av天堂久久9| 久久久久久久亚洲中文字幕| 五月伊人婷婷丁香| 人妻系列 视频| 一区在线观看完整版| 蜜桃国产av成人99| 最黄视频免费看| 久久精品国产a三级三级三级| 99久久中文字幕三级久久日本| 欧美97在线视频| 成人影院久久| 亚洲在久久综合| xxxhd国产人妻xxx| 日本黄色日本黄色录像| 亚洲,一卡二卡三卡| 久久久国产精品麻豆| 99久久综合免费| 制服丝袜香蕉在线| 欧美日韩精品网址| 国产黄色免费在线视频| 丰满饥渴人妻一区二区三| 亚洲精品日韩在线中文字幕| 国产黄色视频一区二区在线观看| 男女边摸边吃奶| 青春草国产在线视频| 国产精品无大码| 欧美 日韩 精品 国产| 看非洲黑人一级黄片| 欧美成人午夜免费资源| 亚洲伊人久久精品综合| 亚洲图色成人| 日韩伦理黄色片| 欧美成人午夜免费资源| 精品国产一区二区久久| 18禁动态无遮挡网站| 日韩中字成人| 建设人人有责人人尽责人人享有的| 视频在线观看一区二区三区| 亚洲精品第二区| 亚洲精品,欧美精品| 欧美 日韩 精品 国产| 少妇人妻 视频| 免费黄频网站在线观看国产| av网站在线播放免费| 少妇的逼水好多| 在线观看美女被高潮喷水网站| 国产欧美亚洲国产| 国产免费一区二区三区四区乱码| 久久免费观看电影| 国产乱人偷精品视频| 青春草亚洲视频在线观看| 免费观看在线日韩| 亚洲成人一二三区av| 搡女人真爽免费视频火全软件| 久久久a久久爽久久v久久| 一级毛片 在线播放| videos熟女内射| 中文精品一卡2卡3卡4更新| 精品一品国产午夜福利视频| √禁漫天堂资源中文www| 亚洲欧美成人精品一区二区| 黑人欧美特级aaaaaa片| 国产在线免费精品| 一区二区三区乱码不卡18| 国产成人精品无人区| 少妇熟女欧美另类| 69精品国产乱码久久久| 女人高潮潮喷娇喘18禁视频| 久久久久国产一级毛片高清牌| 国产av一区二区精品久久| 成人影院久久| 制服丝袜香蕉在线| 男人舔女人的私密视频| 制服人妻中文乱码| 国产免费福利视频在线观看| 亚洲欧美日韩另类电影网站| 亚洲天堂av无毛| 亚洲伊人色综图| 亚洲精品乱久久久久久| 日韩电影二区| 久久午夜综合久久蜜桃| 十八禁网站网址无遮挡| 国产成人免费无遮挡视频| 最近中文字幕2019免费版|