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

    TMS:一種新的海量數據多維選擇Top-k查詢算法

    2017-04-20 10:46:02劉顯敏李建中
    計算機研究與發(fā)展 2017年3期
    關鍵詞:元組分片列表

    劉顯敏 李建中 高 宏

    (哈爾濱工業(yè)大學計算機科學與技術學院 哈爾濱 150001) (xxhan1981@163.com)

    TMS:一種新的海量數據多維選擇Top-k查詢算法

    劉顯敏 李建中 高 宏

    (哈爾濱工業(yè)大學計算機科學與技術學院 哈爾濱 150001) (xxhan1981@163.com)

    在許多應用中,Top-k是一種十分重要的查詢類型,它在潛在的巨大數據空間中返回用戶感興趣的少量數據.Top-k查詢通常具有指定的多維選擇條件.分析發(fā)現:現有算法無法有效處理海量數據的多維選擇Top-k查詢.提出了一個基于有序列表的TMS(top-kwith multi-dimensional selection)算法,有效計算海量數據上的具有多維選擇的Top-k結果.TMS算法利用層次化結構的選擇屬性網格對原數據表執(zhí)行水平劃分,每一個分片的元組以面向列的模式存儲,并且度量屬性的列表根據其屬性值降序排列.給定多維選擇條件,TMS算法利用選擇屬性網格確定相關網格單元,有效減少需要讀取的元組數量,提出雙排序方法執(zhí)行多維選擇的漸進評價,并提出有效剪切操作來剪切不滿足多維選擇條件和分數要求的候選元組.實驗結果表明:TMS算法性能優(yōu)于現有算法.

    TMS算法;有序列表;選擇屬性網格;漸進選擇評價;剪切操作

    在許多應用中,Top-k是一種十分重要的查詢類型,它在潛在的巨大數據空間中返回用戶感興趣的少量數據[1-2].通常,Top-k查詢指定2個組件來反映用戶的查詢興趣:評分函數F和多維選擇P.根據定義的評分函數F,Top-k查詢從滿足P的數據空間中返回k個分數最大的元組.

    由于在實際應用的重要性,Top-k查詢已經獲得研究人員的廣泛關注[1].但是,現有的大多數工作都忽略了Top-k查詢的多維選擇,僅僅考慮有效計算全部元組的Top-k結果.當然,研究人員也提出了幾種算法來處理多維選擇Top-k查詢.Bruno等人[3]將Top-kselection查詢映射為范圍查詢,但是該方法實際上是計算多維空間上的k最近鄰查詢,不同于本文討論的多維選擇Top-k查詢.Stupar等人[4]考慮處理基于集合選擇的Top-k查詢,即預先給定需要的元組ID集合,然后計算滿足條件的查詢結果.該方法的要求過于特殊,而且只考慮有一個度量屬性的情況.Dong等人[5]提出ranking cube的方法來處理多維選擇Top-k查詢,該方法將data cube的思想和排序操作結合在一起來有效返回查詢結果,但是該方法假設多維選擇總是涉及到分類屬性,并且在實際應用中構建和維護ranking cube的代價過于昂貴.綜上所述,現有算法在海量數據上無法有效計算一般情況的多維選擇Top-k查詢.

    本文提出一個新的基于有序列表的算法TMS(top-kwith multi-dimensional selection)來有效處理海量數據多維選擇Top-k查詢.該算法利用層次結構的選擇屬性網格對數據表進行水平劃分,并且存儲為面向列模式.TMS算法對度量屬性對應的度量列表分片按照其屬性值降序排列,保持選擇屬性對應的選擇列表分片的原有順序.給定多維選擇,TMS算法根據網格結構快速確定相關的網格信息.在讀取度量列表分片的元組時,本文提出雙排序方法漸進地執(zhí)行多維選擇評價,從而減少了查詢處理涉及到的IO費用.本文提出分數剪切操作和多維選擇剪切操作,盡早丟棄那些不滿足分數要求或者多維選擇條件的候選元組.本文提出分數剪切的數學分析,來獲得優(yōu)化的剪切效果.本文的實驗結果表明,和現有方法相比,TMS算法可以獲得較大的性能優(yōu)勢.

    本文的主要貢獻有4點:

    1) 提出一個新的基于有序列表的TMS算法,該算法利用選擇屬性網格來有效處理海量數據上多維選擇Top-k查詢;

    2) 提出基于雙排序的方法來有效執(zhí)行漸進選擇評價;

    3) 提出有效的分數剪切和選擇剪切操作,提出分數剪切操作的理論分析來獲得優(yōu)化剪切效果;

    4) 實驗結果表明:TMS算法與現有方法相比具有較大的性能優(yōu)勢.

    1 預備知識

    1.1 問題定義

    多維選擇Top-k查詢:給定表T、多維選擇P和評分函數F,多維選擇Top-k查詢在TP(T中滿足P的元組集合)中返回一個k子集R,使得?t1∈R,?t2∈TP-R,F(t1)≥F(t2).

    典型的多維選擇Top-k查詢SQL語句如下所示:

    select * fromTwherel1≤S1≤u1andl2≤S2≤u2and… andld≤Sd≤udorder byw1×A1+w2×A2+…+wm×Amlimitk.

    其中,lj和uj分別表示P在選擇屬性Sj指定的下界和上界.本文經常用到的符號如表1所示:

    Table 1 The Symbol Notation

    我們給出本文用到的位置索引的定義.

    定義1. 給定表T,元組t∈T的位置索引是a,如果t是T的第a個元組.

    我們用T(a)來表示表T中位置索引為a的元組,用T[a,…,b]表示位置索引大于等于a且小于等于b的元組集合,用T[a,…,b].Ai表示T[a,…,b]中元組的屬性Ai的集合.

    1.2 傳統(tǒng)的有序列表Top-k查詢算法

    自從Fagin等人[6]的先驅性工作,利用有序列表來處理Top-k查詢已經成為研究人員自然的選擇[7-10].我們先介紹在不考慮多維選擇情況下的有序列表Top-k查詢算法.由于其較好的性能,本文采用LARA算法[7]為例來討論有序列表Top-k算法.

    由于LARA算法沒有考慮多維選擇的問題,下面我們提供2種方法來對其進行擴展.

    1) 類樹索引.一種直觀的想法是以元組位置索引為鍵值在選擇屬性上構建類樹索引.在LARA算法執(zhí)行時,對于當前一輪獲得的度量列文件ALi元組(pi,ai),根據類樹索引和pi的值來判斷元組T(pi)是否符合P,如果符合,那么對于該元組的處理類似于傳統(tǒng)LARA算法,否則直接丟棄該元組,然后繼續(xù)讀取該列文件,直到獲得一個滿足條件的元組或文件遍歷完畢.類樹索引的問題在于,由于度量列文件ALi是根據屬性值降序排列的,每次索引判斷可能引起一個磁盤隨機seek操作,在海量數據上執(zhí)行時,這必然引起較多的大范圍隨機IO操作,嚴重影響算法的效率.因此,本文不再討論這種方法.

    下面我們擴展現有的LARA算法來處理多維選擇.假設選擇屬性也存儲為列文件形式,S1,S2,…,SD存儲為選擇列表集合{SL1,SL2,…,SLD},每個選擇列表SLj(1≤j≤D)的模式為SLj(PI,Sj),其中Sj表示元組在對應選擇屬性的值,注意,這里的SLj的元組根據Sj的值升序排列,并在SLj.Sj上構建B+樹.

    2) 批量方法LBE(LARA with batch evalua-tion).該方法采用批量方法來處理多維選擇.對讀取度量列表之前,LBE算法先利用構建的B+樹對SL1,SL2,…,SLd依次執(zhí)行范圍掃描操作,來獲得滿足多維選擇的位向量B.?t=T(pi),如果t滿足P,那么位向量B的第pi位置為1,否則位向量B的第pi位置為0.接下來,LBE算法對度量列表執(zhí)行元組讀取操作,對于當前獲得的ALi元組(pi,ai),LBE算法利用B的第pi位判斷該元組是否符合P,如果滿足條件則對該元組的處理類似于LARA算法,否則直接丟棄該元組,繼續(xù)讀取該度量列表,直到獲得一個滿足條件的元組.

    2 有序列表Top-k算法的性能分析

    為方便分析,我們假設表T的屬性均勻獨立分布.

    在海量數據上,表T維護大量元組,并且用戶提交的查詢通常只涉及一小部分元組,n的值較大而SLT的值較小.根據以上的描述,LBE算法存在3個問題:

    1) LBE算法需要從SLj(1≤j≤d)中讀取n×SLTj個元組;

    3) LBE算法需要維護一個n-bit的位向量,在海量數據上該位向量需要占據較多的內存空間.針對存在的問題,我們提出新的TMS算法有效處理海量數據多維選擇Top-k查詢.

    3 TMS算法

    3.1 算法概述

    多維選擇P實際給出一個查詢子空間,如果在讀取度量列表ALi(1≤i≤m)時,算法可以快速定位其對應行元組落入該子空間的元組,那么算法就可以較好地處理多維選擇Top-k查詢.本文采用選擇屬性網格來分布表T的元組,將對應網格的元組維護為列存儲形式.基于選擇屬性網格的劃分過程其實是把表T的Ai對應的度量列表ALi(1≤i≤m)劃分為度量列表分片.給定多維選擇條件P,算法可以根據網格結構來確定相關分片,也就確定了相關的度量屬性列表分片.通常,與P相關的度量列表分片集合只是初始度量列表的一部分,從而有效減少讀取不滿足多維選擇的元組的費用.本文還提出基于雙排序的漸進多維選擇評價方法來判斷讀取的度量屬性是否符合P.為進一步減少雙排序方法中需要評價的度量屬性值的數量,本文提出有效的多維選擇剪切操作和分數剪切操作.下面,我們分別介紹TMS算法的基本執(zhí)行過程.

    3.2 選擇屬性網格

    圖1給出的是D=2和MXH=2的SAL最底層劃分情況,葉節(jié)點的編號表示其在兄弟節(jié)點中的次序.令TSAL(tncode)表示TSAL中編號tncode的節(jié)點.例如,具有編號“0100”的葉節(jié)點是編號“01”的節(jié)點的第1個孩子,而編號為“01”的節(jié)點是根結點的第2個孩子.

    Fig. 1 The illustration of cell partitioning in SAL圖1 選擇屬性網格底層劃分

    給定樹結構TSAL,TMS算法順序掃描表T,將表T的元組劃分為(2D)MXH組分片,每一組分片維護著其選擇屬性落入對應子空間的元組集合.注意,TMS算法只將元組存儲到TSAL的葉節(jié)點對應的分片,因此,TMS算法只維護表T的水平劃分的單個副本.?t∈T,TMS算法從根節(jié)點TNrt開始,根據元組t的選擇屬性值來決定該元組應當落入哪個子節(jié)點的子空間,令該元組落入根節(jié)點的第(b1b2…bD)2+1個子節(jié)點,其位bj(1≤j≤D)的取值如下定義:

    該過程自TSAL的根節(jié)點開始執(zhí)行,直到找到葉節(jié)點TNlf,元組t輸出到TNlf對應的分片.對于每一個元組,TMS算法只需要進行MXH次判斷就可以確定應當放入的分片.我們將葉節(jié)點對應的分片存儲為面向列的格式,其中,度量列表分片和選擇列表分片的模式分別為(PI,Ai,PIptn)和(PI,Sj).這里,PI表示對應元組在表T的位置索引,PIptn表示元組在對度量列表分片中的元組排序前的位置索引.

    分片劃分完畢后,TMS算法對每個葉節(jié)點對應的度量列表分片執(zhí)行排序操作,使得度量列表分片的元組根據Ai降序排列,但對選擇列表分片不排序.

    3.3 查詢處理

    3.3.1 確定相關子空間

    在執(zhí)行查詢處理時,TMS算法根據多維選擇P來確定相關的子空間.對于P中任何未出現的選擇屬性Sj,我們通過在P中添加選擇條件minSj≤Sj≤maxSj來擴展.這里,minSj和maxSj分別表示選擇屬性Sj的最小值和最大值.

    給定多維選擇P,TMS算法對TSAL執(zhí)行層次遍歷來確定不和P相離的葉節(jié)點.對于獲得的葉節(jié)點TNlf,其處理方式如下:1)TNlf.hcube和P部分相交,TNlf插入到數組AP;2)TNlf.hcube被P包含,TNlf插入到數組AF.這里,AP維護其子空間和P部分相交的葉節(jié)點集合,AF維護其子空間被P包含的葉節(jié)點集合.

    給定AP,令NAP表示AP的元素數量,TMS算法獲得d個具有NAP個元素的數組PS1,PS2,…,PSd,其中,PSj(1≤j≤d)維護和Sj對應的相關選擇列表分片,還獲得m個具有NAP個元素的數組PR1,PR2,…,PRm,其中,PRi(1≤i≤m)維護和Ai對應的相關有序度量列表分片.

    給定AF,令NAF表示AF的元素數量,TMS算法獲得m個具有NAF個元素的數組FR1,FR2,…,FRm,其中,FRi(1≤i≤m)維護和Ai對應的相關有序度量列表分片.

    3.3.2 多維選擇評價

    在執(zhí)行過程中,TMS算法需要從PRi和FRi中按照降序順序讀取滿足條件的度量屬性Ai的值.在讀取度量列表分片時,TMS算法漸進地計算當前讀取的元組的多維選擇評價結果.?(pi,ai,piptn)∈PRi[h],T(pi).Sj的值出現在PSj[h](1≤j≤d)的第piptn個元組中,TMS算法需要讀取PS1[h],PS2[h],…,PSd[h]的第piptn個元組來獲得T(pi)的選擇屬性S1,S2,…,Sd的值,可以判斷T(pi)是否滿足P.如果對獲得的每個來自PRi[h]的元組都根據其piptn的值來跳轉到對應選擇列表分片的指定位置進行多維選擇評價,必然影響查詢處理的效率.本文提出一個基于雙排序的漸進評價方法,盡量采用磁盤順序讀取操作評價來自PRi的元組是否滿足P.

    雙排序方法是:在每輪的元組讀取操作中,TMS算法用大小為NAP的最大堆結構PMHi來讀取PRi中當前最大的度量屬性Ai的值,并且在內存中維護一個緩沖區(qū)PBi,令其大小為SZi.TMS算法分別讀取PRi的每個分片的一個元組來填充PMHi,并不斷讀取PMHi的根節(jié)點元組來填充PBi.在填充PBi時,我們并不對來自PRi的元組執(zhí)行多維選擇評價,而是填充操作完成后批量地對PBi的元組執(zhí)行多維選擇評價.

    假設PMHi的當前根節(jié)點元組t(PI,Ai,PIptn)∈PRi[h],將元組t填充到PBi時,執(zhí)行t.PIptn+=OA[h].填充完畢后,TMS算法根據屬性PIptn對PBi執(zhí)行升序排序操作.根據定理1,排序后PBi中來自PRi[h]的元組連續(xù)存儲,而這些元組對應的選擇屬性順序存儲在選擇屬性列表分片PSj[h](1≤j≤d).

    定理1. 雙排序方法的第1次排序后,PBi中來自PRi[h] (1≤h≤NAP)的元組連續(xù)存儲,且這些元組對應的選擇屬性Sj(1≤j≤d)順序存儲在選擇列表分片PSj[h].

    證明. 給定1≤h1

    很明顯,t1.PIptn

    證畢.

    在第1次排序后,令PBi[bh,…,eh]表示PBi中來自PRi[h]的元組.在評價多維選擇時,TMS算法按照P[S1],P[S2],…,P[Sd]的順序依次對PBi的元組執(zhí)行多維選擇評價,盡量利用對單個文件的順序掃描來提高磁盤處理效率.在評價P[Sj]時,TMS算法從頭開始掃描PBi中的元組,如果bh≤eh,TMS算法根據PBi[bh,…,eh]的PIptn屬性的值,選擇性地獲得選擇列表分片PSj[h]的第PIptn-OA[h]個元組來評價PBi[bh,…,eh]的對應元組的P[Sj]評價結果.在完成對P[S1],P[S2],…,P[Sd]的評價后,TMS算法根據Ai的值對PBi執(zhí)行降序排序,我們就完成對PBi的元組的多維選擇評價.

    為返回分片集合FRi當前最大的屬性Ai的值,TMS算法維護大小為NAF的最大堆結構FMHi.初始時,TMS算法讀取FRi的每個分片的一個元組來填充FMHi.

    在讀取下一個滿足條件的度量屬性Ai的值時,TMS算法順序讀取PBi直到獲得一個滿足條件的元組t1,比較FMHi的當前根節(jié)點元組t2(假設t2∈FRi[h]),如果t1.Ai≤t2.Ai,TMS算法就獲得t2作為當前輪的度量屬性Ai的值,并讀取FRi[h]的下一個元組填充FMHi,否則TMS算法就獲得t1作為當前輪的度量屬性Ai的值.如果PBi的元組被讀取完畢,TMS算法重新執(zhí)行填充操作.元組讀取操作不斷執(zhí)行,直到返回查詢結果或者相關度量列表分片的元組被遍歷完畢.

    下面,我們討論如何確定緩沖區(qū)PBi的大小SZi的優(yōu)化值.根據系統(tǒng)的性能和日常負載,系統(tǒng)首先設置緩沖區(qū)大小的上限MXSIZE,要求SZi≤MXSIZE.

    下面,我們估計PDi的值,假設表T的屬性均勻獨立分布,數值選擇屬性的值域是[0, 1].

    令DPNOP表示沒有多維選擇情況下TMS算法的掃描深度,令NFh表示分片FRi[h]的元組數量,SELh表示分片PRi[h]對應的子空間和P相交的空間比例,TMS算法在FRi上的掃描深度FDi計算如下:

    在其執(zhí)行過程,TMS算法不需要讀取選擇列表分片集合PSj(1≤j≤d)的所有元組,只是選擇性地讀取指定位置的選擇屬性值來給出度量列表的候選元組的多維選擇評價結果.很明顯,需要執(zhí)行多維選擇評價和維護的度量列表候選元組的數量直接影響著TMS算法的性能.下面,我們在算法中提出剪切操作來有效減少需要處理的元組數量.

    3.4 剪切操作

    3.4.1 多維選擇剪切

    給定相關的度量列表分片集合PRi和FRi(1≤i≤m).?t1∈FRi[h],t1肯定滿足多維選擇P,但是?t2∈PRi[h],t2可能不滿足P.這部分提出多維選擇剪切策略來盡早丟棄那些不滿足P的度量列表分片的候選元組.

    考慮度量列表分片PRi[h](1≤i≤m),令其對應的選擇屬性子空間和多維選擇P部分相交的子空間是ISTCh,那么多維選擇剪切規(guī)則定義如下:

    ?t(PI,Ai,PIptn)∈PRi[h],如果?j(1≤j≤d),PSj[h](PIptn).Sj不在區(qū)間ISTCh[Sj]內,那么t不滿足多維選擇,其中PSj[h](PIptn).Sj表示文件PSj[h]中位置索引為PIptn的元組的Sj屬性.

    本文限制SAL的最大層次MXH,葉節(jié)點維護的選擇屬性子空間無法進一步劃分,多維選擇剪切方法就是在最底層的選擇屬性子空間中丟棄那些不滿足條件的度量列表候選元組.本文采用指數間距前向bloom filter表和指數間距后向bloom filter表來有效實現多維選擇剪切.

    定義2. 給定選擇列表分片PSj[h]及其對應的選擇屬性子空間HCh,EFBFTj,h和EBBFTj,h分別表示PSj[h]上的指數間距前向和后向bloom filter表,如果它們滿足條件:1)|EFBFTj,h|=|EBBFTj,h|=lb(HCh[Sj].upp-HCh[Sj].low+1); 2)EFBFTj,h(b)表示在PSj[h].Sj∈[HCh[Sj].low,HCh[Sj].low+2b)的PSj[h]元組上利用屬性PIptn構建的bloom filter,EBBFTj,h(b)表示在PSj[h].Sj∈(HCh[Sj].upp-2b,HCh[Sj].upp)的PSj[h]元組上利用屬性PIptn構建的bloom filter.

    我們可以分別將PSj[h]的元組按照選擇屬性Sj的值升序和降序排列,從而有效構建EFBFTj,h和EBBFTj,h.

    已知,一個D維子空間SDS有2D個頂點,令該子空間的左下方和右上方的坐標分別是(bl1,bl2,…,blD)和(tr1,tr2,…,trD),給定子空間SDS的某一坐標為(cod1,cod2,…,codD)的頂點,其編號(b1b2…bD)定義如下:

    令SDS(b1b2…bD)表示子空間SDS中具有編號為(b1b2…bD)的頂點,令SDS(b1b2…bD)[j]表示該頂點第j個坐標的值.

    Fig. 2 The illustration of selection pruning圖2 選擇剪切操作示例圖

    3.4.2 分數剪切

    分數剪切操作利用評分函數單調性來剪切候選元組,從而減少多維選擇評價和元組維護的費用.

    先考慮一個簡單模型來討論分數剪切,即:查詢不涉及多維選擇,表T的元組數量是n2,并且表T的屬性均勻獨立分布.其中,我們?yōu)槎攘繉傩訟i(1≤i≤m)構建有序列表ALi.當執(zhí)行Top-k查詢時,我們對AL1,AL2,…,ALm執(zhí)行round-robin掃描操作,且掃描深度是sdend=dp(n2,m,k).如圖3所示,分數剪切操作需要確定存在深度exdep(≤sdend)和分數剪切深度spdep,使得ALi[1,…,exdep]有k個候選元組(pii,1,ai,1,ptni,1),(pii,2,ai,2,ptni,2),…,(pii,k,ai,k,ptni,k)滿足存在條件:所有1≤k′≤k和1≤i′≤m(i′≠i),pii,k′∈πPI(ALi′[1,…,spdep]).

    Fig. 3 The illustration of score pruning圖3 分數剪切示例圖

    給定exdep和spdep,?t(PI,Ai,PIptn)∈ALi[(exdep+1),…,sdend],如果對所有1≤i′≤m(i′≠i),t.PI?πPI(ALi′[1,…,spdep]),算法不需要維護候選元組t.因為,根據評分函數的單調性,T(t.PI)的分數肯定低于在ALi中滿足存在條件的那k個元組的分數.

    根據對簡單模型的討論,下面介紹如何在相關的度量列表分片集合上執(zhí)行分數剪切.這里,我們同樣假設度量屬性A1,A2,…,Am均勻獨立分布,需要注意的是,均勻獨立分布假設只是為了計算方便,而并不影響TMS算法的執(zhí)行.

    已知,在不考慮多維選擇時,TMS算法的優(yōu)化分數剪切深度是spdepopt,我們需要計算在相關的度量列表分片上的分數剪切深度,換句話說,要獲得spdepopt個滿足多維選擇的Ai屬性的值需要從PRi和FRi分別讀取的元組數量.

    在對度量列表分片的掃描過程中,?t1(PI,Ai,PIptn)∈PRi[h],如果所有1≤i′≤m并且i′≠i,t1.PI∈πPI(PRi′[h][1,…,pnph]),我們稱t1滿足存在條件,?t2∈FRi[h],如果所有1≤i′≤m并且i′≠i,t2.PI∈πPI(FRi′[h][1,…,pnfh]),我們稱t2滿足存在條件.

    令獲得k個滿足條件的元組時PRi[h1](1≤h1≤NAP)和FRi[h2](1≤h2≤NAF)掃描深度分別為edph1和edfh2,pnph1和pnfh2分別表示根據以上方法計算的PRi[h1]和FRi[h2]上的分數剪切深度,分數剪切規(guī)則定義如下:

    給定度量列表分片集合PRi和FRi(1≤i≤m):1)?t1∈PRi[h1][edph1+1,…,NPh1],如果對于所有1≤i′≤m并且i′≠i,t1.PI?πPI(PRi′[h1][1,…,pnph1]),那么t1可以被剪切; 2)?t2∈FRi[h2][edfh2+1,…,NFh2],如果對于所有1≤i′≤m并且i′≠i,t2.PI?πPI(FRi′[h2][1,…,pnfh2]),那么t2可以被剪切.

    本文采用指數間距bloom filter表來有效實現分數剪切.

    定義3. 給定具有n個元素的度量列表Ri(PI,Ai,PIptn),EGBFTi是Ri上的指數間距bloom filter表,如果它滿足條件:1)|EGBFTi|=lbn;2)EGBFTi(b)表示在Ri[1,…,2b]的PI屬性上構建的bloom filter(1≤b≤lbn).

    3.5 處理高維選擇屬性

    本節(jié)介紹TMS算法如何處理高維選擇屬性的情況.

    給定選擇屬性S1,S2,…,SD,選擇屬性網格SAL的第MXH層的子空間數量是(2D)MXH.如果D的值較大,TMS算法將生成大量的子空間,這也將導致文件系統(tǒng)的較大的維護費用,此外,給定同樣的多維選擇P,較大的D值也將使得TMS算法涉及到較多的相關分片.例如,給定D=12,MXH=3,TMS算法需要維護68 719 476 736個子空間.

    在深入研究高維選擇屬性之前,我們先給出2個觀察[5]:

    觀察1. 雖然選擇屬性的維度可能較大,但是提交的查詢通常只涉及到較小數量的選擇屬性.

    觀察2. 在實際應用中,選擇屬性的查詢頻率通常服從Zipfian分布.

    為處理高維選擇屬性,我們限制用來構建單個選擇屬性網格的選擇屬性數量,將S1,S2,…,SD劃分成大小為GS的組,即G1={S1,S2,…,SGS},G2={SGS+1,SGS+2,…,SGS+GS},…,GDGS={SD-GS+1,SD-GS+2,…,SD},并且為每一個組構建選擇屬性網格.在這種情況下,TMS算法將維護數據表T的個副本,但是有效減少了需要維護的總的子空間數量.例如給定GS=3,MXH=3以及D=12,TMS算法只需要維護4個組,并且每個組只需要生成512個子空間.

    根據觀察2,如果磁盤空間大小有限,我們甚至可以不需要為每個組都構建選擇屬性網格,而是只選擇具有較高查詢頻率的幾個組.這樣,我們不但可以有效減少需要的磁盤空間,而且還可以滿足絕大多數的查詢需求.例如給定GS=3,z=2以及D=12,只為第1個組構建選擇屬性網格也可以覆蓋87%的查詢.

    給定多維選擇P,TMS算法首先計算P和G1,G2,…,GDGS的交.不失一般性,令G1是具有和P最多的公共選擇屬性的組.例如給定G1={S1,S2,S3},G2={S4,S5,S6},G3={S7,S8,S9}以及G4={S10,S11,S12},P={(l1≤S1≤u1) and (l2≤S2≤u2) and (l4≤S4≤u4)},TMS算法將在G1構建的選擇屬性網格上執(zhí)行.因為P中不包括S3,TMS算法利用{(l1≤S1≤u1)且(l2≤S2≤u2)且(minS3≤S3≤maxS3)}來確定相關子空間集合.當然,此時所有的相關子空間都是和P部分相交.接著,采用如3.3節(jié)和3.4節(jié)的方法來計算Top-k結果.

    4 性能評價

    4.1 實驗設置

    本節(jié)評價算法的性能.我們利用Java語言實現TMS算法,jdk版本為jdk-7u21-windows-x64, 實驗在LENOVO ThinkCentre工作站上執(zhí)行(Intel?CoreTMi7-3770 CPU @ 3.40 GHz (8 CPUs)+32 GB memory+64bit Windows 7).實驗所用的數據集合存儲于Seagate Expansion STBV3000300 (3 TB).實驗比較TMS算法、LBE和ranking cube的性能.實驗不比較文獻[3-4]中的方法,其原因在于,文獻[3]中的方法實際上是計算多維空間上的k最近鄰查詢結果,文獻[4]中的方法則只考慮只有一個數值屬性的查詢,并且要求預先給定需要的元組ID集合,從而文獻[3-4]的方法從本質上不同于本文考慮的問題.對于TMS算法,考慮到文件系統(tǒng)的負載,選擇屬性網格的最大層次設置為3.

    我們從不同方面評價TMS算法的性能:元組數量n、結果數量k、涉及到的選擇屬性數量d、涉及到的評價屬性數量m、選擇度s和相關系數p.實驗參數設置如表2所示:

    Table 2 Parameter Settings

    實驗用來評價具有數值選擇屬性的表的Top-k查詢如下:

    select * fromTwherel1≤S1≤u1andl2≤

    S2≤u2and … andld≤Sd≤udorder byA1+

    A2+…+Amlimitk.

    其中,lj和uj分別表示多維選擇在屬性Sj上的上界和下界值.

    類似地,實驗用來評價具有類別選擇屬性的表的 Top-k查詢如下:

    select * fromTwhereS1=a1andS2=a2

    and … andSd=adorder byA1+A2+…+

    Amlimitk.

    其中,aj是屬性Sj的特定值.當然,在類別選擇屬性上,選擇屬性網格結構不需要劃分整個的數據空間,而是根據不同的屬性組合來對數據表執(zhí)行水平劃分.

    4.2 實驗1:結果數量的效果

    給定n=10×108,s=0.001,m=3,d=3,p=0,實驗1評價不同結果數量下TMS算法的性能.如圖4(a)所示,TMS算法比LBE算法快2.79倍.隨著需要返回更多的結果數量時,LBE算法的執(zhí)行時間增長較快,從48.956 s增長到68.598 s.相對而言,TMS算法的執(zhí)行時間增長幅度較小,這是由于選擇評價的費用占據了總的執(zhí)行費用的大部分.如圖4(b)所示,LBE算法讀取的元組數量比TMS算法多71.68倍.這里,讀取的元組數量是度量列表中讀取的元組數量和選擇列表中讀取的元組數量之和.剪切操作的效果如圖4(c)和圖4(d)所示,其中,選擇剪切比是被選擇剪切操作丟棄的元組數量和讀取的所有元組數量的比值,分數剪切比是被分數剪切操作丟棄的元組數量和未被選擇剪切操作丟棄的元組數量的比值.由于選擇屬性和度量屬性的獨立分布,這里的分數剪切效果可以反應真實的分數剪切效果.如圖4(c)和圖4(d)所示,選擇剪切操作可以丟棄72%的元組,分數剪切操作可以丟棄70%~77%元組.圖4(d)中虛線表示理論的分數剪切比例.分數剪切的剪切比隨著結果數量的增加而降低,這符合理論分析的結果.

    Fig. 4 The effect of result size圖4 結果數量的效果

    4.3 實驗2:元組數量的效果

    給定k=10,s=0.001,m=3,d=3,p=0,實驗2評價不同元組數量下的TMS算法性能.如圖5(a)所示,TMS算法比LBE算法快3.37倍.如圖5(b)所示,LBE算法的讀取的元組數量比TMS算法多80.99倍.圖5(c)給出選擇剪切比例基本保持在72%;圖5(d)所示的分數剪切比例表示,分數剪切比在65%~78%之間.我們可以看到,隨著元組數量的增加,分數剪切比逐漸增大,這也符合理論分析的結果.

    4.4 實驗3:選擇屬性數量的效果

    給定n=10×108,k=10,s=0.001,m=3,p=0,實驗3評價不同選擇屬性數量下的TMS算法性能.實驗3假設多維選擇在涉及到的選擇屬性上具有相等的選擇度.在確定相關網格單元時,如果多維選擇中的屬性數量少于構建SAL使用的屬性數量(例如多維選擇不包括Sj屬性,算法在多維選擇條件上增加minSj≤Sj≤maxSj),否則,算法直接忽略選擇條件上多余的選擇屬性.需要注意的是,這只是在確定相關網格單元,不影響算法的正確執(zhí)行.如圖6(a)所示,TMS算法比LBE算法快1.72倍.我們看到TMS算法的執(zhí)行時間隨著選擇屬性增大而迅速增長,給定選擇度,更多的選擇屬性使得每個選擇屬性上的選擇度增大,從而增加了涉及到的網格單元的數量.如圖6(b)所示,LBE算法讀取的元組數量比TMS算法多97.89倍.如圖6(c)所示,多維選擇涉及到更多的網格單元也使得選擇剪切比例的下降.由于選擇屬性和度量屬性的獨立性,如圖6(d)所示,當選擇屬性數量增大時,分數剪切比表現出增長趨勢,但是真實剪切比仍然沒有達到理論剪切比.

    Fig. 5 The effect of tuple number圖5 元組數量的效果

    Fig. 6 The effect of selection attribute size圖6 選擇屬性數量的效果

    4.5 實驗4:度量屬性數量的效果

    給定n=10×108,k=10,s=0.001,d=3,p=0,實驗4評價不同度量屬性數量下的TMS算法性能.如圖7(a)所示,TMS算法比LBE算法快3.98倍.隨著涉及到的度量屬性數量的增加,2個算法的執(zhí)行時間都快速增長.如圖7(b)所示,LBE算法讀取的元組數量比TMS算法多137.96倍.根據計算公式dp(n,m,k),TMS算法的掃描深度與度量屬性數量成指數關系,這也解釋了TMS算法的讀取的元組數量的快速增長.選擇剪切操作的效果如圖7(c)所示,其剪切比例基本保持在72%.根據3.4.2節(jié)的分析,更多的度量屬性使得分數剪切比例下降,如圖7(d)所示,實驗結果符合理論分析結果.

    Fig. 7 The effect of ranking attribute size圖7 度量屬性數量的效果

    4.6 實驗5:選擇度的效果

    給定n=10×108,k=10,m=3,d=3,p=0,實驗5評價不同選擇度下的TMS算法性能.如圖7(a)所示,TMS算法比LBE算法快5.88倍.當選擇度增大時,LBE算法的執(zhí)行時間首先下降,然后逐漸增加.這是由于,當選擇度較小時,評價多維選擇條件的費用較小,而讀取有序度量列表的費用則較大,反之亦然.因此,圖8(a)中的LBE算法的變化趨勢是這2個因素的整合結果.當然,當選擇度較大時,TMS算法涉及到更多的網格單元,從而增加了TMS算法的執(zhí)行費用.如圖8(b)所示,LBE算法讀取的元組數量比TMS算法多72.11倍,并且讀取元組數量的變化趨勢類似于圖8(a)的變化趨勢.如圖8(c)所示,更大的選擇度使得查詢涉及到更多的網格單元,從而減少了選擇剪切比例.如圖8(d)所示,分數剪切比首先增加,然后下降.這是由于,更大的選擇度使得更多的元組滿足查詢條件,根據3.4.2節(jié)的分析,更多的元組滿足查詢條件也使得分數剪切比例增加,這解釋了s=10-5到s=10-3的變化趨勢,但是,隨著選擇度進一步提高,相關的網格單元的數量也增長較快,分配到每個單元的剪切深度就相應減少,采用EGBFT元組執(zhí)行分數剪切操作使得剪切深度擴展到2的最小的指數間距上界,從而降低分數剪切比例.

    4.7 實驗6:相關系數的效果

    給定n=10×108,k=10,s=0.001,m=3,d=3,實驗6評價不同相關系數下的TMS算法性能.如圖9(a)所示,平均來看,TMS算法比LBE算法快3.99倍.很明顯,隨著相關系數的增大,2個算法的執(zhí)行時間都下降,但是下降的速率不同,這取決于不同算法的執(zhí)行方法.如圖9(b)所示,LBE算法讀取的元組數量比TMS算法多73.22倍.如圖9(c)所示,選擇剪切比例基本維持在72%.從圖9(d)看到,隨著相關系數從負值增大到正值,分數剪切的比例迅速增大,從不到10%增長到接近80%.

    Fig. 8 The effect of selectivity圖8 選擇度的效果

    Fig. 9 The effect of correlation圖9 屬性相關的效果

    4.8 實驗7:和ranking cube的比較

    給定n=10×108,d=3,m=3,p=0,實驗7比較在不同結果數量下的TMS算法和ranking cube算法的性能.在實驗7中,選擇屬性是類別類型的,并且每個選擇屬性的基數設置為8,那么滿足多維選擇條件的元組比例是1512.在ranking cube的每個單元中,元組根據基于幾何的劃分來進行組織,我們?yōu)槊總€度量屬性的值域設置8個等長的桶.為提供ranking cube的優(yōu)化性能,我們只保留每個元組的查詢處理需要的屬性.如圖10(a)所示,ranking cube比TMS算法快4倍.圖10(b)解釋了ranking cube的執(zhí)行時間的優(yōu)勢的原因,該算法的IO費用比TMS算法少了一個數量級.圖10(c)給出了需要執(zhí)行多維選擇評價的元組數量,我們看到,該數值隨著結果數量的增加而增大.由于在類別選擇屬性上,相關的元組都滿足多維選擇,所以實驗7不提供多維選擇剪切的結果.如圖10(d)所示,雖然隨著結果數量的增加其剪切比例降低,TMS算法的分數剪切可以丟棄超過82%的候選元組.

    Fig. 10 The comparison with ranking cube圖10 和ranking cube的比較

    5 相關工作

    作為多個領域中一種重要的數據操作,Top-k查詢得到了研究人員的廣泛關注[1].在海量數據環(huán)境中,Fagin等人[6]提出NRA算法來處理只支持順序讀的Top-k查詢.研究人員也提出一系列對于NRA算法的改進,包括LARA算法[7]、TBB算法[8]和TKEP[9]等.研究人員還提出利用索引結構[11-13]或者視圖[14-15]來處理Top-k查詢.但是,大多數的現有方法都沒考慮多維選擇Top-k查詢問題.

    Bruno等人[3]把Top-k查詢轉換為數據庫上的范圍查詢,從而可以利用現有數據庫技術來直接回答Top-k查詢,該方法實際上執(zhí)行的是kNN查詢,不同于本文考慮的多維選擇查詢.Stupar等人[4]考慮處理基于集合選擇的Top-k查詢,即預先給定需要的元組ID集合,然后計算滿足條件的查詢結果.但是,該方式只考慮一個數值屬性的情況,而且基于集合的選擇條件也過于特殊.Dong等人[5]考慮具有類別選擇屬性和數值度量屬性的多維選擇Top-k查詢,在選擇屬性上構建ranking cube來分布元組,每個單元內的元組采用基于幾何信息劃分方式組織成不同基本塊.查詢處理階段,算法從最可能包括查詢結果的基本塊開始掃描,從而快速計算查詢結果.但是,ranking cube方法只能處理類別選擇屬性,無法處理一般情況下(數值選擇屬性)的多維選擇Top-k查詢.

    6 結 論

    本文分析發(fā)現,現有方法無法有效處理海量數據上多維選擇Top-k查詢.因此,本文提出一個新的基于有序列表的TMS算法,該算法利用層次化的選擇屬性網格來對數據執(zhí)行水平劃分,并且每個網格單元對應的分片按列模式存儲.給定多維選擇,TMS算法首先確定相關的網格單元,這有效減少了需要讀取的元組數量.TMS算法利用雙排序方法來漸進評價度量列表分片元組的多維選擇結果,并提出有效的選擇剪切和分數剪切操作來進一步減少需要處理的元組數量.本文實驗表示TMS算法比現有算法具有較大的優(yōu)勢.

    [1]Ilyas I, Beskales G, Soliman M. A survey of top-kquery processing techniques in relational database systems[J]. ACM Computing Survey, 2008, 40(4): Article No 11

    [2]Han Xixian, Li Jianzhong, Gao Hong. Efficient top-kretrieval on massive data[J]. IEEE Trans on Knowledge and Database Engineering, 2015, 27(10): 2687-2699

    [3]Bruno N, Chaudhuri S, Gravano L. Top-kselection queries over relational databases: Mapping strategies and performance evaluation[J]. ACM Trans on Database Systems, 2002, 27(2): 153-187

    [4]Stupar A, Michel S. Being picky: Processing top-kqueries with set-defined selections[C]Proc of the 21st ACM Int Conf on Information and Knowledge Management. New York: ACM, 2012: 912-921

    [5]Dong Xin, Han Jiawei, Cheng Hong, et al. Answering top-kqueries with multi-dimensional selections: The ranking cube approach[C]Proc of the 32nd Int Conf on Very Large Data Bases. New York: ACM, 2006: 463-474

    [6]Fagin R, Lotem A, Naor M. Optimal aggregation algorithms for middleware[J]. Journal of Computer and System Sciences, 2003, 66(4):614-656

    [7]Mamoulis N, Yiu M, Cheng K, et al. Efficient top-kaggregation of ranked inputs[J]. ACM Trans on Database Systems, 2007, 32(3): Article No 19

    [8]Pang H, Ding Xuhua, Zheng Baihua. Efficient processing of exact top-kqueries over disk-resident sorted lists[J]. The VLDB Journal, 2010, 19(3): 437-456

    [9]Han Xixian, Li Jianzhong, Yang Donghua. Supporting early pruning in top-kquery processing on massive data[J]. Information Processing Letter, 2011, 111(11): 524-532

    [10]Han Xixian, Li Jianzhong, Gao Hong. An efficient top-kdominating algorithm on massive data[J]. Chinese Journal of Computers, 2013, 36(10): 2132-2145 (in Chinese)(韓希先, 李建中, 高宏. 一種有效的海量數據top-kdomi-nating查詢算法[J]. 計算機學報, 2013, 36(10): 2132-2145)

    [11]Heo J, Cho J, Whang K. Subspace top-kquery processing using the hybrid-layer index with a tight bound[J]. Data & Knowledge Engineering, 2013, 83: 1-19

    [12]Zou Lei, Chen Lei. Pareto-based dominant graph: An efficient indexing structure to answer top-kqueries[J]. IEEE Trans on Knowledge and Data Engineering, 2011, 23(5): 727-741

    [13]Lee J, Cho H, Hwang S. Efficient dual-resolution layer indexing for top-kqueries[C]Proc of the 28th IEEE Int Conf on Data Engineering. Los Alamitos, CA: IEEE Computer Society, 2012: 1084-1095

    [14]Das G, Gunopulos D, Koudas N, et al. Answering top-kqueries using views[C]Proc of the 32nd Int Conf on Very Large Data Bases. New York: ACM, 2006: 451-462

    [15]Xie Min, Lakshmanan L, Wood P. Efficient top-kquery answering using cached views[C]Proc of the 16th Int Conf on Extending Database Technology. New York: ACM, 2013: 489-500

    Han Xixian, born in 1981. PhD, associate professor. His main research interests include massive data management and data intensive computing.

    Liu Xianmin, born in 1984. PhD, lecturer. His main research interests include massive data computing and data quality management.

    Li Jianzhong, born in 1950. Professor, PhD supervisor. Fellow member of CCF. His main research interests include data-intensive computing, wireless sensor networks and CPS.

    Gao Hong, born in 1966. Professor, PhD supervisor. Her main research interests include data-intensive computing, wireless sensor networks and CPS.

    TMS: An Novel Algorithm for Top-kQueries with Multi-Dimensional Selections on Massive Data

    Han Xixian, Liu Xianmin, Li Jianzhong, and Gao Hong

    (SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)

    In many applications, top-kquery is an important operation to return a set of interesting points among potentially huge data space. Usually, a multi-dimensional selection is specified in top-kquery. It is found that the existing algorithms cannot process the query on massive data efficiently. A sorted-list based algorithm TMS (top-kwith multi-dimensional selection) is proposed to process top-kquery with selection condition on massive data efficiently. TMS employs selection attribute lattice (SAL) of hierarchical structure to distribute tuples and obtains a horizontal partitioning of the table. Each partition is stored in column-oriented model and the lists of ranking attributes are arranged in descending order of attribute values. Given multi-dimensional selection, the relevant lattice cells are determined by SAL and this reduces the number of the retrieved tuples significantly. Double-sorting operation is devised to perform progressive selection evaluation. The efficient pruning is developed to discard the candidates which do not satisfy selection condition or score requirement. The extensive experimental results show that TMS has a significant performance advantage over the existing algorithms.

    top-kwith multi-dimensional selection (TMS) algorithm; sorted list; selection attribute lattice (SAL); progressive selection evaluation; pruning

    2015-06-30;

    2015-10-29

    國家“九七三”重點基礎研究發(fā)展計劃基金項目(2012CB316200);國家自然科學基金項目(61502121,61402130,61272046,61190115,61173022,61033015);山東省自然科學基金項目(ZR2013FQ028);山東省科技重大專項基金項目(2015ZDXX0210B02) This work was supported by the National Basic Research Program of China (973 Program) (2012CB316200), the National Natural Science Foundation of China (61502121, 61402130, 61272046, 61190115, 61173022, 61033015), the Natural Science Foundation of Shandong Province of China (ZR2013FQ028), and the Major Projects of Science and Technology of Shandong Province (2015ZDXX0210B02).

    TP311

    猜你喜歡
    元組分片列表
    巧用列表來推理
    上下分片與詞的時空佈局
    詞學(2022年1期)2022-10-27 08:06:12
    Python核心語法
    電腦報(2021年14期)2021-06-28 10:46:22
    學習運用列表法
    分片光滑邊值問題的再生核方法
    CDN存量MP4視頻播放優(yōu)化方法
    擴列吧
    海量數據上有效的top-kSkyline查詢算法*
    基于模糊二分查找的幀分片算法設計與實現
    基于減少檢索的負表約束優(yōu)化算法
    亚洲男人的天堂狠狠| 激情在线观看视频在线高清| 少妇裸体淫交视频免费看高清| 欧美日韩综合久久久久久 | 亚洲欧美精品综合一区二区三区| 别揉我奶头~嗯~啊~动态视频| 久久天堂一区二区三区四区| 欧美不卡视频在线免费观看| 欧美丝袜亚洲另类 | 欧美一区二区国产精品久久精品| 亚洲欧美精品综合一区二区三区| 精品午夜福利视频在线观看一区| 丰满人妻一区二区三区视频av | 久久久国产成人免费| 国产欧美日韩精品一区二区| 亚洲aⅴ乱码一区二区在线播放| 日韩欧美国产一区二区入口| svipshipincom国产片| 免费观看人在逋| 精品久久久久久久毛片微露脸| 免费av毛片视频| 国产伦在线观看视频一区| 午夜免费激情av| 99久久精品热视频| 欧美精品啪啪一区二区三区| 国产日本99.免费观看| 久久久国产精品麻豆| 成年女人看的毛片在线观看| xxx96com| 成人无遮挡网站| 热99在线观看视频| 久久午夜综合久久蜜桃| 国产精品免费一区二区三区在线| 99热这里只有是精品50| 桃红色精品国产亚洲av| 国产成年人精品一区二区| 亚洲人成网站在线播放欧美日韩| 精品午夜福利视频在线观看一区| 69av精品久久久久久| 日韩成人在线观看一区二区三区| 亚洲va日本ⅴa欧美va伊人久久| 国产成人av教育| 国产精品日韩av在线免费观看| 成人av一区二区三区在线看| 国产成人啪精品午夜网站| 亚洲黑人精品在线| 亚洲激情在线av| 精品国产超薄肉色丝袜足j| 亚洲av成人精品一区久久| 久9热在线精品视频| 亚洲熟妇熟女久久| 国产一级毛片七仙女欲春2| 亚洲第一电影网av| 国产一区二区在线观看日韩 | 亚洲av中文字字幕乱码综合| 午夜亚洲福利在线播放| 在线观看免费视频日本深夜| 欧美极品一区二区三区四区| 成年女人永久免费观看视频| 999精品在线视频| 欧洲精品卡2卡3卡4卡5卡区| 亚洲av美国av| 日日摸夜夜添夜夜添小说| 亚洲五月天丁香| 成人三级黄色视频| 久久精品国产综合久久久| 精品一区二区三区视频在线 | 精品熟女少妇八av免费久了| 国产激情欧美一区二区| 两个人视频免费观看高清| 国产爱豆传媒在线观看| www.熟女人妻精品国产| 久久久成人免费电影| 小蜜桃在线观看免费完整版高清| www.www免费av| av视频在线观看入口| 国产毛片a区久久久久| xxxwww97欧美| 欧美黑人欧美精品刺激| 麻豆久久精品国产亚洲av| 亚洲av中文字字幕乱码综合| АⅤ资源中文在线天堂| 国产av麻豆久久久久久久| 男女之事视频高清在线观看| 亚洲中文字幕一区二区三区有码在线看 | 校园春色视频在线观看| 亚洲精品美女久久av网站| 窝窝影院91人妻| 最近最新中文字幕大全免费视频| 悠悠久久av| 亚洲国产精品成人综合色| 国产成+人综合+亚洲专区| 久久这里只有精品19| 国产欧美日韩一区二区三| 国产av麻豆久久久久久久| 最新在线观看一区二区三区| 国产又色又爽无遮挡免费看| 亚洲av中文字字幕乱码综合| 欧美丝袜亚洲另类 | 亚洲自偷自拍图片 自拍| 18禁裸乳无遮挡免费网站照片| 日本免费一区二区三区高清不卡| 亚洲av电影不卡..在线观看| 丰满人妻一区二区三区视频av | а√天堂www在线а√下载| 国内精品美女久久久久久| 国产av一区在线观看免费| 一个人观看的视频www高清免费观看 | 亚洲七黄色美女视频| 日本熟妇午夜| 国产精品美女特级片免费视频播放器 | 久久午夜综合久久蜜桃| 黄频高清免费视频| 精品国产超薄肉色丝袜足j| 淫妇啪啪啪对白视频| 日本a在线网址| 国产精品亚洲一级av第二区| svipshipincom国产片| 国产精品日韩av在线免费观看| 久久伊人香网站| 欧美午夜高清在线| 亚洲国产高清在线一区二区三| 久久伊人香网站| 国产精品av久久久久免费| 亚洲av免费在线观看| 又黄又爽又免费观看的视频| 很黄的视频免费| 国产成年人精品一区二区| 熟妇人妻久久中文字幕3abv| 精品一区二区三区四区五区乱码| 男人舔女人的私密视频| 国产1区2区3区精品| 精品熟女少妇八av免费久了| 亚洲精品美女久久av网站| 岛国在线观看网站| 亚洲 欧美一区二区三区| 91久久精品国产一区二区成人 | svipshipincom国产片| 亚洲av第一区精品v没综合| 久久婷婷人人爽人人干人人爱| 又黄又粗又硬又大视频| 别揉我奶头~嗯~啊~动态视频| 丰满的人妻完整版| 黄色日韩在线| 中文字幕最新亚洲高清| 欧美一区二区国产精品久久精品| 欧美日韩黄片免| 欧美极品一区二区三区四区| 一个人免费在线观看电影 | 最新中文字幕久久久久 | 国产精品一区二区免费欧美| 男女做爰动态图高潮gif福利片| 成年免费大片在线观看| 国产三级黄色录像| 国产精品98久久久久久宅男小说| 亚洲一区高清亚洲精品| 亚洲精品国产精品久久久不卡| 好看av亚洲va欧美ⅴa在| 久9热在线精品视频| 精品久久久久久久毛片微露脸| 1000部很黄的大片| 久久午夜综合久久蜜桃| 亚洲aⅴ乱码一区二区在线播放| ponron亚洲| 天堂影院成人在线观看| 综合色av麻豆| 日韩欧美国产一区二区入口| 久久精品国产综合久久久| 操出白浆在线播放| 黄片小视频在线播放| 熟女电影av网| 9191精品国产免费久久| 欧美日韩乱码在线| ponron亚洲| 中文资源天堂在线| 熟女人妻精品中文字幕| 小说图片视频综合网站| 精品国产乱子伦一区二区三区| 国内毛片毛片毛片毛片毛片| 小说图片视频综合网站| 一区二区三区国产精品乱码| 毛片女人毛片| 欧美日韩中文字幕国产精品一区二区三区| 最好的美女福利视频网| 国产精品99久久99久久久不卡| 免费一级毛片在线播放高清视频| 18禁裸乳无遮挡免费网站照片| 舔av片在线| 国产私拍福利视频在线观看| 午夜福利在线观看免费完整高清在 | 久久久久国产精品人妻aⅴ院| 久久热在线av| 18禁黄网站禁片午夜丰满| 亚洲国产欧美人成| 欧美一区二区精品小视频在线| 黑人操中国人逼视频| 日本在线视频免费播放| 午夜福利视频1000在线观看| 亚洲国产欧美人成| 天天添夜夜摸| 美女黄网站色视频| 99热只有精品国产| 97超视频在线观看视频| 日本与韩国留学比较| 亚洲自偷自拍图片 自拍| 精品久久久久久成人av| 最近在线观看免费完整版| 亚洲18禁久久av| 此物有八面人人有两片| 中文资源天堂在线| 国产精品久久电影中文字幕| a在线观看视频网站| 无人区码免费观看不卡| 超碰成人久久| 99精品久久久久人妻精品| 久久久国产精品麻豆| 国产成人系列免费观看| 国内精品美女久久久久久| 亚洲午夜理论影院| 黄色丝袜av网址大全| 色播亚洲综合网| 欧美日韩中文字幕国产精品一区二区三区| 草草在线视频免费看| 成人特级黄色片久久久久久久| 欧美高清成人免费视频www| 校园春色视频在线观看| 欧美性猛交黑人性爽| 国产极品精品免费视频能看的| 欧美日韩瑟瑟在线播放| 亚洲av成人精品一区久久| 在线免费观看不下载黄p国产 | 国产精品久久久久久人妻精品电影| 国产亚洲欧美在线一区二区| 亚洲精品国产精品久久久不卡| 国产精品日韩av在线免费观看| 亚洲无线在线观看| 淫秽高清视频在线观看| 国产精品精品国产色婷婷| 亚洲av电影在线进入| 舔av片在线| 90打野战视频偷拍视频| 他把我摸到了高潮在线观看| 午夜福利在线在线| 国产精品亚洲一级av第二区| 日韩大尺度精品在线看网址| 欧美黑人巨大hd| avwww免费| 不卡一级毛片| 一卡2卡三卡四卡精品乱码亚洲| 1024手机看黄色片| 性色avwww在线观看| 狠狠狠狠99中文字幕| 成人国产一区最新在线观看| 日韩大尺度精品在线看网址| 很黄的视频免费| 嫁个100分男人电影在线观看| 精品免费久久久久久久清纯| 淫秽高清视频在线观看| www.999成人在线观看| 18禁国产床啪视频网站| 村上凉子中文字幕在线| 久久久久久九九精品二区国产| 免费av不卡在线播放| 高潮久久久久久久久久久不卡| 男人舔奶头视频| 精品久久久久久久久久免费视频| 国产v大片淫在线免费观看| 久久久久性生活片| 久久九九热精品免费| 免费搜索国产男女视频| 国产精品自产拍在线观看55亚洲| 国产高清激情床上av| 亚洲国产精品999在线| 亚洲av成人不卡在线观看播放网| 精品不卡国产一区二区三区| 亚洲av五月六月丁香网| 午夜日韩欧美国产| 亚洲人成网站高清观看| 老司机午夜十八禁免费视频| 欧美色视频一区免费| tocl精华| 成人午夜高清在线视频| 亚洲午夜精品一区,二区,三区| 看黄色毛片网站| aaaaa片日本免费| 无人区码免费观看不卡| 1024手机看黄色片| 欧美色视频一区免费| 日韩高清综合在线| 99riav亚洲国产免费| 男女之事视频高清在线观看| 一二三四社区在线视频社区8| 99热只有精品国产| 丰满的人妻完整版| 1024香蕉在线观看| 久久久国产精品麻豆| 亚洲五月天丁香| 1024香蕉在线观看| 久久久久久九九精品二区国产| 曰老女人黄片| 老司机深夜福利视频在线观看| 一本综合久久免费| 9191精品国产免费久久| 国产激情久久老熟女| 日本黄色片子视频| 两个人视频免费观看高清| 亚洲国产欧洲综合997久久,| av天堂在线播放| 午夜影院日韩av| 国产三级中文精品| 热99在线观看视频| 欧美一区二区国产精品久久精品| 亚洲欧美日韩卡通动漫| 亚洲成av人片免费观看| 国产亚洲欧美98| 九色国产91popny在线| 欧美日本视频| 小说图片视频综合网站| 国产av在哪里看| 精品国产美女av久久久久小说| 亚洲国产欧美人成| 日本 欧美在线| 黄色片一级片一级黄色片| 国产精品 欧美亚洲| 午夜日韩欧美国产| 麻豆成人av在线观看| 日韩精品青青久久久久久| 久久久成人免费电影| 国产精品自产拍在线观看55亚洲| 成人无遮挡网站| 日本黄色片子视频| 精品一区二区三区av网在线观看| 国产伦一二天堂av在线观看| 国产精品亚洲一级av第二区| 男女午夜视频在线观看| 88av欧美| 日韩av在线大香蕉| bbb黄色大片| 久久午夜综合久久蜜桃| 国产免费男女视频| 亚洲一区二区三区色噜噜| 国产真人三级小视频在线观看| 国产午夜精品久久久久久| 国产精品久久久久久人妻精品电影| 99久久国产精品久久久| 色尼玛亚洲综合影院| 亚洲无线观看免费| 不卡一级毛片| 男人舔女人下体高潮全视频| 成人特级av手机在线观看| www.www免费av| 免费在线观看亚洲国产| 真实男女啪啪啪动态图| netflix在线观看网站| 国产一区二区三区视频了| 午夜a级毛片| 久久中文字幕人妻熟女| 久久久久九九精品影院| 成人三级做爰电影| 9191精品国产免费久久| 999精品在线视频| 日韩欧美一区二区三区在线观看| 免费观看人在逋| 国产美女午夜福利| svipshipincom国产片| 欧美乱色亚洲激情| 99久久久亚洲精品蜜臀av| 国产欧美日韩一区二区三| 免费看美女性在线毛片视频| 欧美成狂野欧美在线观看| 国产高清videossex| 欧美精品啪啪一区二区三区| 亚洲成人久久性| 精品乱码久久久久久99久播| 免费看美女性在线毛片视频| 亚洲人成电影免费在线| 真实男女啪啪啪动态图| 婷婷精品国产亚洲av| 搡老岳熟女国产| av在线天堂中文字幕| 18禁黄网站禁片午夜丰满| 天堂网av新在线| 国产真人三级小视频在线观看| 偷拍熟女少妇极品色| 在线观看午夜福利视频| 1024手机看黄色片| 制服人妻中文乱码| 一二三四在线观看免费中文在| 成人av一区二区三区在线看| 久久精品国产清高在天天线| 日韩欧美免费精品| 亚洲欧美激情综合另类| 麻豆一二三区av精品| 12—13女人毛片做爰片一| 丰满人妻一区二区三区视频av | 日本成人三级电影网站| 18禁观看日本| 一区福利在线观看| 亚洲av熟女| 精品午夜福利视频在线观看一区| 国产成+人综合+亚洲专区| 亚洲精品一区av在线观看| 一二三四社区在线视频社区8| 男人的好看免费观看在线视频| 色尼玛亚洲综合影院| 老司机在亚洲福利影院| 国产一区二区在线观看日韩 | 757午夜福利合集在线观看| 午夜影院日韩av| 久久中文字幕一级| 色综合欧美亚洲国产小说| 国产伦在线观看视频一区| 亚洲乱码一区二区免费版| 极品教师在线免费播放| 国产成人av教育| 亚洲午夜理论影院| av中文乱码字幕在线| 国产精品av久久久久免费| 99久久精品国产亚洲精品| 91在线观看av| 麻豆久久精品国产亚洲av| 老汉色av国产亚洲站长工具| 18美女黄网站色大片免费观看| 黄色丝袜av网址大全| 女同久久另类99精品国产91| av天堂在线播放| 香蕉丝袜av| 亚洲欧美精品综合久久99| 曰老女人黄片| 色综合亚洲欧美另类图片| 18禁裸乳无遮挡免费网站照片| 最新美女视频免费是黄的| 久久香蕉精品热| www.999成人在线观看| 欧美日韩福利视频一区二区| 99热精品在线国产| 欧美不卡视频在线免费观看| 九九久久精品国产亚洲av麻豆 | 国产成人av教育| 好看av亚洲va欧美ⅴa在| 亚洲国产精品999在线| 亚洲精品中文字幕一二三四区| 亚洲av电影不卡..在线观看| 一个人看的www免费观看视频| 91av网一区二区| 五月玫瑰六月丁香| 国产欧美日韩一区二区精品| 欧美国产日韩亚洲一区| 日韩中文字幕欧美一区二区| 久久精品影院6| 国产成人aa在线观看| 可以在线观看毛片的网站| 午夜福利在线在线| 俄罗斯特黄特色一大片| 国产v大片淫在线免费观看| 国产精品98久久久久久宅男小说| 日韩欧美三级三区| 99久久国产精品久久久| 国产免费男女视频| 草草在线视频免费看| 两性夫妻黄色片| 精品久久久久久久人妻蜜臀av| 亚洲成人精品中文字幕电影| 舔av片在线| 欧美另类亚洲清纯唯美| 亚洲中文字幕日韩| 国产亚洲欧美在线一区二区| 国产成人欧美在线观看| 黄色日韩在线| 长腿黑丝高跟| 一进一出抽搐动态| 成人高潮视频无遮挡免费网站| 他把我摸到了高潮在线观看| 真人一进一出gif抽搐免费| 91在线观看av| 国产主播在线观看一区二区| 欧美成狂野欧美在线观看| 亚洲午夜理论影院| 国内揄拍国产精品人妻在线| 给我免费播放毛片高清在线观看| www.精华液| 国产一区二区三区视频了| 国产精品自产拍在线观看55亚洲| 亚洲第一欧美日韩一区二区三区| 99视频精品全部免费 在线 | 精品久久久久久成人av| 国产一级毛片七仙女欲春2| 亚洲狠狠婷婷综合久久图片| 99久国产av精品| 999久久久精品免费观看国产| 中文字幕熟女人妻在线| 婷婷丁香在线五月| 不卡一级毛片| 一夜夜www| 淫妇啪啪啪对白视频| 国产野战对白在线观看| 日本 欧美在线| 99久久精品一区二区三区| 天天躁狠狠躁夜夜躁狠狠躁| a级毛片在线看网站| 真人做人爱边吃奶动态| 亚洲国产看品久久| 亚洲国产色片| www日本在线高清视频| 欧美黑人欧美精品刺激| 日本黄色片子视频| 全区人妻精品视频| 午夜福利免费观看在线| 美女扒开内裤让男人捅视频| 日韩欧美 国产精品| 久久久久久久精品吃奶| 欧美最黄视频在线播放免费| 色哟哟哟哟哟哟| 观看美女的网站| 午夜精品一区二区三区免费看| 天天躁狠狠躁夜夜躁狠狠躁| 给我免费播放毛片高清在线观看| 91在线观看av| 日韩欧美三级三区| 欧美中文日本在线观看视频| 午夜福利在线观看免费完整高清在 | 91老司机精品| 亚洲国产精品sss在线观看| 男插女下体视频免费在线播放| 搡老熟女国产l中国老女人| 亚洲,欧美精品.| 久久精品国产99精品国产亚洲性色| 久久香蕉精品热| 国产伦人伦偷精品视频| 国产探花在线观看一区二区| 最新中文字幕久久久久 | 色尼玛亚洲综合影院| 日韩精品青青久久久久久| www.www免费av| 欧美绝顶高潮抽搐喷水| АⅤ资源中文在线天堂| 国产成人啪精品午夜网站| 亚洲精品在线观看二区| 高清毛片免费观看视频网站| 国产精品99久久久久久久久| 长腿黑丝高跟| 国产高清videossex| 久久国产乱子伦精品免费另类| 香蕉国产在线看| 亚洲色图av天堂| 久久久精品欧美日韩精品| 国产在线精品亚洲第一网站| 美女午夜性视频免费| 女人被狂操c到高潮| 搡老岳熟女国产| 熟女少妇亚洲综合色aaa.| av欧美777| xxxwww97欧美| 1000部很黄的大片| 国模一区二区三区四区视频 | 天堂动漫精品| 日本在线视频免费播放| 亚洲成人精品中文字幕电影| av女优亚洲男人天堂 | 九九热线精品视视频播放| 观看免费一级毛片| 一区福利在线观看| 成人鲁丝片一二三区免费| 成人av一区二区三区在线看| 久久久久国内视频| 国内精品一区二区在线观看| 亚洲av电影在线进入| 久久热在线av| 国产免费av片在线观看野外av| 免费看日本二区| 国产精品影院久久| 一级作爱视频免费观看| 日韩中文字幕欧美一区二区| 久久亚洲真实| 亚洲欧美日韩东京热| 久久久久久大精品| 精品国内亚洲2022精品成人| 国产私拍福利视频在线观看| 亚洲男人的天堂狠狠| 亚洲精品一区av在线观看| 熟女人妻精品中文字幕| 国产99白浆流出| 丝袜人妻中文字幕| 老司机在亚洲福利影院| 精品免费久久久久久久清纯| 久久精品国产综合久久久| 国产亚洲欧美在线一区二区| 精品国产乱子伦一区二区三区| 91麻豆精品激情在线观看国产| 熟女少妇亚洲综合色aaa.| 国产成人系列免费观看| 日本黄色片子视频| 人人妻,人人澡人人爽秒播| 亚洲成人久久爱视频| 两个人的视频大全免费| 亚洲成av人片免费观看| 九九在线视频观看精品| 欧美成人性av电影在线观看| 亚洲专区字幕在线| 俄罗斯特黄特色一大片| 中文字幕高清在线视频| 麻豆国产97在线/欧美| 人妻丰满熟妇av一区二区三区| 99热只有精品国产| 制服人妻中文乱码| 精品国产美女av久久久久小说| svipshipincom国产片| 国产主播在线观看一区二区| 亚洲avbb在线观看| 一a级毛片在线观看| 精品日产1卡2卡| 欧美日韩黄片免| 亚洲色图 男人天堂 中文字幕| 国产精品亚洲美女久久久| 免费看美女性在线毛片视频|