TMS:一种新的海量数据多维选择Top-k查询算法

(哈尔滨工业大学计算机科学与技术学院哈尔滨 150001) (xxhan1981@163.com)

摘要： 在许多应用中，Top- k 是一种十分重要的查询类型，它在潜在的巨大数据空间中返回用户感兴趣的少量数据.Top- k 查询通常具有指定的多维选择条件.分析发现：现有算法无法有效处理海量数据的多维选择Top- k 查询.提出了一个基于有序列表的TMS(top- k with multi-dimensional selection)算法，有效计算海量数据上的具有多维选择的Top- k 结果.TMS算法利用层次化结构的选择属性网格对原数据表执行水平划分，每一个分片的元组以面向列的模式存储，并且度量属性的列表根据其属性值降序排列.给定多维选择条件，TMS算法利用选择属性网格确定相关网格单元，有效减少需要读取的元组数量，提出双排序方法执行多维选择的渐进评价，并提出有效剪切操作来剪切不满足多维选择条件和分数要求的候选元组.实验结果表明：TMS算法性能优于现有算法.

关键词： 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- k selection查询映射为范围查询，但是该方法实际上是计算多维空间上的 k 最近邻查询，不同于本文讨论的多维选择Top- k 查询.Stupar等人 [4] 考虑处理基于集合选择的Top- k 查询，即预先给定需要的元组ID集合，然后计算满足条件的查询结果.该方法的要求过于特殊，而且只考虑有一个度量属性的情况.Dong等人 [5] 提出ranking cube的方法来处理多维选择Top- k 查询，该方法将data cube的思想和排序操作结合在一起来有效返回查询结果，但是该方法假设多维选择总是涉及到分类属性，并且在实际应用中构建和维护ranking cube的代价过于昂贵.综上所述，现有算法在海量数据上无法有效计算一般情况的多维选择Top- k 查询.

本文提出一个新的基于有序列表的算法TMS(top- k with multi-dimensional selection)来有效处理海量数据多维选择Top- k 查询.该算法利用层次结构的选择属性网格对数据表进行水平划分，并且存储为面向列模式.TMS算法对度量属性对应的度量列表分片按照其属性值降序排列，保持选择属性对应的选择列表分片的原有顺序.给定多维选择，TMS算法根据网格结构快速确定相关的网格信息.在读取度量列表分片的元组时，本文提出双排序方法渐进地执行多维选择评价，从而减少了查询处理涉及到的I

O费用.本文提出分数剪切操作和多维选择剪切操作，尽早丢弃那些不满足分数要求或者多维选择条件的候选元组.本文提出分数剪切的数学分析，来获得优化的剪切效果.本文的实验结果表明，和现有方法相比，TMS算法可以获得较大的性能优势.

1) 提出一个新的基于有序列表的TMS算法，该算法利用选择属性网格来有效处理海量数据上多维选择Top- k 查询；

3) 提出有效的分数剪切和选择剪切操作，提出分数剪切操作的理论分析来获得优化剪切效果；

4) 实验结果表明：TMS算法与现有方法相比具有较大的性能优势.

1 预备知识

给定具有度量属性 A 1 , A 2 ,…, A M 和选择属性 S 1 , S 2 ,…, S D 的表 T ，不失一般性，令P是定义在 S 1 , S 2 ,…, S d 上的多维选择，F是定义在 A 1 , A 2 ,…, A m 上的评分函数，∀

t . A i )，这里 w i 是F在 A i 上的权重.通常F是单调函数，即∀ t 1 , t 2 ∈ T ，如果所有1≤ i ≤ m ， t 1 . A i ≤ t 2 . A i ，F( t 1 )≤F( t 2 ).

多维选择Top- k 查询：给定表 T 、多维选择P和评分函数F，多维选择Top- k 查询在 T P ( T 中满足P的元组集合)中返回一个 k 子集 R ，使得∀ t 1 ∈ R ，∀ t 2 ∈ T P - R ，F( t 1 )≥F( t 2 ).

select * from T where l 1 ≤ S 1 ≤ u 1 and l 2 ≤ S 2 ≤ u 2 and… and l d ≤ S d ≤ u d order by w 1 × A 1 + w 2 × A 2 +…+ w m × A m limit k .

其中， l j 和 u j 分别表示P在选择属性 S j 指定的下界和上界.本文经常用到的符号如表1所示：

Table 1 The Symbol Notation

表1 符号表

定义1. 给定表 T ，元组 t ∈ T 的位置索引是 a ，如果 t 是 T 的第 a 个元组.

我们用 T ( a )来表示表 T 中位置索引为 a 的元组，用 T [ a ,…, b ]表示位置索引大于等于 a 且小于等于 b 的元组集合，用 T [ a ,…, b ]. A i 表示 T [ a ,…, b ]中元组的属性 A i 的集合.

自从Fagin等人 [6] 的先驱性工作，利用有序列表来处理Top- k 查询已经成为研究人员自然的选择 [7-10] .我们先介绍在不考虑多维选择情况下的有序列表Top- k 查询算法.由于其较好的性能，本文采用LARA算法 [7] 为例来讨论有序列表Top- k 算法.

给定具有度量属性 A 1 , A 2 ,…, A M 的表 T ，有序列表方法要求将度量属性存储为度量列表集合{ AL 1 , AL 2 ,…, AL M }，每个度量列表 AL i 的模式为 AL i ( PI , A i )，其中 PI 表示元组的位置索引， A i 表示元组在对应属性的值， AL i 根据属性值 A i 降序排列.LARA算法的执行包括2个阶段：增长阶段和收缩阶段.1)在增长阶段，LARA算法以round-robin方法在 AL 1 , AL 2 ,…, AL m 上依次读取元组.假设在当前轮读取中获得元组分别是( pi 1 , a 1 )，( pi 2 , a 2 ),…,( pi m , a m )，则LARA算法的分数阈值 τ =F( a 1 , a 2 ,…, a m ).对于获得每一个元组 t (通过 t . PI 来识别)，LARA算法维护它的分数下界F t lb .

