# A Trajectory Privacy Protect Method Based on Location Pair Reorganization

Authors: Wanqing Wu; Wenlong Shang; Ruohe Lei; Xin Yang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

With the rapid development of mobile Internet and communication technology, location-based services (LBS) are widely used in our daily life. The server stores a large amount of user location data, and these location data constitute user trajectories. If trajectory information on the server is leaked, it will seriously endanger users’ privacy. Trajectoryk-anonymity technology is one of the most important methods to protect the privacy of user trajectory. However, current trajectory k-anonymity methods have less discussion on the semantic of stop point when selecting dummy trajectory, which leads to the fact that attacker can still exclude the dummy trajectory from the k-anonymity set and infer the real trajectory by combining background knowledge with the semantic information of stop points. To address this problem, this paper decomposes the real trajectory into location pairs set; the set consists of start-end points and stop points. According to the similarity of location pairs, the similar location pairs in history trajectory set are used to generate dummy trajectory: firstly, extracting the start-end points and stop points from real trajectory and assigning semantic to them. Then, based on the semantic, temporal, and geographical attributes, eligible location pairs are selected from history trajectory set to construct equivalence class. Finally, according to the location pairs in equivalence class, k−1 dummy trajectories are generated to form a k-anonymity set. We evaluate our method thoroughly with real dataset. The results show that our method achieve an effective data availability and higher privacy protection than other methods.


---

## Body

## 1. Introduction

In recent years, with the rapid development of 5G technology and the Internet of Things (IoT), smart city is gradually becoming a reality. As an important cornerstone of smart city, location-based services (LBS) are used in more and more areas, such as check-in, road conditions, and social networking [1, 2]. When a user requests an LBS service, he submits his current location to the service provider. The service provider stores user’s location sequence on the server as a trajectory. Some service providers regularly release trajectory data to governments and research institutions for analysis and mining [3–5]. For example, the U.S. government updates and optimizes transportation facilities based on users’ GPS trajectory data [6]; the Chinese government constructs epidemic prevention maps based on COVID-19 patients’ trajectories, etc.However, the servers that store trajectory data are not absolutely secure. If the service provider is attacked by attacker, the trajectory data may be leaked without any protection. By analysing the spatial-temporal information in user’s trajectory, attacker combined with background knowledge can deduce user’s hobbies, mobility patterns, health status, work and home address, and other personal information, which can cause economic losses and even threaten user’s personal safety. Accordingly, scholars at home and abroad pay a large amount of attention to this thing: how to better protect the trajectory privacy.The existing trajectory privacy protection methods can be divided into three categories: trajectoryk-anonymity method [7–14], suppression [15, 16], and differential privacy [17–21]. The suppression method assumes that attacker has some specific background knowledge, protecting trajectory privacy by suppressing sensitive information in the trajectory. However, suppression method requires predetermined sensitive information; if sensitive information is not set properly, it can seriously damage data availability. Differential privacy ensures unconditional privacy, i.e., individual information cannot be obtained by analysing specified statistical data. However, differential privacy can only protect a limited amount of information. Compared to the first two methods, trajectory k-anonymity method transforms the 1 : 1 relationship between user and trajectory into k:1 relationship between multiple trajectories and user by generating k−1 dummy trajectories. It is the main method to achieve trajectory privacy protection because of its simple implementation and flexible application scenarios.How to choose the dummy trajectory is the key issue in trajectoryk-anonymity. For availability purposes, dummy trajectory in k-anonymity set should contain the most possible available information. For privacy purposes, dummy trajectory and real trajectory must be indistinguishable. Based on these two demands, many trajectory k-anonymity methods are proposed [12, 14, 22, 23]. In the similarity calculation process, these methods calculate the similarity based on all location points in the trajectory, which leads to huge computational effort and the low data availability after privacy processing. In fact, not every location point in trajectory is necessary for privacy protection [24]. It is the stop points in the user’s trajectory that really reveal the user’s privacy. According to this idea, many methods calculate the similarity between trajectories based on the stop points in the trajectory, which can reduce the calculation volume while maintaining a level of privacy [13]. However, the above methods do not consider the semantic impact in trajectory privacy protection. In a trajectory, stop points combined with semantic attributes reveal the user’s identity and action patterns. By analysing the semantic information of stop points, attacker can easily identify certain dummy trajectories from k-anonymity set or even obtain the user’s real trajectories directly.As shown in Figure1, suppose Tom, an employee of a company, leaves the company at 18:00 on Wednesday to watch a movie at the cinema and then returns to his home. Tom’s trajectory is represented by Tra2. According to trajectory k-anonymity method, now, we generate the dummy trajectories Tra1 and Tra3 to protect Tom’s trajectory. The three trajectories have greater similarity in trajectory shape, geographic location, and overall direction. However, by analysing trajectory’s stop points, attacker can still find the difference between three trajectories. By extracting stop points from three trajectories, attacker can get the semantic trajectory of three trajectories as: A1Planetarium⟶C1KFC⟶E1Hostel;A2Company⟶C2Cinema⟶E2Community; E3Hospital. Compared with Tra1 and Tra2, Tra3has only one stop point, and hospital’s working hours is from 8:00 to 18:00, so attacker speculates that Tra3 is likely to be a dummy trajectory. In addition, although both Tra1 and Tra2 have three stop points, attacker knows that Tom is an employee of a company according to the background knowledge. So, attacker can infer that Tra2 is more consistent with Tom’s action pattern and then determine that Tra2 is the real trajectory.Figure 1
Example of identifying dummy trajectory.To solve the problem that low trajectory utilization and stop point’s semantic lead to trajectoryk-anonymity failed, this paper proposes a trajectory privacy protect method based on location pair reorganization (DSTPP). Specifically, we decompose the real trajectory into a set of location pairs consisting of start-end point and stop points. For each location pair, we select eligible location pairs from the history trajectory set for constructing candidate location set. Finally, we use the location pairs in candidate location set to generate dummy trajectories that satisfy the similarity measure; k−1 dummy trajectories are generated to form a k-anonymity set.The main contributions of this paper are as follows:(i)
We design a candidate location set generation method. For each location pair in the real trajectory, according to the defined location pair similarity, the eligible location pairs are selected from the history trajectory dataset and added to the candidate location. Location pairs in the candidate location have high spatial-temporal and semantic similarity and can be used to generate dummy trajectory that match user action patterns(ii)
We design a dummy trajectory generation method that conforms to user action patterns. According to the similarity measures, dummy trajectory is similar to real trajectory in terms of geography, semantics, and direction(iii)
We evaluated the privacy and availability of DSTPP with two similar methods [13, 25] on real dataset [26–28]. The experimental results show that the trajectory k-anonymity set constructed by DSTPP meets the privacy protection requirements and has high data availabilityThe rest of this paper is structured as follows: relevant work is reviewed in Section2. Section 3 provides a description of relevant concepts and measure standards. Section 4 elaborates the trajectory privacy protect method based on location pair reorganization. In Section 5, we compare with existing solutions in terms of availability and privacy, and this paper is concluded in Section 6.


## 2. Related Work

Typical privacy-preserving methods include suppression, generalization, and perturbation. Among them,k-anonymity technique based on generalization are widely used in trajectory privacy protection. The k-anonymity model was proposed by Sweeney [29] in 2002, which is the first complete model of privacy protection. This model prevents attacker from uniquely identifying a specific user in the dataset, making it impossible to obtain further accurate information about that user. Gruteser and Grunwald [30] first applied k-anonymity techniques to LBS services. For the purpose of protecting user privacy, they replace the user’s exact location points with a location region that contains k location points, so the probability of users being identified is reduced. However, this method cannot resist the privacy leakage problem caused by trajectory data leakage, nor can it resist the background knowledge attack. For this reason, trajectory k-anonymity method was developed. This type of method constitutes a k-anonymity set that includes k−1 dummy trajectories and real trajectory. k trajectories in the anonymous set have indistinguishability, which reduces the identification probability of real trajectories to 1/k. According to the way of generating dummy trajectory, the existing trajectories k-anonymity can be divided into two categories: local method and integral method.For a trajectory, user really cares about certain specific geographic location, not all locations. Based on this idea, the local method is proposed. The local method means only protecting trajectory’s sensitive locations byk-anonymity, not the whole trajectory. Pan et al. [31] considered the user’s movement direction and velocity when generating the generalized region, ensuring the user trajectory’s privacy while improving the service quality. Zhang et al. [9] proposed a double-k mechanism to protect user’s sensitive locations. They send the user’s sensitive location and k−1 fake locations to k anonymizers. Then, each anonymizer is k-anonymized for a location. This method has a higher degree of privacy. However, this method has a high computational volume, and the trajectory availability is lower. To address this problem of high computational volume, Zhou and Wang [11] combined fog computing and k-anonymity to reduce the computational consumption of generating k-anonymity sets. Zhao et al. [10] consider the start-end points of user’s trajectory are sensitive locations. Based on user’s behaviour, they generate secure start-end candidate point set for constructing dummy trajectory. Ye et al. [32] propose protect location points within sensitive areas; they build the cloaking region for sensitive areas, which contains another k similar POIs to the sensitive place, and randomly select one to replace the sensitive place. However, the local method requires presetting sensitive locations. If the sensitive locations are set improperly, it can seriously affect data availability. In addition, user privacy can also be leaked based on location points in nonsensitive areas.In order to solve the defects caused by the local method, the integral method is proposed. The integral method is to selectk−1 dummy trajectories that are similar to real trajectory to form a k-anonymity set. Xu et al. [12] evaluated the trajectory similarity based on four features: angle, velocity, time, and space. Then, they selected k−1 historical trajectories that were similar to the real trajectories to form a k-anonymity set. Wang et al. [22] propose constituting k-anonymous set by exchanging the locations of neighbour nodes, protecting user privacy by interchanging the location between neighbour nodes on the K-core subnet of the relationship network. But this method ignores the privacy needs of different location points, which leads to insufficient availability. According to the spatial and temporal characteristics of trajectory data, Li et al. [23] propose a data partitioning method to store and calculate trajectory, which reduces computational volume. Liu et al. [25] generated k−1 dummy locations for each location point in the real trajectory and randomly generated dummy trajectory based on these dummy locations. The dummy trajectory generated by this method have some unreachable positions, so the data availability and privacy are insufficient. Dai et al. [33] proposed simplifying real trajectory into a trajectory that is only consisting of stop points. Then, each stop points constructs a k-anonymity set. The k-anonymity set contains k−1 semantically similar location points. According to these k-anonymity sets, generate dummy trajectory randomly. The dummy trajectory generated by this method only considers stop points, which may pass through unreachable locations. Meanwhile, it does not consider whether the direction of dummy trajectory is similar to real trajectory. Xu et al. [13] evaluated the trajectory similarity based on the number of stop points and average velocity. Then, select k−1 historical trajectories that are similar to the real trajectories to form a k-anonymity set. The integral method selects history trajectory or fake trajectory as dummy trajectory. However, although using fake trajectory can ensure the similarity requirement, the fake trajectory may pass through or be at unreachable locations. Therefore, the availability and privacy are insufficient. If using history trajectory, the problem that the trajectory number is insufficient may be faced; meanwhile, although the whole trajectory does not satisfy the similarity requirement, some trajectory segments in these trajectories can still be utilized. But the integral method cannot utilize these trajectory segments.In conclusion, existing dummy trajectory selection methods have the defects in low trajectory utilization and pay less attention to stop point’s semantic, which leads to the fact that attacker combining with background knowledge can still exclude the dummy trajectory from thek-anonymity set. In order to solve above problem, this paper constructs dummy trajectory by the location pairs. Location pairs consist of stop points in history trajectory set. The history trajectory is taken from real user’s trajectory, so dummy trajectory does not pass through or reach unreachable locations. At the same time, we defined semantic, geographical, and directional similarities, which ensure the similarity between dummy trajectory and real trajectory. This method can effectively resist background knowledge attack and improve data availability.


