刘显敏 李建中 高 宏

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

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

刘显敏 李建中 高 宏

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

在许多应用中，Top-k是一种十分重要的查询类型，它在潜在的巨大数据空间中返回用户感兴趣的少量数据.Top-k查询通常具有指定的多维选择条件.分析发现：现有算法无法有效处理海量数据的多维选择Top-k查询.提出了一个基于有序列表的TMS(top-kwith 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查询已经获得研究人员的广泛……