t . A i ,L )，如果 t . A i 的值已经在 AL i 的顺序读取过程获得， t . A i ,L = t . A i ，否则 t . A i ,L =min A i (min A i 是 t . A i 可能的最小值).LARA算法利用一个优先队列 P Q 来维护当前已经出现的具有最大分数下界的 k 个元组，令 P Q .min表示 P Q 中的最小值.LARA算法在集合 C 维护候选元组，不断更新 P Q 和阈值 τ ，直到 P Q .min≥ τ ，增长阶段结束，Top- k 结果肯定包括在集合 C .2)在收缩阶段，LARA算法继续对 AL 1 , AL 2 ,…, AL m 执行round-robin方式读取操作，如果当前获得的元组 t 不在集合 C 中，元组 t 肯定不是查询结果，否则，LARA算法更新元组 t 的分数上界F t ub 和分数下界F t lb .

t . A i ,U )，如果 t . A i 的值已经在 AL i 的顺序读取过程获得， t . A i ,U = t . A i ，否则 t . A i ,U = a i .LARA算法更新 P Q 和阈值 τ ，直到∀ t ∈( C - P Q )， P Q .min≥F t ub . P Q 维护的就是Top- k 查询结果.

由于LARA算法没有考虑多维选择的问题，下面我们提供2种方法来对其进行扩展.

1) 类树索引.一种直观的想法是以元组位置索引为键值在选择属性上构建类树索引.在LARA算法执行时，对于当前一轮获得的度量列文件 AL i 元组( pi , a i )，根据类树索引和 pi 的值来判断元组 T ( pi )是否符合P，如果符合，那么对于该元组的处理类似于传统LARA算法，否则直接丢弃该元组，然后继续读取该列文件，直到获得一个满足条件的元组或文件遍历完毕.类树索引的问题在于，由于度量列文件 AL i 是根据属性值降序排列的，每次索引判断可能引起一个磁盘随机seek操作，在海量数据上执行时，这必然引起较多的大范围随机I

O操作，严重影响算法的效率.因此，本文不再讨论这种方法.

下面我们扩展现有的LARA算法来处理多维选择.假设选择属性也存储为列文件形式， S 1 , S 2 ,…, S D 存储为选择列表集合{ SL 1 , SL 2 ,…, SL D }，每个选择列表 SL j (1≤ j ≤ D )的模式为 SL j ( PI , S j )，其中 S j 表示元组在对应选择属性的值，注意，这里的 SL j 的元组根据 S j 的值升序排列，并在 SL j . S j 上构建B+树.

2) 批量方法LBE(LARA with batch evalua-tion).该方法采用批量方法来处理多维选择.对读取度量列表之前，LBE算法先利用构建的B+树对 SL 1 , SL 2 ,…, SL d 依次执行范围扫描操作，来获得满足多维选择的位向量 B .∀ t = T ( pi )，如果 t 满足P，那么位向量 B 的第 pi 位置为1，否则位向量 B 的第 pi 位置为0.接下来，LBE算法对度量列表执行元组读取操作，对于当前获得的 AL i 元组( pi , a i )，LBE算法利用 B 的第 pi 位判断该元组是否符合P，如果满足条件则对该元组的处理类似于LARA算法，否则直接丢弃该元组，继续读取该度量列表，直到获得一个满足条件的元组.

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

令表 T 的元组数量为 n ，不失一般性，假设位置索引是long型, 选择属性是double型(8 B).令多维选择P的选择度为 SLT ，其在选择属性 S j 的选择度为

SLT j ，那么LBE算法对选择列表 SL 1 , SL 2 ,…, SL d 执行范围扫描操作需要读取的数据量为

(16× n × SLT j )个字节.已知，在没有多维选择的情况下，LARA算法的扫描深度

.本文采用函数 dp ( n , m , k )的值作为LARA的扫描深度.在具有多维选择的情况下，LBE算法在单个度量列表上需要获得满足条件的元组数量是 dp ( n 2 , m , k )， n 2 = n × SLT ，LBE算法需要读取的度量列表 AL 1 , AL 2 ,…, AL m 的数据量为

m .LBE算法在执行过程读取的数据量

在海量数据上，表 T 维护大量元组，并且用户提交的查询通常只涉及一小部分元组， n 的值较大而 SLT 的值较小.根据以上的描述，LBE算法存在3个问题：

2) 给定多维选择条件，LBE算法需要在 AL i (1≤ i ≤ m )上读取

个元组才能获得一个满足条件的元组，由于 SLT 的值较小，LBE算法读取 AL i (1≤ i ≤ m )的I

O费用较高；

3) LBE算法需要维护一个 n -bit的位向量，在海量数据上该位向量需要占据较多的内存空间.针对存在的问题，我们提出新的TMS算法有效处理海量数据多维选择Top- k 查询.

3 TMS算法

多维选择P实际给出一个查询子空间，如果在读取度量列表 AL i (1≤ i ≤ m )时，算法可以快速定位其对应行元组落入该子空间的元组，那么算法就可以较好地处理多维选择Top- k 查询.本文采用选择属性网格来分布表 T 的元组，将对应网格的元组维护为列存储形式.基于选择属性网格的划分过程其实是把表 T 的 A i 对应的度量列表 AL i (1≤ i ≤ m )划分为度量列表分片.给定多维选择条件P，算法可以根据网格结构来确定相关分片，也就确定了相关的度量属性列表分片.通常，与P相关的度量列表分片集合只是初始度量列表的一部分，从而有效减少读取不满足多维选择的元组的费用.本文还提出基于双排序的渐进多维选择评价方法来判断读取的度量属性是否符合P.为进一步减少双排序方法中需要评价的度量属性值的数量，本文提出有效的多维选择剪切操作和分数剪切操作.下面，我们分别介绍TMS算法的基本执行过程.

