Sub-trajectory Similarity Join with Obfuscation

Most trajectory similarity measurements are either spatial distance based or spatio-temporal distance based.

Spatial-based measurements (Shang et al., 2018; Buzan et al., 2004; Chen et al., 2005; Sakurai et al., 2005; Salvador and Chan, 2007) focus on the spatial distance between two trajectories. They aggregate distance between aligned point pairs form two trajectories, such as dynamic time warping (DTW)(Shang et al., 2018) , longest common subsequence (LCSS)(Buzan et al., 2004) and edit distance on real sequence (EDR)(Chen et al., 2005).

Spatio-temporal-based measurements (Vlachos et al., 2002; Yuan and Raubal, 2014; Nanni and Pedreschi, 2006; Shang et al., 2017; Wu et al., 2016) consider the distance in both space and time. For example, LCSS and EDR have been extended to incorporate temporal thresholds (Vlachos et al., 2002; Yuan and Raubal, 2014). Nanni and Pedreschi (Nanni and Pedreschi, 2006) assume a constant moving speed on each segment of a trajectory, which is computed as the length of the segment divided by its time span. They then compute the distance between two trajectories as the average distance between two users who travel along the two trajectories with the constant speed of each segment. Shang et al. (Shang et al., 2017) sum point-to-trajectory distances from one trajectory to the other as the distance between two trajectories, where the summed distance is a weighted sum of the spatial and temporal distances. Wu et al. (Wu et al., 2016) consider points from two trajectories to be compatible if their spatial distance over time difference is within a velocity threshold.

These measurements compute similarity based on full trajectories which are different from our sub-trajectory-based metric.

Studies leverage distributed structures to join trajectories, such as DITA (Shang et al., 2018) and DISON (Yuan and Li, 2019). DITA supports a variety of trajectory distance functions based on full trajectories, while DISON measures trajectory similarity by counting the length of common road segments among the trajectories. Our trajectory join procedure supports distributed processing in two senses: (i) our join refinement procedure is distributed to client machines, and (ii) our index is based on non-overlapping space/time partitioning, which can be easily distributed.

There are also studies on sub-trajectory join (Alamdari et al., 2020; Tampakis et al., 2020; Bakalov and Tsotras, 2006). CSTJ (Bakalov and Tsotras, 2006) joins trajectories online. It returns two trajectories once they stay as close-distance pairs for a given time threshold. Its distance measure is based on points in trajectories rather than segments as in our study. DTJr (Tampakis et al., 2020) also measures point distance. It finds the longest sub-trajectory pair satisfying both spatial and temporal distance thresholds, while we find all pairs that satisfy a sub-trajectory similarity metric.

ALSTJ (Alamdari et al., 2020) is the closest work to ours. Its similarity metric is based on the spatial span of sub-trajectory pairs that are within a given distance threshold. The main differences between ALSTJ and our STS-Join are in three aspects: (i) ALSTJ does not consider the temporal factor and may join trajectories generated at different times, while STS-Join requires the trajectories to be close in both space and time so as to be joined; (ii) ALSTJ may have false negatives in its query result due to its trajectory simplification procedure, while our STS-Join guarantees accurate query results; and (iii) ALSTJ does not consider user privacy while we do.

Trajectory privacy has been studied extensively in the last decade (Chow and Mokbel, 2011; You et al., 2007; Andrés et al., 2013; Jiang et al., 2013; Naghizade et al., 2014; Monreale et al., 2010). For example, a study (You et al., 2007) introduces position dummy to hide a user’s location by mixing it with fake locations. Another study (Chow and Mokbel, 2007) extends $k$-anonymity to trajectory data. Studies (Andrés et al., 2013; Jiang et al., 2013) leverage differential privacy for release of trajectory data. Geo-indistinguishability (Andrés et al., 2013) generalizes differential privacy to user location data. SDD (Jiang et al., 2013) applies the exponential-based randomized mechanism to trajectory data by sampling a rational distance and direction with noises between locations in the trajectory. There are also studies focusing on semantic privacy of trajectories (Naghizade et al., 2014; Monreale et al., 2010). Monreale et al. (Monreale et al., 2010) present a place taxonomy based method to preserve the trajectory semantic privacy. It guarantees that the probability of inferring the sensitive stops of a user is below a threshold. Naghizade et al. (Naghizade et al., 2014) propose an algorithm to protect the semantic information of a trajectory by substituting sensitive stops of a trajectory with less sensitive ones.

