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

    一種分布式環(huán)境下高效查詢算法?

    2016-03-24 09:20:42曲海鵬

    王 寧,曲海鵬,范 令

    (中國海洋大學(xué)信息科學(xué)與工程學(xué)院, 山東 青島 266100)

    ?

    一種分布式環(huán)境下高效查詢算法?

    王寧,曲海鵬??,范令

    (中國海洋大學(xué)信息科學(xué)與工程學(xué)院, 山東 青島 266100)

    摘要:很多交互系統(tǒng)需要實(shí)時返回潛在的數(shù)據(jù)空間中最重要的前k條記錄,即為top-k查詢。當(dāng)今大數(shù)據(jù)時代,面對海量更加復(fù)雜的數(shù)據(jù),輸出這種top-k記錄是一個非常具有挑戰(zhàn)性的問題。傳統(tǒng)的方案主要采用基于閾值的方法,然而對分布式系統(tǒng)來說,這些方法是比較耗時的,并且需要巨大的通信量。隨著網(wǎng)絡(luò)流量的增加,這些問題會變得無法解決。本文提出了一種新穎的top-k算法PCMRA(Data Partitioning and COIT Indexing Top-k query Algorithm based on MapReduce)。該解決方案構(gòu)造了預(yù)處理結(jié)構(gòu)COIT(候選對象索引表),并采用數(shù)據(jù)分割策略和并行編程框架MapReduce,一輪通信就可以完成top-k查詢。此外本文還對算法給出了正確性證明和理論分析,并且實(shí)驗表明該算法僅需要較小的空間開銷和較短的時間代價,即可篩選出較少的候選對象,大幅度節(jié)約了計算和通信資源,并且算法具有良好的可擴(kuò)展性。

    關(guān)鍵詞:top-k查詢;COIT;數(shù)據(jù)分割; MapReduce

    WANG Ning, QU Hai-Peng, FAN Ling. PCMRA: An efficient top-kalgorithm in distributed environment[J]. Periodical of Ocean University of China, 2016, 46(2): 138-145.

    當(dāng)今大數(shù)據(jù)時代,數(shù)據(jù)不僅數(shù)量大,而且類型更加復(fù)雜,這導(dǎo)致了對數(shù)據(jù)處理的需求越來越高[1]。傳統(tǒng)的算法和數(shù)據(jù)庫系統(tǒng)已經(jīng)難以有效應(yīng)對,因此大數(shù)據(jù)快速查詢算法的研究成為熱點(diǎn),排名查詢就是復(fù)雜查詢中一種。

    排名查詢也被稱為top-k查詢,它為高效搜索問題提供了解決方案。top-k查詢只檢索k個最符合用戶需求的對象,從而避免計算、存儲大量的結(jié)果集。在傳統(tǒng)的集中式數(shù)據(jù)庫,分布式數(shù)據(jù)庫,以及大數(shù)據(jù)環(huán)境下,top-k查詢都已受到廣泛的重視,在這些應(yīng)用場景中,只計算輸出k個“最好”的結(jié)果就已經(jīng)足夠了。如有許多應(yīng)用,如網(wǎng)絡(luò)搜索,信息檢索,多媒體數(shù)據(jù)庫,數(shù)字圖書館,數(shù)據(jù)挖掘和推薦系統(tǒng),只需要查詢前k個最好合乎要求的記錄[2]。

    對于確定數(shù)據(jù)庫而言,根據(jù)數(shù)據(jù)庫的類型又分為兩大類。對于集中式數(shù)據(jù)庫,學(xué)術(shù)界為解決top-k查詢問題已經(jīng)做了很多工作[3],而對于分布式數(shù)據(jù)庫,這個問題一直沒能得到很好的解決。根據(jù)數(shù)據(jù)劃分策略,top-k查詢又可以分為兩類[4]:一類數(shù)據(jù)是水平劃分的,這和本文所研究的應(yīng)用場景是完全不同的。另一類數(shù)據(jù)是垂直劃分的。對于這類top-k查詢,大多解決方案主要采用基于閾值的方法。TPUT[5]和Klee[6]算法就是這類算法的典型代表。這類算法是從集中式數(shù)據(jù)庫的算法發(fā)展來的,主要針對單一數(shù)據(jù)庫的,沒有考慮分布式的環(huán)境,盡管改進(jìn),但是仍需要與服務(wù)器幾輪往返開銷才能完成查詢[7],比較費(fèi)時,需要大量的通信。隨著網(wǎng)絡(luò)通信量的增加,top-k查詢將更加難以處理。

    此外,近年來,由于在很多新興的應(yīng)用,如傳感器網(wǎng)絡(luò),基于位置的服務(wù),以及數(shù)據(jù)集成等應(yīng)用領(lǐng)域管理的信息往往是不確定的,為了處理數(shù)據(jù)的不確定性,概率數(shù)據(jù)庫被廣泛研究。隨之概率數(shù)據(jù)庫的top-k查詢問題也吸引了廣泛的研究興趣。在定義不確定型數(shù)據(jù)模型的基礎(chǔ)上,多種可能世界語義的top-k查詢模型已經(jīng)提出,包括U-Topk[9],U-kRanks[9],PT-k[10],Gobal-topk[11],以及Expected Rank queries[12]等,相應(yīng)的算法也被大量的研究。

    本文為了提高算法的并行度,引入了計算模型MapReduce[8]。MapReduce是一個并行編程模型,它主要是針對大規(guī)模數(shù)據(jù)。它為用戶提供2個接口,方便用戶編寫一些自定義的代碼來處理大規(guī)模數(shù)據(jù)。

    為了可以快速、準(zhǔn)確地完成top-k查詢,本文針對確定數(shù)據(jù)庫提出了一種高效的算法PCMRA。該算法需要預(yù)先構(gòu)建候選對象索引表COIT,top-k查詢的k值一般比較小,因此算法只需要維護(hù)有限的COIT記錄,就可以完成絕大多數(shù)top-k查詢。有限的數(shù)據(jù)記錄節(jié)約了數(shù)據(jù)構(gòu)建的成本以及占有的空間。數(shù)據(jù)一般分布在網(wǎng)絡(luò)中不同的節(jié)點(diǎn),并且通常每個服務(wù)器中只儲存著一個或幾個屬性,而top-k查詢涉及到同一個對象的多個屬性的綜合得分,這就需要不止一個服務(wù)器的參與才能完成計算。本文采用數(shù)據(jù)劃分策略,減少了節(jié)點(diǎn)間的通信開銷,這就使算法具有很高的可擴(kuò)展性,隨著數(shù)據(jù)量的增加,這種優(yōu)勢將更加明顯。通過使用預(yù)構(gòu)建數(shù)據(jù)結(jié)構(gòu)COIT,我們的算法首先獲取候選id集合,然后根據(jù)數(shù)據(jù)劃分策略對候選id集合進(jìn)行分組。在得到分組后的id集合后,借助并行編程模型MapReduce的開源實(shí)現(xiàn)平臺Hadoop,只需一輪往返通信就可以完成top-k查詢。

    1算法介紹

    1.1 問題描述

    top-k查詢:給定一個表T和一個單調(diào)的排名函數(shù)F,top-k查詢返回表T的一個包含k條記錄的子集R(k≤|T|)),滿足條件?ti∈R,?tj∈[T-R],則F(ti)≥F(tj)。表的關(guān)系模式為T(ID,A1,A2,……,Am),表T中元組tj的各屬性Ai都對應(yīng)一個得分值,記為Tj.bsi。排名函數(shù)F=∑wi×Tj.bsi是單調(diào)的,即對于?i,若存在1≤i≤m,xi≤yi,則F(x1,……,xm)≤F(y1,……,ym),其中wi是對應(yīng)屬性Ai的權(quán)重,并且各屬性權(quán)重和為1,即∑wi=1。

    1.2 預(yù)處理結(jié)構(gòu)

    在收到top-k查詢之前,為了實(shí)現(xiàn)算法,需要預(yù)先建立數(shù)據(jù)結(jié)構(gòu)候選對象索引表COIT。COIT表是一種全局索引表,從中可以方便的查到各個k值以及各屬性組合對應(yīng)top-k查詢的候選id集合,借助COIT來可以快速的完成排名查詢。

    全局索引表(COIT):處理的數(shù)據(jù)對象是分布在不同數(shù)據(jù)源上的,每個數(shù)據(jù)源都是可以轉(zhuǎn)換或者提取出一個或者少數(shù)幾個關(guān)系模式R(O,A),O為對象的鍵,如id等能唯一標(biāo)識對象的屬性列,A為該模式對應(yīng)屬性的得分,每個數(shù)據(jù)源都是按照屬性A得分降序排列的。如果可以提取到m個這樣的關(guān)系模式,我們可以假設(shè)多源數(shù)據(jù)的全部屬性可以組成一個大的虛擬的關(guān)系模式R’(O,A1,A2,……,Am),Ai分別對應(yīng)屬性i的得分。

    每個節(jié)點(diǎn)都需要建立一個id索引,記為Li,其中i∈(1,m),該id索引是按照相關(guān)屬性的得分值降序排列的。索引Li的長度是可配置的。top-k查詢的k值一般較小,所以為了減少維護(hù)索引的空間代價和處理開銷,提高效率,設(shè)置了索引Li只有有限的記錄。索引Li的長度可根據(jù)實(shí)際應(yīng)用場景進(jìn)行設(shè)置。

    每個數(shù)據(jù)源節(jié)點(diǎn)都將把各自的索引Li發(fā)送給全局節(jié)點(diǎn),全局節(jié)點(diǎn)將根據(jù)所有屬性的索引建立全局的COIT。COIT包含了id以及在所在屬性列的排名,表中每一行形式如下(id,rank inL1,rank inL2……rank inLm) 。對于每一條記錄,它包括id和對象在所有節(jié)點(diǎn)的屬性排名,表1是多源數(shù)據(jù)庫索引一個實(shí)例,這一實(shí)例包括4列索引,各有5個元組,根據(jù)這一索引,按照COIT表構(gòu)建方法,建立COIT表如表2所示。

    表1 多源數(shù)據(jù)索引實(shí)例

    表2 COIT表

    1.2.1 建立COIT表的步驟

    (1)多數(shù)據(jù)源節(jié)點(diǎn)獲取按相關(guān)屬性降序排列的id索引列Li,初始化COIT表,COIT表中每條記錄形式如下(id,rank inL1,rank inL2……rank inLm)。

    (2)逐行并行順序訪問m列id索引列,對讀取到的索引列Li的id,若該id已經(jīng)存在于COIT表中,則更新該id新讀到的排名rank;若訪問到的id不存在于COIT表中,則在COIT表末尾為該id新建一條記錄,并將排名rank記錄在相應(yīng)的列。

    (3)順序訪問COIT表,對沒有排名信息的位置填入UNDEF,代表該id在該列的排名rank暫時沒有讀到。

    1.2.2 建立COIT表的偽代碼

    算法1.建立COIT

    Retrieve L1,L2,……,Lm

    COIT[ ][ ] coit

    Initialize coit

    for i = 1 to the length of Li do

    for j = 1 to m do

    read current id

    if (id is in coit)

    //更新id在j個位置的排名為i;

    updateCOIT(coit, id, j,i)

    else

    //在COIT表插入新id,并更新id

    在j個位置的排名為i;

    insertCOIT(coit, id, j,i)

    end for

    end for

    fori = 1 to the length of COIT do

    for j = 1 to m do

    if (id rank is empty)

    //更新id在j個位置的排名為UNDEF;

    updateCOIT(coit, id,j,UNDEF)

    end for

    end for

    return COIT

    1.2.3 建立COIT表的流程圖

    COIT表的建立流程見圖 1。

    1.3 數(shù)據(jù)分割策略

    算法處理的數(shù)據(jù)來自于不同源數(shù)據(jù),每個數(shù)據(jù)源可能包含對象的一個或者少數(shù)幾個屬性信息,這些數(shù)據(jù)可以看做是根據(jù)不同屬性垂直分布在不同節(jié)點(diǎn)的。top-k查詢涉及到對象的多個屬性的綜合得分值,而這些屬性數(shù)據(jù)一般來說分散在網(wǎng)絡(luò)中的各個節(jié)點(diǎn),如果直接查詢,通信的代價將會非常高。

    為了降低節(jié)點(diǎn)間通信代價,在查詢處理之前,需要將這些不同源數(shù)據(jù)進(jìn)行預(yù)處理和劃分,使相同的對象劃分到相同的分組。假設(shè)id是區(qū)分對象的標(biāo)示符,則對象id被當(dāng)做劃分?jǐn)?shù)據(jù)的標(biāo)準(zhǔn);數(shù)據(jù)源被分割成的子數(shù)據(jù)組的個數(shù)與數(shù)據(jù)處理的并行度Pn一致。引言中介紹了本算法采用的MapReduce這一并行處理模型,Pn的值取決于MapReduce這一并行編程模型。源數(shù)據(jù)的元組被分割到哪個子數(shù)據(jù)組取決于數(shù)據(jù)分割方法,本算法采用了簡單的hash函數(shù)映射的方法,將對象的id對N取模加1即得到子數(shù)據(jù)組的序號group.num,即

    group.num=(object.id modN)+1。

    (1)

    圖1 COIT表的建立流程圖

    這種分割函數(shù)簡單方便,每個對象都能被映射到唯一的子數(shù)據(jù)組,而且由于對象的id一般是連續(xù)遞增的,采用這種數(shù)據(jù)分割函數(shù),能比較均勻的將數(shù)據(jù)分割到各個子數(shù)據(jù)組。不同源數(shù)據(jù)采用的數(shù)據(jù)分割函數(shù)要相同,在Pn和hash函數(shù)相同的條件下,可以保證不同源數(shù)據(jù)中id相同的對象被劃分到子序號相同的子數(shù)據(jù)組。這樣節(jié)點(diǎn)之間的通信量大幅度減少,以此來減少top-k查詢時節(jié)點(diǎn)間的通信代價。

    1.4 PCMRA算法

    本節(jié)介紹算法PCMRA的原理,收到top-k查詢之后,首先利用預(yù)先構(gòu)建的COIT,得到候選id集合,然后根據(jù)數(shù)據(jù)映射規(guī)則,將分組的id集合發(fā)送到相應(yīng)的節(jié)點(diǎn),最后,由Hadoop平臺計算輸出整體的top-k查詢結(jié)果。具體算法細(xì)節(jié)步驟如下:

    (1)top-k查詢解析。當(dāng)接收到top-k查詢時,首先根據(jù)查詢請求進(jìn)行解析,分析出查詢所涉及的屬性集合。

    (2)獲取COIT相關(guān)排名表列。根據(jù)解析后的屬性集合,從COIT表中選取與這些屬性相關(guān)的排名表列。

    (3)排名表列化簡。上一步已經(jīng)獲取所有id在查詢屬性列的所有排名,然而本文算法只關(guān)心這些屬性的排名范圍,即最大和最小排名,對于中間的排名可以不關(guān)心,因此可以對以上結(jié)果進(jìn)行化簡,只保留最大和最小排名。根據(jù)取到的相關(guān)的表列,逐行掃描,只保留每個id對象的最小排名和最大排名并分別定義為RankMin,RankMax。

    (4)id集合排序。經(jīng)過以上處理得到id及其排名范圍,但是這些id可能是無序的,為了方便候選查詢,需要對這些id對象進(jìn)行排序。排序原則為,先根據(jù)RankMax升序排列,如果RankMax值相同,再按RankMin的升序排列。

    (5)截止排名StopRank獲取。為了獲取候選id集合,需要事先獲取截止排名,定義為StopRank。StopRank跟隨k值的變化而變化的,根據(jù)查詢的k值,順序掃描排序后的id集合,當(dāng)讀到第k個id,得到該id的RankMax,表示當(dāng)并行順序訪問到第RankMax行時,第一次至少有k個對象全部屬性都已讀到。該RankMax值即為StopRank。

    (6)候選id集合獲取。根據(jù)上述StopRank值,將所有RankMin不大于StopRank的id插入到候選id集合中。

    (7)候選id集合分組。由于獲得的候選id集合是混亂的,我們需要按照數(shù)據(jù)分割策略對它們進(jìn)行分組和編號。數(shù)據(jù)是根據(jù)哈希函數(shù)來分割的,編號是按模取余來編號的。

    (8)Hadoop并行計算和top-k結(jié)果輸出。為了提高算法的并行度,啟動Hadoop完成結(jié)果top-k計算。輸入為分組并編號的原始數(shù)據(jù)和分組并編號的候選id集合。計算時,只需要根據(jù)原始數(shù)據(jù)的編號找到編號相同的候選id集合分組。只對包含在候選id集合的數(shù)據(jù)進(jìn)行計算。被分配到做map操作的worker節(jié)點(diǎn),做map操作“map(id, wi×listi.value)”,被分配到做reduce操作的worker節(jié)點(diǎn),做reduce操作“reduce(id, list ( w1×list1.value, ……,wm×listm.value))”,最終輸出最大的k個結(jié)果作為最終輸出。

    1.4.1 PCMRA算法偽代碼

    算法2. 獲取候選id分組

    AttrColumn[]related_Attributes

    COIT[] [] coit

    COIT[] [] coit1

    COIT[] [2] coit2

    ID[] Id

    ID[N][] IdGroup

    int i,j,RankMin, RankMax,StopRank

    coit = Establish COIT( )

    //解析top-k查詢的相關(guān)屬性;

    related_Attributes= parse(String sql)

    //獲取COIT相關(guān)排名表列;

    coit1 = retrieveCOIT(related_Attributes,coit)

    for i = 1 to the length of coit1 do

    for j=1 to the length of related_Attributes do

    RankMin = read(coit1[i],1)

    RankMax = read(coit1[i],1)

    if (read(coit[i],j) > RankMax)

    RankMax = read(coit1[i],j)

    if(read(coit[i],j) < RankMax)

    RankMin = read(coit1[i],j)

    end for

    insertCOIT(coit2, id, 1,RankMin)

    updateCOIT(coit2, id, 2,RankMax)

    end for

    //排序,按RankMax升序排列,如過RankMax相同則按RankMin升序排列

    sort(coit2)

    //獲取StopRank值;

    StopRank = (coit2[k],2)

    //候選Id集合獲取

    Id = retrieveIds(coit2, StopRank)

    //候選Id集合分組

    IdGroup = group(id,N)

    return IdGroup

    1.4.2 PCMRA算法流程圖

    本文PCMRA算法的流程見圖2。

    圖2 PCMRA算法流程圖

    2理論分析

    2.1 算法正確性證明

    定理1對于任意一個k值和任意一個單調(diào)得分函數(shù)F,top-k結(jié)果集O是候選id集合X的子集。所有未出現(xiàn)在候選id集合X中的對象z,肯定不屬于top-k結(jié)果集O。

    證明假設(shè)用集合A表示所有的id集合,用X表示對于確定k值和確定得分函數(shù)F的候選id集合,用集合Y表示集合A中除去集合X剩下對象集合,即A-X。我們需要證明top-k結(jié)果集O是候選id集合X的子集,而顯然候選id集合Y中對象個數(shù)是大于等于k的,因此不可能成為top-k結(jié)果集O的子集,因此只需要證明任何出現(xiàn)在集合Y中的對象z不屬于top-k的結(jié)果集O。假設(shè),F(xiàn)函數(shù)涉及到m個屬性得分,而出現(xiàn)在集合Y中的對象z的m個屬性得分為x1,…,xm。

    根據(jù)候選id的獲取方法,首先確定所有id的排名范圍,即最大排名RankMax和最小排名RankMin,假設(shè)對m個排序列做并行順序訪問,id的最大排名RankMax和最小排名RankMin,分別表示該id第一次被訪問的行數(shù)和最后一次被訪問的行數(shù),也就是當(dāng)訪問到第RankMax行時,該對象的所有屬性得分都已經(jīng)被訪問到。然后對所有對象按照先按RankMax再按RankMin的升序排列,讀取第k個id的最大排名RankMax即為StopRank,也就是表示當(dāng)讀到第StopRank行時,有k個對象的所有屬性得分都已經(jīng)被讀到。最后取出所有最小排名RankMin小于StopRank的id放入候選id集合X,因為這些對象都曾經(jīng)出現(xiàn)在StopRank行之前。

    已知而每個排序列是按照屬性得分的降序排列的,所以,顯然先被訪問到的得分要比后被訪問的得分高。假設(shè)所有屬性都被訪問對象中,第k大的對象p的屬性得分為x1,…,xm,顯然對于任何i,都有xm≤xm,又因為得分函數(shù)F時單調(diào)增的,所以F(x1,…,xm)≤F(x1,…,xm,),即對象集合Y中任意對象z得分肯定小于排名為k的對象得分,也就是說出現(xiàn)在集合Y中任何對象z都不屬于top-k結(jié)果集O。

    2.2 算法分析

    本節(jié)根據(jù)算法流程進(jìn)行詳細(xì)的理論分析。COIT記錄有P條記錄,候選屬性列有M個。

    2.2.1時間復(fù)雜度按照算法詳細(xì)流程,收到top-k查詢處理之后對查詢進(jìn)行解析,得到k值和相關(guān)列,時間復(fù)雜度為O(1);獲取排名表列,進(jìn)行化簡,將所有id掃描一遍即可完成,算法時間復(fù)雜度為O(P);對id集合排序,排序時只需要對MaxRank較小的前k個對象排序即可,遍歷一遍所有id,時間復(fù)雜度為O(P),前k個對象的排序,用插入排序法,時間復(fù)雜度為O(k2);候選id集合獲取和分組時間復(fù)雜度都為O(P),上述步驟都在內(nèi)存中可以完成,不需要I/O操作;最后Hadoop并行計算和top-k結(jié)果輸出即可,時間復(fù)雜度跟Hadoop平臺有關(guān)。除去Hadoop的計算時間,綜上,時間復(fù)雜度為O(P+k2)。

    2.2.2 空間復(fù)雜度算法預(yù)先建立的數(shù)據(jù)結(jié)構(gòu)COIT只記錄有限條記錄,因此該空間開銷是比較小的。整個算法中,Master節(jié)點(diǎn)需要維護(hù)一個全局的COIT表,假設(shè)有M個屬性,對象id和M個屬性都為整數(shù),占4個字節(jié),則COIT表每條記錄占4(M+1)字節(jié),整個COIT表占4(M+1)×P。在算法計算過程中,需要建立臨時候選id集合,每個id只保留RankMax和RankMin,所以每條記錄占12個字節(jié),空間開銷為12P字節(jié)。對id集合排序過程中,需要維護(hù)前k條記錄,每條記錄只保留id和RankMax,占8k字節(jié)。綜上,空間開銷為O(MP+k)。

    3實(shí)驗分析

    在本節(jié)中,通過實(shí)驗來評估算法PCMRA。首先,介紹實(shí)驗設(shè)計。然后是具體實(shí)驗以及結(jié)果分析。

    3.1 實(shí)驗設(shè)計

    3.1.1 實(shí)驗環(huán)境

    實(shí)驗在6臺32位Linux機(jī)器上運(yùn)行,每一臺處理器型號為奔騰G620,主頻2.60GHz的,內(nèi)存4GB,硬盤8G,操作系統(tǒng)為centos。這些機(jī)器都預(yù)先安裝并行數(shù)據(jù)處理引擎的Hadoop。這些機(jī)器與局域網(wǎng)連接起來,局域網(wǎng)網(wǎng)速為1000Mbps。算法用Java完成。

    3.1.2 對比實(shí)驗對比實(shí)驗不采用預(yù)處理數(shù)據(jù)結(jié)構(gòu)COIT,用Hadoop平臺計算所有對象的得分,并排序得到前k個對象,本文稱該對比算法為Naive算法。

    3.1.3 數(shù)據(jù)集均勻分布數(shù)據(jù)集。

    3.1.4 實(shí)驗參數(shù)元組數(shù)N,一共分為10組,取值分別為1k,2k,3k,4k,5k,6k,7k,8k,9k,10k,默認(rèn)取值為5k。

    查詢結(jié)果數(shù)k,也分為10組,取值分別為10,20,30,40,50,60,70,80,90,100,默認(rèn)取值為50。

    查詢屬性個數(shù)W,也分為10組,取值分別為1,2,3,4,5,6,7,8,9,10,默認(rèn)取值為5。

    3.1.5 性能指標(biāo)運(yùn)行時間time:顯然算法運(yùn)行時間越短代表算法的性能越好。

    候選元組比率Ratio:Ratio為本文自定義的參數(shù),它是總的元組數(shù)N、查詢結(jié)果數(shù)K以及查詢屬性個數(shù)W的乘積與候選id個數(shù)Cn的比值的倒數(shù)的1000倍。容易看出,候選id個數(shù)Cn,隨著總的元組數(shù)N,查詢結(jié)果數(shù)K以及查詢屬性個數(shù)W的增加,其候選id個數(shù)顯然是增加的,顯然候選id個數(shù)Cn與以上3個因素是成正相關(guān)的。因此如果算法是線性可擴(kuò)展的,則隨著元組數(shù)N的線性增長,候選元組數(shù)也是線性增長的。倘若算法線性擴(kuò)展能力好,在總的元組數(shù)N、查詢結(jié)果數(shù)K以及查詢屬性個數(shù)W其中2個值固定,一個值線性增長的情況下,候選元組比率應(yīng)該Ratio是一常量,甚至是降低的。Ratio的計算公式如下:

    (2)

    3.1.6 查詢設(shè)定為了方便起見,查詢請求的各屬性權(quán)重設(shè)為wi=1/W,查詢屬性列選取COIT表中前W列屬性。

    3.2 實(shí)驗及結(jié)果分析

    3.2.1 實(shí)驗一:元組數(shù)N的影響設(shè)定k=50,W=5,實(shí)驗一反映了PCMRA和Naive算法隨著元組數(shù)N的變化,算法的性能指標(biāo)的變化。圖3(a)表明隨著元組數(shù)從1k增加到10k,PCMRA算法候選元組比率Ratio從0.17左右降到大約0.03,并且在元組數(shù)為10k時,候選元組比率Ratio僅為0.03,根據(jù)公式計算,候選元組數(shù)Cn僅為總元組數(shù)的8%左右,篩選的不相關(guān)元組數(shù)能達(dá)到90%以上,并且由圖中趨勢推斷,隨著元組數(shù)的增加,候選元組比例仍在降低,而Naive算法一直穩(wěn)定在4。Ratio越低說明算法性能越好,說明PCMRA算法性能更優(yōu),明顯具有更好的擴(kuò)展性。圖3(b)表明隨著元組數(shù)從1k遞增到10k,PCMRA算法運(yùn)行時間從24s增到27s,時間增加12.5%,而Naive算法從25s增加到34s,時間增加36%,顯然Naive算法比PCMRA算法運(yùn)行時間慢,并且增幅比為后者的將近3倍。由圖中趨勢看隨著元組數(shù)N的增加,這一差異將更加明顯,顯然PCMRA算法在時間性能上更好。

    圖3 元組數(shù)N的影響

    3.2.2 實(shí)驗二:查詢結(jié)果數(shù)k的影響設(shè)定N=5k,W=5,實(shí)驗二反映了PCMRA和Naive算法隨著查詢結(jié)果數(shù)k的變化,算法的性能指標(biāo)的變化。圖4(a)表明隨著查詢結(jié)果數(shù)從10逐漸增加到100,PCMRA算法候選元組比率Ratio從0.85降到0.45左右,雖然Naive算法候選元組比率Ratio從20降到2,降幅明顯,但是前者一直比后者低,并且前者比例也一直在降低。同實(shí)驗一分析結(jié)果一致。圖4(b)表明隨著查詢結(jié)果數(shù)從10遞增到100,PCMRA算法運(yùn)行時間從24s增到25s,而Naive算法從25s增加到28s,2個算法時間增加都不明顯,但是PCMRA算法仍然比Naive算法運(yùn)行時間短,PCMRA算法在時間性能上仍然優(yōu)于Naive算法。

    圖4 查詢結(jié)果數(shù)k的影響

    3.2.3 實(shí)驗三:查詢屬性個數(shù)W的影響設(shè)定k=50,N=5k,實(shí)驗三反映了PCMRA和Naive算法隨著查詢屬性個數(shù)W的變化,算法的性能指標(biāo)的變化。圖5(a)表明查詢屬性從1個增加到10個,PCMRA算法候選元組比率Ratio比例一直在0.5左右,仍有不太明顯的降低趨勢,同實(shí)驗二,Naive算法降幅明顯,但是仍然一直比PCMRA算法Ratio要高的多,因此分析結(jié)果同實(shí)驗一一致。圖5(b)表明查詢屬性從1個增加到10個,PCMRA算法運(yùn)行時間從23s增到25s,而Naive算法從25s增加到30s,同實(shí)驗二2個算法時間增加都不明顯,但是PCMRA算法仍然比Naive算法運(yùn)行時間短,PCMRA算法在時間性能上仍然優(yōu)于Naive算法。

    圖5 查詢屬性個數(shù)W的影響

    4結(jié)語

    本文中,我們分析了當(dāng)今數(shù)據(jù)的發(fā)展趨勢,而現(xiàn)有算法比較耗時,并需要大量的通信。隨著網(wǎng)絡(luò)數(shù)據(jù)的增加,傳統(tǒng)的top-k算法更加難以處理這些問題。所以本文提出了一種分布式環(huán)境下top-k算法PCMRA。它僅需要較小的構(gòu)建代價和較少的空間開銷,就可以建立數(shù)據(jù)預(yù)處理結(jié)構(gòu)COIT。借助COIT,使用我們的數(shù)據(jù)分割策略,并采用并行編程模型MapReduce,我們的算法PCMRA只需要與服務(wù)器的一輪通信就可以完成top-k查詢。本文給出了算法正確性證明,并對算法的時間復(fù)雜度和空間復(fù)雜度進(jìn)行分析。實(shí)驗部分表明該算法僅涉及有效通信,并且運(yùn)行時間短,查詢結(jié)果準(zhǔn)確,可擴(kuò)展性好。這表明該算法在一定條件下優(yōu)于現(xiàn)有的算法。

    本文算法設(shè)計針對大數(shù)據(jù)的應(yīng)用環(huán)境的確定數(shù)據(jù)庫,但是隨著數(shù)據(jù)的爆炸增長,數(shù)據(jù)的不確定性為top-k查詢問題帶來了很多困難,圍繞不確定型數(shù)據(jù)模型和可能世界語義的top-k查詢已經(jīng)引起了廣泛的關(guān)注。但可能世界語義的top-k查詢問題仍需要大量的研究。下一步,我們將本文的算法擴(kuò)展到不確定數(shù)據(jù)庫。首先定義基于多屬性綜合得分的可能世界語義的top-k查詢模型,然后針對此查詢,設(shè)計一種帶有預(yù)處理結(jié)構(gòu)的不確定數(shù)據(jù)庫上top-k查詢,并沿用數(shù)據(jù)分割和采用MapReduce并行編程的思路。

    參考文獻(xiàn):

    [1]Lohr S. The Age of Big Data[J]. SR1, online: http: //www.nytimes.com/2012/02/12/sunday-review/big-datas-impact- in-the-world.html, 2012, 16(4): 10-15.

    [2]Han X, Li J, Wang J, et al. TJJE: An efficient algorithm for top-k join on massive data[J]. Information Sciences An International Journal, 2013, 222(3): 362-383.

    [3]Ronald Fagin, Amnon Lotem, Moni Naor. Optimal aggregation algorithms for middleware[J]. Journal of Computer and System Sciences, 2003: 102-113.

    [4]Zhao K, Tao Y, Zhou S. Efficient top- k processing in large-scaled distributed environments[J]. Data & Knowledge Engineering, 2007, 63(2): 315-335.

    [5]Cao Pei, Wang Zhe. Efficient Top-K Query Calculation in Distributed Networks[C].Newfoundland: PODC, 2004: 206-215.

    [6]Michel S, Triantafillou P, Weikum G. KLEE: A Framework for Distributed Top-K Query Algorithms[J]. Vldb, 2005: 637-648.

    [7]Chrysakis I, Chalkidis C, Plexousakis D. A Detailed Evaluation of Threshold Algorithms for Answering Top-k queries in Peer-to-Peer Networks[J]. 2010.

    [8]Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters.[J]. In Proceedings of Operating Systems Design and Implementation 2004, 51(1): 107-113.

    [9]Soliman M A, Ilyas I F, Chen-Chuan Chang K. Top-k Query Processing in Uncertain Databases[C]//Data Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on. IEEE, 2007: 896-905.

    [10]Hua M, Pei J, Zhang W, et al. Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach[C]. Florida: Computer Science Department, Florida State University, 2008: 673-686.

    [11]Yi K, Li F, Kollios G, et al. Efficient processing of top-k queries in uncertain databases with x-relations.[J]. IEEE Transactions on Knowledge & Data Engineering, 2008, 20(12): 1669-1682.

    [12]Cormode G, Li F, Yi K. Semantics of Ranking Queries for Probabilistic Data and Expected Ranks[C].Chicago: 2014 IEEE 30th International Conference on Data Engineering, 2009: 305-316.

    責(zé)任編輯陳呈超

    PCMRA: An Efficient Top-kAlgorithm in Distributed Environment

    WANG Ning, QU Hai-Peng, FAN Ling

    (College of Information Science and Engineering, Ocean University of China, Qingdao 266100, China)

    Abstract:With the unceasing expansion size of the data and the increasing complexity of data types, human race has entered the era of big data. On the one hand, there is a sharp increase of the data provided from different areas and applications, on the other hand, the traditional data processing techniques can not cope with such a large-scale data, thus this situation brings serious challenges to the current data processing techniques. We are on a pressing demand to effectively dig out the beneficial information we need, thus we have to raise a faster and more effective query technique. Ranking queries, which is known as top-k query, is one of various complex data queries. It works by calculating the scores of all objects by an aggregation function, and then return the top-k objects with the highest scores. For many interactive systems, efficient Top-k query are very important. Top-k query problem also involves a lot of database processing technologies, including indexing and query optimization, etc. Top-k query is now attracting more and more attention for the broad use and the efficiency, so it is now a hot spot in research area, and it is also has very important theory value and the very extensive application prospects. This paper mainly researched on the corresponding top-k query algorithm for large-scale data, and then made some innovation. Finding the top-k best records among the potentially huge answer space in real time for many interactive systems, is a challenging issue today, for there is an increasing trend that more and more data needs to be processed. With the increase of network traffic, these problems will become unsolvable. Learning from the good features of the traditional top-k query processing technology and using parallel programming model - MapReduce, this paper proposes a novel top-k algorithm PCMRA(Data Partitioning and COIT Indexing Top-k query Algorithm based on MapReduce). Our solution develops a pre-construction algorithm to construct COIT (Candidate Objects Index Table), adopting a new strategy of data partitioning, completing the top-k query in one round by means of parallel programming model: MapReduce. The correctness proof and cost analysis of PCMRA are present in this paper. Experiments show that the algorithm only requires lower construction cost and less space overhead . A small number of candidate objects can be selected in a relatively short period of time, greatly saving computing and communication resources, and also the algorithm has good scalability.

    Key words:top-k query; COIT; data partitionin; MapReduce; massive data

    DOI:10.16441/j.cnki.hdxb.20140032

    中圖法分類號:TP311

    文獻(xiàn)標(biāo)志碼:A

    文章編號:1672-5174(2016)02-138-08

    作者簡介:王寧(1987-),女,碩士生。E-mail:wangnynn@gmail.com??通訊作者: E-mail:quhaipeng@ouc.edu.cn

    收稿日期:2014-03-05;

    修訂日期:2014-10-09

    基金項目:? 國家自然科學(xué)基金項目(60773057);國家海洋局海洋公益項目(201105033)

    引用格式:王寧, 曲海鵬, 范令. 一種分布式環(huán)境下高效查詢算法[J]. 中國海洋大學(xué)學(xué)報(自然科學(xué)版), 2016, 46(2): 138-145.

    Supported by National Natural Science Foundation of China(60773057);The State Oceanic Administration of Marine Public Welfare Projects(201105033)

    亚洲国产精品999| 久久久久久久大尺度免费视频| 少妇被粗大的猛进出69影院| 国产日韩欧美视频二区| 超碰成人久久| 久久天躁狠狠躁夜夜2o2o| 国产野战对白在线观看| 亚洲情色 制服丝袜| 大香蕉久久成人网| 免费女性裸体啪啪无遮挡网站| 一级a爱视频在线免费观看| 永久免费av网站大全| 亚洲全国av大片| 99国产精品一区二区蜜桃av | 国产精品 欧美亚洲| 久久天堂一区二区三区四区| 国产1区2区3区精品| 亚洲avbb在线观看| 亚洲精品中文字幕一二三四区 | 国产成人av激情在线播放| 亚洲av日韩在线播放| 每晚都被弄得嗷嗷叫到高潮| 91麻豆av在线| 人人妻人人澡人人爽人人夜夜| 久久久久网色| av又黄又爽大尺度在线免费看| 十八禁网站网址无遮挡| 不卡一级毛片| 黄色a级毛片大全视频| 亚洲色图 男人天堂 中文字幕| 男女免费视频国产| a级片在线免费高清观看视频| 热99国产精品久久久久久7| 桃花免费在线播放| 午夜福利在线免费观看网站| 69av精品久久久久久 | 欧美日韩亚洲高清精品| 在线 av 中文字幕| 亚洲精品国产一区二区精华液| 欧美精品一区二区大全| h视频一区二区三区| 亚洲中文字幕日韩| 一级毛片精品| 老司机午夜福利在线观看视频 | 国产精品影院久久| 两性午夜刺激爽爽歪歪视频在线观看 | 日韩三级视频一区二区三区| 亚洲欧美激情在线| 欧美人与性动交α欧美精品济南到| 乱人伦中国视频| 国产一区有黄有色的免费视频| 亚洲成人免费av在线播放| 国产成人一区二区三区免费视频网站| 久久性视频一级片| 中文字幕制服av| 国产精品欧美亚洲77777| 国产福利在线免费观看视频| 国产免费av片在线观看野外av| 美国免费a级毛片| 法律面前人人平等表现在哪些方面 | 久久人妻福利社区极品人妻图片| videos熟女内射| 在线十欧美十亚洲十日本专区| 色综合欧美亚洲国产小说| 男女之事视频高清在线观看| 欧美在线黄色| 国产精品久久久久久精品电影小说| 久久人人爽av亚洲精品天堂| 亚洲美女黄色视频免费看| 美女高潮喷水抽搐中文字幕| 亚洲精品国产av蜜桃| 99久久99久久久精品蜜桃| 国产极品粉嫩免费观看在线| 日韩三级视频一区二区三区| 性色av一级| 两个人看的免费小视频| 亚洲精品久久久久久婷婷小说| 国产黄频视频在线观看| 制服诱惑二区| 欧美激情高清一区二区三区| 一个人免费看片子| 国产精品久久久久成人av| 夜夜夜夜夜久久久久| 啪啪无遮挡十八禁网站| 91麻豆精品激情在线观看国产 | 老司机深夜福利视频在线观看 | 黑丝袜美女国产一区| 好男人电影高清在线观看| 亚洲一区中文字幕在线| 久久人人爽av亚洲精品天堂| 三级毛片av免费| 狠狠狠狠99中文字幕| 人妻一区二区av| 亚洲全国av大片| 曰老女人黄片| 成人国产av品久久久| 日本猛色少妇xxxxx猛交久久| 桃红色精品国产亚洲av| 亚洲精品美女久久av网站| 国产真人三级小视频在线观看| 亚洲一区中文字幕在线| 日日爽夜夜爽网站| √禁漫天堂资源中文www| 18禁裸乳无遮挡动漫免费视频| 18在线观看网站| 黄色视频不卡| 国产一级毛片在线| 久久精品亚洲熟妇少妇任你| 免费日韩欧美在线观看| 老司机深夜福利视频在线观看 | 18禁观看日本| 97精品久久久久久久久久精品| 国产成人a∨麻豆精品| 成人18禁高潮啪啪吃奶动态图| 亚洲avbb在线观看| 久久这里只有精品19| 日本一区二区免费在线视频| 视频区图区小说| 多毛熟女@视频| 久久人妻福利社区极品人妻图片| 巨乳人妻的诱惑在线观看| 亚洲精品成人av观看孕妇| 老司机深夜福利视频在线观看 | 亚洲国产看品久久| 亚洲精品在线美女| 亚洲欧美一区二区三区久久| 九色亚洲精品在线播放| 不卡一级毛片| 韩国高清视频一区二区三区| 婷婷色av中文字幕| 欧美乱码精品一区二区三区| 久久ye,这里只有精品| 国产男人的电影天堂91| 波多野结衣一区麻豆| 天天添夜夜摸| 欧美变态另类bdsm刘玥| 亚洲av日韩精品久久久久久密| 91成人精品电影| 亚洲少妇的诱惑av| 国产精品久久久久久精品电影小说| 亚洲精品久久午夜乱码| 久久久久国产一级毛片高清牌| 亚洲一卡2卡3卡4卡5卡精品中文| 性高湖久久久久久久久免费观看| 人人妻人人爽人人添夜夜欢视频| 亚洲视频免费观看视频| 午夜影院在线不卡| 亚洲专区中文字幕在线| 国产亚洲一区二区精品| 丝袜美足系列| 在线观看免费高清a一片| 亚洲 欧美一区二区三区| 国产精品欧美亚洲77777| 老司机福利观看| 欧美日韩成人在线一区二区| 日韩熟女老妇一区二区性免费视频| 他把我摸到了高潮在线观看 | 久久久久久久国产电影| 亚洲精品中文字幕在线视频| 午夜两性在线视频| av免费在线观看网站| 黑人巨大精品欧美一区二区mp4| 天天躁日日躁夜夜躁夜夜| 99九九在线精品视频| 国产高清视频在线播放一区 | 大香蕉久久成人网| 母亲3免费完整高清在线观看| 天天添夜夜摸| 一二三四社区在线视频社区8| 精品乱码久久久久久99久播| 欧美激情高清一区二区三区| 三级毛片av免费| 国产高清videossex| 免费日韩欧美在线观看| 亚洲欧洲日产国产| 99久久精品国产亚洲精品| 欧美日韩成人在线一区二区| 91国产中文字幕| 午夜福利在线观看吧| 最近最新免费中文字幕在线| 人成视频在线观看免费观看| 叶爱在线成人免费视频播放| 十八禁网站网址无遮挡| 久久亚洲国产成人精品v| 在线永久观看黄色视频| 国产一卡二卡三卡精品| 精品人妻1区二区| 天天躁狠狠躁夜夜躁狠狠躁| 在线观看一区二区三区激情| 丝袜喷水一区| 午夜影院在线不卡| 久久精品aⅴ一区二区三区四区| 亚洲视频免费观看视频| 91精品三级在线观看| 久久久精品免费免费高清| 在线观看免费视频网站a站| 久久亚洲国产成人精品v| 捣出白浆h1v1| 国产欧美日韩一区二区精品| 俄罗斯特黄特色一大片| 日韩欧美免费精品| 免费女性裸体啪啪无遮挡网站| 欧美变态另类bdsm刘玥| 久久毛片免费看一区二区三区| 一个人免费看片子| 每晚都被弄得嗷嗷叫到高潮| 国产精品久久久久久精品古装| 男人爽女人下面视频在线观看| 亚洲专区国产一区二区| 亚洲专区国产一区二区| 成年人午夜在线观看视频| 婷婷色av中文字幕| 国产不卡av网站在线观看| 日韩,欧美,国产一区二区三区| 亚洲国产看品久久| 丁香六月天网| 波多野结衣av一区二区av| 12—13女人毛片做爰片一| 国产在线一区二区三区精| 少妇粗大呻吟视频| 欧美 日韩 精品 国产| 欧美激情久久久久久爽电影 | 亚洲精品国产av蜜桃| 亚洲中文字幕日韩| 韩国精品一区二区三区| 热re99久久精品国产66热6| 黑人操中国人逼视频| 中文精品一卡2卡3卡4更新| 欧美一级毛片孕妇| 国产精品欧美亚洲77777| 欧美日韩av久久| 亚洲 国产 在线| 婷婷色av中文字幕| 国产精品一二三区在线看| 超碰97精品在线观看| 亚洲专区国产一区二区| 久久久久久免费高清国产稀缺| 亚洲欧美激情在线| 性色av一级| 久热爱精品视频在线9| 午夜两性在线视频| 亚洲三区欧美一区| 亚洲少妇的诱惑av| 在线观看人妻少妇| 精品人妻1区二区| 亚洲欧美色中文字幕在线| 搡老岳熟女国产| 男女无遮挡免费网站观看| 日本91视频免费播放| 91成人精品电影| 啦啦啦免费观看视频1| 国产精品久久久人人做人人爽| av天堂在线播放| 久热这里只有精品99| 亚洲第一青青草原| 精品人妻熟女毛片av久久网站| 日本黄色日本黄色录像| 深夜精品福利| 国产亚洲欧美在线一区二区| 免费观看人在逋| 欧美xxⅹ黑人| 国产激情久久老熟女| 国产日韩欧美视频二区| 日本黄色日本黄色录像| 国产精品.久久久| 老汉色av国产亚洲站长工具| 两个人免费观看高清视频| 亚洲成人免费av在线播放| 国产在线一区二区三区精| 巨乳人妻的诱惑在线观看| 午夜影院在线不卡| 巨乳人妻的诱惑在线观看| 一区二区日韩欧美中文字幕| 欧美激情 高清一区二区三区| 午夜福利在线观看吧| 99久久精品国产亚洲精品| 久9热在线精品视频| 欧美日韩一级在线毛片| 99久久国产精品久久久| 国产成人一区二区三区免费视频网站| 免费高清在线观看视频在线观看| 欧美日韩亚洲综合一区二区三区_| 大型av网站在线播放| 18在线观看网站| 伊人亚洲综合成人网| 久久免费观看电影| 99国产精品一区二区蜜桃av | 久久香蕉激情| 99国产精品一区二区蜜桃av | 黄色视频在线播放观看不卡| 欧美变态另类bdsm刘玥| 亚洲 国产 在线| 高清欧美精品videossex| 亚洲精品日韩在线中文字幕| 亚洲七黄色美女视频| 男女之事视频高清在线观看| 国产成人影院久久av| 美女主播在线视频| e午夜精品久久久久久久| 欧美一级毛片孕妇| 免费在线观看日本一区| 老司机深夜福利视频在线观看 | 一二三四社区在线视频社区8| 午夜福利免费观看在线| 亚洲七黄色美女视频| 如日韩欧美国产精品一区二区三区| 日本猛色少妇xxxxx猛交久久| 国产免费视频播放在线视频| 亚洲av片天天在线观看| 亚洲欧美精品综合一区二区三区| 日韩欧美国产一区二区入口| 国产欧美日韩一区二区三 | av超薄肉色丝袜交足视频| 日本一区二区免费在线视频| 欧美国产精品一级二级三级| 99九九在线精品视频| 日韩一区二区三区影片| www.自偷自拍.com| 日韩精品免费视频一区二区三区| 精品国产一区二区三区久久久樱花| 丝袜人妻中文字幕| 久久久久久亚洲精品国产蜜桃av| av国产精品久久久久影院| 两性午夜刺激爽爽歪歪视频在线观看 | 久热爱精品视频在线9| 亚洲精品中文字幕在线视频| 日韩视频在线欧美| 1024香蕉在线观看| 免费观看人在逋| 久久香蕉激情| 丰满迷人的少妇在线观看| a级毛片黄视频| 亚洲少妇的诱惑av| 亚洲精品粉嫩美女一区| 久久久久国内视频| 自拍欧美九色日韩亚洲蝌蚪91| 亚洲欧美一区二区三区久久| 不卡一级毛片| 国产av一区二区精品久久| 国产精品av久久久久免费| 男人操女人黄网站| 欧美精品av麻豆av| 色婷婷久久久亚洲欧美| 99国产极品粉嫩在线观看| 精品人妻熟女毛片av久久网站| 最新的欧美精品一区二区| 爱豆传媒免费全集在线观看| 脱女人内裤的视频| 在线观看www视频免费| 在线观看免费视频网站a站| 欧美日韩中文字幕国产精品一区二区三区 | 国产精品av久久久久免费| 99热国产这里只有精品6| av天堂久久9| 老司机在亚洲福利影院| 亚洲国产看品久久| 午夜福利在线观看吧| 高清在线国产一区| 欧美成人午夜精品| kizo精华| 这个男人来自地球电影免费观看| 日本猛色少妇xxxxx猛交久久| 热99国产精品久久久久久7| 巨乳人妻的诱惑在线观看| 狠狠狠狠99中文字幕| 各种免费的搞黄视频| av不卡在线播放| 国产真人三级小视频在线观看| 国产免费福利视频在线观看| 亚洲免费av在线视频| 男男h啪啪无遮挡| 亚洲国产成人一精品久久久| 宅男免费午夜| 欧美精品一区二区免费开放| 久久久久久久久免费视频了| 亚洲专区国产一区二区| 亚洲视频免费观看视频| 亚洲精品久久久久久婷婷小说| 搡老乐熟女国产| 不卡一级毛片| 99精品欧美一区二区三区四区| 亚洲色图 男人天堂 中文字幕| 久久人人爽av亚洲精品天堂| 国产精品国产三级国产专区5o| av视频免费观看在线观看| 久久99一区二区三区| 亚洲第一欧美日韩一区二区三区 | 18禁黄网站禁片午夜丰满| 亚洲欧美清纯卡通| 美女高潮喷水抽搐中文字幕| av福利片在线| 亚洲成人手机| 999久久久国产精品视频| 精品国产乱码久久久久久男人| 一区二区av电影网| 国产免费视频播放在线视频| 飞空精品影院首页| 啦啦啦 在线观看视频| 免费观看a级毛片全部| 青青草视频在线视频观看| 少妇粗大呻吟视频| 欧美黑人欧美精品刺激| 丝袜人妻中文字幕| 国产高清国产精品国产三级| 性色av乱码一区二区三区2| 国产成人免费观看mmmm| 久久久精品区二区三区| 免费观看av网站的网址| 一进一出抽搐动态| 久久99热这里只频精品6学生| 久久国产精品影院| 国产免费av片在线观看野外av| 国产av精品麻豆| 十分钟在线观看高清视频www| 一本久久精品| 久久狼人影院| 日韩欧美免费精品| 一本—道久久a久久精品蜜桃钙片| 国产精品久久久久成人av| 97在线人人人人妻| 亚洲国产精品一区二区三区在线| 各种免费的搞黄视频| 国产精品免费视频内射| 欧美激情 高清一区二区三区| 中文欧美无线码| 两个人看的免费小视频| 国产精品一二三区在线看| 人人妻人人爽人人添夜夜欢视频| 两性夫妻黄色片| 精品一区二区三区av网在线观看 | 亚洲 欧美一区二区三区| 亚洲精品中文字幕在线视频| 欧美人与性动交α欧美软件| 国产免费视频播放在线视频| av在线app专区| 伊人亚洲综合成人网| 91大片在线观看| 亚洲国产成人一精品久久久| 美女大奶头黄色视频| 精品少妇内射三级| kizo精华| 热99re8久久精品国产| 又黄又粗又硬又大视频| 波多野结衣av一区二区av| 中亚洲国语对白在线视频| av天堂久久9| 成年av动漫网址| 肉色欧美久久久久久久蜜桃| 国产精品一区二区在线不卡| 亚洲三区欧美一区| 午夜福利免费观看在线| 一本—道久久a久久精品蜜桃钙片| 亚洲一区中文字幕在线| 欧美黄色片欧美黄色片| 黄色片一级片一级黄色片| 亚洲精品国产av成人精品| 欧美激情极品国产一区二区三区| 国产成人av激情在线播放| 久久久精品免费免费高清| 国产欧美日韩综合在线一区二区| 亚洲一区中文字幕在线| 在线精品无人区一区二区三| 99久久国产精品久久久| a级毛片黄视频| 欧美日本中文国产一区发布| 国产精品亚洲av一区麻豆| 成年人午夜在线观看视频| 亚洲精品一二三| 精品一区二区三区四区五区乱码| 美女国产高潮福利片在线看| 国产亚洲欧美在线一区二区| 日日摸夜夜添夜夜添小说| 日韩精品免费视频一区二区三区| 美女主播在线视频| 欧美 亚洲 国产 日韩一| 91麻豆精品激情在线观看国产 | 国产国语露脸激情在线看| a级毛片黄视频| 日韩,欧美,国产一区二区三区| 99久久精品国产亚洲精品| 97人妻天天添夜夜摸| 免费高清在线观看日韩| 欧美大码av| av线在线观看网站| 啪啪无遮挡十八禁网站| 日日摸夜夜添夜夜添小说| 波多野结衣av一区二区av| 后天国语完整版免费观看| 又黄又粗又硬又大视频| 亚洲成人国产一区在线观看| 成人国产av品久久久| 国产成人免费无遮挡视频| 国产日韩欧美在线精品| 在线观看免费日韩欧美大片| netflix在线观看网站| 精品人妻在线不人妻| 别揉我奶头~嗯~啊~动态视频 | 日本黄色日本黄色录像| 亚洲精品乱久久久久久| 国产亚洲一区二区精品| 纵有疾风起免费观看全集完整版| 国产av国产精品国产| 精品人妻在线不人妻| 99热国产这里只有精品6| 欧美精品亚洲一区二区| 国产三级黄色录像| 2018国产大陆天天弄谢| 人人妻,人人澡人人爽秒播| 国产精品偷伦视频观看了| 亚洲自偷自拍图片 自拍| 精品人妻熟女毛片av久久网站| 国产精品免费大片| 亚洲国产成人一精品久久久| 中国美女看黄片| av电影中文网址| 国产精品一区二区在线观看99| 我的亚洲天堂| 精品一区二区三卡| 在线观看免费午夜福利视频| 久热爱精品视频在线9| 久久精品国产亚洲av高清一级| 少妇猛男粗大的猛烈进出视频| 久久亚洲精品不卡| 精品国产一区二区久久| 亚洲成人免费电影在线观看| 欧美精品一区二区大全| 亚洲av成人一区二区三| 高清视频免费观看一区二区| 大码成人一级视频| 亚洲国产欧美日韩在线播放| 免费在线观看日本一区| 亚洲视频免费观看视频| 人妻久久中文字幕网| av线在线观看网站| 欧美成狂野欧美在线观看| 五月天丁香电影| av有码第一页| √禁漫天堂资源中文www| 十八禁高潮呻吟视频| 国产黄色免费在线视频| 亚洲va日本ⅴa欧美va伊人久久 | 满18在线观看网站| 精品少妇内射三级| 国产不卡av网站在线观看| 精品久久久久久电影网| 韩国精品一区二区三区| 日本vs欧美在线观看视频| 涩涩av久久男人的天堂| 18禁裸乳无遮挡动漫免费视频| 国产欧美日韩一区二区三区在线| 亚洲一区二区三区欧美精品| 女性被躁到高潮视频| 欧美激情高清一区二区三区| 99国产精品一区二区三区| 成人亚洲精品一区在线观看| 9色porny在线观看| 一个人免费看片子| 国产成人av教育| 国产成人欧美| 在线观看免费日韩欧美大片| 水蜜桃什么品种好| 在线看a的网站| 超碰成人久久| 久久人妻福利社区极品人妻图片| 美女福利国产在线| 精品人妻熟女毛片av久久网站| av国产精品久久久久影院| 91成年电影在线观看| 国产免费视频播放在线视频| 99精品欧美一区二区三区四区| 欧美大码av| 欧美午夜高清在线| 欧美中文综合在线视频| 日韩欧美国产一区二区入口| 亚洲一卡2卡3卡4卡5卡精品中文| 九色亚洲精品在线播放| 狠狠狠狠99中文字幕| 老司机亚洲免费影院| 美女脱内裤让男人舔精品视频| 我的亚洲天堂| 欧美变态另类bdsm刘玥| 777米奇影视久久| 丁香六月天网| 人人妻人人澡人人看| 午夜精品国产一区二区电影| tocl精华| 久久人人爽人人片av| 母亲3免费完整高清在线观看| 老司机深夜福利视频在线观看 | 国产精品 欧美亚洲| 国产又爽黄色视频| 国产精品亚洲av一区麻豆| 国产精品影院久久| 女警被强在线播放| 精品国产超薄肉色丝袜足j| 最新的欧美精品一区二区| 老熟妇乱子伦视频在线观看 | 在线看a的网站| 国产成+人综合+亚洲专区| 国产男女超爽视频在线观看| 亚洲国产精品一区三区| 日韩欧美一区视频在线观看| 亚洲第一欧美日韩一区二区三区 | 国产精品一区二区在线不卡| 久久精品aⅴ一区二区三区四区| 女人精品久久久久毛片| 狠狠精品人妻久久久久久综合| 日本av免费视频播放| 亚洲精品第二区| 美女大奶头黄色视频| 亚洲国产精品成人久久小说| 欧美xxⅹ黑人| 咕卡用的链子| 高清视频免费观看一区二区| 青青草视频在线视频观看|