Skyline Queries For Moving Objects Based On MapReduce

With the vigorous development of the Internet and the Internet of things, the appearance of Big Data hasbrought a great challenge to storage, process and query of data. Skyline query, which is applied in different fieldssuch as multi-objective decision and data visualization, has been researched extensively. At present, traditionalresearch of Skyline query focuses on centralized and distributed environments. However, these environments arenot well satisfied for Big Data processing. As a distributed and parallel framework, MapReduce can process thecomputing of Big Data. This paper studies the problem of Skyline query for moving object under MapReduceparallelframework.Themainresearchwork andcontributionsinclude:1. The problem of load balancing is solved by using angle-based partition and a kind of filtering method isintroduced to improve computing efficiency. On the basis of those methods, a static Skyline algorithmand an event tracking algorithm named MR-Track are implemented respectively. The static Skylinealgorithm reduces duplication of computing by pre-computing and storing the static Skyline sets, thuscomputing time is reduced. MR-Track algorithm defines events influencing change of Skyline setaccording the distance function of moving object and data points and improves the efficiency by trackingand updating local Skyline sets. These new algorithms are compared with an existed algorithm byexperiments,andthe resultsshowthatthe newalgorithmsare effectiveandefficient.2. For the situation of the uncertain location of moving object, the paper researches MR-DTrack algorithmwhich is an efficient algorithm of continuous probabilistic Skyline updating based on MapReduce. Bypre-computing change time of dominating relationships among data points according to distancefunctions, the dominating relationship set of data points is updated, and a filtering strategy is used todelete non-Skyline points to improve computing efficiency. A series of experiments prove theeffectivenessofMR-DTrackalgorithm.