给定表 T 的选择属性 S 1 , S 2 ,…, S D ，TMS算法首先构建选择属性网格 SAL ，这里先假设选择属性数量不大，3.5节讨论高维选择属性问题. SAL 是一个层次结构组织，其第0层结构维护 S 1 , S 2 ,…, S D 构成的整个 D -维空间 DS .接下来， SAL 将每个选择属性 S i 的值域均匀划分为2个区间，第1层结构维护的就是整个 D -维空间 DS 的2 D 个子空间， DS 1 , DS 2 ,…, DS 2 D ，这里我们有

S .给定第 level 层结构，第 level +1层类似地将第 level 层结构的每一个子空间 SDS 划分为大小相等的2 D 个子空间 SDS 1 , SDS 2 ,…, SDS 2 D ，同样这里

SDS .本文设定 SAL 的最大层次为 MXH .TMS算法采用一个树结构 T SAL 来有效维护 SAL ， T SAL 的根节点维护 SAL 的第0层结构，其每个节点具有2 D 个子节点.给定某节点 TN ，令 TN . hcube 代表该节点维护的子空间， TN . hcube [ S j ]， TN . hcube [ S j ]. low ， TN . hcube [ S j ]. upp 分别代表子空间 TN . hcube 在选择属性 S j 上的投影、该投影的区间下界和上界， TN . level 代表该节点所维护的 SAL 结构的当前层次， TN . child 代表该节点的子节点数组.在 TN . level +1层， SAL 将 TN . hcube 在每个选择属性 S j 上均匀划分为2个区间， TN . hcube 在 TN . level +1层被划分为2 D 个子空间， TN 的第 h 个子节点 TN . child [ h ]( h =( b 1 b 2 … b D ) 2 +1), 1≤ h ≤2 D )，我们有 TN . child [ h ]. level = TN . level +1，如果 TN . child [ h ]. hcube [ S j ]是 TN . child [ h ]的数值较小的半区间， b j =0；否则， b j =1. TN . child [ h ]. low 和 TN . child [ h ]. upp 也相应的设置为 TN . child [ h ]. hcube [ S j ]的端点值.在第 MXH 层， SAL 维护的子空间数量为(2 D ) MXH .

图1给出的是 D =2和 MXH =2的 SAL 最底层划分情况，叶节点的编号表示其在兄弟节点中的次序.令 T SAL ( tncode )表示 T SAL 中编号 tncode 的节点.例如，具有编号“0100”的叶节点是编号“01”的节点的第1个孩子，而编号为“01”的节点是根结点的第2个孩子.

给定树结构 T SAL ，TMS算法顺序扫描表 T ，将表 T 的元组划分为(2 D ) MXH 组分片，每一组分片维护着其选择属性落入对应子空间的元组集合.注意，TMS算法只将元组存储到 T SAL 的叶节点对应的分片，因此，TMS算法只维护表 T 的水平划分的单个副本.∀ t ∈ T ，TMS算法从根节点 TN rt 开始，根据元组 t 的选择属性值来决定该元组应当落入哪个子节点的子空间，令该元组落入根节点的第( b 1 b 2 … b D ) 2 +1个子节点，其位 b j (1≤ j ≤ D )的取值如下定义：

该过程自 T SAL 的根节点开始执行，直到找到叶节点 TN lf ，元组 t 输出到 TN lf 对应的分片.对于每一个元组，TMS算法只需要进行 MXH 次判断就可以确定应当放入的分片.我们将叶节点对应的分片存储为面向列的格式，其中，度量列表分片和选择列表分片的模式分别为( PI , A i , PI ptn )和( PI , S j ).这里， PI 表示对应元组在表 T 的位置索引， PI ptn 表示元组在对度量列表分片中的元组排序前的位置索引.

分片划分完毕后，TMS算法对每个叶节点对应的度量列表分片执行排序操作，使得度量列表分片的元组根据 A i 降序排列，但对选择列表分片不排序.

在执行查询处理时，TMS算法根据多维选择P来确定相关的子空间.对于P中任何未出现的选择属性 S j ，我们通过在P中添加选择条件min S j ≤ S j ≤max S j 来扩展.这里，min S j 和max S j 分别表示选择属性 S j 的最小值和最大值.

给定多维选择P，TMS算法对 T SAL 执行层次遍历来确定不和P相离的叶节点.对于获得的叶节点 TN lf ，其处理方式如下：1) TN lf . hcube 和P部分相交， TN lf 插入到数组 AP ；2) TN lf . hcube 被P包含， TN lf 插入到数组 AF .这里， AP 维护其子空间和P部分相交的叶节点集合， AF 维护其子空间被P包含的叶节点集合.

给定 AP ，令 N AP 表示 AP 的元素数量，TMS算法获得 d 个具有 N AP 个元素的数组 PS 1 , PS 2 ,…, PS d ，其中， PS j (1≤ j ≤ d )维护和 S j 对应的相关选择列表分片，还获得 m 个具有 N AP 个元素的数组 PR 1 , PR 2 ,…, PR m ，其中， PR i (1≤ i ≤ m )维护和 A i 对应的相关有序度量列表分片.

给定 AF ，令 N AF 表示 AF 的元素数量，TMS算法获得 m 个具有 N AF 个元素的数组 FR 1 , FR 2 ,…, FR m ，其中， FR i (1≤ i ≤ m )维护和 A i 对应的相关有序度量列表分片.

在执行过程中，TMS算法需要从 PR i 和 FR i 中按照降序顺序读取满足条件的度量属性 A i 的值.在读取度量列表分片时，TMS算法渐进地计算当前读取的元组的多维选择评价结果.∀( pi , a i , pi ptn )∈ PR i [ h ]， T ( pi ). S j 的值出现在 PS j [ h ](1≤ j ≤ d )的第 pi ptn 个元组中，TMS算法需要读取 PS 1 [ h ], PS 2 [ h ],…, PS d [ h ]的第 pi ptn 个元组来获得 T ( pi )的选择属性 S 1 , S 2 ,…, S d 的值，可以判断 T ( pi )是否满足P.如果对获得的每个来自 PR i [ h ]的元组都根据其 pi ptn 的值来跳转到对应选择列表分片的指定位置进行多维选择评价，必然影响查询处理的效率.本文提出一个基于双排序的渐进评价方法，尽量采用磁盘顺序读取操作评价来自 PR i 的元组是否满足P.

