Graphs can be used to represent not only road networks but also routing networks and computer networks. In such kind of applications, entities, such as packets, are moving on the network and the information associated with these movements are known regarding to the vertices they traverse. In such a context a trajectory for these entities can be de ned as sequences of vertices and time intervals. We aim at designing fast algorithms for nding all the trajectories which are similar to (i.e. moving close to) a given trajectory in a speci ed time window.
In this work, we are interested in algorithms to e ciently retrieve similar
trajectories to a given one for an undirected graph. Many papers in literature have
focused on extracting information from sets of trajectories, basically, looking at
them as strings, so the similarity between trajectories corresponds to similarity
between strings. In such a context, the similarity measure have been formalized
by means of some concepts like longest common subsequences [
Problem 1. Given a graph, a set of trajectories, a trajectory x, and a time interval, nd the subset of trajectories which are similar to x in the speci ed time interval.
Problem 2. Given a vertex v of a graph G, a set of trajectories, and a time
interval, nd all the trajectories close to v for the whole given time interval.
Related work. Some papers have focused on nding trajectories moving together
in a certain area of the plane in some applications like tra c monitoring,
emarketing and route nding [
Our contribution. In this paper, we propose a method, to solve our problems which consists of the following two phases.
The preprocessing phase: given a graph and a set of trajectories, prepare suitable data structures to maintain trajectories in order to answer queries. This phase is the same for both problems.
The query phase: { given a vertex and a time interval, use the data structures built in the preprocessing phase to nd all trajectories traversing close to the vertex within the given time interval, which corresponds to Problem 2 { given a trajectory and a time interval, use the solutions of Problem 2 to answer queries for Problem 1. 2
De nition 1 (Trajectory). Given an undirected graph G = (V; E), a trajectory x is a sequence x = h(v1; T1); (v2; T2); ; (vl; Tl)i such that for each i 2 N; 1 i l 1, we have (vi; vi+1) 2 E and Ti is a time interval [ai; bi] with ai; bi 2 N, and ai bi < ai+1 bi+1; bi + 1 = ai+1. We call l, i.e. the length of x, as number of movements.
Given a set of trajectories T , let us de ne the projection set Sv for each v 2 V , as f(T; x)j(v; T ) 2 xg (i.e. (v; T ) appears in x). As we can see in the following example, there can be more than one pair associated with a vertex for a given trajectory, since each trajectory can traverse a vertex multiple times during its lifetime. For a trajectory x and a time t 2 N, the notation x(t) indicates the vertex v 2 V such that x contains (v; T ) and t 2 T . For each vertex v 2 V , we denote Nv as the set of neighbors of vertex v and fvg [ Nv as Bv. De nition 2 (Time Constrained Similar Trajectories). Given two trajectories x; y and time t 2 N, let u and v be vertices x(t) and y(t), respectively. We say x; y are similar at time t, if either u = v or u 2 Nv. For a given time interval T , x and y are similar in T if they are similar for each time t 2 T . We explain the de nitions by giving a simple example. Example 1 Graph G = (V; E); V = fv1; : : : v4g and a set of two trajectories T = fx1; x2g are shown in Figure 1. Consider (v1; [1; 7]) in x1. This means that trajectory x1 have traversed through the vertex v1 2 G for each time t 2 [1; 7]. x1 = h(v1; [1; 7]); (v2; [8; 9]); (v4; [10; 13]); (v1; [14; 17]); (v3; [18; 20])i x2 = h(v1; [1; 4]); (v2; [5; 7]); (v3; [8; 9])i
x1 x2 v1 [1; 7]; [14; 17] [1; 4] v2 [8; 9] [5; 7] v3 [18; 20] [8; 9] v4 [10; 13]
For a given trajectory x2 and the time interval T = [3; 6] in our example, the trajectory x1 is similar to x2 at time interval T , since for each time t 2 T they are at neighbor vertices v1 and v2. For instance, x1 is at v1 during the time interval [3; 6], and x2 is at v1 at times t = 3; 4 and at v2 for t = 5; 6. In our given example, in Figure 1, we have Sv1 = f([1; 7]; x1); ([14; 17]; x1); ([1; 4]; x2)g. Preprocessing and Query De nition. For both Problems 1 and 2, we de ne preprocessing(G; T ), where G = (V; E) is a graph and T is a set of trajectories. Given G and T , we aim at answering the following queries, which corresponds to Problem 1 and 2, respectively. query1(x; T ). Given a trajectory x, and a time interval T = [a; b], nd the set of trajectories which are similar to x in the time interval. query2(v; T ). Given a vertex v, and a time interval T = [a; b], nd the set of trajectories, traversing vertices in Bv for each time t 2 T .
Lemma 1. Suppose we can solve query2(vi; Ti) in time O(Z) for some Z( ). By using its solution, query1(x; T = [a; b]) can be answered in time O(log l + h Z), where h is the number of movements in x within the time interval T . Proof. Let H be the set of pairs (vi; Ti) in x, with Ti = [ai; bi] such that b ai and a bi. We have h = jHj. We run query2(vi; Ti) for each pair (vi; Ti) 2 H. Let Uvi be the output set of query2(vi; Ti), then we report Tih=1 Uvi as the solution set for query1(x; T ). We now prove that this algorithm is correct. For each pair (vi; Ti) in x, trajectory x is at vertex vi during time interval Ti (i.e. 8t 2 Ti; x(t) = vi). This means that all trajectories, traversing either vi or Nvi for each time instance t 2 Ti, are similar to x in a time interval Ti (De nition 2). By de nition of query2, these are returned by query2(vi; Ti). As the set of trajectories similar to x in T = Sih=1 Ti is the intersection of trajectories similar to x in each Ti with 1 i h, we return the intersection of the sets Uvi . As x is a time ordered sequence of pairs, we can nd the set H easily in time O(log l +h). Since, we run query2(vi; Ti) for each pair (vi; Ti) 2 H, we pay O(h Z). The cost of the intersection is dominated by this cost.
Hence, in the following we will concentrate on solving query2. In our solution preprocessing(G; T ) is the same for both the problems.
Preprocessing Phase. Recall that for each vertex u 2 V , Su is the set of
trajectories from T that pass through u with the corresponding time intervals.
Similarly, here we de ne SBu for each vertex u 2 V as SBu = Sw2Bu Sw. Let
jSBu j denotes the size of the set SBu ,which is the number of movements that
trajectories have done within the vertices in Bu. Given a set SBu , we de ne
C(SBu ), a re nement of SBu , which basically considers time intervals spent by
a trajectory in Bu as a unique interval in O(jSBu j jNuj) time. More formally,
assume y is a trajectory passing through Bu, i.e. y appears in SBu . If we have
consecutive pairs h(ui; Ti); (ui+1; Ti+1)i belong to y, such that ui; ui+1 2 Bu,
we have h(Ti; y); (Ti+1; y)i 2 SBu , so we consider (Ti [ Ti+1; y) 2 C(SBu ). For
instance, assume we are given v3 2 V in our graph example in Figure 1, and
Bv3 = fv1; v2; v3g. For the trajectory x1 = h(v1; [1; 7]); (v2; [8; 9])i, we consider
([1; 9]; x1) 2 C(SBv3 ). Our preprocessing phase builds an interval tree [
Lemma 2. preprocessing(G; T ) takes O( u2V (jSBu j jNuj) + ru log ru) time and uses O( u2V ru) space. Given a vertex v, and a time interval T = [a; b], we want to nd the set of trajectories, traversing the vertices in Bv at each time instance t 2 T . We will make use of the interval trees built in preprocessing(G; T ).
Query Phase. Consider the interval tree associated with C(SBv ) which maintains the time intervals endowed with the trajectories passing Bv they belong to. We obtain all the trajectories traversing Bv for each time t 2 T , by nding all the intervals which are fully contained in T . As the interval tree associated with v has depth O(log rv), the cost of retrieving all the intervals fully contained in T is O(log rv + jUvj), where jUvj is the number of reported trajectory id's. Indeed, notice that we cannot have two time intervals belonging to the same trajectory in the output set, since we are reporting the intervals fully contained in T . Theorem 1. For a vertex v and a time interval T , we can answer query2(v; T ) in O(log rv + jUvj) time, where jUvj is the number of reported trajectories. Let K =
vij(vi;Ti)2H jUvi j, by applying Lemma 1, we obtain the following. Corollary 1. query1(x; T ) can be answered in O(log l + K) time. vij(vi;Ti)2H log rvi + As future work, we plan to enhance our algorithm to reduce the storage usage and consider di erent similarity measures.
Acknowledgments. The author wishes to thank R. Grossi and A. Marino for helpful discussions.