As mentioned earlier, our aim is not to propose a new privacy protection scheme but to show that it is feasible to process STS-Join queries with a client-server architecture where the server only stores a modified version of the user trajectories. We use obfuscation for its simplicity. Other privacy protection methods (e.g., position dummy) can be applied in our STS-Join if the modification on the trajectory points can be bounded by a distance threshold, which helps guarantee no false negative query results.

A user’s original trajectories are stored on the client side. We simplify and obfuscate an original trajectory before sending it (together with the client ID and a local trajectory ID) to the server in order to reduce the communication and protect user’s privacy. We index the trajectories by their local IDs (e.g., using a sorted array or a B-tree) for fast retrieval at the refinement stage of query processing.

Trajectory simplification. First, we simplify an original trajectory $\mathcal{T}_{\mu}$ by reducing the number of sampled points. This reduces the storage space and improves the query efficiency later. Our simplification algorithm is adapted from the Douglas–Peucker algorithm (DP) (Douglas and Peucker, 1973). The native DP algorithm ignores the temporal dimension. Consider two sampled points $p^{\mu}_{i}$ and $p^{\mu}_{i+k}(k>1)$ on $\mathcal{T}_{\mu}$. For all other sampled points between $p^{\mu}_{i}$ and $p^{\mu}_{i+k}$, if their perpendicular distances to the segment between $p^{\mu}_{i}$ and $p^{\mu}_{i+k}$ are within a simplification threshold $\theta_{sp}$ (an empirical parameter), then these points are all removed from $\mathcal{T}_{\mu}$ by DP.

In our case, since we interpolate user locations on the trajectory segments, we require the user location on the simplified segment $\overline{p^{\mu}_{i},p^{\mu}_{i+k}}$ to be within $\theta_{sp}$ distance from that on the original segments at every time point $t\in[t^{\mu}_{i},t^{\mu}_{i+k}]$. This guarantees no false negatives in STS-Join over the simplified trajectories. Fig. 3 shows an example. The original (black) trajectory $\mathcal{T}_{\mu}$ has three segments, which is simplified to just one (red) segment $\overline{{p^{\widetilde{\mu}}_{1}},{p^{\widetilde{\mu}}_{4}}}$. We compute $p^{\widetilde{\mu}}_{2}$ and $p^{\widetilde{\mu}}_{3}$ on $\overline{{p^{\widetilde{\mu}}_{1}},{p^{\widetilde{\mu}}_{4}}}$ at times $t^{\mu}_{2}$ and $t^{\mu}_{3}$ (i.e., the time points of $p^{\mu}_{2}$ and $p^{\mu}_{3}$), respectively. To ensure valid simplification, the distance between $p^{\mu}_{2}$ and $p^{\widetilde{\mu}}_{2}$ (i.e., $d_{2}$) and that between $p^{\mu}_{3}$ and $p^{\widetilde{\mu}}_{3}$ (i.e., $d_{3}$) must both be within $\theta_{sp}$. This contrasts to the native DP that examines the perpendicular distances of $p^{\mu}_{2}$ and $p^{\mu}_{3}$ (i.e., $d^{\perp}_{2}$ and $d^{\perp}_{3}$), which are shorter and may lead to false negatives at query processing.

Trajectory obfuscation. Our simplified trajectories retain a subset of the trajectory points. To protect privacy, we further adapt the bounded Laplace mechanism (i.e., an algorithm) to obfuscate the simplified trajectories as inspired by previous studies (Dwork et al., 2006; Holohan et al., 2020).

The bounded Laplace mechanism adds a noise from the bounded Laplace distribution to the output of a (query) function. In our problem, we add a bounded noise to each dimension of a point on a simplified trajectory to protect users’ location privacy. The probability distribution function (PDF) of the added noise is (Holohan et al., 2020):