## 3. Preliminaries

To facilitate reader’s understanding of the various system parameters used in this paper, Table1 provides a description of the various system parameters used in this paper.Table 1
Summary of notation.
SymbolNotionDTraiHistorical trajectory dataset/ith trajectory in historical trajectory datasetT=tii=1,2,⋯,nReal trajectory/ith location pointSEM=slii=1,2,⋯,nSemantic trajectory/ith semantic location pointTC=tcii=1,2,⋯,nTrajectory equivalence class/ith trajectory in the classSTC=stcii=1,2,⋯,nSemantic trajectory equivalence class/ith semantic trajectoryCan=Cii=1,2,⋯,nSet of candidate location/ith candidate locationFS=fsii=1,2,⋯,nFake semantic trajectoryFTThe set ofk−1 dummy trajectories forming the k-anonymity setF=fii=1,2,⋯,nFake trajectory inFTsimG/simSsimAGeographical similarity/semantic similarity/directional similarity


### 3.1. Related Concepts

Definition 1.
GPS trajectory: the GPS trajectory can be represented as a polyline in three-dimensional space (two-dimensional coordinates and time dimension), denoted asT=t1,t2,,t3,⋯,te−1,te, where tk=xk,yk,timek indicates that the position xk,yk of the trajectory T at time timek,t1<t2<⋯<te, and e is the number of sampling points of real trajectory T.The location points in real trajectory can be divided into two categories: moving point and stop point. Stop point is a location where the user stays (speed is 0 and lasts for a period of time) or visits (speed is not 0, but repeatedly wanders around a location). Moving point is a location that the user simply passes through. The specific description of stop point is given by Definition2.Definition 2.
Stop point: a stop point is a geographic area where user stays within a distance thresholdθd longer than a time threshold θt. In the real trajectory T, the subtrajectory is denoted as SubT=<ti,ti+1,⋯,tj>, where, ∀k∈i,j, Disgeoti,tk≤θd, and Distimeti,tj≥θt. Then, <ti,ti+1,⋯,tj> can be combined into a stop point s. Denote as: s=x,y,timea,timel,timed, where:
(1)x=∑k=ijtk.xSubT,(2)y=∑k=ijtk.ySubT,represent the latitude and longitude of stop point s, respectively. tk.x and tk.y denote the longitude and latitude of location point tk.timea denotes the time of entering the stop point s, timel denotes the time to leave the stop point s, and timed denotes the stay time at stop point s. The values are calculated using the first position point ti, the last position point tj, and the time difference between tj and ti in the SubT, respectively. According to Definition 1 and Definition 2, trajectory can be composed of stop points and moving points between top points.Definition 3.
Semantic category: the semantic category of location point can be represented by points of interest (POI). Each location pointxi,yi has an independent POI, and the semantic category can be obtained through Chinese POI standard [34].According to Chinese POI standard, POI semantic category is divided into three levels: major category, middle category, and minor category. Each level consists of a 2-digit code. The codesL1 for the major category, L2 for the middle category, and L3 for the minor category are arranged in order to form a fixed 6-bit semantic code (L1, L2, and L3), as shown in Figure 2.Definition 4.
Semantic location point: the semantic location pointsl can be represented as <loc,cat,time>, where loc denotes the center coordinates of semantic location point; cat denotes the semantic category of semantic location point, consisting of the triplet <L1,L2,L3>; and time represents the temporal characteristics of semantic location point, which consists of the triplet <timea,timel,timed>. The three attributes indicate visit time, leave time, and stay time, respectively.Definition 5.
Semantic trajectory: a semantic trajectorySEM is an ordered list of start-end points and a set of semantic points:
(3)SEM=sl1,sl2,⋯,sln.Definition 6.
Semantic distancedsem: dsem refers to the semantic difference between two semantic location points. It is expressed by semantic encoding difference of two semantic location points:
(4)dsem=l1,l2,l3SEM1−l1′,l2′,l3′SEM2=10000l1−l1′+100l2−l2′+l3−l3′.Figure 2
Example of the semantic information levels and the semantic codes.According to the specification:When the semantic distancedsem∈0,100, it means that two semantics differ only in minor category. The two points have a high degree of similarity.When the semantic distancedsem∈100,9999, it means that two semantics differ only in middle category. The two points have a low degree of similarity.When the semantic distancedsem∈100,9999, it means that two semantics differ only in major category. No similarity between the two points at all.Definition 7.
Geographical distancedgeo: dgeo refers to the geographical difference between two semantic location points, which can be calculated by the Euclidean distance:
(5)dgeo=x2−x12+y2−y12.Definition 8.
Location pair similarity [14]: suppose <sli−1,sli> and <cli−1,cli> are the location pairs in real semantic trajectory SEM and semantic trajectory equivalence class STC, respectively. Two location pairs satisfy the location pair similarity if they satisfy the following conditions:
(1)
dsemsli−1,cli−1<δsem,dsemsli,cli<δsem(2)
dgeosli−1,cli−1<δgeo,dsemsli,cli<δgeo(3)
dtimesli−1,cli−1<δtime,dtimesli,cli<δtimewhere, δsem, δgeo, and δtime are semantic distance threshold, geographic distance threshold, and time threshold, respectively. Equations (1) and (2) ensure that location pairs are semantically and geographically similar. Equation (6) ensures that two location pairs are similar in velocity and time period by calculating the location time difference.


### 3.2. Similarity Measure

In thek-anonymity set, we want the generated dummy trajectory to be semantically and geographically indistinguishable from real trajectories. In this subsection, geographic similarity and semantic similarity are proposed to evaluate the differences between dummy trajectory and real trajectory.We first give two theorems and utilize them to prove that the difference between two probability distributions is the expectation of the difference between the features of the corresponding positions.Theorem 9.
SupposeX0 is a random variable with probability distribution PX0. X=Xii=1,2,⋯,n is a set of random variables, the corresponding probability distribution is PXi. For each Xi, there is a probability distribution difference with X0, the probability distribution difference between PX0 and PXi is denoted by dX0,Xi. The probability of the probability distribution difference between PX0 and PXi is PXiXi. Therefore, the probability distribution difference dX0,X1,⋯,Xi between X0,X1,⋯,Xi and X0 is the expectation of each difference, i.e.,
(6)dX0,X1,⋯,Xi=∑i=1nPXiXi∙dX0,Xi.Proof.
PXiXi and dX0,Xi are functions of variables X0 and Xi. When the value of X0 remains unchanged, the results of two functions depend only on Xi. If Xi is also deterministic, then both PXiXi and dX0,Xi are constants. That is, there is a one-to-one correspondence between PXiXi and dX0,Xi. Therefore, PXiXi can be regarded as the probability of dX0,Xi in all probability distributions difference. Accordingly, dX0,X1,⋯,Xi is the expectation of probability distribution difference d=dX0,Xii=1,2,⋯,n and its probability d=PXiXii=1,2,⋯,n.Theorem 10.
SupposeX′ and Y′ are two sets of random variables with probability distributions PX′=xi and PY′=yi, where X′=xii=1,2,⋯,m and Y′=yii=1,2,⋯,m. For ∀xi and yi, the probability distributions difference of PX′=xi and PY′=yi is dxi,yi. The probability of probability distributions difference between PX′=xi and PY′=yi is PY′Y′=yi. The probability distribution difference between X′ and Y′ is the expectation dX′,Y′ of all dxi,yi, i.e.,
(7)dX′,Y′=∑i=1mPY′Y′=yi∙dxi,yi.Proof.
For∀xi′∈X′, according to Theorem 9, the difference between xi′ and Y′ is ∑i=1mPY′Y′=yi,X′=xi′∙dxi′,yi. Then, dX′,Y′=∑i=1m∑i=1mPY′Y′=yi,X′=xi′∙dxi′,yi. However, for dX′,Y′, if i≠i′, then PY′Y′=yi,X′=0 and dxi′,yi are 0. That means dX′,Y′=∑i=1mPY′Y′=yi∙dxi,yi. Therefore, the probability distribution difference of X′ and Y′ is the expectation dX′,Y′ of all dxi,yi.For∀F∈FT and real trajectory T, semantic distance, geographic distance, and its corresponding probability distribution (the probability of distance difference) depend only on F. Therefore, according to Theorem 10, we define geographical similarity and semantic similarity between F and T as the expectation of distance difference.Definition 11.
Visit probability:Pvp represents the probability of a user visiting location P, which is calculated as follows:
(8)Pvp=NumpN,where Nump represents the number of people visiting location P and N denotes the total number of people.The larger the value ofPvp, the more people visit location P, and the higher the probability that location P will be visited.Definition 12.
Geographical similarity [14]: for ∀F∈FT and real trajectory T, DGti,fi denotes the geographic distance between ti and fi, and the probability distribution of geographic distance is denoted by PGfi. The geographical similarity between T and F can be defined as the expectation of all DGti,fi:
(9)∑i=1nPGfi∙DGti,fi.Attacker’s goal is to infer user’s real trajectory from thek-anonymity set. In order to achieve this goal, attacker usually assumes a location (called hypothetical location) to be the real location and evaluate the probability that this location is the true location by background knowledge. In the candidate location Ci, we assume that ei is the hypothetical location. Without considering background knowledge, the probability that ei is the true location is denoted by PeiCi. In this paper, there is an equal probability that any location in Ci is assumed to be the true location, so, PeiCi=1/k. For fi, the background knowledge that fi is the hypothetical location ei is attacker believes fi is the true location ti, i.e., the joint probability Pfi,ti. So, the probability that fi is assumed to be ti is Pfi,ti∙PeiCi. The higher the probability, the higher the probability that ei is ti, which means that attacker believes that fi and ti are more similar. Therefore, we use this probability to calculate the probability distribution of geographic distance PGfi:
(10)PGfi=1−Pfi,ti∙PeiCi=1−Pvfi∙Pvti∙PeiCi,According to the above formula, the geographical similaritysimGF,T between F and T is calculated as follows:
(11)simGF,T=1zg∑i=1n1−PGfi∙DGti,fi,where 1/zg is a constant used to normalize the geographical similarity value to lie in the range [0,1]. zg is the sum of the maximum location distance difference in each candidate location Ci and user location ti:
(12)zg=∑i=1n∑j=1CimaxDGti,fj.Definition 13.
Semantic similarity: for∀F∈FT and real trajectory T, DSti,fi denotes the semantic distance between ti and fi, and the probability distribution of the semantic distance is denoted by PSfi. The semantic similarity between T and F can be defined as the expectation of all DSti,fi:
(13)∑i=1nPSfi∙DSti,fi.Similar to Definition12, for Equation (13), we still calculate PSfi by Pfi,ti∙PeiCi:
(14)PSfi=1−Pvfi∙Pvti∙PeiCi.According to the above formula, the semantic similaritysimSF,T between F and T is calculated as follows:
(15)simSF,T=1zs∑i=1n1−PSfi∙DSti,fi,where 1/zS is a constant used to normalize the geographical similarity value to lie in the range [0,1]. zS is the sum of the maximum semantic distance difference in each candidate location Ci and user location ti:
(16)zs=∑i=1n∑j=1CimaxDSti,fj.Attacker can also analyse the trajectory’s movement direction in the published trajectory set. If a trajectory differs from other trajectories, attacker deduces that this trajectory is likely to be a dummy trajectory. Therefore, it is necessary to ensure the movement direction similarity between dummy trajectory and real trajectoryT. We use the least squares method to fit the slope of the overall trajectory movement direction and determine whether dummy trajectory direction is similar to real trajectory direction by the slope ratio. The slope is calculated as follows:
(17)l=∑i=1nxiyi−nx¯y¯∑i=1nxi2−nx¯2=∑i=1nxi−x¯yi−y¯∑i=1nxi−x¯2,where x¯=1/n∑i=1nxi; y¯=1/n∑i=1nyi.Definition 14.
Directional similarity: for∀F∈FT and real trajectory T, according to Equation (17), calculate the slope of two trajectories lF and lT. The directional similarity between T and F is calculated as follows:
(18)simAF,T=lFlT,simAF,T∈0,1.
The larger the value ofsimAF,T, the more similar the overall direction of the two trajectories.


