Research On Compression Technology Of Private Car Trajectory Data

With the continuous and rapid development of the urban economy,the contradiction between the rapid growth of car ownership and the limited urban road resources is increasing.Among them,private cars have a higher proportion,and the number of private car ownership has risen rapidly.In China,according to statistics of the Ministry of Public Security,as of December 31,2019,the number of cars had reached 260 million vehicles,compared with the end of 2018,an increase of 21.22 million vehicles,an increase of 8.83%.On the one hand,the high ownership of private cars exacerbates urban problems,such as energy consumption,traffic congestion and environmental pollution.On the other hand,with the development of technologies such as positioning technology,information processing and data mining,private cars are calculated.Vehicle positioning technology has brought convenience to obtain large-scale accurate trajectories continuously.In today’s intelligent transportation systems,large-scale vehicle trajectory data has high utilization value.In most cases,the widely used Global Positioning System(GPS)positioning technology can accurately provide real-time vehicle position information.In the era of big data,quantities of data reach almost incomprehensible proportions.As we move forward,we are going to have more and more huge data collections.Data mining technology can extract valuable information from a large amount of trajectory data,which requires the collection of a large amount of high-quality original trajectory data.Location-based services use trajectory data to provide services to users,but massive trajectory data bring considerable challenges to the storage,transmission,query,analysis,and mining.For example,the transmission and storage of raw trajectory data consume too much network bandwidth and storage capacity,and at the same time,increases the number of communication between the sensor and the server and increases the power consumption.Besides,the query,analysis,and mining of massive original trajectory data also cause problems such as delay.Therefore,an efficient trajectory database compression technology is urgently needed.The trajectory data compression originates from the basic data compression technology.Based on the simplification of multiple line segments,the original trajectory is replaced by a polyline connected by multiple line segments,and the polyline is simplified to reduce the trajectory points.The most original trajectory compression algorithm is only to reduce the number of trajectory points.The line segment simplification process does not consider various important information contained in the trajectory data itself,such as time,speed,direction,position,etc.However,the compression result reduces the storage pressure because of much loss of trajectory information.Therefore,trajectory compression should be based on retaining important trajectory information,and trajectory points with little information should be regarded as redundant data to be deleted to achieve the purpose of compression.On the other hand,if there are too few trajectory points reserved,although it is beneficial to transmission,storage,etc.The information contained in the trajectory data will be seriously lost,making the compressed trajectory unable to express the original trajectory and losing the meaning of trajectory compression.Therefore,the requirement for trajectory data compression is to reduce the number of track points while taking into account the retention of track information.With the in-depth study of trajectory data,more and more compression algorithms are based on the characteristics of trajectory data,such as retaining trajectory points with important spatial information in the original trajectory data.At the same time,external factors constrain the trajectory data generated by some moving objects.For example,the trajectory of a taxi is limited by the road network structure and traffic conditions.Road network-based trajectory compression methods are used to process the trajectories generated by moving objects restricted by geographic space.For trajectory data updated in real-time,it is also possible to refer to road network information for pre-judgment,which has high compression efficiency and can handle offline and online trajectory data.Due to the limitations of the road network,it is impossible to process trajectory data based on the road network.Also,with the proposition and development of semantic concepts,semantics have been gradually introduced and applied to the field of trajectory compression.The collected trajectory data is usually composed of latitude,longitude,altitude,time,and other data.But because the trajectory data is not visualized,users often cannot read and understand the trajectory.So a series of simple and clear descriptions can be used to explain the trajectory data.The semantic-based trajectory compression splits the entire trajectory data with events and replaces the trajectory points in the direction change with an edge to achieve the compression purpose.After compression,only a part of the motion state of the corresponding moving object is retained,thereby significantly reduced space overhead.Although the compressed semantic trajectory is easier to read and understand than the original trajectory,the latitude,longitude,altitude,and other information of the original trajectory have been completely lost,which affects the subsequent use of the compressed trajectory.The application support for location services is not high,so the semantic-based application of the trajectory compression method is very limited.This research is the long-term cooperation between the project team and Shenzhen Maigu Technology Co.,Ltd.of products and the establishment of a specialized research laboratory that provides prerequisites for obtaining private car trajectory data.Based on the above cooperation,an integrated navigation and positioning system is developed.Private car trajectory data mainly obtained by collecting onboard OBD location terminal equipment.The vehicle-mounted OBD position terminal equipment is composed of three major functional modules: a GPRS communication module with a built-in SIM card,a GPS positioning module,and an OBD interface module.It can collect vehicle trajectory data in real-time,and on this basis,provide vehicle owners with anti-theft tracking,electronic fences,trip management,and vehicle fault diagnosis services.The private car trajectory data covers all major cities in the country.Based on the above navigation and positioning system,this paper conducted the following research:(1)This thesis proposed a map-matching method based Hidden Markov model combined with the Viterbi algorithm and the Baum-Welch algorithm.First,we determine the parameter values corresponding to the parameters of the HMM model.Hidden Markov models can solve three types of problems.About the evaluation problem,the most probable system to the observed sequence is matched and using a forward algorithm to solve it.Regarding the decoding problem,we need to determine the hidden sequence that is most likely to produce the observed sequence.In the HMM-based matching algorithm,for each GPS trajectory point,a set of candidate road segments is first determined.Each candidate road segment is represented as a hidden state in the Markov chain and has the observation state probability,which is the possibility of observing whether the GPS point matches the candidate road segment.If the GPS point is found to be very close to a particular road segment,a higher probability value is assigned to this road segment.Then,calculate the weights for the edges connecting each pair of adjacent vertices in the Markov chain,that is,the state transition probability.The maximum likelihood path with the highest observed state probability and state transition probability is found on the Markov chain.Generally,the Viterbi algorithm is used to solve the problem.Through the Viterbi algorithm,the maximum likelihood path with the highest observed state probability and state transition probability can be taken.About the learning problem,the series of observations that are most likely to be provided by the model parameters are needed to determine.The Baum-Welch algorithm is used to solve this problem.The Baum-Welch is the Expectation-Maximization algorithm,used to train HMM parameters.It uses the backward and forward algorithm in each iteration.The algorithm uses the principle of dynamic programming to efficiently compute the values that are required to obtain the posterior marginal distributions in two passes.The forward and backward algorithm is not used to train HMM parameters,but only to smooth: compute the marginal possibility of a sequence of states.The Baum-Welch algorithm estimates the discrete emission probabilities or the mean and covariance associated with the state.The Baum-Welch algorithm can be run a given number of times to study the parameters of the model.During this procedure,the internal representation of learnable parameters is updated after each iteration.The transition provided probability function should take two objects from the state space and return the probability of moving from the first object to the second argument.Because this is handled internally regardless,the function does not need to be normalized,i.e.,sum to1 over all states.The Hidden Markov Model requires a function that returns the emission probability of a certain observation when given the observation and the state.In map-matching method based Hidden Markov model,after an object has been instantiated,the methods such as decode,which returns the estimated hidden state sequence,can be accessed and estimated.In the simulation,assuming that a road network is set up in the form of a directed graph,the proposed map-matching algorithm matches a series random of points to the side road.The Frobenius norm is used to evaluate the performance of the proposed algorithm.(2)About trajectory compression method for private car data,this thesis proposed the trajectory compression method based on the prediction model.In most cases,the use of private cars reflects the travel needs of users who have used the car for a long time,and its frequent travel patterns reflect the characteristics of regular travel.Private cars tend to drive in specific areas,such as residential areas,workplaces,and hot spots.Therefore,the private vehicle trajectory has special trajectory characteristics,based on user behavior;the trajectory can be relatively theoretically stable.Thus,trajectory compression based on a predictive model is possible.This method decomposes trajectories into two components-spatial and temporal trajectory information-for which different prediction algorithms are proposed.The spatial compression algorithm used the prediction by the partial matching algorithm to predict road segments.This process is divided into two stages:one is to generate a prediction model from historical data;the second is to compress the trajectory through the prediction model.The temporal compression algorithm is also based on a prediction model learned using training data.However,instead of predicting road segments,the goal is to predict a vehicle travel-times.The experiment is conducted with a trajectory dataset of collected 6000 object ID private cars in Shenzhen in six months from January 2016 to June 2016.The compression methods are implemented and tested via Python code compiled with version 3.6.3.The dataset of this experiment divided into 80% of the trajectories are used for training,and 20%are used for compression.Experiments show that the advantage of trajectory compression based on prediction model is that it can help trajectory compression has better performance.The proposed methods achieve high compression ratios in terms of spatial and temporal compression for real datasets.