有效处理海量数据多维选择top-k查询

摘要

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