## 3.1. Related Concepts

Definition 1.
GPS trajectory: the GPS trajectory can be represented as a polyline in three-dimensional space (two-dimensional coordinates and time dimension), denoted asT=t1,t2,,t3,⋯,te−1,te, where tk=xk,yk,timek indicates that the position xk,yk of the trajectory T at time timek,t1<t2<⋯<te, and e is the number of sampling points of real trajectory T.The location points in real trajectory can be divided into two categories: moving point and stop point. Stop point is a location where the user stays (speed is 0 and lasts for a period of time) or visits (speed is not 0, but repeatedly wanders around a location). Moving point is a location that the user simply passes through. The specific description of stop point is given by Definition2.Definition 2.
Stop point: a stop point is a geographic area where user stays within a distance thresholdθd longer than a time threshold θt. In the real trajectory T, the subtrajectory is denoted as SubT=<ti,ti+1,⋯,tj>, where, ∀k∈i,j, Disgeoti,tk≤θd, and Distimeti,tj≥θt. Then, <ti,ti+1,⋯,tj> can be combined into a stop point s. Denote as: s=x,y,timea,timel,timed, where:
(1)x=∑k=ijtk.xSubT,(2)y=∑k=ijtk.ySubT,represent the latitude and longitude of stop point s, respectively. tk.x and tk.y denote the longitude and latitude of location point tk.timea denotes the time of entering the stop point s, timel denotes the time to leave the stop point s, and timed denotes the stay time at stop point s. The values are calculated using the first position point ti, the last position point tj, and the time difference between tj and ti in the SubT, respectively. According to Definition 1 and Definition 2, trajectory can be composed of stop points and moving points between top points.Definition 3.
Semantic category: the semantic category of location point can be represented by points of interest (POI). Each location pointxi,yi has an independent POI, and the semantic category can be obtained through Chinese POI standard [34].According to Chinese POI standard, POI semantic category is divided into three levels: major category, middle category, and minor category. Each level consists of a 2-digit code. The codesL1 for the major category, L2 for the middle category, and L3 for the minor category are arranged in order to form a fixed 6-bit semantic code (L1, L2, and L3), as shown in Figure 2.Definition 4.
Semantic location point: the semantic location pointsl can be represented as <loc,cat,time>, where loc denotes the center coordinates of semantic location point; cat denotes the semantic category of semantic location point, consisting of the triplet <L1,L2,L3>; and time represents the temporal characteristics of semantic location point, which consists of the triplet <timea,timel,timed>. The three attributes indicate visit time, leave time, and stay time, respectively.Definition 5.
Semantic trajectory: a semantic trajectorySEM is an ordered list of start-end points and a set of semantic points:
(3)SEM=sl1,sl2,⋯,sln.Definition 6.
Semantic distancedsem: dsem refers to the semantic difference between two semantic location points. It is expressed by semantic encoding difference of two semantic location points:
(4)dsem=l1,l2,l3SEM1−l1′,l2′,l3′SEM2=10000l1−l1′+100l2−l2′+l3−l3′.Figure 2
Example of the semantic information levels and the semantic codes.According to the specification:When the semantic distancedsem∈0,100, it means that two semantics differ only in minor category. The two points have a high degree of similarity.When the semantic distancedsem∈100,9999, it means that two semantics differ only in middle category. The two points have a low degree of similarity.When the semantic distancedsem∈100,9999, it means that two semantics differ only in major category. No similarity between the two points at all.Definition 7.
Geographical distancedgeo: dgeo refers to the geographical difference between two semantic location points, which can be calculated by the Euclidean distance:
(5)dgeo=x2−x12+y2−y12.Definition 8.
Location pair similarity [14]: suppose <sli−1,sli> and <cli−1,cli> are the location pairs in real semantic trajectory SEM and semantic trajectory equivalence class STC, respectively. Two location pairs satisfy the location pair similarity if they satisfy the following conditions:
(1)
dsemsli−1,cli−1<δsem,dsemsli,cli<δsem(2)
dgeosli−1,cli−1<δgeo,dsemsli,cli<δgeo(3)
dtimesli−1,cli−1<δtime,dtimesli,cli<δtimewhere, δsem, δgeo, and δtime are semantic distance threshold, geographic distance threshold, and time threshold, respectively. Equations (1) and (2) ensure that location pairs are semantically and geographically similar. Equation (6) ensures that two location pairs are similar in velocity and time period by calculating the location time difference.


## 3.2. Similarity Measure

In thek-anonymity set, we want the generated dummy trajectory to be semantically and geographically indistinguishable from real trajectories. In this subsection, geographic similarity and semantic similarity are proposed to evaluate the differences between dummy trajectory and real trajectory.We first give two theorems and utilize them to prove that the difference between two probability distributions is the expectation of the difference between the features of the corresponding positions.Theorem 9.
SupposeX0 is a random variable with probability distribution PX0. X=Xii=1,2,⋯,n is a set of random variables, the corresponding probability distribution is PXi. For each Xi, there is a probability distribution difference with X0, the probability distribution difference between PX0 and PXi is denoted by dX0,Xi. The probability of the probability distribution difference between PX0 and PXi is PXiXi. Therefore, the probability distribution difference dX0,X1,⋯,Xi between X0,X1,⋯,Xi and X0 is the expectation of each difference, i.e.,
(6)dX0,X1,⋯,Xi=∑i=1nPXiXi∙dX0,Xi.Proof.
PXiXi and dX0,Xi are functions of variables X0 and Xi. When the value of X0 remains unchanged, the results of two functions depend only on Xi. If Xi is also deterministic, then both PXiXi and dX0,Xi are constants. That is, there is a one-to-one correspondence between PXiXi and dX0,Xi. Therefore, PXiXi can be regarded as the probability of dX0,Xi in all probability distributions difference. Accordingly, dX0,X1,⋯,Xi is the expectation of probability distribution difference d=dX0,Xii=1,2,⋯,n and its probability d=PXiXii=1,2,⋯,n.Theorem 10.
SupposeX′ and Y′ are two sets of random variables with probability distributions PX′=xi and PY′=yi, where X′=xii=1,2,⋯,m and Y′=yii=1,2,⋯,m. For ∀xi and yi, the probability distributions difference of PX′=xi and PY′=yi is dxi,yi. The probability of probability distributions difference between PX′=xi and PY′=yi is PY′Y′=yi. The probability distribution difference between X′ and Y′ is the expectation dX′,Y′ of all dxi,yi, i.e.,
(7)dX′,Y′=∑i=1mPY′Y′=yi∙dxi,yi.Proof.
For∀xi′∈X′, according to Theorem 9, the difference between xi′ and Y′ is ∑i=1mPY′Y′=yi,X′=xi′∙dxi′,yi. Then, dX′,Y′=∑i=1m∑i=1mPY′Y′=yi,X′=xi′∙dxi′,yi. However, for dX′,Y′, if i≠i′, then PY′Y′=yi,X′=0 and dxi′,yi are 0. That means dX′,Y′=∑i=1mPY′Y′=yi∙dxi,yi. Therefore, the probability distribution difference of X′ and Y′ is the expectation dX′,Y′ of all dxi,yi.For∀F∈FT and real trajectory T, semantic distance, geographic distance, and its corresponding probability distribution (the probability of distance difference) depend only on F. Therefore, according to Theorem 10, we define geographical similarity and semantic similarity between F and T as the expectation of distance difference.Definition 11.
Visit probability:Pvp represents the probability of a user visiting location P, which is calculated as follows:
(8)Pvp=NumpN,where Nump represents the number of people visiting location P and N denotes the total number of people.The larger the value ofPvp, the more people visit location P, and the higher the probability that location P will be visited.Definition 12.
Geographical similarity [14]: for ∀F∈FT and real trajectory T, DGti,fi denotes the geographic distance between ti and fi, and the probability distribution of geographic distance is denoted by PGfi. The geographical similarity between T and F can be defined as the expectation of all DGti,fi:
(9)∑i=1nPGfi∙DGti,fi.Attacker’s goal is to infer user’s real trajectory from thek-anonymity set. In order to achieve this goal, attacker usually assumes a location (called hypothetical location) to be the real location and evaluate the probability that this location is the true location by background knowledge. In the candidate location Ci, we assume that ei is the hypothetical location. Without considering background knowledge, the probability that ei is the true location is denoted by PeiCi. In this paper, there is an equal probability that any location in Ci is assumed to be the true location, so, PeiCi=1/k. For fi, the background knowledge that fi is the hypothetical location ei is attacker believes fi is the true location ti, i.e., the joint probability Pfi,ti. So, the probability that fi is assumed to be ti is Pfi,ti∙PeiCi. The higher the probability, the higher the probability that ei is ti, which means that attacker believes that fi and ti are more similar. Therefore, we use this probability to calculate the probability distribution of geographic distance PGfi:
(10)PGfi=1−Pfi,ti∙PeiCi=1−Pvfi∙Pvti∙PeiCi,According to the above formula, the geographical similaritysimGF,T between F and T is calculated as follows:
(11)simGF,T=1zg∑i=1n1−PGfi∙DGti,fi,where 1/zg is a constant used to normalize the geographical similarity value to lie in the range [0,1]. zg is the sum of the maximum location distance difference in each candidate location Ci and user location ti:
(12)zg=∑i=1n∑j=1CimaxDGti,fj.Definition 13.
Semantic similarity: for∀F∈FT and real trajectory T, DSti,fi denotes the semantic distance between ti and fi, and the probability distribution of the semantic distance is denoted by PSfi. The semantic similarity between T and F can be defined as the expectation of all DSti,fi:
(13)∑i=1nPSfi∙DSti,fi.Similar to Definition12, for Equation (13), we still calculate PSfi by Pfi,ti∙PeiCi:
(14)PSfi=1−Pvfi∙Pvti∙PeiCi.According to the above formula, the semantic similaritysimSF,T between F and T is calculated as follows:
(15)simSF,T=1zs∑i=1n1−PSfi∙DSti,fi,where 1/zS is a constant used to normalize the geographical similarity value to lie in the range [0,1]. zS is the sum of the maximum semantic distance difference in each candidate location Ci and user location ti:
(16)zs=∑i=1n∑j=1CimaxDSti,fj.Attacker can also analyse the trajectory’s movement direction in the published trajectory set. If a trajectory differs from other trajectories, attacker deduces that this trajectory is likely to be a dummy trajectory. Therefore, it is necessary to ensure the movement direction similarity between dummy trajectory and real trajectoryT. We use the least squares method to fit the slope of the overall trajectory movement direction and determine whether dummy trajectory direction is similar to real trajectory direction by the slope ratio. The slope is calculated as follows:
(17)l=∑i=1nxiyi−nx¯y¯∑i=1nxi2−nx¯2=∑i=1nxi−x¯yi−y¯∑i=1nxi−x¯2,where x¯=1/n∑i=1nxi; y¯=1/n∑i=1nyi.Definition 14.
Directional similarity: for∀F∈FT and real trajectory T, according to Equation (17), calculate the slope of two trajectories lF and lT. The directional similarity between T and F is calculated as follows:
(18)simAF,T=lFlT,simAF,T∈0,1.
The larger the value ofsimAF,T, the more similar the overall direction of the two trajectories.