双排序方法是：在每轮的元组读取操作中，TMS算法用大小为 N AP 的最大堆结构 PMH i 来读取 PR i 中当前最大的度量属性 A i 的值，并且在内存中维护一个缓冲区 PB i ，令其大小为 SZ i .TMS算法分别读取 PR i 的每个分片的一个元组来填充 PMH i ，并不断读取 PMH i 的根节点元组来填充 PB i .在填充 PB i 时，我们并不对来自 PR i 的元组执行多维选择评价，而是填充操作完成后批量地对 PB i 的元组执行多维选择评价.

对应于分片集合 PR i ，TMS算法维护一个具有 N AP 个元素的偏移量数组 OA ，令 NP h 表示分片 PR i [ h ]的元组数量，

，令 OA [1]=0.

假设 PMH i 的当前根节点元组 t ( PI , A i , PI ptn )∈ PR i [ h ]，将元组 t 填充到 PB i 时，执行 t . PI ptn += OA [ h ].填充完毕后，TMS算法根据属性 PI ptn 对 PB i 执行升序排序操作.根据定理1，排序后 PB i 中来自 PR i [ h ]的元组连续存储，而这些元组对应的选择属性顺序存储在选择属性列表分片 PS j [ h ](1≤ j ≤ d ).

定理1. 双排序方法的第1次排序后， PB i 中来自 PR i [ h ] (1≤ h ≤ N AP )的元组连续存储，且这些元组对应的选择属性 S j (1≤ j ≤ d )顺序存储在选择列表分片 PS j [ h ].

证明. 给定1≤ h 1 < h 2 ≤ N AP ，∀ t 1 ( PI , A i , PI ptn )∈ PR i [ h 1 ]， t 2 ( PI , A i , PI ptn )∈ PR i [ h 2 ].由于 OA 的帮助，在第1次排序阶段， t 1 . PI ptn 和 t 2 . PI ptn 满足如下条件：

很明显， t 1 . PI ptn < t 2 . PI ptn .经过双排序方法的第1次排序， PB i 中来自文件 PR i [ h ](1≤ h ≤ N AP )的元组连续存储.排序后 PB i 中来自 PR i [ h ]的元组是根据 PI ptn 升序排列，且 PS j [ h ]的元组也是根据 PI ptn 升序排列， PB i 中来自 PR i [ h ]的元组对应的选择属性 S j 顺序存储在选择列表分片 PS j [ h ].

在第1次排序后，令 PB i [ b h ,…, e h ]表示 PB i 中来自 PR i [ h ]的元组.在评价多维选择时，TMS算法按照P[ S 1 ],P[ S 2 ],…,P[ S d ]的顺序依次对 PB i 的元组执行多维选择评价，尽量利用对单个文件的顺序扫描来提高磁盘处理效率.在评价P[ S j ]时，TMS算法从头开始扫描 PB i 中的元组，如果 b h ≤ e h ，TMS算法根据 PB i [ b h ,…, e h ]的 PI ptn 属性的值，选择性地获得选择列表分片 PS j [ h ]的第 PI ptn - OA [ h ]个元组来评价 PB i [ b h ,…, e h ]的对应元组的P[ S j ]评价结果.在完成对P[ S 1 ],P[ S 2 ],…,P[ S d ]的评价后，TMS算法根据 A i 的值对 PB i 执行降序排序，我们就完成对 PB i 的元组的多维选择评价.

为返回分片集合 FR i 当前最大的属性 A i 的值，TMS算法维护大小为 N AF 的最大堆结构 FMH i .初始时，TMS算法读取 FR i 的每个分片的一个元组来填充 FMH i .

在读取下一个满足条件的度量属性 A i 的值时，TMS算法顺序读取 PB i 直到获得一个满足条件的元组 t 1 ，比较 FMH i 的当前根节点元组 t 2 (假设 t 2 ∈ FR i [ h ])，如果 t 1 . A i ≤ t 2 . A i ，TMS算法就获得 t 2 作为当前轮的度量属性 A i 的值，并读取 FR i [ h ]的下一个元组填充 FMH i ，否则TMS算法就获得 t 1 作为当前轮的度量属性 A i 的值.如果 PB i 的元组被读取完毕，TMS算法重新执行填充操作.元组读取操作不断执行，直到返回查询结果或者相关度量列表分片的元组被遍历完毕.

下面，我们讨论如何确定缓冲区 PB i 的大小 SZ i 的优化值.根据系统的性能和日常负载，系统首先设置缓冲区大小的上限 MXSIZE ，要求 SZ i ≤ MXSIZE .

令TMS算法在 PR i 上的扫描深度是 PD i ，即算法结束时从 PR i 读取的元组数量.对于每一个读取的 PR i 的元组 t ，TMS算法都需要判断元组 t 是否满足P.因此，TMS算法需要执行 PD i 次多维选择评价操作.令 cost read 和 cost skip ( dv )分别表示读取单个列表元组和跳过数据量 dv 的磁盘操作费用，那么利用 PB i 执行 PD i 个元组的多维选择评价操作的费用计算如下：

其中，

表示 PR i 包括的所有元组数量.很明显，要最小化 cost pe 的值，就要求最大化 SZ i 的值，本文取 SZ i =min( PD i , MXSIZE ).

下面，我们估计 PD i 的值，假设表 T 的属性均匀独立分布，数值选择属性的值域是[0, 1].

令 DP NOP 表示没有多维选择情况下TMS算法的扫描深度，令 NF h 表示分片 FR i [ h ]的元组数量， SEL h 表示分片 PR i [ h ]对应的子空间和P相交的空间比例，TMS算法在 FR i 上的扫描深度 FD i 计算如下：

那么在 PR i 上读取的满足条件的元组数量是 DP NOP - FD i ，令 cp 表示 AP 维护子空间的并和P相交的空间比例，我们有

