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

劉顯敏 李建中 高 宏

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001) (xxhan1981@163.com)

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

劉顯敏 李建中 高 宏

(哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001) (xxhan1981@163.com)

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

TMS算法;有序列表;選擇屬性網(wǎng)格;漸進(jìn)選擇評(píng)價(jià);剪切操作

在許多應(yīng)用中，Top-k是一種十分重要的查詢類型，它在潛在的巨大數(shù)據(jù)空間中返回用戶感興趣的少量數(shù)據(jù)[1-2].通常，Top-k查詢指定2個(gè)組件來(lái)反映用戶的查詢興趣：評(píng)分函數(shù)F和多維選擇P.根據(jù)定義的評(píng)分函數(shù)F，Top-k查詢從滿足P的數(shù)據(jù)空間中返回k個(gè)分?jǐn)?shù)最大的元組.

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

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

本文的主要貢獻(xiàn)有4點(diǎn)：

1) 提出一個(gè)新的基于有序列表的TMS算法，該算法利用選擇屬性網(wǎng)格來(lái)有效處理海量數(shù)據(jù)上多維選擇Top-k查詢；

2) 提出基于雙排序的方法來(lái)有效執(zhí)行漸進(jìn)選擇評(píng)價(jià)；

3) 提出有效的分?jǐn)?shù)剪切和選擇剪切操作，提出分?jǐn)?shù)剪切操作的理論分析來(lái)獲得優(yōu)化剪切效果；

4) 實(shí)驗(yàn)結(jié)果表明：TMS算法與現(xiàn)有方法相比具有較大的性能優(yōu)勢(shì).

1 預(yù)備知識(shí)

1.1 問(wèn)題定義

多維選擇Top-k查詢：給定表T、多維選擇P和評(píng)分函數(shù)F，多維選擇Top-k查詢?cè)赥P(T中滿足P的元組集合)中返回一個(gè)k子集R，使得?t1∈R，?t2∈TP-R，F(xiàn)(t1)≥F(t2).

典型的多維選擇Top-k查詢SQL語(yǔ)句如下所示：

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

其中，lj和uj分別表示P在選擇屬性Sj指定的下界和上界.本文經(jīng)常用到的符號(hào)如表1所示：

Table 1 The Symbol Notation

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

定義1. 給定表T，元組t∈T的位置索引是a，如果t是T的第a個(gè)元組.

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

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

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

由于LARA算法沒(méi)有考慮多維選擇的問(wèn)題，下面我們提供2種方法來(lái)對(duì)其進(jìn)行擴(kuò)展.

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

下面我們擴(kuò)展現(xiàn)有的LARA算法來(lái)處理多維選擇.假設(shè)選擇屬性也存儲(chǔ)為列文件形式，S1,S2,…,SD存儲(chǔ)為選擇列表集合{SL1,SL2,…,SLD}，每個(gè)選擇列表SLj(1≤j≤D)的模式為SLj(PI,Sj)，其中Sj表示元組在對(duì)應(yīng)選擇屬性的值，注意，這里的SLj的元組根據(jù)Sj的值升序排列，并在SLj.Sj上構(gòu)建B+樹(shù).

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

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

為方便分析，我們假設(shè)表T的屬性均勻獨(dú)立分布.

在海量數(shù)據(jù)上，表T維護(hù)大量元組，并且用戶提交的查詢通常只涉及一小部分元組，n的值較大而SLT的值較小.根據(jù)以上的描述，LBE算法存在3個(gè)問(wèn)題：

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

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

3 TMS算法

3.1 算法概述

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

3.2 選擇屬性網(wǎng)格

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

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

給定樹(shù)結(jié)構(gòu)TSAL，TMS算法順序掃描表T，將表T的元組劃分為(2D)MXH組分片，每一組分片維護(hù)著其選擇屬性落入對(duì)應(yīng)子空間的元組集合.注意，TMS算法只將元組存儲(chǔ)到TSAL的葉節(jié)點(diǎn)對(duì)應(yīng)的分片，因此，TMS算法只維護(hù)表T的水平劃分的單個(gè)副本.?t∈T，TMS算法從根節(jié)點(diǎn)TNrt開(kāi)始，根據(jù)元組t的選擇屬性值來(lái)決定該元組應(yīng)當(dāng)落入哪個(gè)子節(jié)點(diǎn)的子空間，令該元組落入根節(jié)點(diǎn)的第(b1b2…bD)2+1個(gè)子節(jié)點(diǎn)，其位bj(1≤j≤D)的取值如下定義：

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

分片劃分完畢后，TMS算法對(duì)每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)的度量列表分片執(zhí)行排序操作，使得度量列表分片的元組根據(jù)Ai降序排列，但對(duì)選擇列表分片不排序.

3.3 查詢處理

3.3.1 確定相關(guān)子空間

在執(zhí)行查詢處理時(shí)，TMS算法根據(jù)多維選擇P來(lái)確定相關(guān)的子空間.對(duì)于P中任何未出現(xiàn)的選擇屬性Sj，我們通過(guò)在P中添加選擇條件minSj≤Sj≤maxSj來(lái)擴(kuò)展.這里，minSj和maxSj分別表示選擇屬性Sj的最小值和最大值.

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

