The Study Of Location-based Multi-source Skyline Query In Road Network

With the continuous development of database technology, the amount of data that can becollected and used increases sharply. How to find out most interesting information from hugeamounts of data for helping people make effective decision has become an important researchtopic. Skyline computing is to retrieve the data points that are not dominated by any otherdata point. Because of the potential application in visualization, multi-objectivedecision-making, Skyline query has become one of the hot topics in database and informationretrieval field in recent years,.The Location Based Service (LBS) has been proposed with the development of wirelesscommunication technology and smart mobile terminal, and has been widely applied in themilitary, logistics, transportation and other fields. How to supply the special Skyline queryservice based on the location of multi-source, considering the positional relationship betweenthe data points with more than one query point in the traditional Skyline query, has becomethe new direction of the Skyline study. According to the study of the status quo of Skylinequery based on the location of multi-source at home and abroad, for the shortcomings ofexisting solutions, the paper proposes two new solutions, devises algorithm for each solution,and verifies the feasibility and efficiency of each solution by experiments.This paper makes contributions from the following aspects,1It studies the status quo of Skyline query algorithms at home and abroad, analyzes theexisting solutions for the Location-based Multi-source Skyline Query, and summarizes theweakness of the existing solutions in aspect to the query results and computational time cost.2To reduce the computational complexity and enhance the meaning of the query results,it proposes the Dimension Reduction-based Multi-source Skyline Query. Corresponding to it,the paper designs one native algorithm based on preprocessing and domination relationship.To optimize the space efficiency of the native algorithm, the paper proposes the most simpledomination graph, which is a new data structure to efficiently store the dominationrelationship in the dataset. Based on the special data structure, it develops a heuristic searchalgorithm. It focuses on analyzing and comparing the time and space efficiency between thetwo algorithms. It sets up extensive experimens, using the synthetic data set experiments, inconsistent with the theoretical analysis, the experiments' results show that the graphic basedalgorithm improves the space efficiency ennormensously and performs well on timeefficiency.3To return the specified number of Skyline points in the Location-based Multi-source Skyline Query, it proposes the Top-K based Multi-source Skyline Query. Corresponding to it,this paper gives an algorithm based on the sorting in each dimension, this algorithm canprogressively ouput the number of K skyline point which has the smallest average distance tothe query points without accessing the entire dataset. Then this paper analyzes its timeefficiency and progressiveness. It sets up experiments to verify the algorithm,using syntheticdata set and actual NBA players' dataset, the experiment's results show the algorithm canrespond quickly and progressively return the results.