## 4. Scheme Description

### 4.1. Scheme Framework

This scheme is designed to protect user’s trajectory privacy. To prevent attacker from identifying user’s real trajectory from thek-anonymity set. In this paper, we construct k−1 dummy trajectories based on stop point location pairs to form k-anonymity set, thus protecting user privacy and security. The scheme is divided into three steps:Trajectory preprocessing stage: based on the start time and end time of real trajectory, the trajectories with similar time periods are selected from the history trajectory datasetD. The trajectory equivalence class TC consists of these historical trajectories. According to Definition 2 and Definition 3, we extract stop points in real trajectory T and the equivalent class TC, then assign semantic to start-end points of T and all stop points to generate the corresponding semantic trajectory SEM and semantic trajectory equivalent class STC.Selection of candidate location stage. For each location pointsli in semantic trajectory SEM, we select the location points that satisfy Definition 8 from STC and then add them to candidate location Ci to form the candidate location set Can.
(1)
Dummy trajectory generation stage. We generate dummy semantic trajectoryFS based on candidate location set Can. If FS meets similarity measure, moving points between stop points in FS are also added to the trajectory FS to generate corresponding dummy trajectory F. Repeat this step until k−1 dummy trajectories are generated to form a k-anonymity set. The overall process is shown in Figure 3. We will then describe each step separately in chapter 4.Figure 3
System overview of scheme.


### 4.2. Trajectory Preprocessing

This subsection preprocesses real trajectory. It can be divided into the following two steps: (1) construct a trajectory equivalence classTC for T and add trajectories with similar time periods to TC; (2) extract stop points in real trajectory T and the equivalent class TC and assign semantic to them, and construct the corresponding semantic trajectory SEM and semantic trajectory equivalent class STC.


#### 4.2.1. Construct Trajectory Equivalence Class

Ink-anonymity set, if the time period of a trajectory is different from other trajectories, attacker may infer that this trajectory is a dummy trajectory. Therefore, we need to ensure that the trajectory in the equivalent class TC is similar to real trajectory T in terms of time period. According to the set time offset ∆t, if a trajectory Tra in history trajectory dataset D satisfies the following conditions:
(19)Tra.ts∈T.ts−∆t,T.ts+∆t,,Tra.te∈T.ts−∆t,T.ts+∆t,.Then,Tra is added to the equivalent class TC, where ts and te denote the start time and end time of trajectory Tra, respectively.The specific steps are shown in Algorithm1.Algorithm 1: Construct trajectory equivalence class
Input: Real trajectoryT; time offset ∆t; history trajectory dataset DOutput: Trajectory equivalent classTC1.TC⟵∅2.forallTra∈Ddo3.ifTra meets the candidate of Formula (19) then4.TC⟵TC∪Tra5.returnTCAlgorithm1 traverses the trajectories in the trajectory dataset D by a for-loop and calculates whether they satisfy Equation (19). The time cost of Algorithm 1 is numD, i.e., the algorithm time complexity is On.


#### 4.2.2. Construct Trajectory Equivalence Class

Stop point contains richer information than moving point, and attacker can identifyk-anonymity set’s dummy trajectory by analysing stop point. The dummy trajectory that constitutes the k-anonymity set have to be semantically similar to the real trajectories T. So, in this subsection, we extract stop points in real trajectories T and equivalence class TC and assign semantic to start-end points of T and all stop points to construct the corresponding semantic trajectory and semantic trajectory equivalence class STC.When the distance between a segment of consecutive location pointsti and tji≤j is less than the distance threshold θd and the interval time is greater than the time threshold θt, the location points from ti to tj are aggregated into a stop point. If the Euclidean distance between ti and tj is greater than the distance threshold θd, then ti and tj cannot be aggregated into a stop point. Next, the interval time between ti and tj−1 is calculated to determine whether it is greater than the time threshold θt, if the interval time is greater than the time threshold θt, then ti to tj−1 is aggregated as a stop point. If the interval time is less than the time threshold θt, the location points ti to tj are all moving points and repeat this operation from tj+1.For example, in the subtrajectorytr=t1,t2,⋯,t5,t6, Disgeot1,t5≤θd, Disgeot1,t6, and Distimet1,t5≥θt. We can aggregate the location points t1 to t5 as a stop point. After acquiring stop points, we assign semantic of the closest POI to stop point based on the PAT. The step is repeated, and the semantic trajectory is finally generated.The specific steps are shown in Algorithm2.Algorithm 2: Construct semantic trajectory
Input: Real trajectoryT; time threshold θt; distance threshold θd; point-of-interest setPATOutput: Semantic trajectorySem; Semantic trajectory equivalence class STC1.SEM⟵∅,STC⟵∅2.sl=assign_semt1,PAT3.SEM⟵SEM∪sl4.sl=assign_semte,PAT5.SEM⟵SEM∪sl6.whileallti∈t2,t3,⋯,te−1do7.j⟵i+18.whiletj∈t2,t3,⋯,te−1do9.ifDis_geoti,tj<θdthen10.ifDis_timeti,tj>θdthen11.sp=gen_spti,tj12.sl=assign_semsp,PAT13.SEM⟵SEM∪sl14.j⟵j+115.i⟵j+116.forallTc∈TCdo17.whilealltci∈Tcdo18.j⟵i+119.whiletcj∈Tcdo20.ifDis_geotci,tcj<θdthen21.ifDis_timetci,tcj>θdthen22.sp=gen_sptci,tcj23.cl=assign_semsp,PAT24.stc⟵stc∪cl25.j⟵j+126.i⟵j+127.STC⟵STC∪stc28.returnSEM,STCIn Algorithm2, lines 2-5 assign semantic to start-end points of real trajectory T and add them to semantic trajectory SEM. Lines 6-15 extract stop points in real trajectory T based on the threshold θt and distance threshold θd and assign semantic. Then, add these points to SEM. Lines 15-27 traverse the trajectories in the equivalence class TC, convert the trajectory to semantic trajectory, and add them to semantic trajectory equivalence class STC.Algorithm2 transforms real trajectory T into semantic trajectory SEM by two layers of while-loop. In the worst case, the time consumption is numT∗numT, and the time complexity is On2. Second, the trajectories in TC are traversed by a for-loop, and then, the equivalence class is transformed into semantic trajectory equivalence class STC by two layers of while-loop. In the worst case, the time consumption is numTC∗numT∗numT, and the time complexity is On3. Therefore, the total time consumption of Algorithm 2 is numTC∗T∗T+numT2, and the total time complexity is On3.


### 4.3. Construct Candidate Location Set

The purpose of this subsection is to select the location pairs used to construct the dummy trajectory. We traverse semantic trajectory SEM and compute the similarity of location pairs inSTC according to Definition 8. If there is a location pair that satisfies the condition, this location pair is added to the candidate location Ci and Ci+1. After traversing all position pairs, the composition of Can=C1,C2,⋯,Cn,=<C1,C2>,<C2,C3>,⋯,<Cn−1,Cn>.The specific steps are shown in Algorithm3.Algorithm 3: Construct candidate location set
Input: Semantic trajectorySEM; semantic trajectory equivalence class STC; locationpair similarity thresholdδsem,δgeo,δtimeOutput: Candidate location setCan1.Can⟵∅2.forall<sli,sli+1>∈SEMdo3.Ci⟵sli,Ci+1⟵sli+14.forallstc∈STCdo5.forallclj∈stcdo6.if <sli,sli> and <clj,clj+1>meets the candidate ofDefinition8then7.Ci⟵clj,Ci+1⟵clj+18.exit9.Can⟵Ci,Can⟵Ci+110.returnCanFor the location pair<sli,sli+1> in the semantic trajectory SEM, Algorithm 3 traverses each trajectory in STC. If there exists position pair similar to <sli,sli+1> in this trajectory, this location pair will be added to Ci and Ci+1. Then, traverse the next trajectory until all trajectories have been traversed. Algorithm 3 finally returns the candidate location set Can.Algorithm3 constructs the candidate location set Can by a three-level for-loop. The first level for-loop traverses the location pairs in SEM with a time consumption of numSEM. The second level for-loop traverses the trajectory in STC with a time consumption of numSTC. The third-level for-loop traverses the location pairs in the trajectory stc with a time consumption of numstc. Therefore, the total time consumption of Algorithm 3 is numSEM∗STC∗stc, and the time complexity is On3.


### 4.4. Construct Location Pair Graph

