一种基于改进网格多维TTI索引的动态Top-k查询算法

• 作者: 刘亮 李博涵 李雪 秦小麟 邓丹苹 郑伟
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: Top-k查询 网格索引 分区 概要 动态
• 年，卷（期）: 2019,（8）
• 所属期刊栏目: 大数据
• 页码范围: 1827-1844
• 页数: 18页
• 分类号: TP311
• 字数: 17941字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.01827

摘要

Top k查询是目前海量数据在动态环境中高效处理的重要方法之一.在许多实际应用中,满足用户偏好的top-k查询一般由两个部分组成:选择条件和排序函数.用户可自行设置排序函数,也可选择对不同数据子集进行查询.在传统数据库领域中已经对top-k算法进行了深入的研究,但是现有的方法不适用于大量目标对象的属性值发生动态变化的情况.在查询过程中由于目标对象的属性值发生改变可能导致查询结果的改变,从而对算法性能有更高的要求.围绕动态top-k计算问题,在网格索引的基础上提出了TTI索引,通过TTI索引中的概要信息高效计算网格k支配能力并划分影响区和自由区.根据划分的区域裁剪数据集并降低数据动态变化时需重新计算发生的概率.实验中采用多种数据集进行测试,分别与top-k、RankCube和CIA算法进行了比较.实验结果验证了算法的有效性,实验数据表明在静态情况下,该文算法的查询效率可比传统top-k算法最多快至8倍,动态情况下可比传统top-k算法最多快10倍.