数据流环境下的关键词轮廓查询算法

Keyword Skyline Query Algorithm Over Streaming Data

本文针对滑动窗口模型下的连续关键词轮廓查询问题,提出了一种流数据环境下的关键词轮廓查询算法.其通过对当前窗口进行划分,过滤掉大部分不可能成为查询结果的对象,克服了数据间时序关系对算法性能带来的影响.本文还提出了关键词轮廓网格索引KSG(Keyword Skyline Grid),实现了对各分片中对象的有效关键词过滤以及轮廓过滤.另外,本文通过调整分片粒度,实现了窗口的有效划分.最后,本文通过大量实验对所提算法的性能进行了评估,实验结果表明,本文所提算法PSKSWI(Partition-based Continuous Keyw ord Skyline w ith Index)与basline算法相比,查询效率提高了71%,与不带索引的查询算法PSKS(Partition-based Continuous Keyw ord Skyline)相比,查询效率提高了32%.

To solve the problem of continuous keyword skyline query over sliding window Jthis paper propose akeyword skyline queiy algorithm over streaming data.By partitioning the current window,the algorithm filters out most objects that cannot be the queiy result,and overcomes the influence of timing relation between data on the performance of the algorithm.After that,this paper propose theindex KSG(Keyword Skyline Grid)to realize the effective keyword filtering and skyline filtering for the objects in each partition.In addition,by adjusting the granularity of partition Jthis paperrealize the effectively partition of window and improve the queiy efficiency.Lastly,a great deal of experiments are carned out to evaluate the perfoimance of the proposed algorithm.Experimental results show that the queiy efficiency of the proposed algorithm PCKSWI(Partition-based Continuous Keyword Skyline with Index)is 71%highei than that of the basline algorithm,and 32%highei than that of the algorithm PCKS(Partition-based Continuous Keywoid Skyline)without index.