在其执行过程，TMS算法不需要读取选择列表分片集合 PS j (1≤ j ≤ d )的所有元组，只是选择性地读取指定位置的选择属性值来给出度量列表的候选元组的多维选择评价结果.很明显，需要执行多维选择评价和维护的度量列表候选元组的数量直接影响着TMS算法的性能.下面，我们在算法中提出剪切操作来有效减少需要处理的元组数量.

给定相关的度量列表分片集合 PR i 和 FR i (1≤ i ≤ m ).∀ t 1 ∈ FR i [ h ]， t 1 肯定满足多维选择P，但是∃ t 2 ∈ PR i [ h ]， t 2 可能不满足P.这部分提出多维选择剪切策略来尽早丢弃那些不满足P的度量列表分片的候选元组.

考虑度量列表分片 PR i [ h ](1≤ i ≤ m )，令其对应的选择属性子空间和多维选择P部分相交的子空间是 ISTC h ，那么多维选择剪切规则定义如下：

∀ t ( PI , A i , PI ptn )∈ PR i [ h ]，如果∃ j (1≤ j ≤ d )， PS j [ h ]( PI ptn ). S j 不在区间 ISTC h [ S j ]内，那么 t 不满足多维选择，其中 PS j [ h ]( PI ptn ). S j 表示文件 PS j [ h ]中位置索引为 PI ptn 的元组的 S j 属性.

本文限制 SAL 的最大层次 MXH ，叶节点维护的选择属性子空间无法进一步划分，多维选择剪切方法就是在最底层的选择属性子空间中丢弃那些不满足条件的度量列表候选元组.本文采用指数间距前向bloom filter表和指数间距后向bloom filter表来有效实现多维选择剪切.

定义2. 给定选择列表分片 PS j [ h ]及其对应的选择属性子空间 HC h ， EFBFT j , h 和 EBBFT j , h 分别表示 PS j [ h ]上的指数间距前向和后向bloom filter表，如果它们满足条件：1)| EFBFT j , h |=| EBBFT j , h |=lb( HC h [ S j ]. upp - HC h [ S j ]. low +1); 2) EFBFT j , h ( b )表示在 PS j [ h ]. S j ∈[ HC h [ S j ]. low , HC h [ S j ]. low +2 b )的 PS j [ h ]元组上利用属性 PI ptn 构建的bloom filter， EBBFT j , h ( b )表示在 PS j [ h ]. S j ∈( HC h [ S j ]. upp -2 b , HC h [ S j ]. upp )的 PS j [ h ]元组上利用属性 PI ptn 构建的bloom filter.

我们可以分别将 PS j [ h ]的元组按照选择属性 S j 的值升序和降序排列，从而有效构建 EFBFT j , h 和 EBBFT j , h .

已知，一个 D 维子空间 SDS 有2 D 个顶点，令该子空间的左下方和右上方的坐标分别是( bl 1 , bl 2 ,…, bl D )和( tr 1 , tr 2 ,…, tr D )，给定子空间 SDS 的某一坐标为( cod 1 , cod 2 ,…, cod D )的顶点，其编号( b 1 b 2 … b D )定义如下：

令 SDS ( b 1 b 2 … b D )表示子空间 SDS 中具有编号为( b 1 b 2 … b D )的顶点，令 SDS ( b 1 b 2 … b D )[ j ]表示该顶点第 j 个坐标的值.

如图2(a)所示，∀ t ∈ PR i [ h ]，如果 t 满足多维选择P， t 肯定出现在对角顶点为 HC h ( b 1 b 2 … b D )和

D )的不可剪切空间.要保证最好的多维选择剪切效果，我们选择其面积最小的不可剪切空间 UPS best .不失一般性，令 UPS best 的对角顶点分别为 HC h ( b 1 b 2 … b D )和

如图2(b)所示，如果 b j =0，我们为 PS j [ h ]载入

；如果 b j =1，我们为 PS j [ h ]载入

).∀ t ( PI , A i , PI ptn )∈ PR i [ h ]，如果∃ j (1≤ j ≤ D )，对应于 PS j [ h ]的bloom filter对 t . PI ptn 的成员检测结果为假，则 t 肯定不满足多维选择P.如图2(b)所示， t 1 , t 2 不能被选择剪切丢弃，而 t 3 , t 4 , t 5 则可以被选择剪切操作丢弃.

分数剪切操作利用评分函数单调性来剪切候选元组，从而减少多维选择评价和元组维护的费用.

先考虑一个简单模型来讨论分数剪切，即：查询不涉及多维选择，表 T 的元组数量是 n 2 ，并且表 T 的属性均匀独立分布.其中，我们为度量属性 A i (1≤ i ≤ m )构建有序列表 AL i .当执行Top- k 查询时，我们对 AL 1 , AL 2 ,…, AL m 执行round-robin扫描操作，且扫描深度是 sd end = dp ( n 2 , m , k ).如图3所示，分数剪切操作需要确定存在深度 exdep (≤ sd end )和分数剪切深度 spdep ，使得 AL i [1,…, exdep ]有 k 个候选元组( pi i ,1 , a i ,1 , ptn i ,1 ),( pi i ,2 , a i ,2 , ptn i ,2 ),…,( pi i , k , a i , k , ptn i , k )满足存在条件：所有1≤ k ′≤ k 和1≤ i ′≤ m ( i ′≠ i )， pi i , k ′ ∈ π PI ( AL i ′ [1,…, spdep ]).

给定 exdep 和 spdep ，∀ t ( PI , A i , PI ptn )∈ AL i [( exdep +1),…, sd end ]，如果对所有1≤ i ′≤ m ( i ′≠ i )， t . PI ∉ π PI ( AL i ′ [1,…, spdep ])，算法不需要维护候选元组 t .因为，根据评分函数的单调性， T ( t . PI )的分数肯定低于在 AL i 中满足存在条件的那 k 个元组的分数.

∀ t ∈ AL i [1,…, exdep ]， t 满足存在条件的概率

m -1 ，那么在 AL i [1,…, exdep ]中满足存在条件的元组个数服从二项分布 BD ( exdep , extprob )，令该分布的期望值 E ( BD )= k ，我们获得 exdep 和 spdep 的关系

