Research And Implementation Of Temporal Spatial Query Processing Based On Map-Reduce Framework

Temporal Spatial data management is the unity of temoral data management and spatial data management. It includes temporal factor and spatial factor. It is mainly used to store and manage spatial objects whose position and shape changed with time. Temporal spatial data management can be applied in fields such as research of environment changing, regional management oriement and cadastral management. At the same time, cloud computing based on Map-Reduce framework is becoming a popular computing model as its features of low price and fault tolerance.Queries such as Top-k, k nearest neighbor and skyline are commonly used in temporal and spatial data management. These are commonly decomposable. However, when these queries take on Map-Reduce framework, the intermediate results cannot be well filtered, which limited the scope of application. This paper proposes a new framework of Map-Filter-Reduce based on origin Map-Reduce framework to solve this problem.First, the charateristics of dealing decomposable queries such as Top-k, k nearest neighbor and skyline on Map-Reduce framework are discussed. Then Map-Filter-Reduce framework and its interfaces are illustrated and scalability and fault tolerance are analyzed.Secondly, based on Map-Filter-Reduce framework schedule strategies such as Lazy, Eager, Hybrid and Prepositive are introduced and compared.Thirdly, this paper proposes algorithms of using Map-Filter-Reduce framework to solve Top-k, k nearest neighbor and skyline queries. The correctness of these algorithms ard discussed.Lastly, the proposals are evaluated with rich dataset. The evaluation results show that the Map-Filter-Reduce framework outperforms the origin Map-Reduce framework on query time and number of intermediateim results. The results also show that Map-Filter-Reduce framework has good scalability.