In the previous subsection, we picked candidate location for each semantic location point inSEM. The next goal is to generate k−1 dummy trajectories based on these candidate positions to form a k-anonymity set. If location points are randomly selected from each candidate location and combined into a dummy trajectory, the generated dummy trajectory may have some unreachable locations. Specifically, as shown in Figure 4, the solid line and dotted line represent the location pair that exist in Can and the location pair that do not exist in Can, respectively. A dummy trajectory consisting of location pairs <A1,B2> and <B2,A3> will pass through unreachable locations. So, attacker can easily identify this trajectory as dummy trajectory.Figure 4
Example of constructing fake trajectory.This subsection constructs the location pair graphG=V,E,W. Among them, V consists of all semantic location points in Can, and each semantic location point represents a node in G. ci is a location in the candidate position Ci and Eci,ci+1 is a directed edge connecting ci and ci+1. Wci,ci+1 is the weight of edge Eci,ci+1, and the value is a binary consisting of geographical similarity and semantic similarity. Algorithm 4 describes the graph generation process as follows.Algorithm 4: Construct location pair graph
Input: Semantic trajectorySEM; location candidate set Can; semantic trajectoryequivalence classSTCOutput: Location pair graphG1.E⟵∅,W⟵∅2.forallCi∈Cando3.forallcj∈Cido4.forallck,∈Ci+1do5.if<cj,ck,>∈STCthen6.E⟵Ecj,ck,7.W⟵Wcj,ck,8.returnGAlgorithm4 first traverses each candidate location Ci and picks locations from Ci and Ci+1 respectively to form the location pair <cj,ck,>. Next, determine whether the location pair <cj,ck,> exists in STC. If it exists, add Eci,ci+1 and Wci,ci+1 to the graph G.Algorithm4 constructs the location pair graph G by a three-level for-loop. The first level for-loop traverses the candidate location of Can, and the time consumption is numCan. The second level for-loop traverses location point cj in candidate position Ci, and the time consumption is numCi. The third level for-loop traverses the location point ck, in the candidate position Ci+1, and the time consumption of numCi+1. The total time consumption of Algorithm 4 is numCan∗Ci∗Ci+1, and the total time complexity is On3.


### 4.5. Constructk-Anonymity Set

