Affiliation of Author(s):计算机科学与技术学院/人工智能学院/软件学院

Journal:计算机学报

Key Words:Top-k查询;网格索引;分区;概要;动态;

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

Translation or Not:no

Date of Publication:2018-07-11

Co-author:邓丹苹,bohan li,zhengwei,Liu Liang,李雪

Correspondence Author:qxz