給定AP，令NAP表示AP的元素?cái)?shù)量，TMS算法獲得d個(gè)具有NAP個(gè)元素的數(shù)組PS1,PS2,…,PSd，其中，PSj(1≤j≤d)維護(hù)和Sj對(duì)應(yīng)的相關(guān)選擇列表分片，還獲得m個(gè)具有NAP個(gè)元素的數(shù)組PR1,PR2,…,PRm，其中，PRi(1≤i≤m)維護(hù)和Ai對(duì)應(yīng)的相關(guān)有序度量列表分片.

給定AF，令NAF表示AF的元素?cái)?shù)量，TMS算法獲得m個(gè)具有NAF個(gè)元素的數(shù)組FR1,FR2,…,FRm，其中，F(xiàn)Ri(1≤i≤m)維護(hù)和Ai對(duì)應(yīng)的相關(guān)有序度量列表分片.

3.3.2 多維選擇評(píng)價(jià)

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

雙排序方法是：在每輪的元組讀取操作中，TMS算法用大小為NAP的最大堆結(jié)構(gòu)PMHi來(lái)讀取PRi中當(dāng)前最大的度量屬性Ai的值，并且在內(nèi)存中維護(hù)一個(gè)緩沖區(qū)PBi，令其大小為SZi.TMS算法分別讀取PRi的每個(gè)分片的一個(gè)元組來(lái)填充PMHi，并不斷讀取PMHi的根節(jié)點(diǎn)元組來(lái)填充PBi.在填充PBi時(shí)，我們并不對(duì)來(lái)自PRi的元組執(zhí)行多維選擇評(píng)價(jià)，而是填充操作完成后批量地對(duì)PBi的元組執(zhí)行多維選擇評(píng)價(jià).

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

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

證明. 給定1≤h1

很明顯，t1.PIptn

證畢.

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

為返回分片集合FRi當(dāng)前最大的屬性Ai的值，TMS算法維護(hù)大小為NAF的最大堆結(jié)構(gòu)FMHi.初始時(shí)，TMS算法讀取FRi的每個(gè)分片的一個(gè)元組來(lái)填充FMHi.

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

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

下面，我們估計(jì)PDi的值，假設(shè)表T的屬性均勻獨(dú)立分布，數(shù)值選擇屬性的值域是[0, 1].

令DPNOP表示沒(méi)有多維選擇情況下TMS算法的掃描深度，令NFh表示分片F(xiàn)Ri[h]的元組數(shù)量，SELh表示分片PRi[h]對(duì)應(yīng)的子空間和P相交的空間比例，TMS算法在FRi上的掃描深度FDi計(jì)算如下：

在其執(zhí)行過(guò)程，TMS算法不需要讀取選擇列表分片集合PSj(1≤j≤d)的所有元組，只是選擇性地讀取指定位置的選擇屬性值來(lái)給出度量列表的候選元組的多維選擇評(píng)價(jià)結(jié)果.很明顯，需要執(zhí)行多維選擇評(píng)價(jià)和維護(hù)的度量列表候選元組的數(shù)量直接影響著TMS算法的性能.下面，我們?cè)谒惴ㄖ刑岢黾羟胁僮鱽?lái)有效減少需要處理的元組數(shù)量.

3.4 剪切操作

3.4.1 多維選擇剪切

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

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

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

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

定義2. 給定選擇列表分片PSj[h]及其對(duì)應(yīng)的選擇屬性子空間HCh，EFBFTj,h和EBBFTj,h分別表示PSj[h]上的指數(shù)間距前向和后向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構(gòu)建的bloom filter，EBBFTj,h(b)表示在PSj[h].Sj∈(HCh[Sj].upp-2b,HCh[Sj].upp)的PSj[h]元組上利用屬性PIptn構(gòu)建的bloom filter.

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

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

令SDS(b1b2…bD)表示子空間SDS中具有編號(hào)為(b1b2…bD)的頂點(diǎn)，令SDS(b1b2…bD)[j]表示該頂點(diǎn)第j個(gè)坐標(biāo)的值.

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

3.4.2 分?jǐn)?shù)剪切

分?jǐn)?shù)剪切操作利用評(píng)分函數(shù)單調(diào)性來(lái)剪切候選元組，從而減少多維選擇評(píng)價(jià)和元組維護(hù)的費(fèi)用.

先考慮一個(gè)簡(jiǎn)單模型來(lái)討論分?jǐn)?shù)剪切，即：查詢不涉及多維選擇，表T的元組數(shù)量是n2，并且表T的屬性均勻獨(dú)立分布.其中，我們?yōu)槎攘繉傩訟i(1≤i≤m)構(gòu)建有序列表ALi.當(dāng)執(zhí)行Top-k查詢時(shí)，我們對(duì)AL1,AL2,…,ALm執(zhí)行round-robin掃描操作，且掃描深度是sdend=dp(n2,m,k).如圖3所示，分?jǐn)?shù)剪切操作需要確定存在深度exdep(≤sdend)和分?jǐn)?shù)剪切深度spdep，使得ALi[1,…,exdep]有k個(gè)候選元組(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 分?jǐn)?shù)剪切示例圖