m -1 .根据以上的描述，分数剪切操作无法对 AL i [1,…, exdep ]的元组执行剪切操作，但是∀ t ∈ AL i [( exdep +1),…, sd end ]， t 被分数剪切的概率是

m -1 .当 spdep 的值增大时， exdep 的值减小，那么在 AL i [1,…, sd end ]中更多的候选元组可以被一个具有较小剪切比例的分数剪切操作剪切，反之亦然，即存在一个优化的分数剪切深度来最大化分数剪切概率

m -1 .令

的计算公式可以表示为如下函数

，优化分数剪切深度

根据对简单模型的讨论，下面介绍如何在相关的度量列表分片集合上执行分数剪切.这里，我们同样假设度量属性 A 1 , A 2 ,…, A m 均匀独立分布，需要注意的是，均匀独立分布假设只是为了计算方便，而并不影响TMS算法的执行.

已知，在不考虑多维选择时，TMS算法的优化分数剪切深度是 spdep opt ，我们需要计算在相关的度量列表分片上的分数剪切深度，换句话说，要获得 spdep opt 个满足多维选择的 A i 属性的值需要从 PR i 和 FR i 分别读取的元组数量.

基于度量属性的均匀独立分布假设，我们可以计算每个相关的 T SAL 叶节点 AP [ h ]维护的子空间和P的相交的比例，该比例可以作为 PR i [ h ]中的候选元组满足多维选择的选择度，该选择度的值记为 SEL h .令 NP h 表示 PR i [ h ]的元组数量，那么 PR i 中满足多维选择的总的元组数量 SNP =

( SEL h × NP h )，令 NF h 表示 FR i [ h ]的元组数量，那么 FR i 中满足多维选择的总的元组数量

NF h .

要获得 spdep opt 个满足多维选择的元组，TMS算法需要从分片 PR i [ h ]读取的元组数量是

，TMS算法需要从 FR i [ h ]读取的元组数量是

在对度量列表分片的扫描过程中，∀ t 1 ( PI , A i , PI ptn )∈ PR i [ h ]，如果所有1≤ i ′≤ m 并且 i ′≠ i ， t 1 . PI ∈ π PI ( PR i ′ [ h ][1,…, pnp h ])，我们称 t 1 满足存在条件，∀ t 2 ∈ FR i [ h ]，如果所有1≤ i ′≤ m 并且 i ′≠ i ， t 2 . PI ∈ π PI ( FR i ′ [ h ][1,…, pnf h ])，我们称 t 2 满足存在条件.

令获得 k 个满足条件的元组时 PR i [ h 1 ](1≤ h 1 ≤ N AP )和 FR i [ h 2 ](1≤ h 2 ≤ N AF )扫描深度分别为 edp h 1 和 edf h 2 ， pnp h 1 和 pnf h 2 分别表示根据以上方法计算的 PR i [ h 1 ]和 FR i [ h 2 ]上的分数剪切深度，分数剪切规则定义如下：

给定度量列表分片集合 PR i 和 FR i (1≤ i ≤ m )：1)∀ t 1 ∈ PR i [ h 1 ][ edp h 1 +1,…, NP h 1 ]，如果对于所有1≤ i ′≤ m 并且 i ′≠ i ， t 1 . PI ∉ π PI ( PR i ′ [ h 1 ][1,…, pnp h 1 ])，那么 t 1 可以被剪切； 2)∀ t 2 ∈ FR i [ h 2 ][ edf h 2 +1,…, NF h 2 ]，如果对于所有1≤ i ′≤ m 并且 i ′≠ i ， t 2 . PI ∉ π PI ( FR i ′ [ h 2 ][1,…, pnf h 2 ])，那么 t 2 可以被剪切.

定义3. 给定具有 n 个元素的度量列表 R i ( PI , A i , PI ptn )， EGBFT i 是 R i 上的指数间距bloom filter表，如果它满足条件：1)| EGBFT i |=lb n ；2) EGBFT i ( b )表示在 R i [1,…,2 b ]的 PI 属性上构建的bloom filter(1≤ b ≤lb n ).

TMS算法为每一个有序度量列表分片构建指数间距bloom filter表.要执行分数剪切，给定 PR i [ h 1 ] (1≤ h 1 ≤ N AP )，TMS算法根据计算的 pnp h 1 ，将

载入内存.类似地，给定 FR i [ h 2 ] (1≤ h 2 ≤ N AF )，TMS算法根据计算的 pnf h 2 ，将

载入内存.在其执行过程中，TMS算法根据载入的EGBFT元组判断当前读取的元组是否可被分数剪切.

给定选择属性 S 1 , S 2 ,…, S D ，选择属性网格 SAL 的第 MXH 层的子空间数量是(2 D ) MXH .如果 D 的值较大，TMS算法将生成大量的子空间，这也将导致文件系统的较大的维护费用，此外，给定同样的多维选择P，较大的 D 值也将使得TMS算法涉及到较多的相关分片.例如，给定 D =12， MXH =3，TMS算法需要维护68 719 476 736个子空间.

观察1. 虽然选择属性的维度可能较大，但是提交的查询通常只涉及到较小数量的选择属性.

观察2. 在实际应用中，选择属性的查询频率通常服从Zipfian分布.

基于以上的观察，令 S 1 , S 2 ,…, S D 的查询频率分别是 f 1 , f 2 ,…, f D ，不失一般性，令 f 1 ≥ f 2 ≥…≥ f D ，并且查询频率符合具有参数 z 的Zipfian分布，即

为处理高维选择属性，我们限制用来构建单个选择属性网格的选择属性数量，将 S 1 , S 2 ,…, S D 划分成大小为 GS 的组，即 G 1 ={ S 1 , S 2 ,…, S GS }， G 2 ={ S GS +1 , S GS +2 ,…, S GS + GS }，…， G D

GS ={ S D - GS +1 , S D - GS +2 ,…, S D }，并且为每一个组构建选择属性网格.在这种情况下，TMS算法将维护数据表 T 的