The goal of this subsection is to generatek−1 dummy trajectories to form k-anonymity sets. These dummy trajectories are semantically, geographically, and directionally similar with real trajectories T. To achieve this goal, dummy semantic trajectory FS is first generated. If FS satisfies the requirements in semantic similarity and geographic and directional similarity, a dummy trajectory F is generated based on FS. The dummy trajectory F consists of each semantic position pair in FS and the moving points between corresponding location pairs.Algorithm5 describes the generation process of dummy trajectory. First, the directed edges that do not satisfy the threshold requirement are removed from the location pair graph G. Then, iteratively generate dummy trajectory up to k−1 trajectories. Lines 3-12 show the detailed steps of dummy trajectory generation. First, a dummy semantic trajectory is randomly generated (line 5). If the generated trajectory happens to be the user semantic trajectory, a new semantic trajectory is regenerated (lines 5-6). If it is not the user semantic trajectory, determine whether FS satisfies the similarity requirement (line 8). If the requirement is satisfied, iteratively traverse the location pair in FS, find the location pair in STC, then add stop points and moving points contained in location pair to the dummy trajectory F (lines 9 to 11). Finally, the eligible dummy trajectories are added to FT. The specific algorithm is as follows.Algorithm 5: Generate fake trajectory set
Input: Semantic trajectorySEM; location pair graph G; semantic similarity threshold δS;Geographical similarity thresholdδG; directional similarity threshold δA;Semantic trajectory equivalence classSTCOutput: Dummy trajectory setFT1.FT⟵∅,nFT⟵02. Calculate the slopelsem of SEM3. Remove allEci,ci+1 which Wci,ci+1 donot satisfy Def(10) and Def(11) from G4.whilenFT<k−1do5.  Random generates a fake semantic trajectoryFS6.ifFS=SEMthen7.nFT=nFT8.else9.ifsimSSEM,FS<δSandsimGSEM<δGandsimASEM,FS>δAthen10.forall<fsi,fsi+1>∈FS11.forallstc∈STCdo12.if<fsi,fsi+1>∈stcthen13.           all point betweenfsiandfsi+1 join F14.FT⟵FT∪F15.returnFTAlgorithm5 generates k−1 dummy trajectories by while-loop, and the time consumption is k−1. In the dummy trajectory generation process, the dummy trajectory F is constructed by two-level for-loop. In the worst case, the time consumption is numFS∗numSTC. Therefore, the total time consumption of Algorithm 5 is (k−1∗numFS∗numSTC, and the total time complexity is On3.According to the above analysis, the total time complexity of this scheme isOn3.


## 4.1. Scheme Framework

This scheme is designed to protect user’s trajectory privacy. To prevent attacker from identifying user’s real trajectory from thek-anonymity set. In this paper, we construct k−1 dummy trajectories based on stop point location pairs to form k-anonymity set, thus protecting user privacy and security. The scheme is divided into three steps:Trajectory preprocessing stage: based on the start time and end time of real trajectory, the trajectories with similar time periods are selected from the history trajectory datasetD. The trajectory equivalence class TC consists of these historical trajectories. According to Definition 2 and Definition 3, we extract stop points in real trajectory T and the equivalent class TC, then assign semantic to start-end points of T and all stop points to generate the corresponding semantic trajectory SEM and semantic trajectory equivalent class STC.Selection of candidate location stage. For each location pointsli in semantic trajectory SEM, we select the location points that satisfy Definition 8 from STC and then add them to candidate location Ci to form the candidate location set Can.
(1)
Dummy trajectory generation stage. We generate dummy semantic trajectoryFS based on candidate location set Can. If FS meets similarity measure, moving points between stop points in FS are also added to the trajectory FS to generate corresponding dummy trajectory F. Repeat this step until k−1 dummy trajectories are generated to form a k-anonymity set. The overall process is shown in Figure 3. We will then describe each step separately in chapter 4.Figure 3
System overview of scheme.


## 4.2. Trajectory Preprocessing

This subsection preprocesses real trajectory. It can be divided into the following two steps: (1) construct a trajectory equivalence classTC for T and add trajectories with similar time periods to TC; (2) extract stop points in real trajectory T and the equivalent class TC and assign semantic to them, and construct the corresponding semantic trajectory SEM and semantic trajectory equivalent class STC.


### 4.2.1. Construct Trajectory Equivalence Class

Ink-anonymity set, if the time period of a trajectory is different from other trajectories, attacker may infer that this trajectory is a dummy trajectory. Therefore, we need to ensure that the trajectory in the equivalent class TC is similar to real trajectory T in terms of time period. According to the set time offset ∆t, if a trajectory Tra in history trajectory dataset D satisfies the following conditions:
(19)Tra.ts∈T.ts−∆t,T.ts+∆t,,Tra.te∈T.ts−∆t,T.ts+∆t,.Then,Tra is added to the equivalent class TC, where ts and te denote the start time and end time of trajectory Tra, respectively.The specific steps are shown in Algorithm1.Algorithm 1: Construct trajectory equivalence class
Input: Real trajectoryT; time offset ∆t; history trajectory dataset DOutput: Trajectory equivalent classTC1.TC⟵∅2.forallTra∈Ddo3.ifTra meets the candidate of Formula (19) then4.TC⟵TC∪Tra5.returnTCAlgorithm1 traverses the trajectories in the trajectory dataset D by a for-loop and calculates whether they satisfy Equation (19). The time cost of Algorithm 1 is numD, i.e., the algorithm time complexity is On.


### 4.2.2. Construct Trajectory Equivalence Class

Stop point contains richer information than moving point, and attacker can identifyk-anonymity set’s dummy trajectory by analysing stop point. The dummy trajectory that constitutes the k-anonymity set have to be semantically similar to the real trajectories T. So, in this subsection, we extract stop points in real trajectories T and equivalence class TC and assign semantic to start-end points of T and all stop points to construct the corresponding semantic trajectory and semantic trajectory equivalence class STC.When the distance between a segment of consecutive location pointsti and tji≤j is less than the distance threshold θd and the interval time is greater than the time threshold θt, the location points from ti to tj are aggregated into a stop point. If the Euclidean distance between ti and tj is greater than the distance threshold θd, then ti and tj cannot be aggregated into a stop point. Next, the interval time between ti and tj−1 is calculated to determine whether it is greater than the time threshold θt, if the interval time is greater than the time threshold θt, then ti to tj−1 is aggregated as a stop point. If the interval time is less than the time threshold θt, the location points ti to tj are all moving points and repeat this operation from tj+1.For example, in the subtrajectorytr=t1,t2,⋯,t5,t6, Disgeot1,t5≤θd, Disgeot1,t6, and Distimet1,t5≥θt. We can aggregate the location points t1 to t5 as a stop point. After acquiring stop points, we assign semantic of the closest POI to stop point based on the PAT. The step is repeated, and the semantic trajectory is finally generated.The specific steps are shown in Algorithm2.Algorithm 2: Construct semantic trajectory
Input: Real trajectoryT; time threshold θt; distance threshold θd; point-of-interest setPATOutput: Semantic trajectorySem; Semantic trajectory equivalence class STC1.SEM⟵∅,STC⟵∅2.sl=assign_semt1,PAT3.SEM⟵SEM∪sl4.sl=assign_semte,PAT5.SEM⟵SEM∪sl6.whileallti∈t2,t3,⋯,te−1do7.j⟵i+18.whiletj∈t2,t3,⋯,te−1do9.ifDis_geoti,tj<θdthen10.ifDis_timeti,tj>θdthen11.sp=gen_spti,tj12.sl=assign_semsp,PAT13.SEM⟵SEM∪sl14.j⟵j+115.i⟵j+116.forallTc∈TCdo17.whilealltci∈Tcdo18.j⟵i+119.whiletcj∈Tcdo20.ifDis_geotci,tcj<θdthen21.ifDis_timetci,tcj>θdthen22.sp=gen_sptci,tcj23.cl=assign_semsp,PAT24.stc⟵stc∪cl25.j⟵j+126.i⟵j+127.STC⟵STC∪stc28.returnSEM,STCIn Algorithm2, lines 2-5 assign semantic to start-end points of real trajectory T and add them to semantic trajectory SEM. Lines 6-15 extract stop points in real trajectory T based on the threshold θt and distance threshold θd and assign semantic. Then, add these points to SEM. Lines 15-27 traverse the trajectories in the equivalence class TC, convert the trajectory to semantic trajectory, and add them to semantic trajectory equivalence class STC.Algorithm2 transforms real trajectory T into semantic trajectory SEM by two layers of while-loop. In the worst case, the time consumption is numT∗numT, and the time complexity is On2. Second, the trajectories in TC are traversed by a for-loop, and then, the equivalence class is transformed into semantic trajectory equivalence class STC by two layers of while-loop. In the worst case, the time consumption is numTC∗numT∗numT, and the time complexity is On3. Therefore, the total time consumption of Algorithm 2 is numTC∗T∗T+numT2, and the total time complexity is On3.


## 4.2.1. Construct Trajectory Equivalence Class

Ink-anonymity set, if the time period of a trajectory is different from other trajectories, attacker may infer that this trajectory is a dummy trajectory. Therefore, we need to ensure that the trajectory in the equivalent class TC is similar to real trajectory T in terms of time period. According to the set time offset ∆t, if a trajectory Tra in history trajectory dataset D satisfies the following conditions:
(19)Tra.ts∈T.ts−∆t,T.ts+∆t,,Tra.te∈T.ts−∆t,T.ts+∆t,.Then,Tra is added to the equivalent class TC, where ts and te denote the start time and end time of trajectory Tra, respectively.The specific steps are shown in Algorithm1.Algorithm 1: Construct trajectory equivalence class
Input: Real trajectoryT; time offset ∆t; history trajectory dataset DOutput: Trajectory equivalent classTC1.TC⟵∅2.forallTra∈Ddo3.ifTra meets the candidate of Formula (19) then4.TC⟵TC∪Tra5.returnTCAlgorithm1 traverses the trajectories in the trajectory dataset D by a for-loop and calculates whether they satisfy Equation (19). The time cost of Algorithm 1 is numD, i.e., the algorithm time complexity is On.


## 4.2.2. Construct Trajectory Equivalence Class

Stop point contains richer information than moving point, and attacker can identifyk-anonymity set’s dummy trajectory by analysing stop point. The dummy trajectory that constitutes the k-anonymity set have to be semantically similar to the real trajectories T. So, in this subsection, we extract stop points in real trajectories T and equivalence class TC and assign semantic to start-end points of T and all stop points to construct the corresponding semantic trajectory and semantic trajectory equivalence class STC.When the distance between a segment of consecutive location pointsti and tji≤j is less than the distance threshold θd and the interval time is greater than the time threshold θt, the location points from ti to tj are aggregated into a stop point. If the Euclidean distance between ti and tj is greater than the distance threshold θd, then ti and tj cannot be aggregated into a stop point. Next, the interval time between ti and tj−1 is calculated to determine whether it is greater than the time threshold θt, if the interval time is greater than the time threshold θt, then ti to tj−1 is aggregated as a stop point. If the interval time is less than the time threshold θt, the location points ti to tj are all moving points and repeat this operation from tj+1.For example, in the subtrajectorytr=t1,t2,⋯,t5,t6, Disgeot1,t5≤θd, Disgeot1,t6, and Distimet1,t5≥θt. We can aggregate the location points t1 to t5 as a stop point. After acquiring stop points, we assign semantic of the closest POI to stop point based on the PAT. The step is repeated, and the semantic trajectory is finally generated.The specific steps are shown in Algorithm2.Algorithm 2: Construct semantic trajectory
Input: Real trajectoryT; time threshold θt; distance threshold θd; point-of-interest setPATOutput: Semantic trajectorySem; Semantic trajectory equivalence class STC1.SEM⟵∅,STC⟵∅2.sl=assign_semt1,PAT3.SEM⟵SEM∪sl4.sl=assign_semte,PAT5.SEM⟵SEM∪sl6.whileallti∈t2,t3,⋯,te−1do7.j⟵i+18.whiletj∈t2,t3,⋯,te−1do9.ifDis_geoti,tj<θdthen10.ifDis_timeti,tj>θdthen11.sp=gen_spti,tj12.sl=assign_semsp,PAT13.SEM⟵SEM∪sl14.j⟵j+115.i⟵j+116.forallTc∈TCdo17.whilealltci∈Tcdo18.j⟵i+119.whiletcj∈Tcdo20.ifDis_geotci,tcj<θdthen21.ifDis_timetci,tcj>θdthen22.sp=gen_sptci,tcj23.cl=assign_semsp,PAT24.stc⟵stc∪cl25.j⟵j+126.i⟵j+127.STC⟵STC∪stc28.returnSEM,STCIn Algorithm2, lines 2-5 assign semantic to start-end points of real trajectory T and add them to semantic trajectory SEM. Lines 6-15 extract stop points in real trajectory T based on the threshold θt and distance threshold θd and assign semantic. Then, add these points to SEM. Lines 15-27 traverse the trajectories in the equivalence class TC, convert the trajectory to semantic trajectory, and add them to semantic trajectory equivalence class STC.Algorithm2 transforms real trajectory T into semantic trajectory SEM by two layers of while-loop. In the worst case, the time consumption is numT∗numT, and the time complexity is On2. Second, the trajectories in TC are traversed by a for-loop, and then, the equivalence class is transformed into semantic trajectory equivalence class STC by two layers of while-loop. In the worst case, the time consumption is numTC∗numT∗numT, and the time complexity is On3. Therefore, the total time consumption of Algorithm 2 is numTC∗T∗T+numT2, and the total time complexity is On3.


## 4.3. Construct Candidate Location Set

The purpose of this subsection is to select the location pairs used to construct the dummy trajectory. We traverse semantic trajectory SEM and compute the similarity of location pairs inSTC according to Definition 8. If there is a location pair that satisfies the condition, this location pair is added to the candidate location Ci and Ci+1. After traversing all position pairs, the composition of Can=C1,C2,⋯,Cn,=<C1,C2>,<C2,C3>,⋯,<Cn−1,Cn>.The specific steps are shown in Algorithm3.Algorithm 3: Construct candidate location set
Input: Semantic trajectorySEM; semantic trajectory equivalence class STC; locationpair similarity thresholdδsem,δgeo,δtimeOutput: Candidate location setCan1.Can⟵∅2.forall<sli,sli+1>∈SEMdo3.Ci⟵sli,Ci+1⟵sli+14.forallstc∈STCdo5.forallclj∈stcdo6.if <sli,sli> and <clj,clj+1>meets the candidate ofDefinition8then7.Ci⟵clj,Ci+1⟵clj+18.exit9.Can⟵Ci,Can⟵Ci+110.returnCanFor the location pair<sli,sli+1> in the semantic trajectory SEM, Algorithm 3 traverses each trajectory in STC. If there exists position pair similar to <sli,sli+1> in this trajectory, this location pair will be added to Ci and Ci+1. Then, traverse the next trajectory until all trajectories have been traversed. Algorithm 3 finally returns the candidate location set Can.Algorithm3 constructs the candidate location set Can by a three-level for-loop. The first level for-loop traverses the location pairs in SEM with a time consumption of numSEM. The second level for-loop traverses the trajectory in STC with a time consumption of numSTC. The third-level for-loop traverses the location pairs in the trajectory stc with a time consumption of numstc. Therefore, the total time consumption of Algorithm 3 is numSEM∗STC∗stc, and the time complexity is On3.


## 4.4. Construct Location Pair Graph

In the previous subsection, we picked candidate location for each semantic location point inSEM. The next goal is to generate k−1 dummy trajectories based on these candidate positions to form a k-anonymity set. If location points are randomly selected from each candidate location and combined into a dummy trajectory, the generated dummy trajectory may have some unreachable locations. Specifically, as shown in Figure 4, the solid line and dotted line represent the location pair that exist in Can and the location pair that do not exist in Can, respectively. A dummy trajectory consisting of location pairs <A1,B2> and <B2,A3> will pass through unreachable locations. So, attacker can easily identify this trajectory as dummy trajectory.Figure 4
Example of constructing fake trajectory.This subsection constructs the location pair graphG=V,E,W. Among them, V consists of all semantic location points in Can, and each semantic location point represents a node in G. ci is a location in the candidate position Ci and Eci,ci+1 is a directed edge connecting ci and ci+1. Wci,ci+1 is the weight of edge Eci,ci+1, and the value is a binary consisting of geographical similarity and semantic similarity. Algorithm 4 describes the graph generation process as follows.Algorithm 4: Construct location pair graph
Input: Semantic trajectorySEM; location candidate set Can; semantic trajectoryequivalence classSTCOutput: Location pair graphG1.E⟵∅,W⟵∅2.forallCi∈Cando3.forallcj∈Cido4.forallck,∈Ci+1do5.if<cj,ck,>∈STCthen6.E⟵Ecj,ck,7.W⟵Wcj,ck,8.returnGAlgorithm4 first traverses each candidate location Ci and picks locations from Ci and Ci+1 respectively to form the location pair <cj,ck,>. Next, determine whether the location pair <cj,ck,> exists in STC. If it exists, add Eci,ci+1 and Wci,ci+1 to the graph G.Algorithm4 constructs the location pair graph G by a three-level for-loop. The first level for-loop traverses the candidate location of Can, and the time consumption is numCan. The second level for-loop traverses location point cj in candidate position Ci, and the time consumption is numCi. The third level for-loop traverses the location point ck, in the candidate position Ci+1, and the time consumption of numCi+1. The total time consumption of Algorithm 4 is numCan∗Ci∗Ci+1, and the total time complexity is On3.


## 4.5. Constructk-Anonymity Set

The goal of this subsection is to generatek−1 dummy trajectories to form k-anonymity sets. These dummy trajectories are semantically, geographically, and directionally similar with real trajectories T. To achieve this goal, dummy semantic trajectory FS is first generated. If FS satisfies the requirements in semantic similarity and geographic and directional similarity, a dummy trajectory F is generated based on FS. The dummy trajectory F consists of each semantic position pair in FS and the moving points between corresponding location pairs.Algorithm5 describes the generation process of dummy trajectory. First, the directed edges that do not satisfy the threshold requirement are removed from the location pair graph G. Then, iteratively generate dummy trajectory up to k−1 trajectories. Lines 3-12 show the detailed steps of dummy trajectory generation. First, a dummy semantic trajectory is randomly generated (line 5). If the generated trajectory happens to be the user semantic trajectory, a new semantic trajectory is regenerated (lines 5-6). If it is not the user semantic trajectory, determine whether FS satisfies the similarity requirement (line 8). If the requirement is satisfied, iteratively traverse the location pair in FS, find the location pair in STC, then add stop points and moving points contained in location pair to the dummy trajectory F (lines 9 to 11). Finally, the eligible dummy trajectories are added to FT. The specific algorithm is as follows.Algorithm 5: Generate fake trajectory set
Input: Semantic trajectorySEM; location pair graph G; semantic similarity threshold δS;Geographical similarity thresholdδG; directional similarity threshold δA;Semantic trajectory equivalence classSTCOutput: Dummy trajectory setFT1.FT⟵∅,nFT⟵02. Calculate the slopelsem of SEM3. Remove allEci,ci+1 which Wci,ci+1 donot satisfy Def(10) and Def(11) from G4.whilenFT<k−1do5.  Random generates a fake semantic trajectoryFS6.ifFS=SEMthen7.nFT=nFT8.else9.ifsimSSEM,FS<δSandsimGSEM<δGandsimASEM,FS>δAthen10.forall<fsi,fsi+1>∈FS11.forallstc∈STCdo12.if<fsi,fsi+1>∈stcthen13.           all point betweenfsiandfsi+1 join F14.FT⟵FT∪F15.returnFTAlgorithm5 generates k−1 dummy trajectories by while-loop, and the time consumption is k−1. In the dummy trajectory generation process, the dummy trajectory F is constructed by two-level for-loop. In the worst case, the time consumption is numFS∗numSTC. Therefore, the total time consumption of Algorithm 5 is (k−1∗numFS∗numSTC, and the total time complexity is On3.According to the above analysis, the total time complexity of this scheme isOn3.


## 5. Experiment Analysis

### 5.1. Data Set and Experimental Environment

In this paper, we use the GeoLife dataset [26–28] to evaluate the performance of the trajectory privacy protect method based on location pair reorganization. The dataset collected 5 years of trajectories of 182 volunteers, and this dataset contains 17,621 trajectories. Most of the trajectories in GeoLife dataset are recorded in Beijing, China. Therefore, this paper extracts the trajectory data of the Beijing area for experimental analysis. We select 5 attributes in GeoLife to compose the history trajectory dataset D. The 5 attributes are user ID, longitude, latitude, date, and time. We generate the trajectory k-anonymity set on the historical trajectory dataset D.In this paper, the point of interest set (PAT) includes a total of 211,615 POIs within the 6th Ring Road of Beijing. The semantic categories adopt the three-level classification of Chinese POI standard, including 15 major categories, 51 middle categories, and 145 minor categories.The hardware environment of the experiment is: Intel i7-8750H 2.20 GHz, 16.00 GB memory, the operating system is Microsoft Windows 10, and the algorithms are all implemented under Pycharm2020.


### 5.2. Experimental Parameter and Evaluation Indicator

To verify the performance of the DSTPP algorithm, we randomly select 10 user trajectories from the trajectory datasetD for the experiment. Each user’s semantic trajectory contains at least 4 semantic location points. The experimental parameters are set as shown in Table 2.Table 2
Experimental parameters.
ParameterRangeθt10 minθd100 mδgeo200 mδsem98δtime10 minδG0.3δS0.3δA0.85Anonymity level3-10In this paper, we verify the performance of DSTPP by comparing with Random algorithm [25] and MTPPA [13] algorithm in terms of both privacy and availability. Random algorithm randomly selects k−1 locations from the candidate location to generate dummy trajectory. MTPPA algorithm selects k−1 history trajectories to form k-anonymity set. Under the same conditions, we run 3 algorithms on 10 user trajectories. To ensure the accuracy of the experimental results, each group of experiments was measured 100 times. Finally, the average of 100 results was taken as the final result.


### 5.3. Privacy Analysis

In this section, we use identification probability (IP) to evaluatek-anonymity set’s privacy. In k-anonymity set, there are m trajectories that are similar to T. The identification probability is 1/m. The larger the value of m, the more difficult it is for attacker to identify true trajectory T from k-anonymity set and the better privacy. The identification probability is calculated by the following equation.
(20)IP=1tra_numkset,δG,δA,δS,where tra_numkset,δG,δA,δS is used to calculate the number of trajectories that satisfy the similarity measure in the trajectory k-anonymity set.We evaluate the privacy by the average identification probability of 10 trajectories. Figure5 shows the three methods’ average identification probability under different values of k. As shown in Figure 5, the average identification probability of all methods tends to decrease when the k value increases. This is because as the k value increases, the more trajectories in k-anonymity set and the more trajectories that are similar to the real trajectory. Under the same k value, random algorithm has the highest average identification probability; this is because (1) the dummy trajectory passes through some unreachable locations and (2) the dummy trajectory do not consider geographic and semantic attribute. Attacker can easily filter dummy trajectories in k-anonymity set by analysing the stop points; (3) the dummy trajectory may differ significantly from the real trajectory in the overall direction.Figure 5
Privacy vs.k.The average identification probability of MTPPA algorithm is lower than random algorithm. This is because MTPPA algorithm selects history trajectories to form ak-anonymous set, so there are no unreachable locations. Meanwhile, dummy trajectory is selected based on the number of stop point, which can ensure the semantic similarity of trajectories in the k-anonymity set to a certain degree.Compared to the above two methods, DSTPP has a lower average identification probability. This is because DSTPP constructs dummy trajectory based on real position pairs, so no unreachable locations appear. In addition, dummy trajectory and real trajectories are similar in terms of overall direction, semantic property, and geographical property.


### 5.4. Availability Analysis

After the service provider publishes thek-anonymity set, researchers can conduct statistics, research, and other studies by mining the trajectories in the anonymity set. Therefore, the k-anonymity set’s availability is to be evaluated. According to the research needs, availability can be divided into two categories: trajectory availability and data availability.


#### 5.4.1. Trajectory Availability Analysis

Trajectory availability means: for traffic optimization, logistics management, and other needs, researchers want to use trajectory data to evaluate traffic flow. This requires that the dummy trajectory must have a high degree of shape similarity and geographic similarity to the real trajectory.In this subsection, we evaluate the trajectory availability ofk-anonymous sets by trajectory difference (TD). The trajectory difference is calculated by the following equation.
(21)TD=∑i=1FFT,Fik,where FT,Fi is the Fre´chet distance between two trajectories. Fre´chet distance is calculated by the following equation.
(22)FA,B=infα,β,t∈0,1maxdAαt,Bβt.A and B are two trajectories for comparison, with t representing a specific moment and Aαt,Bβt representing A and B’s location point at moment t, respectively. dAαt,Bβt denotes the Euclidean distance between two location points.We use the average trajectory difference of the 10 trajectories to evaluate thek-anonymity set’s trajectory availability. For the k-anonymous set, larger TD values represent weaker trajectory availability. Figure 6 shows three methods’ average trajectory difference of under different k values. As shown in Figure 6, three methods’ trajectory difference shows an increasing trend when the k value increases. This is because, as the k value becomes larger, the number of required dummy trajectories increases. So, the dummy trajectories’ overall quality decreases. Under the same k value, DSTPP has the lowest trajectory difference. This is because DSTPP considers the overall direction and geographic location, and the generated dummy trajectory is more similar to the real trajectory. Random’s average trajectory difference is higher than DSTPP. This is because Random randomly generates dummy trajectory based on fake location points. The generated dummy trajectory has some geographical similarity, but the overall direction is not considered. The MTPPA algorithm has the largest average trajectory difference. This is because MTPPA does not consider trajectory shape similarity and overall direction at all when selecting dummy trajectory.Figure 6
Trajectory difference vs.k.


#### 5.4.2. Data Availability Analysis

Data availability is pointed out for needs such as interest recommendation and location prediction [26, 35]; researchers want to analyse semantic properties in trajectories. This requires that there must be enough available data in the k-anonymity set and the data must be accurate.In this paper, the available data rate (AD) is used to evaluate the amount of available data in the anonymous set, which is calculated as follows.(23)AD=num_reachksetnum_allkset,where num_allkset denotes all the location points in the k-anonymous set and num_reachkset denotes the reachable location points in the k-anonymous set.We use information loss (IL) to evaluate the accuracy of the anonymous set. Less information loss indicates more accurate data and better data availability. Information loss depends on the size of the anonymity zone; the method was similar with Xu et al. [13]. The calculation formula is as follows.
(24)IL=∑i=1SEMArealoci,timei/Max_AreaksetSEM,where Arealoci,timei denotes the ith semantic location point’s anonymous set size, and Max_Areakset denotes the size of the trajectory k-anonymous set, and SEM denotes the number of semantic location points.We evaluate thek-anonymity set’s data availability by the average available data rate and the average loss information for the 10 trajectories. Figure 7 illustrates the effect of k value on data availability.Figure 7
Availability vs.k.
(a)
Available data vs.k(b)
Data availability vs.kFigure7(a) evaluates three methods’ available data rate. Among them, Random has the lowest available data rate. This is because, this method contains or passes through some unreachable locations that are not available for data analysis. The available data rate of both MTPPA and DSTPP is 1. This is because the dummy trajectory of MTPPA is taken from history trajectories set, and the dummy trajectory by DSTPP is also taken from history trajectories. Therefore, no unreachable positions will be present or passed.Figure7(b) evaluates three methods’ data accuracy. When k value increases, the information loss of all three methods shows an increasing trend. This is because the quality of dummy trajectory decreases as the k-anonymity set increases. When k values are constant, Random has the greatest loss information. This is because the dummy trajectory generated by Random does not consider semantic similarity. So, there is too much noise in the query results of each query. MTPPA’s information loss is in the middle; MTPPA considers the number of stop point between trajectories. Therefore, the query result of each query contains a high amount of semantic information, which can be used for data analysis. DSTPP has minimal information loss. This is because the dummy trajectory generated by DSTPP not only considers the number of stop point but also considers the semantics of stop point are similar to the real trajectory. The query results contain rich semantic information for researchers to analyse.


## 5.1. Data Set and Experimental Environment

In this paper, we use the GeoLife dataset [26–28] to evaluate the performance of the trajectory privacy protect method based on location pair reorganization. The dataset collected 5 years of trajectories of 182 volunteers, and this dataset contains 17,621 trajectories. Most of the trajectories in GeoLife dataset are recorded in Beijing, China. Therefore, this paper extracts the trajectory data of the Beijing area for experimental analysis. We select 5 attributes in GeoLife to compose the history trajectory dataset D. The 5 attributes are user ID, longitude, latitude, date, and time. We generate the trajectory k-anonymity set on the historical trajectory dataset D.In this paper, the point of interest set (PAT) includes a total of 211,615 POIs within the 6th Ring Road of Beijing. The semantic categories adopt the three-level classification of Chinese POI standard, including 15 major categories, 51 middle categories, and 145 minor categories.The hardware environment of the experiment is: Intel i7-8750H 2.20 GHz, 16.00 GB memory, the operating system is Microsoft Windows 10, and the algorithms are all implemented under Pycharm2020.


## 5.2. Experimental Parameter and Evaluation Indicator

To verify the performance of the DSTPP algorithm, we randomly select 10 user trajectories from the trajectory datasetD for the experiment. Each user’s semantic trajectory contains at least 4 semantic location points. The experimental parameters are set as shown in Table 2.Table 2
Experimental parameters.
ParameterRangeθt10 minθd100 mδgeo200 mδsem98δtime10 minδG0.3δS0.3δA0.85Anonymity level3-10In this paper, we verify the performance of DSTPP by comparing with Random algorithm [25] and MTPPA [13] algorithm in terms of both privacy and availability. Random algorithm randomly selects k−1 locations from the candidate location to generate dummy trajectory. MTPPA algorithm selects k−1 history trajectories to form k-anonymity set. Under the same conditions, we run 3 algorithms on 10 user trajectories. To ensure the accuracy of the experimental results, each group of experiments was measured 100 times. Finally, the average of 100 results was taken as the final result.


## 5.3. Privacy Analysis

In this section, we use identification probability (IP) to evaluatek-anonymity set’s privacy. In k-anonymity set, there are m trajectories that are similar to T. The identification probability is 1/m. The larger the value of m, the more difficult it is for attacker to identify true trajectory T from k-anonymity set and the better privacy. The identification probability is calculated by the following equation.
(20)IP=1tra_numkset,δG,δA,δS,where tra_numkset,δG,δA,δS is used to calculate the number of trajectories that satisfy the similarity measure in the trajectory k-anonymity set.We evaluate the privacy by the average identification probability of 10 trajectories. Figure5 shows the three methods’ average identification probability under different values of k. As shown in Figure 5, the average identification probability of all methods tends to decrease when the k value increases. This is because as the k value increases, the more trajectories in k-anonymity set and the more trajectories that are similar to the real trajectory. Under the same k value, random algorithm has the highest average identification probability; this is because (1) the dummy trajectory passes through some unreachable locations and (2) the dummy trajectory do not consider geographic and semantic attribute. Attacker can easily filter dummy trajectories in k-anonymity set by analysing the stop points; (3) the dummy trajectory may differ significantly from the real trajectory in the overall direction.Figure 5
Privacy vs.k.The average identification probability of MTPPA algorithm is lower than random algorithm. This is because MTPPA algorithm selects history trajectories to form ak-anonymous set, so there are no unreachable locations. Meanwhile, dummy trajectory is selected based on the number of stop point, which can ensure the semantic similarity of trajectories in the k-anonymity set to a certain degree.Compared to the above two methods, DSTPP has a lower average identification probability. This is because DSTPP constructs dummy trajectory based on real position pairs, so no unreachable locations appear. In addition, dummy trajectory and real trajectories are similar in terms of overall direction, semantic property, and geographical property.


## 5.4. Availability Analysis

After the service provider publishes thek-anonymity set, researchers can conduct statistics, research, and other studies by mining the trajectories in the anonymity set. Therefore, the k-anonymity set’s availability is to be evaluated. According to the research needs, availability can be divided into two categories: trajectory availability and data availability.


### 5.4.1. Trajectory Availability Analysis

Trajectory availability means: for traffic optimization, logistics management, and other needs, researchers want to use trajectory data to evaluate traffic flow. This requires that the dummy trajectory must have a high degree of shape similarity and geographic similarity to the real trajectory.In this subsection, we evaluate the trajectory availability ofk-anonymous sets by trajectory difference (TD). The trajectory difference is calculated by the following equation.
(21)TD=∑i=1FFT,Fik,where FT,Fi is the Fre´chet distance between two trajectories. Fre´chet distance is calculated by the following equation.
(22)FA,B=infα,β,t∈0,1maxdAαt,Bβt.A and B are two trajectories for comparison, with t representing a specific moment and Aαt,Bβt representing A and B’s location point at moment t, respectively. dAαt,Bβt denotes the Euclidean distance between two location points.We use the average trajectory difference of the 10 trajectories to evaluate thek-anonymity set’s trajectory availability. For the k-anonymous set, larger TD values represent weaker trajectory availability. Figure 6 shows three methods’ average trajectory difference of under different k values. As shown in Figure 6, three methods’ trajectory difference shows an increasing trend when the k value increases. This is because, as the k value becomes larger, the number of required dummy trajectories increases. So, the dummy trajectories’ overall quality decreases. Under the same k value, DSTPP has the lowest trajectory difference. This is because DSTPP considers the overall direction and geographic location, and the generated dummy trajectory is more similar to the real trajectory. Random’s average trajectory difference is higher than DSTPP. This is because Random randomly generates dummy trajectory based on fake location points. The generated dummy trajectory has some geographical similarity, but the overall direction is not considered. The MTPPA algorithm has the largest average trajectory difference. This is because MTPPA does not consider trajectory shape similarity and overall direction at all when selecting dummy trajectory.Figure 6
Trajectory difference vs.k.


### 5.4.2. Data Availability Analysis

Data availability is pointed out for needs such as interest recommendation and location prediction [26, 35]; researchers want to analyse semantic properties in trajectories. This requires that there must be enough available data in the k-anonymity set and the data must be accurate.In this paper, the available data rate (AD) is used to evaluate the amount of available data in the anonymous set, which is calculated as follows.(23)AD=num_reachksetnum_allkset,where num_allkset denotes all the location points in the k-anonymous set and num_reachkset denotes the reachable location points in the k-anonymous set.We use information loss (IL) to evaluate the accuracy of the anonymous set. Less information loss indicates more accurate data and better data availability. Information loss depends on the size of the anonymity zone; the method was similar with Xu et al. [13]. The calculation formula is as follows.
(24)IL=∑i=1SEMArealoci,timei/Max_AreaksetSEM,where Arealoci,timei denotes the ith semantic location point’s anonymous set size, and Max_Areakset denotes the size of the trajectory k-anonymous set, and SEM denotes the number of semantic location points.We evaluate thek-anonymity set’s data availability by the average available data rate and the average loss information for the 10 trajectories. Figure 7 illustrates the effect of k value on data availability.Figure 7
Availability vs.k.
(a)
Available data vs.k(b)
Data availability vs.kFigure7(a) evaluates three methods’ available data rate. Among them, Random has the lowest available data rate. This is because, this method contains or passes through some unreachable locations that are not available for data analysis. The available data rate of both MTPPA and DSTPP is 1. This is because the dummy trajectory of MTPPA is taken from history trajectories set, and the dummy trajectory by DSTPP is also taken from history trajectories. Therefore, no unreachable positions will be present or passed.Figure7(b) evaluates three methods’ data accuracy. When k value increases, the information loss of all three methods shows an increasing trend. This is because the quality of dummy trajectory decreases as the k-anonymity set increases. When k values are constant, Random has the greatest loss information. This is because the dummy trajectory generated by Random does not consider semantic similarity. So, there is too much noise in the query results of each query. MTPPA’s information loss is in the middle; MTPPA considers the number of stop point between trajectories. Therefore, the query result of each query contains a high amount of semantic information, which can be used for data analysis. DSTPP has minimal information loss. This is because the dummy trajectory generated by DSTPP not only considers the number of stop point but also considers the semantics of stop point are similar to the real trajectory. The query results contain rich semantic information for researchers to analyse.


## 5.4.1. Trajectory Availability Analysis

Trajectory availability means: for traffic optimization, logistics management, and other needs, researchers want to use trajectory data to evaluate traffic flow. This requires that the dummy trajectory must have a high degree of shape similarity and geographic similarity to the real trajectory.In this subsection, we evaluate the trajectory availability ofk-anonymous sets by trajectory difference (TD). The trajectory difference is calculated by the following equation.
(21)TD=∑i=1FFT,Fik,where FT,Fi is the Fre´chet distance between two trajectories. Fre´chet distance is calculated by the following equation.
(22)FA,B=infα,β,t∈0,1maxdAαt,Bβt.A and B are two trajectories for comparison, with t representing a specific moment and Aαt,Bβt representing A and B’s location point at moment t, respectively. dAαt,Bβt denotes the Euclidean distance between two location points.We use the average trajectory difference of the 10 trajectories to evaluate thek-anonymity set’s trajectory availability. For the k-anonymous set, larger TD values represent weaker trajectory availability. Figure 6 shows three methods’ average trajectory difference of under different k values. As shown in Figure 6, three methods’ trajectory difference shows an increasing trend when the k value increases. This is because, as the k value becomes larger, the number of required dummy trajectories increases. So, the dummy trajectories’ overall quality decreases. Under the same k value, DSTPP has the lowest trajectory difference. This is because DSTPP considers the overall direction and geographic location, and the generated dummy trajectory is more similar to the real trajectory. Random’s average trajectory difference is higher than DSTPP. This is because Random randomly generates dummy trajectory based on fake location points. The generated dummy trajectory has some geographical similarity, but the overall direction is not considered. The MTPPA algorithm has the largest average trajectory difference. This is because MTPPA does not consider trajectory shape similarity and overall direction at all when selecting dummy trajectory.Figure 6
Trajectory difference vs.k.


## 5.4.2. Data Availability Analysis

Data availability is pointed out for needs such as interest recommendation and location prediction [26, 35]; researchers want to analyse semantic properties in trajectories. This requires that there must be enough available data in the k-anonymity set and the data must be accurate.In this paper, the available data rate (AD) is used to evaluate the amount of available data in the anonymous set, which is calculated as follows.(23)AD=num_reachksetnum_allkset,where num_allkset denotes all the location points in the k-anonymous set and num_reachkset denotes the reachable location points in the k-anonymous set.We use information loss (IL) to evaluate the accuracy of the anonymous set. Less information loss indicates more accurate data and better data availability. Information loss depends on the size of the anonymity zone; the method was similar with Xu et al. [13]. The calculation formula is as follows.
(24)IL=∑i=1SEMArealoci,timei/Max_AreaksetSEM,where Arealoci,timei denotes the ith semantic location point’s anonymous set size, and Max_Areakset denotes the size of the trajectory k-anonymous set, and SEM denotes the number of semantic location points.We evaluate thek-anonymity set’s data availability by the average available data rate and the average loss information for the 10 trajectories. Figure 7 illustrates the effect of k value on data availability.Figure 7
Availability vs.k.
(a)
Available data vs.k(b)
Data availability vs.kFigure7(a) evaluates three methods’ available data rate. Among them, Random has the lowest available data rate. This is because, this method contains or passes through some unreachable locations that are not available for data analysis. The available data rate of both MTPPA and DSTPP is 1. This is because the dummy trajectory of MTPPA is taken from history trajectories set, and the dummy trajectory by DSTPP is also taken from history trajectories. Therefore, no unreachable positions will be present or passed.Figure7(b) evaluates three methods’ data accuracy. When k value increases, the information loss of all three methods shows an increasing trend. This is because the quality of dummy trajectory decreases as the k-anonymity set increases. When k values are constant, Random has the greatest loss information. This is because the dummy trajectory generated by Random does not consider semantic similarity. So, there is too much noise in the query results of each query. MTPPA’s information loss is in the middle; MTPPA considers the number of stop point between trajectories. Therefore, the query result of each query contains a high amount of semantic information, which can be used for data analysis. DSTPP has minimal information loss. This is because the dummy trajectory generated by DSTPP not only considers the number of stop point but also considers the semantics of stop point are similar to the real trajectory. The query results contain rich semantic information for researchers to analyse.


## 6. Conclusions

With the rapid development of information technology and 5G technology, human society has entered the era of big data. Analysing the user’s daily action trajectory is of great help in optimizing national resource scheduling and improving public facilities. User trajectories contain sensitive information: how to ensure the availability of trajectories on the premise of ensuring user privacy and security. Aiming at this problem, this paper proposes a trajectory privacy protect method based on location pair reorganization. The real trajectory is decomposed into location pairs consisting of start-send point and stop points. Then,k−1 dummy trajectories are generated by selecting eligible location pairs from the historical trajectory set to form trajectory k-anonymous. Finally, this paper experiments privacy and availability on real dataset. By comparing with MTPPA algorithm and Random algorithm, our method reduces information loss and improves privacy protection. Overall, MTPPA algorithm is better than MTPPA algorithm and Random algorithm.



---

*Source: 8635275-2022-07-05.xml*