where $\lambda$ is a constant, $b$ is the bias of the distribution, $\theta_{ob}\in\mathbb{R}^{+}$ is the obfuscated distance threshold. Since the domain of the distribution is bounded in $[-\theta_{ob},\theta_{ob}]$, the integral of PDF should be 1 for $x\in[-\theta_{ob},\theta_{ob}]$. This yields the value of $\lambda$:

We then leverage the inverse cumulative distribution function to generate random noises that satisfy the PDF. Firstly, we derive the CDF from the PDF by computing the integral of the PDF for $x<0$ and $x\geqslant 0$ respectively:

Then, we can obtain the inverse CDF from Equation 7:

Here, variable $y$ is a random number in $(0,1)$. We generate $y$ and use it to obtain noise $x$, which is then added to each point coordinate of the simplified trajectory. Parameter $\lambda$ is determined by $b$ and $\theta_{ob}$ (Equation 6), while $b$ is the distribution bias.

The obfuscated trajectories are stored in a tree structure on the server that indexes both the spatial and temporal features of the trajectories (in the form of segments). As Fig. 4 shows, the top levels of the structure together can be seen as a B-tree that indexes time intervals hierarchically, and the node capacity (which is a system parameter) of the example is 20. The time span of an entry in the leaf nodes is 3 minutes which is determined by the time span of the trajectory segments, and every entry points to a spatial index for the trajectory segments in that interval. If a segment spans across the intervals of multiple entries (which is rare as the segments are usually short even after simplification), we break the segment into multiple segments to suit the entry intervals. For example, if a segment starts at 8:29:50 and ends at 8:30:03, we break the segment at 8:30:00 into two segments that suit the time intervals [8:27:00, 8:30:00) (i.e., $N_{5}$) and [8:30:00, 8:33:00) of the leaf entries.

We create a quasi-quadtree as the spatial index to obtain nodes with non-overlapping minimum bounding rectangles (MBR). We use endpoints of the segments to build this tree. First, we insert the endpoints into the root. Once the root node capacity is reached, we partition the space into four quadrants each forming a child node. Every endpoint is moved to the child node enclosing it, while the root node now stores pointers to the child nodes. The process is done recursively until every node is within its capacity. In a leaf node, we further store the segments overlapped by the node MBR (a segment may be in multiple nodes), together with the IDs of the corresponding trajectories and clients.

When the data distribution is skewed, we may have many segments in the same leaf node. We add bitmaps to help query such segments. The bitmaps correspond to disjoint intervals that together cover the time interval of the segments in the node. The number of bitmaps can be empirically determined based on the sampling rate. Each bit value denotes whether a segment overlaps with a time interval. In Fig. 4, we build a bitmap for $N_{7}$ with 10-second intervals, where both the first and the seventh segments in $N_{7}$ overlap with the interval [8:27:00, 8:27:10).

Update handling. When there are new obfuscated trajectories, their segments (and the endpoints of the segments) are added to the index by a top-down traversal to find the nodes to be inserted into (following the query procedure in the next section). Trajectory deletion can be also done by first a tree traversal to locate the trajectory segments to be deleted. Then, the segments are removed, together with any empty nodes.

A straightforward algorithm is to query every segment from $\mathcal{D}_{q}$ independently over STS-Index, identify the data segments satisfying the query, and send the query trajectory to the corresponding clients for verification against the original trajectories.

We observe that, segments of a trajectory are connected end to end. Points of adjacent segments are likely to be in the leaf nodes that are in short-hop distance from each other in the index. Besides, our quasi-quadtrees divide the space without overlaps. By leveraging these features, we propose an efficient backtracking-based join algorithm that starts from the inner nodes instead of the root for querying each segment of a trajectory.