个副本，但是有效减少了需要维护的总的子空间数量.例如给定 GS =3， MXH =3以及 D =12，TMS算法只需要维护4个组，并且每个组只需要生成512个子空间.

根据观察2，如果磁盘空间大小有限，我们甚至可以不需要为每个组都构建选择属性网格，而是只选择具有较高查询频率的几个组.这样，我们不但可以有效减少需要的磁盘空间，而且还可以满足绝大多数的查询需求.例如给定 GS =3， z =2以及 D =12，只为第1个组构建选择属性网格也可以覆盖87%的查询.

给定多维选择P，TMS算法首先计算P和 G 1 ， G 2 ，…， G D

GS 的交.不失一般性，令 G 1 是具有和P最多的公共选择属性的组.例如给定 G 1 ={ S 1 , S 2 , S 3 }， G 2 ={ S 4 , S 5 , S 6 }， G 3 ={ S 7 , S 8 , S 9 }以及 G 4 ={ S 10 , S 11 , S 12 }，P={( l 1 ≤ S 1 ≤ u 1 ) and ( l 2 ≤ S 2 ≤ u 2 ) and ( l 4 ≤ S 4 ≤ u 4 )}，TMS算法将在 G 1 构建的选择属性网格上执行.因为P中不包括 S 3 ，TMS算法利用{( l 1 ≤ S 1 ≤ u 1 )且( l 2 ≤ S 2 ≤ u 2 )且(min S 3 ≤ S 3 ≤max S 3 )}来确定相关子空间集合.当然，此时所有的相关子空间都是和P部分相交.接着，采用如3.3节和3.4节的方法来计算Top- k 结果.

4 性能评价