給定exdep和spdep，?t(PI,Ai,PIptn)∈ALi[(exdep+1),…,sdend]，如果對(duì)所有1≤i′≤m(i′≠i)，t.PI?πPI(ALi′[1,…,spdep])，算法不需要維護(hù)候選元組t.因?yàn)?，根?jù)評(píng)分函數(shù)的單調(diào)性，T(t.PI)的分?jǐn)?shù)肯定低于在ALi中滿足存在條件的那k個(gè)元組的分?jǐn)?shù).

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

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

在對(duì)度量列表分片的掃描過(guò)程中，?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個(gè)滿足條件的元組時(shí)PRi[h1](1≤h1≤NAP)和FRi[h2](1≤h2≤NAF)掃描深度分別為edph1和edfh2，pnph1和pnfh2分別表示根據(jù)以上方法計(jì)算的PRi[h1]和FRi[h2]上的分?jǐn)?shù)剪切深度，分?jǐn)?shù)剪切規(guī)則定義如下：

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

本文采用指數(shù)間距bloom filter表來(lái)有效實(shí)現(xiàn)分?jǐn)?shù)剪切.

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

3.5 處理高維選擇屬性

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

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

在深入研究高維選擇屬性之前，我們先給出2個(gè)觀察[5]：

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

觀察2. 在實(shí)際應(yīng)用中，選擇屬性的查詢頻率通常服從Zipfian分布.

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

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

給定多維選擇P，TMS算法首先計(jì)算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構(gòu)建的選擇屬性網(wǎng)格上執(zhí)行.因?yàn)镻中不包括S3，TMS算法利用{(l1≤S1≤u1)且(l2≤S2≤u2)且(minS3≤S3≤maxS3)}來(lái)確定相關(guān)子空間集合.當(dāng)然，此時(shí)所有的相關(guān)子空間都是和P部分相交.接著，采用如3.3節(jié)和3.4節(jié)的方法來(lái)計(jì)算Top-k結(jié)果.

4 性能評(píng)價(jià)

4.1 實(shí)驗(yàn)設(shè)置

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

我們從不同方面評(píng)價(jià)TMS算法的性能：元組數(shù)量n、結(jié)果數(shù)量k、涉及到的選擇屬性數(shù)量d、涉及到的評(píng)價(jià)屬性數(shù)量m、選擇度s和相關(guān)系數(shù)p.實(shí)驗(yàn)參數(shù)設(shè)置如表2所示：

Table 2 Parameter Settings

實(shí)驗(yàn)用來(lái)評(píng)價(jià)具有數(shù)值選擇屬性的表的Top-k查詢?nèi)缦拢?/p>

select * fromTwherel1≤S1≤u1andl2≤

S2≤u2and … andld≤Sd≤udorder byA1+

A2+…+Amlimitk.

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

類似地，實(shí)驗(yàn)用來(lái)評(píng)價(jià)具有類別選擇屬性的表的 Top-k查詢?nèi)缦拢?/p>

select * fromTwhereS1=a1andS2=a2

and … andSd=adorder byA1+A2+…+

Amlimitk.

其中，aj是屬性Sj的特定值.當(dāng)然，在類別選擇屬性上，選擇屬性網(wǎng)格結(jié)構(gòu)不需要?jiǎng)澐终麄€(gè)的數(shù)據(jù)空間，而是根據(jù)不同的屬性組合來(lái)對(duì)數(shù)據(jù)表執(zhí)行水平劃分.

4.2 實(shí)驗(yàn)1：結(jié)果數(shù)量的效果

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

Fig. 4 The effect of result size圖4 結(jié)果數(shù)量的效果

4.3 實(shí)驗(yàn)2：元組數(shù)量的效果

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

4.4 實(shí)驗(yàn)3：選擇屬性數(shù)量的效果

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

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

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

4.5 實(shí)驗(yàn)4：度量屬性數(shù)量的效果

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

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

4.6 實(shí)驗(yàn)5：選擇度的效果

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

4.7 實(shí)驗(yàn)6：相關(guān)系數(shù)的效果

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

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

Fig. 9 The effect of correlation圖9 屬性相關(guān)的效果

4.8 實(shí)驗(yàn)7：和ranking cube的比較

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

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

5 相關(guān)工作

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

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

6 結(jié) 論

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

[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)(韓希先, 李建中, 高宏. 一種有效的海量數(shù)據(jù)top-kdomi-nating查詢算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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

國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2012CB316200)；國(guó)家自然科學(xué)基金項(xiàng)目(61502121,61402130,61272046,61190115,61173022,61033015)；山東省自然科學(xué)基金項(xiàng)目(ZR2013FQ028)；山東省科技重大專項(xiàng)基金項(xiàng)目(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