MBR expansion for accurate query processing. To ensure no false dismissals, we expand the MBRs of query segments to cover the simplified-and-obfuscated trajectories, as well as the query distance threshold $\delta_{d}$. Overall, we expand the MBR of a query segment by $\delta_{d}+\theta_{sp}+\theta_{ob}$ on each side. This ensures no false negatives, because by definition, the distance between a point on an original trajectory segment and the corresponding point on its simplified-and-obfuscated version cannot be greater than $\delta_{d}+\theta_{sp}+\theta_{ob}$ in any dimension. We use $\lceil{mbr}\rceil_{s_{i}}$ to denote the expanded MBR of $s_{i}$. In Fig. 5, $\lceil{mbr}\rceil_{s^{\hat{\nu}}_{1}}$ is the expanded MBR of the segment $s^{\hat{\nu}}_{1}$.

Pivots. We use pivots to help locate the adjacent segments in our algorithm. Pivots are vertices of the expanded MBR of a query segment that are close to the endpoints of the segment. Using a pivot instead of an endpoint helps avoid false negative query results, since the query MBR is expanded. In Fig. 5, $v^{\hat{\nu}}_{1\vdash}$ and $v^{\hat{\nu}}_{1\dashv}$ are the pivots of query segment $s^{\hat{\nu}}_{1}$.

On server side. As summarized in Algorithm 1, our server-side algorithm iteratively searches for similar segments for the query trajectories (lines 1 to 20). For every query trajectory $\mathcal{T}_{\nu}$, we split its segments according to the time intervals of the root nodes of the quasi-quadtrees (line 2), like we did in index construction. Then, we search for data segments similar to every segment in the split query trajectory $\mathcal{T}_{\hat{\nu}}$ (lines 3 to 20). We first update $pivot$ and its corresponding leaf node $N$. This is only needed for the first segment in $\mathcal{T}_{\hat{\nu}}$ or when we move on to a segment in a new time interval (lines 4 to 7), which rarely happens. Function $FindNode(N,pivot)$ locates node $N$ whose MBR covers the pivot in the quasi-quadtree by a point query (line 7). Then, we can leverage node $N$ to backtrack with function $Backtrack(N,p)$ that starts from $N$ and recursively traces back to the ancestor node whose MBR covers $p$. For each query segment, we stop the backtracking at the ancestor node $N_{p}$ that covers the upper pivot $v^{\hat{\nu}}_{i\dashv}$ of the expanded MBR of the current query segment (lines 8 and 9). Then, we search for similar segment pairs from $N_{p}$ for the current query segment (lines 10 to 20). For pruning, only tree nodes whose MBRs overlap with the expanded MBR $\lceil mbr\rceil_{s^{\hat{\nu}}_{i}}$ of the query segment are visited, which are stored in a queue $Q$ to support the traversal (lines 14 to 16). When the traversal reaches a simplified-and-obfuscated segment $s^{\widetilde{\mu}}$, we add $\langle s^{\widetilde{\mu}},s^{\hat{\nu}}_{i}\rangle$ to the result set $\mathcal{S}$ (line 18). Meanwhile, we verify each leaf node for whether it contains the lower pivot of the next query segment which will be used at the stage of backtracking in the next segment query (line 19). After all query trajectories have been processed, we update the query segments in $\mathcal{S}$ to their corresponding non-time-interval-split segments (line 21). Then, we group the pairs in $\mathcal{S}$ by the client that generated $s^{\widetilde{\mu}}$, and send the pairs to the clients based on the client IDs of the segments (line 22). STS-Join verifies the trajectory similarity on the clients, since the server only stores simplified-and-obfuscated trajectories. After each client has computed the trajectory similarity, it returns the result set to the server.

On client side. On each client, the trajectories corresponding to the segments $s^{\widetilde{\mu}}$ received from the server are retrieved (by ID lookups using the local trajectory IDs of the segments). Then, we compute the CDD of the segment pairs from the server and add up the CDDS for every trajectory pair formed by the segment pairs. The pairs satisfying the time threshold $\delta_{t}$ are returned as the query result to the server. This guarantees no false positives.

Discussion. Backtracking is not limited to quasi-quadtrees. It is applicable to all space-partitioning indices in which the process can stop at a common parent node. A query starting from such parent nodes will not have false negatives, since there are no overlaps among MBRs on the same level in the tree. That means one location can be covered only by one MBR at each level. In addition, backtracking can be applied in index construction, insertion, and deletion, because segments are inserted or deleted sequentially, and we can leverage the common parent node approach to reduce the node accesses when operating on the next segment.

