Research On Competitive Location Selection Over Moving Objects

With the advent of the data age,more and more data with temporal and spatial information is stored and used for analysis and mining.Spatio-temporal data can not only characterizes the geographic location generated by the data and the movement history of the object,but also describes the movement behavior,law and trend between the individual and the whole,and helps people build the global relationship between time,space,objects,behavior and other elements.As a research branch of spatio-temporal data,the problem of spatial location selection not only has important theoretical research significance but also has practical application value.The research can be widely used in spatial decision support systems,such as urban planning,logistics and other application scenarios.This thesis studies the location selection problem of maximizing the influence considering competitive factors among facilities in moving scenes.Given the historical location data of objects and the location data of the competing facilities,taking into account the mobility of objects and the competitiveness of existing facilities,we select locations from the candidate location set to establish service facilities.The locations we select can influence the most moving objects in the competitive environment.In response to this problem,the following research work has been completed in this thesis:Firstly,we have extracted the spatio-temporal features of the moving object.For trajectory data,the kernel density estimation method in probability statistics and grid strategy are used to extract the motion data characteristics of the object.It can identify multiple reference location data of the object,and effectively remove the invalid or even incorrect data information such as noise points,outliers,and passing points.At the same time,the check-in data as the location where the object often appears play the same role as the reference location data.Secondly,we have established an influence model and a competition model.Based on the extracted spatial features of moving objects,a model of the influence relationship between moving objects and service facilities has been established.For objects with multiple moving locations,the many-to-many influence relationship between service facilities and objects is determined based on the Euclidean spatial probability cumulative influence model.On this basis,a competitive relationship model between facilities and moving objects is designed.There are competitive relationships among multiple facilities that influence the same object.After identifying the service facilities that have competitive relationships,the competitive influence value is evaluated for the candidate locations according to the evenly divided cumulative probability model,which is used as the location selection criterion.Finally,we have designed and evaluated efficient location selection algorithms and solutions.In order to improve the efficiency of processing a large number of moving objects,the competition facility data uses an R-tree-based spatial data index structure,and the moving object related data uses a two-dimensional array storage structure.Three solutions are designed in this thesis: the baseline solution,the improvement solution based on the existing algorithm and the influence pruning solution.The baseline solution is realized by the baseline algorithm designed in this thesis based on the linear scanning process.The improvement solution adopts the existing pruning algorithm to improve the calculation process of the influence relationship in the baseline algorithm.The influence pruning solution uses the influence pruning algorithm designed in this thesis to reduce the calculation redundancy and further improve the data query efficiency.The influence pruning algorithm combines the influence relationship pruning rule and the influence value pruning rule.It prunes objects that are not influenced by candidates and objects that are influenced by inferior candidates.The experiment is carried out on real data sets with different data distribution characteristics and large synthetic data sets.All solutions are evaluated.Experiment results show that the solution designed in this thesis can solve the problem of location selection in a competitive environment under dynamic scenarios.Comparing with the baseline solution and the improvement solution,the influence pruning solution has higher computational efficiency in scenarios that have large data sets and require higher data accuracy.