• <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ù)
    中文字幕人妻熟女乱码| 无人区码免费观看不卡 | 99久久人妻综合| 深夜精品福利| 久久精品亚洲av国产电影网| 欧美国产精品一级二级三级| 欧美精品啪啪一区二区三区| 国产高清视频在线播放一区| 他把我摸到了高潮在线观看 | 97人妻天天添夜夜摸| 国产深夜福利视频在线观看| 欧美黑人欧美精品刺激| 免费人妻精品一区二区三区视频| 国产亚洲午夜精品一区二区久久| 免费日韩欧美在线观看| 国产亚洲一区二区精品| 国产亚洲av高清不卡| 黄频高清免费视频| 男女下面插进去视频免费观看| 国产精品 国内视频| 最黄视频免费看| 亚洲熟女精品中文字幕| 美女主播在线视频| 亚洲精品乱久久久久久| 大码成人一级视频| 一级毛片精品| 9热在线视频观看99| 99国产极品粉嫩在线观看| 黄片小视频在线播放| 国产成人精品久久二区二区91| 99香蕉大伊视频| 亚洲成a人片在线一区二区| 青草久久国产| 久久久久视频综合| 色视频在线一区二区三区| 国产成人啪精品午夜网站| 亚洲综合色网址| 2018国产大陆天天弄谢| 日韩大片免费观看网站| 亚洲第一欧美日韩一区二区三区 | 黄色毛片三级朝国网站| 在线观看舔阴道视频| 亚洲午夜精品一区,二区,三区| 激情视频va一区二区三区| 精品人妻在线不人妻| 亚洲一码二码三码区别大吗| 在线av久久热| 最近最新中文字幕大全电影3 | 午夜福利影视在线免费观看| 日韩欧美国产一区二区入口| 女性生殖器流出的白浆| 国产单亲对白刺激| 性高湖久久久久久久久免费观看| 免费在线观看黄色视频的| 啦啦啦中文免费视频观看日本| 国产精品久久久久久精品古装| 人妻一区二区av| 黄片大片在线免费观看| 中文字幕av电影在线播放| 国产成人欧美| 亚洲中文av在线| 精品国产乱码久久久久久小说| 99精品在免费线老司机午夜| 午夜精品国产一区二区电影| 视频区欧美日本亚洲| 视频区图区小说| 国产成人精品久久二区二区免费| 99国产极品粉嫩在线观看| 亚洲国产精品一区二区三区在线| 国产亚洲欧美精品永久| 水蜜桃什么品种好| 精品少妇黑人巨大在线播放| 成年人黄色毛片网站| 天堂8中文在线网| 建设人人有责人人尽责人人享有的| kizo精华| 精品国产乱码久久久久久小说| 成人精品一区二区免费| 国产精品久久久av美女十八| 天天影视国产精品| av有码第一页| 国产单亲对白刺激| 中文亚洲av片在线观看爽 | 在线观看免费日韩欧美大片| 国产在线精品亚洲第一网站| 婷婷成人精品国产| 黄色视频不卡| 国产成人欧美在线观看 | 久久狼人影院| 中文欧美无线码| 亚洲欧美日韩高清在线视频 | 成人国产av品久久久| 久久精品人人爽人人爽视色| 免费不卡黄色视频| 欧美人与性动交α欧美软件| 国产日韩欧美在线精品| 日韩成人在线观看一区二区三区| 成人免费观看视频高清| 777米奇影视久久| 下体分泌物呈黄色| 在线天堂中文资源库| 欧美日韩一级在线毛片| 中文字幕精品免费在线观看视频| 免费少妇av软件| 纵有疾风起免费观看全集完整版| 久久久久视频综合| 精品国产亚洲在线| 精品久久久久久久毛片微露脸| 国产一区二区在线观看av| 夜夜骑夜夜射夜夜干| 天天影视国产精品| 国产色视频综合| 脱女人内裤的视频| 在线观看一区二区三区激情| 男女边摸边吃奶| 成人18禁高潮啪啪吃奶动态图| 亚洲精品在线美女| 免费观看人在逋| 在线av久久热| 黄网站色视频无遮挡免费观看| 中文字幕人妻丝袜一区二区| 国产成人av教育| 女人爽到高潮嗷嗷叫在线视频| 国产精品久久久av美女十八| 麻豆av在线久日| 丰满人妻熟妇乱又伦精品不卡| 两性午夜刺激爽爽歪歪视频在线观看 | 美女视频免费永久观看网站| 日韩欧美一区二区三区在线观看 | 岛国毛片在线播放| 亚洲五月婷婷丁香| 亚洲精品国产色婷婷电影| 国产精品99久久99久久久不卡| 久久精品aⅴ一区二区三区四区| 久久亚洲真实| 国产亚洲午夜精品一区二区久久| 侵犯人妻中文字幕一二三四区| 男女无遮挡免费网站观看| 最近最新中文字幕大全免费视频| 老司机午夜福利在线观看视频 | 免费黄频网站在线观看国产| 国产欧美亚洲国产| 男女之事视频高清在线观看| 亚洲天堂av无毛| 大片电影免费在线观看免费| 99国产精品99久久久久| 午夜激情av网站| av线在线观看网站| 亚洲 欧美一区二区三区| 亚洲一区中文字幕在线| 欧美+亚洲+日韩+国产| 一区二区三区乱码不卡18| 在线亚洲精品国产二区图片欧美| 少妇裸体淫交视频免费看高清 | 久久av网站| 亚洲 国产 在线| 成人国产av品久久久| 两人在一起打扑克的视频| 国产在线精品亚洲第一网站| 精品福利观看| 欧美午夜高清在线| 免费看十八禁软件| 久久99热这里只频精品6学生| 蜜桃国产av成人99| 日韩三级视频一区二区三区| 国产黄频视频在线观看| √禁漫天堂资源中文www| 国精品久久久久久国模美| 黄网站色视频无遮挡免费观看| 黑人巨大精品欧美一区二区蜜桃| 亚洲成人国产一区在线观看| 久久人妻福利社区极品人妻图片| 一区在线观看完整版| 亚洲精品国产色婷婷电影| 99国产精品一区二区三区| 国产精品影院久久| 91精品三级在线观看| 麻豆av在线久日| 国产激情久久老熟女| 老司机深夜福利视频在线观看| 亚洲伊人色综图| 岛国毛片在线播放| 99精品久久久久人妻精品| 女人爽到高潮嗷嗷叫在线视频| 国产高清激情床上av| a级毛片黄视频| 久久亚洲精品不卡| 中文字幕人妻熟女乱码| 美女国产高潮福利片在线看| 欧美黄色片欧美黄色片| 成年女人毛片免费观看观看9 | 欧美日韩亚洲高清精品| 亚洲av日韩在线播放| 淫妇啪啪啪对白视频| 日韩欧美国产一区二区入口| 成在线人永久免费视频| 十八禁人妻一区二区| 国产欧美日韩一区二区三区在线| 一个人免费在线观看的高清视频| 日本一区二区免费在线视频| 精品一区二区三区av网在线观看 | 国产激情久久老熟女| 一二三四在线观看免费中文在| 精品少妇黑人巨大在线播放| 日本vs欧美在线观看视频| 色婷婷久久久亚洲欧美| 国产av一区二区精品久久| 成人黄色视频免费在线看| 大片免费播放器 马上看| 成在线人永久免费视频| 国产成人啪精品午夜网站| 亚洲中文字幕日韩| 欧美激情 高清一区二区三区| 久久久久久久久久久久大奶| 国产精品欧美亚洲77777| 搡老熟女国产l中国老女人| 美女视频免费永久观看网站| 色94色欧美一区二区| 精品熟女少妇八av免费久了| 国产99久久九九免费精品| 黄色 视频免费看| 亚洲熟妇熟女久久| 成人手机av| 黄色a级毛片大全视频| 老司机靠b影院| 少妇裸体淫交视频免费看高清 | 久久久久国内视频| 亚洲欧美日韩高清在线视频 | 久久九九热精品免费| 久久人人爽av亚洲精品天堂| 蜜桃国产av成人99| 美女高潮到喷水免费观看| 久久香蕉激情| 人人澡人人妻人| 999久久久精品免费观看国产| 亚洲久久久国产精品| 亚洲天堂av无毛| 日日摸夜夜添夜夜添小说| 亚洲国产av新网站| xxxhd国产人妻xxx| 天堂俺去俺来也www色官网| 视频区欧美日本亚洲| 成人国语在线视频| 黄色毛片三级朝国网站| 亚洲av成人不卡在线观看播放网| 国产在线免费精品| 一本—道久久a久久精品蜜桃钙片| 国产亚洲精品一区二区www | 国产欧美日韩一区二区精品| 大香蕉久久成人网| 热re99久久国产66热| 天天躁狠狠躁夜夜躁狠狠躁| 亚洲中文av在线| 视频区图区小说| 亚洲欧美日韩高清在线视频 | 俄罗斯特黄特色一大片| 亚洲一卡2卡3卡4卡5卡精品中文| 怎么达到女性高潮| 亚洲国产欧美日韩在线播放| 国产精品九九99| 国产麻豆69| 9191精品国产免费久久| 妹子高潮喷水视频| 国产高清激情床上av| 久久精品91无色码中文字幕| 国产亚洲午夜精品一区二区久久| 在线观看66精品国产| kizo精华| 操出白浆在线播放| 一区二区三区乱码不卡18| 天天影视国产精品| 精品一区二区三区四区五区乱码| 超碰97精品在线观看| 国产福利在线免费观看视频| 午夜91福利影院| 男女床上黄色一级片免费看| www.熟女人妻精品国产| av欧美777| 亚洲免费av在线视频| 午夜视频精品福利| 成年人黄色毛片网站| 水蜜桃什么品种好| 人成视频在线观看免费观看| 亚洲av成人一区二区三| 五月开心婷婷网| 精品国内亚洲2022精品成人 | 十八禁网站网址无遮挡| 色尼玛亚洲综合影院| 免费黄频网站在线观看国产| 国产国语露脸激情在线看| 国产精品1区2区在线观看. | 亚洲天堂av无毛| 亚洲专区国产一区二区| 啦啦啦免费观看视频1| 精品熟女少妇八av免费久了| 热re99久久精品国产66热6| 母亲3免费完整高清在线观看| 一本综合久久免费| 大陆偷拍与自拍| 丁香六月欧美| 老汉色av国产亚洲站长工具| 久久影院123| 巨乳人妻的诱惑在线观看| 老司机午夜十八禁免费视频| 大型黄色视频在线免费观看| 久久午夜亚洲精品久久| 不卡一级毛片| 国产欧美日韩一区二区精品| 日韩一区二区三区影片| 亚洲精品自拍成人| 久久精品亚洲熟妇少妇任你| 亚洲九九香蕉| 欧美乱码精品一区二区三区| 国产精品一区二区在线观看99| 精品国内亚洲2022精品成人 | 99精国产麻豆久久婷婷| 精品卡一卡二卡四卡免费| 91精品三级在线观看| av天堂久久9| 精品亚洲成国产av| bbb黄色大片| 黄色 视频免费看| 桃红色精品国产亚洲av| 成人特级黄色片久久久久久久 | 国产精品久久久久成人av| 成人免费观看视频高清| 中文字幕高清在线视频| 亚洲精品粉嫩美女一区| 啦啦啦中文免费视频观看日本| 日韩欧美三级三区| 精品人妻1区二区| 国产欧美日韩综合在线一区二区| 美女视频免费永久观看网站| 后天国语完整版免费观看| 女同久久另类99精品国产91| a级毛片在线看网站| 在线十欧美十亚洲十日本专区| 久久国产精品大桥未久av| 国产av国产精品国产| 精品乱码久久久久久99久播| 丰满迷人的少妇在线观看| av视频免费观看在线观看| 久久久国产一区二区| 在线观看一区二区三区激情| 中文字幕色久视频| 亚洲第一av免费看| 2018国产大陆天天弄谢| 久久精品国产亚洲av香蕉五月 | 国产精品98久久久久久宅男小说| 亚洲av第一区精品v没综合| 一本久久精品| 国产免费福利视频在线观看| 大片免费播放器 马上看| 国产欧美亚洲国产| 99国产精品99久久久久| 国产精品自产拍在线观看55亚洲 | 久久国产精品影院| 亚洲av电影在线进入| 汤姆久久久久久久影院中文字幕| 国产欧美日韩一区二区精品| 9191精品国产免费久久| 人人澡人人妻人| 亚洲国产欧美在线一区| 欧美性长视频在线观看| 天堂动漫精品| 狂野欧美激情性xxxx| 国产视频一区二区在线看| 日韩熟女老妇一区二区性免费视频| 首页视频小说图片口味搜索| 在线观看免费视频日本深夜| 国产三级黄色录像| 亚洲第一欧美日韩一区二区三区 | 国产成人系列免费观看| 青草久久国产| 久久精品亚洲精品国产色婷小说| 1024香蕉在线观看| 性少妇av在线| 一级黄色大片毛片| 国产免费福利视频在线观看| 欧美日韩精品网址| 嫁个100分男人电影在线观看| 亚洲熟女毛片儿| 91国产中文字幕| 亚洲精品国产区一区二| 黄色片一级片一级黄色片| 天天躁夜夜躁狠狠躁躁| 亚洲国产av影院在线观看| 亚洲精品在线观看二区| 亚洲精品乱久久久久久| av欧美777| 色尼玛亚洲综合影院| 热99久久久久精品小说推荐| 极品人妻少妇av视频| 国产视频一区二区在线看| 亚洲国产精品一区二区三区在线| 99九九在线精品视频| 日韩欧美三级三区| 可以免费在线观看a视频的电影网站| 国产亚洲av高清不卡| 国产一卡二卡三卡精品| 国产97色在线日韩免费| 在线观看www视频免费| 18禁美女被吸乳视频| 人人澡人人妻人| 啦啦啦免费观看视频1| 国产色视频综合| 高清欧美精品videossex| 午夜福利,免费看| 欧美另类亚洲清纯唯美| www.自偷自拍.com| 久久精品国产亚洲av高清一级| 一级毛片精品| kizo精华| 欧美一级毛片孕妇| 999久久久国产精品视频| 汤姆久久久久久久影院中文字幕| 动漫黄色视频在线观看| 欧美日韩一级在线毛片| 国产野战对白在线观看| 色老头精品视频在线观看| 亚洲七黄色美女视频| 午夜激情av网站| 最新的欧美精品一区二区| 妹子高潮喷水视频| 精品一区二区三区四区五区乱码| 日本欧美视频一区| av一本久久久久| 亚洲精品一二三| 91老司机精品| 国产精品.久久久| 丰满少妇做爰视频| cao死你这个sao货| 精品国产超薄肉色丝袜足j| 精品熟女少妇八av免费久了| 亚洲美女黄片视频| 国产精品欧美亚洲77777| 免费在线观看完整版高清| 国产精品电影一区二区三区 | 国产精品秋霞免费鲁丝片| 日本五十路高清| 欧美成人免费av一区二区三区 | 黄色视频不卡| 久久精品亚洲精品国产色婷小说| 伦理电影免费视频| 久久毛片免费看一区二区三区| 青青草视频在线视频观看| 99在线人妻在线中文字幕 | 精品亚洲成国产av| 法律面前人人平等表现在哪些方面| 亚洲成人国产一区在线观看| 久久国产亚洲av麻豆专区| 成在线人永久免费视频| 欧美日韩av久久| 91国产中文字幕| 伊人久久大香线蕉亚洲五| 一本—道久久a久久精品蜜桃钙片| 亚洲国产看品久久| 久久热在线av| 国产免费现黄频在线看| 热99国产精品久久久久久7| 色精品久久人妻99蜜桃| 久久婷婷成人综合色麻豆| aaaaa片日本免费| 国产日韩欧美在线精品| 久久人妻av系列| 19禁男女啪啪无遮挡网站| 一区二区三区乱码不卡18| 亚洲黑人精品在线| 悠悠久久av| 免费不卡黄色视频| 午夜福利一区二区在线看| 精品少妇久久久久久888优播| 亚洲性夜色夜夜综合| 女性被躁到高潮视频| 欧美日韩成人在线一区二区| 亚洲av成人不卡在线观看播放网| 美女扒开内裤让男人捅视频| 十八禁网站网址无遮挡| 国产成人一区二区三区免费视频网站| 巨乳人妻的诱惑在线观看| 久久午夜综合久久蜜桃| 五月开心婷婷网| 免费日韩欧美在线观看| 欧美乱妇无乱码| 乱人伦中国视频| 免费久久久久久久精品成人欧美视频| 99re6热这里在线精品视频| 午夜日韩欧美国产| 人成视频在线观看免费观看| 悠悠久久av| 精品一区二区三区四区五区乱码| 亚洲少妇的诱惑av| e午夜精品久久久久久久| 亚洲少妇的诱惑av| 日韩大片免费观看网站| 国产精品麻豆人妻色哟哟久久| 亚洲成a人片在线一区二区| 97在线人人人人妻| 丰满人妻熟妇乱又伦精品不卡| 国产欧美亚洲国产| 国产老妇伦熟女老妇高清| 欧美乱妇无乱码| 91成人精品电影| 国产精品 欧美亚洲| 日韩三级视频一区二区三区| www日本在线高清视频| 欧美精品一区二区免费开放| 国产野战对白在线观看| 成人18禁高潮啪啪吃奶动态图| 亚洲人成77777在线视频| 国产精品1区2区在线观看. | 高清av免费在线| 免费在线观看完整版高清| 亚洲午夜精品一区,二区,三区| 一区二区三区精品91| 国产深夜福利视频在线观看| 男女高潮啪啪啪动态图| videosex国产| 国产精品99久久99久久久不卡| 欧美日韩一级在线毛片| av欧美777| 啦啦啦视频在线资源免费观看| 99国产精品一区二区蜜桃av | 成年人免费黄色播放视频| 亚洲va日本ⅴa欧美va伊人久久| 国产成人啪精品午夜网站| 老汉色av国产亚洲站长工具| www日本在线高清视频| 亚洲天堂av无毛| 啦啦啦免费观看视频1| 精品少妇久久久久久888优播| 18禁美女被吸乳视频| 亚洲精品国产区一区二| 精品欧美一区二区三区在线| 99在线人妻在线中文字幕 | 免费观看a级毛片全部| 涩涩av久久男人的天堂| 丰满迷人的少妇在线观看| 极品教师在线免费播放| 国产亚洲一区二区精品| 少妇的丰满在线观看| 99re6热这里在线精品视频| 超碰成人久久| 69精品国产乱码久久久| 亚洲第一av免费看| 亚洲色图综合在线观看| 精品福利永久在线观看| 国产深夜福利视频在线观看| 久久ye,这里只有精品| 亚洲av电影在线进入| 黑人巨大精品欧美一区二区mp4| 亚洲国产av影院在线观看| 亚洲视频免费观看视频| 国产在视频线精品| 亚洲五月婷婷丁香| 国产成人系列免费观看| 亚洲色图综合在线观看| 国产精品 国内视频| 大型黄色视频在线免费观看| av一本久久久久| 精品国产一区二区三区久久久樱花| 建设人人有责人人尽责人人享有的| 成人国语在线视频| 老汉色av国产亚洲站长工具| 9热在线视频观看99| 久久久精品国产亚洲av高清涩受| 国产91精品成人一区二区三区 | 十八禁人妻一区二区| 免费黄频网站在线观看国产| 久久99热这里只频精品6学生| 精品福利永久在线观看| 老熟女久久久| 制服人妻中文乱码| 少妇裸体淫交视频免费看高清 | 热re99久久国产66热| 这个男人来自地球电影免费观看| 亚洲精品在线观看二区| 黑人欧美特级aaaaaa片| 国产福利在线免费观看视频| 丝瓜视频免费看黄片| 亚洲欧洲精品一区二区精品久久久| 丝袜美腿诱惑在线| 国产无遮挡羞羞视频在线观看| 婷婷丁香在线五月| 精品乱码久久久久久99久播| 老司机亚洲免费影院| 99久久国产精品久久久| 另类亚洲欧美激情| 一本大道久久a久久精品| 麻豆国产av国片精品| 国产淫语在线视频| 色播在线永久视频| 欧美日韩成人在线一区二区| 国产又爽黄色视频| 精品少妇内射三级| 高清毛片免费观看视频网站 | 91精品国产国语对白视频| 高清黄色对白视频在线免费看| 成人国产一区最新在线观看| 精品第一国产精品| 亚洲七黄色美女视频| 成人国产一区最新在线观看| 9色porny在线观看| 欧美在线一区亚洲| 欧美+亚洲+日韩+国产| 9色porny在线观看| 亚洲av欧美aⅴ国产| 午夜免费成人在线视频| 亚洲精品久久午夜乱码| 色精品久久人妻99蜜桃| 少妇精品久久久久久久| 国产免费视频播放在线视频| 这个男人来自地球电影免费观看| 搡老岳熟女国产| 色播在线永久视频|