本节评价算法的性能.我们利用Java语言实现TMS算法，jdk版本为jdk-7u21-windows-x64，实验在LENOVO ThinkCentre工作站上执行(Intel ® Core TM i7-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算法，考虑到文件系统的负载，选择属性网格的最大层次设置为3.

我们从不同方面评价TMS算法的性能：元组数量 n 、结果数量 k 、涉及到的选择属性数量 d 、涉及到的评价属性数量 m 、选择度 s 和相关系数 p .实验参数设置如表2所示：

Table 2 Parameter Settings

表2 实验参数设置

其中， l j 和 u j 分别表示多维选择在属性 S j 上的上界和下界值.

类似地，实验用来评价具有类别选择属性的表的 Top- k 查询如下：

其中， a j 是属性 S j 的特定值.当然，在类别选择属性上，选择属性网格结构不需要划分整个的数据空间，而是根据不同的属性组合来对数据表执行水平划分.

给定 n =10×10 8 ， s =0.001， m =3， d =3， p =0，实验1评价不同结果数量下TMS算法的性能.如图4(a)所示，TMS算法比LBE算法快2.79倍.随着需要返回更多的结果数量时，LBE算法的执行时间增长较快，从48.956 s增长到68.598 s.相对而言，TMS算法的执行时间增长幅度较小，这是由于选择评价的费用占据了总的执行费用的大部分.如图4(b)所示，LBE算法读取的元组数量比TMS算法多71.68倍.这里，读取的元组数量是度量列表中读取的元组数量和选择列表中读取的元组数量之和.剪切操作的效果如图4(c)和图4(d)所示，其中，选择剪切比是被选择剪切操作丢弃的元组数量和读取的所有元组数量的比值，分数剪切比是被分数剪切操作丢弃的元组数量和未被选择剪切操作丢弃的元组数量的比值.由于选择属性和度量属性的独立分布，这里的分数剪切效果可以反应真实的分数剪切效果.如图4(c)和图4(d)所示，选择剪切操作可以丢弃72%的元组，分数剪切操作可以丢弃70%～77%元组.图4(d)中虚线表示理论的分数剪切比例.分数剪切的剪切比随着结果数量的增加而降低，这符合理论分析的结果.

给定 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%之间.我们可以看到，随着元组数量的增加，分数剪切比逐渐增大，这也符合理论分析的结果.

给定 n =10×10 8 ， k =10， s =0.001， m =3， p =0，实验3评价不同选择属性数量下的TMS算法性能.实验3假设多维选择在涉及到的选择属性上具有相等的选择度.在确定相关网格单元时，如果多维选择中的属性数量少于构建 SAL 使用的属性数量(例如多维选择不包括 S j 属性，算法在多维选择条件上增加min S j ≤ S j ≤max S j )，否则，算法直接忽略选择条件上多余的选择属性.需要注意的是，这只是在确定相关网格单元，不影响算法的正确执行.如图6(a)所示，TMS算法比LBE算法快1.72倍.我们看到TMS算法的执行时间随着选择属性增大而迅速增长，给定选择度，更多的选择属性使得每个选择属性上的选择度增大，从而增加了涉及到的网格单元的数量.如图6(b)所示，LBE算法读取的元组数量比TMS算法多97.89倍.如图6(c)所示，多维选择涉及到更多的网格单元也使得选择剪切比例的下降.由于选择属性和度量属性的独立性，如图6(d)所示，当选择属性数量增大时，分数剪切比表现出增长趋势，但是真实剪切比仍然没有达到理论剪切比.

给定 n =10×10 8 ， k =10， s =0.001， d =3， p =0，实验4评价不同度量属性数量下的TMS算法性能.如图7(a)所示，TMS算法比LBE算法快3.98倍.随着涉及到的度量属性数量的增加，2个算法的执行时间都快速增长.如图7(b)所示，LBE算法读取的元组数量比TMS算法多137.96倍.根据计算公式 dp ( n , m , k )，TMS算法的扫描深度与度量属性数量成指数关系，这也解释了TMS算法的读取的元组数量的快速增长.选择剪切操作的效果如图7(c)所示，其剪切比例基本保持在72%.根据3.4.2节的分析，更多的度量属性使得分数剪切比例下降，如图7(d)所示，实验结果符合理论分析结果.

给定 n =10×10 8 ， k =10， m =3， d =3， p =0，实验5评价不同选择度下的TMS算法性能.如图7(a)所示，TMS算法比LBE算法快5.88倍.当选择度增大时，LBE算法的执行时间首先下降，然后逐渐增加.这是由于，当选择度较小时，评价多维选择条件的费用较小，而读取有序度量列表的费用则较大，反之亦然.因此，图8(a)中的LBE算法的变化趋势是这2个因素的整合结果.当然，当选择度较大时，TMS算法涉及到更多的网格单元，从而增加了TMS算法的执行费用.如图8(b)所示，LBE算法读取的元组数量比TMS算法多72.11倍，并且读取元组数量的变化趋势类似于图8(a)的变化趋势.如图8(c)所示，更大的选择度使得查询涉及到更多的网格单元，从而减少了选择剪切比例.如图8(d)所示，分数剪切比首先增加，然后下降.这是由于，更大的选择度使得更多的元组满足查询条件，根据3.4.2节的分析，更多的元组满足查询条件也使得分数剪切比例增加，这解释了 s =10 -5 到 s =10 -3 的变化趋势，但是，随着选择度进一步提高，相关的网格单元的数量也增长较快，分配到每个单元的剪切深度就相应减少，采用EGBFT元组执行分数剪切操作使得剪切深度扩展到2的最小的指数间距上界，从而降低分数剪切比例.

给定 n =10×10 8 ， k =10， s =0.001， m =3， d =3，实验6评价不同相关系数下的TMS算法性能.如图9(a)所示，平均来看，TMS算法比LBE算法快3.99倍.很明显，随着相关系数的增大，2个算法的执行时间都下降，但是下降的速率不同，这取决于不同算法的执行方法.如图9(b)所示，LBE算法读取的元组数量比TMS算法多73.22倍.如图9(c)所示，选择剪切比例基本维持在72%.从图9(d)看到，随着相关系数从负值增大到正值，分数剪切的比例迅速增大，从不到10%增长到接近80%.

给定 n =10×10 8 ， d =3， m =3， p =0，实验7比较在不同结果数量下的TMS算法和ranking cube算法的性能.在实验7中，选择属性是类别类型的，并且每个选择属性的基数设置为8，那么满足多维选择条件的元组比例是1

512.在ranking cube的每个单元中，元组根据基于几何的划分来进行组织，我们为每个度量属性的值域设置8个等长的桶.为提供ranking cube的优化性能，我们只保留每个元组的查询处理需要的属性.如图10(a)所示，ranking cube比TMS算法快4倍.图10(b)解释了ranking cube的执行时间的优势的原因，该算法的I

O费用比TMS算法少了一个数量级.图10(c)给出了需要执行多维选择评价的元组数量，我们看到，该数值随着结果数量的增加而增大.由于在类别选择属性上，相关的元组都满足多维选择，所以实验7不提供多维选择剪切的结果.如图10(d)所示，虽然随着结果数量的增加其剪切比例降低，TMS算法的分数剪切可以丢弃超过82%的候选元组.

5 相关工作

作为多个领域中一种重要的数据操作，Top- k 查询得到了研究人员的广泛关注 [1] .在海量数据环境中，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 查询，该方法实际上执行的是 k NN查询，不同于本文考虑的多维选择查询.Stupar等人 [4] 考虑处理基于集合选择的Top- k 查询，即预先给定需要的元组ID集合，然后计算满足条件的查询结果.但是，该方式只考虑一个数值属性的情况，而且基于集合的选择条件也过于特殊.Dong等人 [5] 考虑具有类别选择属性和数值度量属性的多维选择Top- k 查询，在选择属性上构建ranking cube来分布元组，每个单元内的元组采用基于几何信息划分方式组织成不同基本块.查询处理阶段，算法从最可能包括查询结果的基本块开始扫描，从而快速计算查询结果.但是，ranking cube方法只能处理类别选择属性，无法处理一般情况下(数值选择属性)的多维选择Top- k 查询.

6 结论

本文分析发现，现有方法无法有效处理海量数据上多维选择Top- k 查询.因此，本文提出一个新的基于有序列表的TMS算法，该算法利用层次化的选择属性网格来对数据执行水平划分，并且每个网格单元对应的分片按列模式存储.给定多维选择，TMS算法首先确定相关的网格单元，这有效减少了需要读取的元组数量.TMS算法利用双排序方法来渐进评价度量列表分片元组的多维选择结果，并提出有效的选择剪切和分数剪切操作来进一步减少需要处理的元组数量.本文实验表示TMS算法比现有算法具有较大的优势.

[1]Ilyas I, Beskales G, Soliman M. A survey of top- k query 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- k retrieval on massive data[J]. IEEE Trans on Knowledge and Database Engineering, 2015, 27(10): 2687-2699

[3]Bruno N, Chaudhuri S, Gravano L. Top- k selection 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- k queries 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- k queries 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- k aggregation 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- k queries 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- k query processing on massive data[J]. Information Processing Letter, 2011, 111(11): 524-532

[10]Han Xixian, Li Jianzhong, Gao Hong. An efficient top- k dominating algorithm on massive data[J]. Chinese Journal of Computers, 2013, 36(10): 2132-2145 (in Chinese)(韩希先, 李建中, 高宏. 一种有效的海量数据top- k domi-nating查询算法[J]. 计算机学报, 2013, 36(10): 2132-2145)

[11]Heo J, Cho J, Whang K. Subspace top- k query 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- k queries[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- k queries[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- k queries 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- k query 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- k Queries with Multi-Dimensional Selections on Massive Data

( School of Computer Science and Technology , Harbin Institute of Technology , Harbin 150001)

Abstract： In many applications, top- k query 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- k query. It is found that the existing algorithms cannot process the query on massive data efficiently. A sorted-list based algorithm TMS (top- k with multi-dimensional selection) is proposed to process top- k query 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.

Key words： top- k with multi-dimensional selection (TMS) algorithm; sorted list; selection attribute lattice (SAL); progressive selection evaluation; pruning

基金项目： 国家“九七三”重点基础研究发展计划基金项目(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).

TMS:一种新的海量数据多维选择Top- k 查询算法