Research On Efficient Keyword Skyline Query Algorithm

General skyline query which does not take user preference into account returns the same result to all customers. However, keyword skyline query, making use of tags or comments of objects, can return certain result based on the keywords, which meets the customer’s preference. Typical keyword skyline splits query process into two steps——keyword matching and skyline query respectively. As the intermediate result is related to the keywords, the index cannot be drawn in advance. In this way, only non-index skyline algorithm like BNL and DC can be used in step two, which takes long time and is not progressive. Besides, with the coming of the "big data" era, it’s inefficient to process keyword skyline query of massive data on single node.To solve the above problems, we propose two new algorithms on keyword skyline query. The main achievements are listed below:First, the LKS (Layer-based Keyword Skyline Algorithm) approach is proposed, including SLS(Skyline Layer Structure) drawn off-line, filtering and pruning algorithm based on signature, to promote performance.What’s more, based on the research of MapReduce model in Hadoop, we propose an efficient parallel algorithm—MR-GPKS(Grid Partitioning Keyword Skyline computation algorithm based on MapReduce),used to dealing with keyword skyline query of massive data. We design a grid partitioning scheme to divide the data space into partitions, and employ a bitstring to represent the partitions. Besides, we take advantage of inverted index bitstring generated off-line to seek out the potential partitions. Thanks to the MapReduce model adopted in the whole procedure,the algorithm is effective and efficient in processing keyword skyline query of massive data.Comparative experiments show that both algorithms achieve good results and improve the efficiency of keyword skyline query effectively.