Uncertain trajectory privacy protection method based on graph partition

Abstract

The invention discloses an uncertain trajectory privacy protection method based on graph partition. The method comprises the following steps: step (1) data preprocessing: preprocessing an original trajectory data set so as to make uncertain trajectories intersect on time dimension, wherein each uncertain trajectory has the same sampling point number; step (2) correlation degree constructing: extracting time features, direction features and distance features of the preprocessed trajectory data to compute the correlation degree between unknown trajectories; step (3) undirected graph constructing: mapping the trajectory data set to an undirected graph, wherein each node in the undirected graph represents one trajectory, a weight of a side between the nodes represents the correlation degree of two corresponding uncertain trajectories; and step (4) undirected graph partitioning: partitioning the undirected graph by use of a greedy algorithm to form a plurality of clusters containing k uncertain trajectories. Through the adoption of the method disclosed by the invention, a user can balance the data information loss and privacy level according to a privacy protection requirement.

Description

technical field [0001] The invention relates to the field of graph theory, in particular to an uncertain trajectory privacy protection method based on graph division. Background technique [0002] In the era of smart cities and the Internet of Things, it is easy for people to collect various data, such as location, time, speed, etc., from mobile devices such as mobile phones equipped with GPS. The collected data can provide people with location-based services (LBS), such as finding the nearest gas station, hospital, etc. Due to the low accuracy of the collection equipment or collection errors, there may be errors in the longitude and latitude collected. While location-based service LBS brings convenience to users, it also has potential safety hazards. The release of uncertain trajectory data is easy to leak the privacy of users, so the privacy processing of the release of uncertain trajectory data in offline scenarios becomes extremely important. [0003] In the research ...

AI Technical Summary

Problems solved by technology

The uncertainty of trajectories will affect the calculation of the distance between trajectories and the similarity of trajectory directions; secondly, this method does not take into account the similarity of trajectories in the time dimension, but has already processed trajectories into time in the preprocessing stage of trajectory data. In the same interval, the time difference is eliminated, which makes the algorithm less feasible

Images