Algorithm 1 sends all segment pairs that may satisfy the query distance threshold $\delta_{d}$ to the clients for further verification and CDDS computation. In this subsection, we compute an upper bound of the actual CDDS between a query trajectory $\mathcal{T}_{\nu}$ and a known trajectory $\mathcal{T}_{\mu}$ using $\mathcal{T}_{\nu}$ and the simplified-and-obfuscated segments of $\mathcal{T}_{\mu}$ stored on the server. We only send the segment pairs to the corresponding client when the upper bound exceeds $\delta_{t}$, thus saving both communication costs between the server and the clients and computation costs on the clients. This essentially adds a subprocedure to prune the segment pairs before Line 22 of Algorithm 1 using an upper bound of $cdds(\mathcal{T}_{\mu},\mathcal{T}_{\nu})$. For simplicity, we only describe the CDDS-based pruning procedure below but do not repeat the full pseudocode of the STS-Join algorithm powered by it.

CDDS-based pruning procedure. We group the segment pairs that satisfy the query distance threshold (i.e., the segment pairs in set $\mathcal{S}$ at Line 21 of Algorithm 1) by their client IDs, local trajectory IDs, and query trajectory IDs. The segment pairs that share the same client ID, local trajectory ID, and query trajectory ID all come from the same pair of simplified-and-obfuscated known and query trajectories $(\mathcal{T}_{\widetilde{\mu}},\mathcal{T}_{\nu})$ for CDDS upper bound computation. Let the set of such segment pairs be $\mathcal{S}_{\widetilde{\mu},\nu}$ and the original known trajectory corresponding to $\mathcal{T}_{\widetilde{\mu}}$ be $\mathcal{T}_{\mu}$, respectively. Then, we compute an upper bound of the close-distance duration (i.e., CDD) for every pair of segments in $\mathcal{S}_{\widetilde{\mu},\nu}$. Summing up these upper bounds for all segment pairs in $\mathcal{S}_{\widetilde{\mu},\nu}$ yields our upper bound of $cdds(\mathcal{T}_{\mu},\mathcal{T}_{\nu})$, since these pairs are the only ones in $\mathcal{T}_{\widetilde{\mu}}\times\mathcal{T}_{\nu}$ (and hence $\mathcal{T}_{\mu}\times\mathcal{T}_{\nu}$) that satisfy the query distance threshold by definition. The set $\mathcal{S}_{\widetilde{\mu},\nu}$ is pruned from being sent to a client if the CDDS upper bound is less than $\delta_{t}$. Next, we detail our CDD upper bound computation.

CDD upper bound. Recall that the CDD between a known segment $s^{\mu}_{i}$ of $\mathcal{T}_{\mu}$ and a query segment $s^{\nu}_{j}$ of $\mathcal{T}_{\nu}$, $cdd(s^{\mu}_{i},s^{\mu}_{j})$, is the time duration when their spatial distance is within $\delta_{d}$. We further define the CDD between a simplified-and-obfuscated segment $s^{\widetilde{\mu}}_{i}$ and a query segment $s^{\nu}_{j}$ as the time duration where their spatial distance is within $\delta_{d}+\theta_{sp}+\sqrt{2}\theta_{ob}$, denoted as $\overline{cdd}(s^{\widetilde{\mu}}_{i},s^{\nu}_{j})$. Then, for all known segments $s^{\mu}_{i},s^{\mu}_{i+1},\ldots,s^{\mu}_{i+\Delta}$ corresponding to $s^{\widetilde{\mu}}_{i}$, $\sum_{k=0}^{\Delta}cdd(s^{\mu}_{i+k},s^{\mu}_{j})\leq\overline{cdd}(s^{\widetilde{\mu}}_{i},s^{\nu}_{j})$. This is because, given a point on a known segment, its corresponding point on the simplified-and-obfuscated segment is within a distance of $\theta_{sp}+\sqrt{2}\theta_{ob}$ by definition. Thus, if the distance between (points on) $s^{\mu}_{i+k}$ and $s^{\nu}_{j}$ is within $\delta_{d}$, the distance between (points on) $s^{\widetilde{\mu}}_{i}$ and $s^{\nu}_{j}$ must be within $\delta_{d}+\theta_{sp}+\sqrt{2}\theta_{ob}$. Therefore, we use $\overline{cdd}(s^{\widetilde{\mu}}_{i},s^{\nu}_{j})$ as our CDD upper bound of the original known trajectories.

