论文部分内容阅读
传统Skyline查询没有考虑用户的个人偏好,对所有用户返回相同的结果集。关键词Skyline查询,结合对象的标签、评论等文本信息,基于用户输入的关键词,返回符合用户偏好的Skyline点集。现有的关键词Skyline查询通常采用两个独立的步骤：先使用关键词过滤出相关数据集,然后在此集合上进行Skyline查询得到最终结果集。由于中间结果集是关键词相关的,无法预先构建索引,因此第二阶段只能采用无索引的Skyline算法(如BNL和DC等),耗时很长而且不满足渐进性。此外,随着大数据时代的到来,单节点计算难以支持海量数据的Skyline查询。针对以上问题,本文提出了两种新的关键词Skyline查询算法,主要研究成果如下：(1)提出了一种基于层次结构的关键词Skyline算法LKS(Layer-based Keyword Skyline Algorithm),包括离线生成的分层Skyline索引结构和基于文本特征值的关键词过滤和裁剪算法,能有效裁剪无效节点,避免全局比对,不仅提高查询效率,而且还缩短了响应时间。(2)通过对Map-Reduce算法模型的研究和总结,提出了一种新的并行算法(Grid Partitioning Keyword Skyline computation algorithm based on MapReduce, MR-GPKS),使用Hadoop来解决海量数据的关键词Skyline查询。MR-GPKS使用网格来对数据空间进行划分,因而可以根据网格之间的支配关系,提前排除那些被支配的网格空间。此外,对节点中的文本属性,离线生成网格倒排索引,在线查询时可以快速锁定有效的网格空间。整个过程都使用Map-Reduce模型进行处理,有效提高海量数据的处理效率。对比实验表明,两种算法都取得了较好的效果,有效提高了关键词Skyline查询的效率。