• <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)

    色婷婷av一区二区三区视频| 熟女av电影| 婷婷色综合www| 国产成人av激情在线播放 | 高清黄色对白视频在线免费看| 国产无遮挡羞羞视频在线观看| 国产欧美另类精品又又久久亚洲欧美| 久久久国产精品麻豆| 亚洲丝袜综合中文字幕| 国产亚洲精品久久久com| 草草在线视频免费看| 大陆偷拍与自拍| 亚洲第一av免费看| 中文字幕亚洲精品专区| 在现免费观看毛片| 9色porny在线观看| 国产视频首页在线观看| xxx大片免费视频| 久久99一区二区三区| 精品一区二区三卡| 亚洲情色 制服丝袜| 全区人妻精品视频| 乱人伦中国视频| 一本久久精品| 国产欧美另类精品又又久久亚洲欧美| 日韩av不卡免费在线播放| 一个人看视频在线观看www免费| 中文字幕免费在线视频6| 国内精品宾馆在线| 青青草视频在线视频观看| www.色视频.com| 2022亚洲国产成人精品| 成人亚洲欧美一区二区av| 少妇被粗大的猛进出69影院 | 成人免费观看视频高清| 久久久精品94久久精品| 少妇被粗大猛烈的视频| 国产午夜精品久久久久久一区二区三区| 国产免费福利视频在线观看| 国产免费一级a男人的天堂| 97在线人人人人妻| 精品少妇内射三级| 天堂8中文在线网| 自拍欧美九色日韩亚洲蝌蚪91| 精品国产一区二区久久| videosex国产| 久久女婷五月综合色啪小说| 男的添女的下面高潮视频| 免费高清在线观看日韩| 伦理电影大哥的女人| 熟女av电影| 日韩精品免费视频一区二区三区 | 国产亚洲午夜精品一区二区久久| 日日撸夜夜添| 欧美+日韩+精品| 黄色配什么色好看| 欧美丝袜亚洲另类| 午夜免费鲁丝| 免费观看无遮挡的男女| 成人黄色视频免费在线看| 久久精品国产亚洲av涩爱| 秋霞伦理黄片| 亚洲三级黄色毛片| 三级国产精品片| 国产成人aa在线观看| 日韩亚洲欧美综合| 99九九在线精品视频| 精品国产国语对白av| 热re99久久国产66热| 热re99久久国产66热| 热re99久久国产66热| 久久精品久久精品一区二区三区| 色哟哟·www| 日韩av在线免费看完整版不卡| a级片在线免费高清观看视频| 蜜桃国产av成人99| 91精品国产国语对白视频| 一级a做视频免费观看| 又大又黄又爽视频免费| 亚洲精品视频女| 日本-黄色视频高清免费观看| 人妻制服诱惑在线中文字幕| 一级毛片aaaaaa免费看小| 一级爰片在线观看| 精品人妻一区二区三区麻豆| 丝瓜视频免费看黄片| 国产日韩欧美亚洲二区| 熟妇人妻不卡中文字幕| 精品人妻一区二区三区麻豆| 国产日韩欧美亚洲二区| 亚洲国产精品成人久久小说| 亚洲精品国产av成人精品| 中文字幕av电影在线播放| 一本—道久久a久久精品蜜桃钙片| 精品人妻熟女毛片av久久网站| 人妻系列 视频| 少妇人妻精品综合一区二区| 一边摸一边做爽爽视频免费| 欧美性感艳星| 精品一区在线观看国产| 男女高潮啪啪啪动态图| 黑人欧美特级aaaaaa片| 哪个播放器可以免费观看大片| 寂寞人妻少妇视频99o| 久久久国产精品麻豆| 久久久欧美国产精品| 大又大粗又爽又黄少妇毛片口| 如何舔出高潮| 免费黄色在线免费观看| 在线免费观看不下载黄p国产| 亚洲欧美日韩另类电影网站| 亚洲av综合色区一区| 男人爽女人下面视频在线观看| 在线观看国产h片| 18禁裸乳无遮挡动漫免费视频| 视频区图区小说| 色婷婷av一区二区三区视频| 美女主播在线视频| av福利片在线| 视频区图区小说| 国产亚洲欧美精品永久| av一本久久久久| 美女xxoo啪啪120秒动态图| 久久青草综合色| 国模一区二区三区四区视频| av不卡在线播放| 亚洲天堂av无毛| a级片在线免费高清观看视频| 久久毛片免费看一区二区三区| 高清毛片免费看| 简卡轻食公司| 久久精品国产亚洲网站| 啦啦啦视频在线资源免费观看| 一级片'在线观看视频| 啦啦啦在线观看免费高清www| 久久久国产一区二区| 色哟哟·www| 国产高清国产精品国产三级| 91精品国产国语对白视频| 丝袜脚勾引网站| 十八禁高潮呻吟视频| 国产淫语在线视频| 人妻 亚洲 视频| 久久精品国产亚洲av涩爱| www.av在线官网国产| videosex国产| 久久热精品热| 天天操日日干夜夜撸| 亚洲精品日韩在线中文字幕| 亚洲一区二区三区欧美精品| 国产男女超爽视频在线观看| 亚洲欧美一区二区三区黑人 | 精品久久久久久电影网| 欧美日韩精品成人综合77777| 午夜av观看不卡| 观看av在线不卡| 久久精品国产自在天天线| 精品国产乱码久久久久久小说| 26uuu在线亚洲综合色| 久久精品国产自在天天线| 日韩不卡一区二区三区视频在线| 亚洲国产av影院在线观看| 极品人妻少妇av视频| 啦啦啦在线观看免费高清www| 国产视频首页在线观看| 国产综合精华液| 精品久久国产蜜桃| 欧美日韩视频高清一区二区三区二| 18禁在线播放成人免费| 欧美日韩国产mv在线观看视频| 亚洲国产色片| 久久精品国产亚洲网站| 老熟女久久久| 在线观看一区二区三区激情| 伊人久久国产一区二区| 中文字幕免费在线视频6| 啦啦啦啦在线视频资源| 国产亚洲一区二区精品| 黑人巨大精品欧美一区二区蜜桃 | 亚洲欧美一区二区三区国产| 香蕉精品网在线| 午夜影院在线不卡| 欧美日本中文国产一区发布| 欧美日韩一区二区视频在线观看视频在线| 22中文网久久字幕| 少妇丰满av| 一级a做视频免费观看| 在线观看免费高清a一片| 女性被躁到高潮视频| 中国国产av一级| 国产高清有码在线观看视频| 夫妻午夜视频| 国产日韩一区二区三区精品不卡 | 春色校园在线视频观看| 卡戴珊不雅视频在线播放| 一级二级三级毛片免费看| 毛片一级片免费看久久久久| 久久国产亚洲av麻豆专区| 欧美日韩国产mv在线观看视频| 国产黄色视频一区二区在线观看| 久久精品国产鲁丝片午夜精品| 亚洲精华国产精华液的使用体验| 伦理电影大哥的女人| 午夜日本视频在线| 3wmmmm亚洲av在线观看| 大码成人一级视频| 国精品久久久久久国模美| 水蜜桃什么品种好| 亚洲精品一区蜜桃| 91成人精品电影| av线在线观看网站| 日本91视频免费播放| 久久精品熟女亚洲av麻豆精品| 免费看不卡的av| 日韩在线高清观看一区二区三区| 国产毛片在线视频| 国产白丝娇喘喷水9色精品| 免费观看av网站的网址| 日韩av不卡免费在线播放| 国产 一区精品| 亚洲av.av天堂| 亚洲内射少妇av| 久久韩国三级中文字幕| 久久久久精品性色| 美女视频免费永久观看网站| 日本91视频免费播放| 免费看不卡的av| 狠狠婷婷综合久久久久久88av| 国产精品久久久久久久电影| 中文字幕人妻丝袜制服| 99热国产这里只有精品6| 久久人人爽人人爽人人片va| 99久久综合免费| 婷婷成人精品国产| 男女无遮挡免费网站观看| 成人免费观看视频高清| 黄片无遮挡物在线观看| 草草在线视频免费看| 又粗又硬又长又爽又黄的视频| 亚洲精品国产色婷婷电影| 亚洲高清免费不卡视频| 欧美精品亚洲一区二区| 久久狼人影院| 国产成人精品在线电影| 欧美亚洲 丝袜 人妻 在线| 成人国产麻豆网| 少妇人妻 视频| 中文字幕最新亚洲高清| 国产亚洲精品久久久com| 特大巨黑吊av在线直播| 91精品一卡2卡3卡4卡| 寂寞人妻少妇视频99o| 国产精品秋霞免费鲁丝片| 美女xxoo啪啪120秒动态图| 精品一区二区三区视频在线| 久久久久久久久久久丰满| 看免费成人av毛片| 国产白丝娇喘喷水9色精品| 色94色欧美一区二区| 欧美最新免费一区二区三区| av网站免费在线观看视频| 三级国产精品欧美在线观看| 天天操日日干夜夜撸| 亚洲精品视频女| 成人手机av| 亚洲国产欧美在线一区| 有码 亚洲区| av电影中文网址| 日韩亚洲欧美综合| 亚洲精品一区蜜桃| 岛国毛片在线播放| 黄片无遮挡物在线观看| 国产片内射在线| 亚洲精品日本国产第一区| 乱人伦中国视频| 不卡视频在线观看欧美| 成人毛片60女人毛片免费| 成人手机av| 久久久久久伊人网av| 精品久久国产蜜桃| 国产免费视频播放在线视频| 少妇熟女欧美另类| 黑人巨大精品欧美一区二区蜜桃 | 久久99热6这里只有精品| 日本91视频免费播放| 久久精品国产亚洲av涩爱| 亚洲精品aⅴ在线观看| 成人国产麻豆网| 中国国产av一级| 我要看黄色一级片免费的| 超碰97精品在线观看| 国产精品国产av在线观看| 国产av精品麻豆| 欧美bdsm另类| 狂野欧美激情性xxxx在线观看| 性色avwww在线观看| 蜜桃久久精品国产亚洲av| 看免费成人av毛片| 超色免费av| 一级片'在线观看视频| 99久久精品国产国产毛片| 久久久久久久大尺度免费视频| 免费看光身美女| 亚洲天堂av无毛| 啦啦啦中文免费视频观看日本| 韩国高清视频一区二区三区| 国产不卡av网站在线观看| 2022亚洲国产成人精品| 七月丁香在线播放| 91精品伊人久久大香线蕉| 国产视频内射| 另类亚洲欧美激情| 国产免费福利视频在线观看| 最近最新中文字幕免费大全7| 免费大片18禁| 亚洲国产精品成人久久小说| 老女人水多毛片| 99视频精品全部免费 在线| 精品一区二区免费观看| 王馨瑶露胸无遮挡在线观看| 欧美 日韩 精品 国产| 亚洲在久久综合| 日本色播在线视频| 久久综合国产亚洲精品| 天堂俺去俺来也www色官网| 18+在线观看网站| 黄片无遮挡物在线观看| 少妇人妻久久综合中文| 能在线免费看毛片的网站| 午夜激情av网站| 午夜影院在线不卡| 伦精品一区二区三区| 亚洲国产精品一区二区三区在线| 中文欧美无线码| 国产一区亚洲一区在线观看| 99九九线精品视频在线观看视频| 美女内射精品一级片tv| 伊人久久国产一区二区| 人体艺术视频欧美日本| 菩萨蛮人人尽说江南好唐韦庄| 好男人视频免费观看在线| 亚洲av在线观看美女高潮| 亚洲人成77777在线视频| 精品一区二区免费观看| √禁漫天堂资源中文www| 精品国产国语对白av| 久久精品国产a三级三级三级| 少妇高潮的动态图| 日本vs欧美在线观看视频| 中文字幕av电影在线播放| 少妇熟女欧美另类| 日本欧美视频一区| 精品国产一区二区三区久久久樱花| av播播在线观看一区| 黑人猛操日本美女一级片| 久久午夜福利片| 久久精品国产a三级三级三级| 国产在线免费精品| 欧美人与性动交α欧美精品济南到 | 不卡视频在线观看欧美| 91午夜精品亚洲一区二区三区| 亚洲内射少妇av| a级毛片黄视频| 大又大粗又爽又黄少妇毛片口| 久久久久久久久久久久大奶| 久久人人爽人人爽人人片va| 国产精品99久久99久久久不卡 | 亚洲少妇的诱惑av| av有码第一页| 国产极品粉嫩免费观看在线 | 97精品久久久久久久久久精品| 免费人成在线观看视频色| 大香蕉久久成人网| 久久97久久精品| 在线观看人妻少妇| 大话2 男鬼变身卡| 少妇的逼好多水| 日本黄色片子视频| .国产精品久久| 亚洲av男天堂| 久久午夜综合久久蜜桃| 超碰97精品在线观看| 看免费成人av毛片| 一区二区av电影网| 性色avwww在线观看| 精品一品国产午夜福利视频| 国产极品天堂在线| 免费大片18禁| 纯流量卡能插随身wifi吗| 国产精品一区二区在线观看99| 亚洲一级一片aⅴ在线观看| 老司机影院成人| 亚洲精品久久成人aⅴ小说 | 国产一区二区在线观看av| 免费观看的影片在线观看| 新久久久久国产一级毛片| 满18在线观看网站| 久久午夜综合久久蜜桃| 欧美丝袜亚洲另类| 国内精品宾馆在线| 黄色一级大片看看| 精品熟女少妇av免费看| 亚洲欧美一区二区三区黑人 | 搡老乐熟女国产| 午夜激情福利司机影院| 大又大粗又爽又黄少妇毛片口| 肉色欧美久久久久久久蜜桃| 母亲3免费完整高清在线观看 | 大香蕉97超碰在线| 两个人免费观看高清视频| 中文欧美无线码| 午夜福利视频精品| 又黄又爽又刺激的免费视频.| 99视频精品全部免费 在线| 精品午夜福利在线看| 曰老女人黄片| 国产成人精品福利久久| 欧美精品国产亚洲| 免费黄网站久久成人精品| a级毛片在线看网站| 9色porny在线观看| 中文字幕亚洲精品专区| 精品国产露脸久久av麻豆| 日韩av免费高清视频| 精品一区二区三区视频在线| 日韩在线高清观看一区二区三区| 精品一区二区免费观看| 久久久久网色| 欧美变态另类bdsm刘玥| 91国产中文字幕| 黄片播放在线免费| 热re99久久精品国产66热6| 国产白丝娇喘喷水9色精品| 日韩精品有码人妻一区| 美女内射精品一级片tv| tube8黄色片| 日韩av不卡免费在线播放| 青春草亚洲视频在线观看| 麻豆乱淫一区二区| 国产在线视频一区二区| 亚洲精品日韩在线中文字幕| 亚洲色图综合在线观看| 免费黄频网站在线观看国产| 天天躁夜夜躁狠狠久久av| 人人澡人人妻人| 国产在线一区二区三区精| 日本-黄色视频高清免费观看| 国产亚洲最大av| 亚洲av综合色区一区| 国产白丝娇喘喷水9色精品| 国产精品秋霞免费鲁丝片| 一本久久精品| 两个人免费观看高清视频| 九九久久精品国产亚洲av麻豆| 99久国产av精品国产电影| 久久久欧美国产精品| 国产欧美日韩综合在线一区二区| 九色亚洲精品在线播放| 亚洲在久久综合| 18禁裸乳无遮挡动漫免费视频| 丰满少妇做爰视频| 国产片特级美女逼逼视频| 99re6热这里在线精品视频| 亚洲国产av影院在线观看| 午夜91福利影院| 97在线人人人人妻| 亚洲精品久久久久久婷婷小说| 久久97久久精品| 欧美激情 高清一区二区三区| 国产精品偷伦视频观看了| 日本爱情动作片www.在线观看| 国产爽快片一区二区三区| 99精国产麻豆久久婷婷| 国产精品三级大全| 免费日韩欧美在线观看| 亚洲中文av在线| 日韩三级伦理在线观看| 狂野欧美激情性bbbbbb| 国产欧美亚洲国产| 成人国产av品久久久| 欧美性感艳星| av在线app专区| 汤姆久久久久久久影院中文字幕| 亚洲高清免费不卡视频| 久久av网站| av又黄又爽大尺度在线免费看| 国产精品一二三区在线看| 九九在线视频观看精品| 成人18禁高潮啪啪吃奶动态图 | 午夜福利,免费看| 国产精品国产三级国产av玫瑰| 亚洲精品国产av蜜桃| 91久久精品电影网| 中文字幕最新亚洲高清| 美女视频免费永久观看网站| 精品熟女少妇av免费看| 18禁在线播放成人免费| av线在线观看网站| 天天操日日干夜夜撸| 夫妻午夜视频| 亚洲精品乱码久久久v下载方式| 男的添女的下面高潮视频| 人人妻人人添人人爽欧美一区卜| 国产亚洲精品第一综合不卡 | 伦理电影大哥的女人| 高清av免费在线| 久久精品国产a三级三级三级| 免费高清在线观看视频在线观看| av国产久精品久网站免费入址| 精品人妻在线不人妻| 久久久久精品久久久久真实原创| 热99国产精品久久久久久7| 日韩精品免费视频一区二区三区 | a级毛色黄片| 国产av精品麻豆| 成人18禁高潮啪啪吃奶动态图 | 欧美老熟妇乱子伦牲交| 日本wwww免费看| 蜜桃国产av成人99| 一级,二级,三级黄色视频| 一区二区三区乱码不卡18| 看免费成人av毛片| av天堂久久9| 亚洲av成人精品一区久久| 一区二区av电影网| 欧美亚洲日本最大视频资源| 亚洲精品自拍成人| 青青草视频在线视频观看| 日本91视频免费播放| av播播在线观看一区| 久久国内精品自在自线图片| 久久久国产精品麻豆| 丰满迷人的少妇在线观看| 国产亚洲精品第一综合不卡 | 十八禁网站网址无遮挡| 免费播放大片免费观看视频在线观看| 亚洲国产精品成人久久小说| 免费av不卡在线播放| 午夜免费鲁丝| 中文字幕久久专区| 日本wwww免费看| 亚洲精品456在线播放app| 亚洲激情五月婷婷啪啪| 午夜福利影视在线免费观看| 五月开心婷婷网| 久久ye,这里只有精品| 男女无遮挡免费网站观看| 少妇人妻久久综合中文| 久热久热在线精品观看| 国产极品天堂在线| 亚洲人与动物交配视频| 亚洲第一区二区三区不卡| 一二三四中文在线观看免费高清| 免费看不卡的av| 一本—道久久a久久精品蜜桃钙片| 在现免费观看毛片| 成人二区视频| 高清黄色对白视频在线免费看| 丝袜美足系列| 又黄又爽又刺激的免费视频.| .国产精品久久| 久久综合国产亚洲精品| 九九爱精品视频在线观看| 久久人妻熟女aⅴ| 91久久精品国产一区二区成人| 亚洲欧美成人精品一区二区| 午夜久久久在线观看| 国产亚洲av片在线观看秒播厂| 3wmmmm亚洲av在线观看| 国产视频内射| 精品人妻偷拍中文字幕| 国产亚洲精品久久久com| 老司机影院毛片| av卡一久久| 亚洲性久久影院| xxx大片免费视频| 久久久久久久久久久丰满| 极品人妻少妇av视频| 18禁观看日本| 又大又黄又爽视频免费| 熟妇人妻不卡中文字幕| 亚洲av成人精品一二三区| 丝瓜视频免费看黄片| 人人妻人人澡人人看| 亚洲精品乱码久久久v下载方式| 久久久久精品久久久久真实原创| 中文字幕免费在线视频6| 看非洲黑人一级黄片| 欧美日韩亚洲高清精品| 少妇丰满av| 午夜精品国产一区二区电影| 欧美bdsm另类| 亚洲美女搞黄在线观看| 国产伦精品一区二区三区视频9| 高清毛片免费看| 中国三级夫妇交换| 久久精品熟女亚洲av麻豆精品| 欧美另类一区| 免费看不卡的av| 最近中文字幕高清免费大全6| 99re6热这里在线精品视频| 欧美日韩视频高清一区二区三区二| 另类亚洲欧美激情| 少妇的逼好多水| 热99久久久久精品小说推荐| 18禁在线播放成人免费| 国产探花极品一区二区| 亚洲精品av麻豆狂野| 免费av不卡在线播放| 99久久精品国产国产毛片| 亚洲精品aⅴ在线观看| 免费黄色在线免费观看| 黄片无遮挡物在线观看| 午夜精品国产一区二区电影| 极品人妻少妇av视频|