We formulate the CDD upper bound and show its correctness with the following lemma.

Given Lemma 5.1, we have the following lemma to bound the CDDS for the original known trajectories.

We analyze the cost of Algorithm 1 in terms of the number of node accesses. If a query segment spans the whole spatio-temporal space (worst case), all index nodes may be visited, with or without backtracking. However, this rarely happens. In many cities, points of interest are distributed in a polycentric structure (Deng et al., 2019; Cai et al., 2017). Trajectories are likely to gather near local centers, where backtracking helps query the sub-spatial index of the centers.

The algorithm iterates through the query segments. In each iteration, the costs are spent on finding the common parent node of two adjacent points (and hence adjacent segments) in the query trajectory and on traversing the index to reach leaf nodes.

First, we derive the backtracking distance $bd$ (i.e., the number of tree levels) between the leaf nodes and the common parent node of two adjacent points. We use the expectation $\operatorname{\mathbb{E}}{(bd)}$ to measure the average cost, which is obtained by summing up different backtracking lengths weighted by their probabilities.

We use Fig. 7 to illustrate how to derive $\operatorname{\mathbb{E}}{(bd)}$ with a space division in the quasi-quadtree. The width of the expanded MBR covering the (red) query segment is $m$ and the height is $n$, where $m\geqslant n$. Let the side length of the space be $d$ and that of a cell be $c$. Here, each cell corresponds to a leaf node. In our quasi-quadtree, once the node capacity is exceeded, a node will be divided into four sub-nodes. The space covered by the node is split into four quadrants. We call the vertical and horizontal boundaries (the black dash lines) between the sub-spaces the splitting lines.

Different splitting lines divide the space at different index levels. The backtracking distance can be derived by the levels of the splitting lines that intersect with the expanded MBR. To derive whether an expanded MBR intersects with a splitting line, we compare the location of the upper left vertex of the MBR with the splitting line. In Fig. 7a, when the upper left vertex of the MBR falls in the pink area, the query segment intersects with a splitting line at level 0. The common parent node is the root of the quasi-quadtree, and $bd$ is the height $h$ of this tree, i.e., $\lfloor\log_{2}\frac{d}{c}\rfloor$. Fig. 7b shows the level-1 splitting lines, where the backtracking distance is $h-1$ if the expanded MBR intersects with them.

Next, we consider the stop condition of segment intersection. When $m$ and $n$ are large, a query segment may intersect with splitting lines at multiple lower levels, while common parent nodes cannot be at such levels. Let the lowest feasible level of the common parent node be $I$, $I=\lfloor\log_{2}\frac{d}{2m}\rfloor$. This is because, given a pivot of a query segment in a node, we need at most a common parent node with an MBR side length of $2m$ to also cover the other pivot of the segment. In Fig. 7b, if $m>4c$ and $n>4c$, the query segment intersects with splitting lines at levels 1 to 4. We only need to consider the case where the query segment intersects with the splitting lines at level 0.

The probabilities of different backtracking lengths are derived by the ratio of the data space occupied by the pink area of different levels. We cut off the grey area in Fig. 7, as the query segment is outside the space when its expanded MBR is in this area.

Then, we compute $\operatorname{\mathbb{E}}(bd)$ by summing up the product of the probability and the backtracking distance at every level:

where the fraction part is the probability determined by the size of the pink area, and $h-i$ is the distance between a leaf node and the common parent node. We let $\Lambda=\frac{1}{(b-m)(b-n)}$ and then expand Equation 11: