# A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks

Authors: Yajun Yang; Hanxiao Li; Junhu Wang; Qinghua Hu; Xin Wang; Muxi Leng
Journal: Complexity
 (2019)

---

## Abstract

K nearest neighbor (kNN) search is an important problem in location-based services (LBS) and has been well studied on static road networks. However, in real world, road networks are often time-dependent; i.e., the time for traveling through a road always changes over time. Most existing methods for kNN query build various indexes maintaining the shortest distances for some pairs of vertices on static road networks. Unfortunately, these methods cannot be used for the time-dependent road networks because the shortest distances always change over time. To address the problem of kNN query on time-dependent road networks, we propose a novel voronoi-based index in this paper. Furthermore, we propose a novel balanced tree, named V-t
r
e
e, which is a secondary level index on voronoi-based index to make our querying algorithm more efficient. Moreover, we propose an algorithm for preprocessing time-dependent road networks such that the waiting time is not necessary to be considered. We confirm the efficiency of our method through experiments on real-life datasets.


---

## Body

## 1. Introduction

With the rapid development of mobile devices,k nearest neighbor (kNN) search on road networks has become more and more important in location-based services (LBS)[1–4]. Given a query location and a set of objects (e.g., restaurants) on a road network, it is to find k nearest objects to the query location. kNN search problem has been well studied on static road networks. However, road networks are essentially dynamic complex networks but not static in real world [5–8]. The “dynamic” means that the traveling time on road network is always time-dependent. For example, the Vehicle Information and Communication System (VICS) and the European Traffic Message Channel (TMC) are two transportation systems, which provide real-time traffic information to users. Such road networks are time-dependent; i.e., travel time for a road varies with taking “rush hour” into account.The existing works propose various index techniques for answeringk nearest object query on road networks. The main idea behind these indexes is to partition the vertices into several clusters, and then the clusters are organized as a voronoi diagram or a tree (e.g., R-tree, G-tree). All these methods precompute and maintain the shortest distances for some pairs of vertices to facilitate kNN query. Unfortunately, these indexes cannot be used for time-dependent road networks. The reason is that the minimum travel time between two vertices often varies with time. For example, u and v are in the same cluster for one time period but they may be in two distinct clusters for another time period because of the minimum travel time varying with time. Therefore, the existing index techniques based on the static shortest distance cannot handle the case that the minimum travel time is time-dependent. Moreover, the waiting time is allowed on time-dependent road networks; i.e., someone can wait a time period to find another faster path. When the waiting time is considered, it is more difficult to build an index for kNN query by existing methods because it is difficult to estimate an appropriate waiting time for precomputing the minimum travel time between two vertices.Recently, there are some works aboutkNN query on time-dependent graphs [9–12]. Most of these works utilize A∗ algorithm to expand the road networks by estimating an upper or lower bound of travel time. There are two main drawbacks of these methods. First, in these works, the FIFO (first in first out) property is required for the networks and the waiting time is not allowed. Second, the indexes proposed by these works are based on the estimated value of travel time. However, these indexes cannot facilitate query effectively for large networks because the deviations are always too large between the estimated and the actual travel time.In this paper, we studyk nearest object query on time-dependent road networks. A time-dependent road network is modeled as a graph with time information. The weight of every edge is a time function w
i
,
j
(
t
) which specifies how much time it takes to travel through the edge (
v
i
,
v
j
) if departing at time point t. The main idea of our method is to precompute minimum travel time functions (or m
t
t-function for short) instead of concrete values for some pairs of vertices and then design a “dynamic” voronoi-based index based on such functions. Here “dynamic” means that in a time-dependent network it can be easily decided which cluster a vertex should be in for any given time point t. Furthermore, a secondary level index is built on voronoi-based index, which makes our querying algorithm more “smart” for k nearest objects searching; that is, the k nearest objects will be searched and the others will be filtered as early as possible. Different to previous works, our index can facilitate query effectively for large networks. Moreover, our method does not require the FIFO property for networks and we allow waiting time on every vertex.The main contributions of this paper are summarized as below. First, we propose an algorithm to processw
i
,
j
(
t
) for every edge such that the waiting time is not necessary to be considered. Let G
T and G
T
∗ be the original graph and the graph after processing w
i
,
j
(
t
). We can prove that a shortest path with consideration of waiting time on G
T is one-to-one mapped to shortest path without waiting time on G
T
∗. Furthermore, we show how to compute the m
t
t-function for two vertices. Second, we propose a novel voronoi-based index for time-dependent road networks and an algorithm to answer kNN query using our index. Third, we propose a novel balanced tree structure, named V-t
r
e
e, which can be considered as the secondary level index on voronoi-based index to make k nearest object query more efficient. Finally, we confirm the efficiency of our method through extensive experiments on real-life datasets.The rest of this paper is organized as follows. Section2 gives the problem statement. Section 3 decribes how to process w
i
,
j
(
t
) and compute the m
t
t-function. Section 4 explains how to build the voronoi-based index for time-dependent networks. Section 5 introduces the V-t
r
e
e and how to answer the k nearest object query using it. The experimental results are presented in Section 6. The related work is in Section 7. Finally, we conclude this paper in Section 8.


## 2. Problem Statement

Definition 1 (time-dependent road network).
A time-dependent road network is a simple directed graph, denoted asG
T
(
V
,
E
,
W
) (or G
T for short), where V is the set of vertices; E
⊆
V
×
V is the set of edges; and W is a set of nonnegative value function. For every edge (
v
i
,
v
j
)
∈
E, there is a time function w
i
,
j
(
t
)
∈
W, where t is a time variable. A time function w
i
,
j
(
t
) specifies how much time it takes to travel from v
i to v
j, if one departs from v
i at time point t.In this paper, we assume thatw
i
,
j
(
t
)
≥
0. The assumption is reasonable, because the travel time cannot be less than zero in real applications. Our work can be easily extended to handle undirected graphs. An undirected edge (
v
i
,
v
j
) is equivalent to two directed edges (
v
i
,
v
j
) and (
v
j
,
v
i
), where w
i
,
j
(
t
)
=
w
j
,
i
(
t
).There are several works that study how to construct time functionw
i
,
j
(
t
), which is always modeled as a piecewise linear function [6, 7, 13] and it can be formalized as follows:(1)
w
i
,
j
t
=
a
1
t
+
b
1
,
t
0
≤
t
<
t
1
a
2
t
+
b
2
,
t
1
≤
t
<
t
2
⋯
a
p
t
+
b
p
,
t
p
-
1
≤
t
≤
t
pGiven a pathp, the travel time of p is time-dependent. In order to minimize the travel time, some waiting time ω
i is allowed at every vertex v
i in p. That is, when arriving at v
i, one can wait a time period ω
i if the travel time of p can be minimized. We usea
r
r
i
v
e
(
v
i
) andd
e
p
a
r
t
(
v
i
) to denote the arrival time at v
i and departure time from v
i, respectively. For each v
i in p, we have(2)
d
e
p
a
r
t
v
i
=
a
r
r
i
v
e
v
i
+
ω
iLet p
=
v
1
→
v
2
→
⋯
→
v
h be a given path with the departure time t and the waiting time ω
i for each vertex v
i; then we have(3)
a
r
r
i
v
e
v
1
=
t
a
r
r
i
v
e
v
2
=
d
e
p
a
r
t
v
1
+
w
1,2
d
e
p
a
r
t
v
1
⋯
a
r
r
i
v
e
v
h
=
d
e
p
a
r
t
v
h
-
1
+
w
h
-
1
,
h
d
e
p
a
r
t
v
h
-
1Thus the travel time of pathp isw
(
p
)
=
a
r
r
i
v
e
(
v
h
)
-
t
. Given two vertices v
i and v
j in G
T, the minimum travel time from v
i to v
j with departure time t is defined as m
i
,
j
(
t
)
=
m
i
n
w
p
∣
p
∈
P
i
,
j, where P
i
,
j is the set of all the paths from v
i to v
j in G
T. Obviously, m
i
,
j
(
t
) is also a function related to the departure time t. We call m
i
,
j
(
t
) the minimum travel time function (or m
t
t-function shortly) from v
i to v
j. Letting |
V
| be n, in the following, we use m
i
,
n
+
j
(
t
) to represent m
t
t-function from a vertex v
i to an object o
j, in order to distinguish from m
i
,
j
(
t
) from v
i to a vertex v
j. Note that an object o
i is also a vertex regarded as v
n
+
i in the network.There is a special case that the waiting time is only allowed on a subsetV
w of V; that is, people are allowed to wait a time period ω
i only when they are at the vertex v
i
∈
V
w. For this case, we only need to consider that the waiting time is always zero, i.e., ω
i
≡
0, for every vertex v
i
∈
V
∖
V
w. Therefore, the method proposed in this paper can be extended to handle this case easily.Next, we give the definition ofkNN query over time-dependent road networks.Definition 2 (k nearest objects on time-dependent road networks).
Given a time-dependent road networkG
T
(
V
,
E
,
W
), a set of the objects O
=
o
1
,
o
2
,
⋯, a query point v
q
∈
V, and a departure time t
d, k nearest object query of v
q is to find a k-size subset O
(
v
q
)
⊆
O, such that m
q
,
n
+
j
(
t
d
)
≥
m
a
x
m
q
,
n
+
i
t
d
∣
o
i
∈
O
v
q for every object o
j
∈
O
∖
O
(
v
q
).


## 3. Minimum Travel Time Function

We precomputem
t
t-functions for some pairs of vertices and then build the index to facilitate kNN query over time-dependent road networks. In this section, we first describe how to process the time function w
i
,
j
(
t
) for every edge in G
T such that the waiting time is not necessary to be considered when computing m
t
t-function and then we explain how to compute m
t
t-function without waiting time.


### 3.1. Preprocessing Time Function for Every Edge

Given a pathp, the waiting time ω
i is allowed for any vertex v
i
∈
p. However, it is not easy to find an appropriate value of ω
i for every v
i
∈
p to minimize the travel time of p. In this section, we propose an algorithm to convert time function w
i
,
j
(
t
) to a new function w
i
,
j
∗
(
t
) for every edge (
v
i
,
v
j
)
∈
E. We call w
i
,
j
∗
(
t
) the “no waiting time function” of edge (
v
i
,
v
j
) (or n
w
t-function for short). The waiting time can be considered as zero when n
w
t-function is used to compute the minimum travel time of path p. The n
w
t-function w
i
,
j
∗
(
t
) is defined by the following:(4)
w
i
,
j
∗
t
=
m
i
n
ω
i
ω
i
+
w
i
,
j
t
+
ω
iNote that when the waiting time is only allowed on a vertex subsetV
w, we only need to calculate n
w
t-function w
i
,
j
∗
(
t
) for every vertex v
i
∈
V
w. For every vertex v
i
∈
V
∖
V
w, the n
w
t-function w
i
,
j
∗
(
t
) is exactly the time function w
i
,
j
(
t
) because ω
i
≡
0; that is, anyone is not allowed to wait a time period ω
i at v
i.The following theorem guarantees that then
w
t-function w
i
,
j
∗
(
t
) can be used to compute the minimum travel time for any path p in G
T without waiting time.Theorem 3.
Given two time-dependent graphsG
T
(
V
,
E
,
W
) and G
T
∗
(
V
,
E
,
W
∗
), where W
∗ is the set of n
w
t-functions of all edges in E, for any path p in G
T, the minimum travel time of p in G
T
with consideration of waiting time equals the minimum travel time of p in G
T
∗ without waiting time.Proof.
Letp
=
v
1
→
v
2
→
⋯
→
v
h be a given path with the departure time t. ω
i
∗ is the waiting time on v
i
(
1
≤
i
≤
h
) minimizing the travel time of p in G
T. We haved
e
p
a
r
t
(
v
i
)
=
a
r
r
i
v
e
(
v
i
)
+
ω
i
∗ anda
r
r
i
v
e
(
v
i
+
1
)
=
d
e
p
a
r
t
(
v
i
)
+
w
i
,
i
+
1
(
d
e
p
a
r
t
(
v
i
)
)
. Similarly, we haved
e
p
a
r
t
∗
(
v
i
)
=
a
r
r
i
v
e
∗
(
v
i
) anda
r
r
i
v
e
∗
(
v
i
+
1
)
=
d
e
p
a
r
t
∗
(
v
i
)
+
w
i
,
i
+
1
∗
(
d
e
p
a
r
t
∗
(
v
i
)
) for G
T
∗. We only need to provea
r
r
i
v
e
(
v
h
)
=
a
r
r
i
v
e
∗
(
v
h
)
. It can be easily proved by induction on v
i. We omit it due to the space limitation.The algorithm to computen
w
t-function is shown in Algorithm 1. For every w
i
,
j
(
t
)
∈
W, if v
i
∈
V
w, Algorithm 1 computes w
i
,
j
∗
(
t
) backward from [
t
p
-
1
,
t
p
] to [
t
0
,
t
1
] iteratively. In each iteration, w
i
,
j
∗
(
t
) for t
∈
[
t
k
-
1
,
t
k
) is computed. Algorithm 1 first sets w
i
,
j
∗
(
t
) as a
∗
t
+
b
∗, where a
∗
=
-
1 and b
∗
=
t
k
+
ϕ. ϕ is the minimum value between w
i
,
j
∗
(
t
k
) and w
i
,
j
-
(
t
k
). w
i
,
j
-
(
t
k
) is the left limit value of w
i
,
j
(
t
) on t
k. Note that w
i
,
j
∗
(
t
k
) and ϕ have been computed in the last iteration; i.e., the iteration for computing w
i
,
j
∗
(
t
) on [
t
k
,
t
k
+
1
). ϕ is initialized as w
i
,
j
(
t
p
). Next, Algorithm 1 updates w
i
,
j
∗
(
t
) as m
i
n
w
i
,
j
∗
t
,
w
i
,
j
t for t
∈
[
t
k
-
1
,
t
k
) and then ϕ is updated as m
i
n
w
i
,
j
∗
t
k
-
1
,
w
i
,
j
-
t
k
-
1. The algorithm terminates when w
i
,
j
∗
(
t
) has been computed for t
∈
[
t
0
,
t
1
). Note that if v
i
∉
V
w, w
i
,
j
∗
(
t
) is computed as w
i
,
j
(
t
) immediately.Algorithm 1:Nwt-Function  G
T
V
,
E
,
W
,
V
w.
Input:  G
T
(
V
,
E
,
W
) and V
w.
Output:  W
∗.
1:W
∗
←
∅;
2:for every w
i
,
j
(
t
)
∈
W  do
3:if  v
i
∈
V
w  then
4:ϕ
←
w
i
,
j
(
t
p
), w
i
,
j
∗
(
t
p
)
←
w
i
,
j
(
t
p
);
5:for k
=
p to 1do
6:a
∗
←
-
1, b
∗
←
t
k
+
ϕ;
7:w
i
,
j
∗
(
t
)
←
a
∗
t
+
b
∗ for t
∈
[
t
k
-
1
,
t
k
);
8:w
i
,
j
∗
(
t
)
←
min
⁡
w
i
,
j
∗
t
,
w
i
,
j
t
∣
t
∈
t
k
-
1
,
t
k;
9:ϕ
←
m
i
n
{
w
i
,
j
∗
(
t
k
-
1
)
,
w
i
,
j
-
(
t
k
-
1
)
};
10:else
11:w
i
,
j
∗
(
t
)
←
w
i
,
j
(
t
);
12:W
∗
←
W
∗
∪
{
w
i
,
j
∗
(
t
)
};
13:return  W
∗The time and space complexities analysis for Algorithm1 are given below. Let n and m be the number of the vertices and edges in G
T, respectively. For every edge (
v
i
,
v
j
), Algorithm 1 needs to compute w
i
,
j
∗
(
t
) on [
t
k
-
1
,
t
k
) iteratively from k
=
p to 1. For every time interval [
t
k
-
1
,
t
k
), w
i
,
j
∗
(
t
) can be computed in constant time. Therefore, the time complexity of Algorithm 1 is O
(
m
p
). Moreover, Algorithm 1 needs to maintain w
i
,
j
∗
(
t
) and then the space complexity is also O
(
m
p
).Example 4.
We illustrate how to computew
i
,
j
∗
(
t
) by an example in Figure 1. As the solid black line in Figure 1(a), w
i
,
j
(
t
) is a piecewise linear function:(5)
w
i
,
j
t
=
t
+
5
,
0
≤
t
<
10
15
,
10
≤
t
<
20
-
2
t
+
55
,
20
≤
t
≤
25In the first iteration, ϕ is initialized as w
i
,
j
(
25
)
=
5 and then b
∗
=
25
+
ϕ
=
30. As the dashed red line in the right-side of Figure 1(a), we find that a
∗
t
+
b
∗
=
-
t
+
30 is always less than w
i
,
j
(
t
) on [
20,25
], then w
i
,
j
∗
(
t
)
=
-
t
+
30 for t
∈
[
20,25
], and ϕ is updated as 10. Similarly, in the second iteration, w
i
,
j
∗
(
t
) on [
10,20
) is computed as m
i
n
{
15
,
-
t
+
30
}, i.e., w
i
,
j
∗
(
t
)
=
15 for t
∈
[
10,15
) and w
i
,
j
∗
(
t
)
=
-
t
+
30 for t
∈
[
15,20
). Then ϕ is updated as m
i
n
w
i
,
j
∗
10
,
w
i
,
j
-
10
=
15. In the final iteration, as the dashed red line in the left-side of Figure 1(a), a
∗
t
+
b
∗
=
-
t
+
25 is alway larger than t
+
5 on [
0,10
), and we have w
i
,
j
∗
(
t
)
=
t
+
5 for t
∈
[
0,10
). Then w
i
,
j
∗
(
t
) is given below and depicted in Figure 1(b)).(6)
w
i
,
j
∗
t
=
t
+
5
,
0
≤
t
<
10
15
,
10
≤
t
<
15
-
t
+
30
,
15
≤
t
≤
25Figure 1
Computingw
i
,
j
∗
(
t
).
(a)
w
i
,
j
(
t
)
(b)
w
i
,
j
∗
(
t
)The following theorem guarantees the correctness of Algorithm1.Theorem 5.
w
i
,
j
∗
(
t
) computed by Algorithm 1 is exactly the n
w
t-function w
i
,
j
∗
(
t
) given by (4).Proof.
We proved it by induction onp.
Basis. We need to prove that w
i
,
j
∗
(
t
) on time interval [
t
p
-
1
,
t
p
] can be correctly computed by Algorithm 1. First, ω
i can only be zero when t
=
t
p; then we have w
i
,
j
(
t
p
)
=
w
i
,
j
∗
(
t
p
) and ϕ
p
=
w
i
,
j
(
t
p
). Next, we consider the case of t
∈
[
t
p
-
1
,
t
p
).
By the definiton ofw
i
,
j
∗
(
t
), we have(7)
w
i
,
j
∗
t
=
m
i
n
ω
i
ω
i
+
w
i
,
j
t
+
ω
i
=
m
i
n
ω
i
ω
i
+
a
p
t
+
ω
i
+
b
p
=
m
i
n
ω
i
a
p
+
1
ω
i
+
a
p
t
+
b
p
=
m
i
n
ω
i
a
p
+
1
ω
i
+
w
i
,
j
tFor t
∈
[
t
p
-
1
,
t
p
), if a
p
≥
-
1, w
i
,
j
∗
(
t
) cannot decrease with ω
i increasing. It means that (
a
p
+
1
)
ω
i
+
w
i
,
j
(
t
) is minimum when ω
i
=
0 and then w
i
,
j
∗
(
t
)
=
w
i
,
j
(
t
). If a
p
<
-
1, w
i
,
j
∗
(
t
) will decrease with ω
i increasing and thus (
a
p
+
1
)
ω
i
+
w
i
,
j
(
t
) is minimum when ω
i
=
t
p
-
t, which is the longest waiting time on v
i for t
∈
[
t
p
-
1
,
t
p
). Then we have(8)
w
i
,
j
∗
t
=
a
p
+
1
t
p
-
t
+
a
p
t
+
b
p
=
-
t
+
t
p
+
ϕ
pObviously, w
i
,
j
(
t
)
≤
-
t
+
t
p
+
ϕ
p when a
p
≥
-
1 and w
i
,
j
(
t
)
≥
-
t
+
t
p
+
ϕ
p when a
p
<
-
1. Then we have w
i
,
j
∗
(
t
)
=
m
i
n
w
i
,
j
t
,
-
t
+
t
p
+
ϕ
p for t
∈
[
t
p
-
1
,
t
p
].
Induction. Assuming that the correct w
i
,
j
∗
(
t
) can be computed by Algorithm 1 for t
∈
[
t
k
,
t
p
], then we need to prove it also can be correctly computed for t
∈
[
t
k
-
1
,
t
k
). We consider the following two cases: (1) ω
i
≥
t
k
-
t and (2) ω
i
<
t
k
-
t.
For case (1), the departure timet
+
ω
i
∈
[
t
k
,
t
p
] because ω
i
≥
t
k
-
t. By the assumption, n
w
t-function w
i
,
j
∗
(
t
) has been correctly computed for t
∈
[
t
k
,
t
p
]; then w
i
,
j
∗
(
t
k
) is the minimum travel time for edge (
v
i
,
v
j
) with departure time t
k. Therefore, w
i
,
j
∗
(
t
) for t
∈
[
t
k
-
1
,
t
k
) can be computed by the following:(9)
w
i
,
j
∗
t
=
t
k
-
t
+
w
i
,
j
∗
t
k
For case (2), becauseω
i
<
t
k
-
t, then t
+
ω
i
∈
[
t
k
-
1
,
t
k
). Similar to the proof of basis, we have(10)
w
i
,
j
∗
t
=
min
⁡
w
i
,
j
t
,
-
t
+
t
k
+
w
i
,
j
-
t
kNote that when a
k
<
-
1, w
i
,
j
∗
(
t
)
=
-
t
+
t
k
+
w
i
,
j
-
(
t
k
) because w
i
,
j
(
t
) may be noncontinous at t
k. Therefore, we have (11)
w
i
,
j
∗
t
=
min
⁡
w
i
,
j
t
,
-
t
+
t
k
+
w
i
,
j
-
t
k
,
-
t
+
t
k
+
w
i
,
j
∗
t
kThe proof is completed.


### 3.2. Computing Minimum Travel Time Function

We adopt a Dijkstra-based algorithm proposed in [13] to compute m
t
t-function for two vertices v
i and v
j in G
T. This algorithm is only used in case the waiting time is not allowed. After converting w
i
,
j
(
t
) to n
w
t-function w
i
,
j
∗
(
t
) for every edge in G
T by Algorithm 1, this algorithm can be used for time-dependent graphs with waiting time.The main idea of this Dijkstra-based algorithm is to refine a functiong
i
,
j
(
t
) iteratively for every v
j
∈
V, where g
i
,
j
(
t
) represents the earliest arrival time on v
j if departing from v
i at time point t. In every iteration, algorithm selects a vertex v
x
∈
V and then refines g
i
,
x
(
t
) by extending a time domain I
x to a larger I
x
′, where I
x
=
[
t
0
,
τ
x
] is a subinterval of the whole time domain T. g
i
,
x
(
t
) is regarded as well refined in I
x if it specifies the earliest arrival time at v
x from v
i for any departure time t
∈
I
x. The algorithm repeats time-refinement process till g
i
,
j
(
t
) of destination v
j has been well refined in the whole time domain T and then m
t
t-function m
i
,
j
(
t
) can be computed as m
i
,
j
(
t
)
=
g
i
,
j
(
t
)
-
t. The more details about this Dijkstra-based algorithm is given in [13]. As shown in [13], the time and space complexities are O
(
(
n
log
⁡
n
+
m
)
α
(
T
)
) and O
(
(
n
+
m
)
α
(
T
)
), respectively, where α
(
T
) is the cost required for each function (defined in interval T) operation.


## 3.1. Preprocessing Time Function for Every Edge

Given a pathp, the waiting time ω
i is allowed for any vertex v
i
∈
p. However, it is not easy to find an appropriate value of ω
i for every v
i
∈
p to minimize the travel time of p. In this section, we propose an algorithm to convert time function w
i
,
j
(
t
) to a new function w
i
,
j
∗
(
t
) for every edge (
v
i
,
v
j
)
∈
E. We call w
i
,
j
∗
(
t
) the “no waiting time function” of edge (
v
i
,
v
j
) (or n
w
t-function for short). The waiting time can be considered as zero when n
w
t-function is used to compute the minimum travel time of path p. The n
w
t-function w
i
,
j
∗
(
t
) is defined by the following:(4)
w
i
,
j
∗
t
=
m
i
n
ω
i
ω
i
+
w
i
,
j
t
+
ω
iNote that when the waiting time is only allowed on a vertex subsetV
w, we only need to calculate n
w
t-function w
i
,
j
∗
(
t
) for every vertex v
i
∈
V
w. For every vertex v
i
∈
V
∖
V
w, the n
w
t-function w
i
,
j
∗
(
t
) is exactly the time function w
i
,
j
(
t
) because ω
i
≡
0; that is, anyone is not allowed to wait a time period ω
i at v
i.The following theorem guarantees that then
w
t-function w
i
,
j
∗
(
t
) can be used to compute the minimum travel time for any path p in G
T without waiting time.Theorem 3.
Given two time-dependent graphsG
T
(
V
,
E
,
W
) and G
T
∗
(
V
,
E
,
W
∗
), where W
∗ is the set of n
w
t-functions of all edges in E, for any path p in G
T, the minimum travel time of p in G
T
with consideration of waiting time equals the minimum travel time of p in G
T
∗ without waiting time.Proof.
Letp
=
v
1
→
v
2
→
⋯
→
v
h be a given path with the departure time t. ω
i
∗ is the waiting time on v
i
(
1
≤
i
≤
h
) minimizing the travel time of p in G
T. We haved
e
p
a
r
t
(
v
i
)
=
a
r
r
i
v
e
(
v
i
)
+
ω
i
∗ anda
r
r
i
v
e
(
v
i
+
1
)
=
d
e
p
a
r
t
(
v
i
)
+
w
i
,
i
+
1
(
d
e
p
a
r
t
(
v
i
)
)
. Similarly, we haved
e
p
a
r
t
∗
(
v
i
)
=
a
r
r
i
v
e
∗
(
v
i
) anda
r
r
i
v
e
∗
(
v
i
+
1
)
=
d
e
p
a
r
t
∗
(
v
i
)
+
w
i
,
i
+
1
∗
(
d
e
p
a
r
t
∗
(
v
i
)
) for G
T
∗. We only need to provea
r
r
i
v
e
(
v
h
)
=
a
r
r
i
v
e
∗
(
v
h
)
. It can be easily proved by induction on v
i. We omit it due to the space limitation.The algorithm to computen
w
t-function is shown in Algorithm 1. For every w
i
,
j
(
t
)
∈
W, if v
i
∈
V
w, Algorithm 1 computes w
i
,
j
∗
(
t
) backward from [
t
p
-
1
,
t
p
] to [
t
0
,
t
1
] iteratively. In each iteration, w
i
,
j
∗
(
t
) for t
∈
[
t
k
-
1
,
t
k
) is computed. Algorithm 1 first sets w
i
,
j
∗
(
t
) as a
∗
t
+
b
∗, where a
∗
=
-
1 and b
∗
=
t
k
+
ϕ. ϕ is the minimum value between w
i
,
j
∗
(
t
k
) and w
i
,
j
-
(
t
k
). w
i
,
j
-
(
t
k
) is the left limit value of w
i
,
j
(
t
) on t
k. Note that w
i
,
j
∗
(
t
k
) and ϕ have been computed in the last iteration; i.e., the iteration for computing w
i
,
j
∗
(
t
) on [
t
k
,
t
k
+
1
). ϕ is initialized as w
i
,
j
(
t
p
). Next, Algorithm 1 updates w
i
,
j
∗
(
t
) as m
i
n
w
i
,
j
∗
t
,
w
i
,
j
t for t
∈
[
t
k
-
1
,
t
k
) and then ϕ is updated as m
i
n
w
i
,
j
∗
t
k
-
1
,
w
i
,
j
-
t
k
-
1. The algorithm terminates when w
i
,
j
∗
(
t
) has been computed for t
∈
[
t
0
,
t
1
). Note that if v
i
∉
V
w, w
i
,
j
∗
(
t
) is computed as w
i
,
j
(
t
) immediately.Algorithm 1:Nwt-Function  G
T
V
,
E
,
W
,
V
w.
Input:  G
T
(
V
,
E
,
W
) and V
w.
Output:  W
∗.
1:W
∗
←
∅;
2:for every w
i
,
j
(
t
)
∈
W  do
3:if  v
i
∈
V
w  then
4:ϕ
←
w
i
,
j
(
t
p
), w
i
,
j
∗
(
t
p
)
←
w
i
,
j
(
t
p
);
5:for k
=
p to 1do
6:a
∗
←
-
1, b
∗
←
t
k
+
ϕ;
7:w
i
,
j
∗
(
t
)
←
a
∗
t
+
b
∗ for t
∈
[
t
k
-
1
,
t
k
);
8:w
i
,
j
∗
(
t
)
←
min
⁡
w
i
,
j
∗
t
,
w
i
,
j
t
∣
t
∈
t
k
-
1
,
t
k;
9:ϕ
←
m
i
n
{
w
i
,
j
∗
(
t
k
-
1
)
,
w
i
,
j
-
(
t
k
-
1
)
};
10:else
11:w
i
,
j
∗
(
t
)
←
w
i
,
j
(
t
);
12:W
∗
←
W
∗
∪
{
w
i
,
j
∗
(
t
)
};
13:return  W
∗The time and space complexities analysis for Algorithm1 are given below. Let n and m be the number of the vertices and edges in G
T, respectively. For every edge (
v
i
,
v
j
), Algorithm 1 needs to compute w
i
,
j
∗
(
t
) on [
t
k
-
1
,
t
k
) iteratively from k
=
p to 1. For every time interval [
t
k
-
1
,
t
k
), w
i
,
j
∗
(
t
) can be computed in constant time. Therefore, the time complexity of Algorithm 1 is O
(
m
p
). Moreover, Algorithm 1 needs to maintain w
i
,
j
∗
(
t
) and then the space complexity is also O
(
m
p
).Example 4.
We illustrate how to computew
i
,
j
∗
(
t
) by an example in Figure 1. As the solid black line in Figure 1(a), w
i
,
j
(
t
) is a piecewise linear function:(5)
w
i
,
j
t
=
t
+
5
,
0
≤
t
<
10
15
,
10
≤
t
<
20
-
2
t
+
55
,
20
≤
t
≤
25In the first iteration, ϕ is initialized as w
i
,
j
(
25
)
=
5 and then b
∗
=
25
+
ϕ
=
30. As the dashed red line in the right-side of Figure 1(a), we find that a
∗
t
+
b
∗
=
-
t
+
30 is always less than w
i
,
j
(
t
) on [
20,25
], then w
i
,
j
∗
(
t
)
=
-
t
+
30 for t
∈
[
20,25
], and ϕ is updated as 10. Similarly, in the second iteration, w
i
,
j
∗
(
t
) on [
10,20
) is computed as m
i
n
{
15
,
-
t
+
30
}, i.e., w
i
,
j
∗
(
t
)
=
15 for t
∈
[
10,15
) and w
i
,
j
∗
(
t
)
=
-
t
+
30 for t
∈
[
15,20
). Then ϕ is updated as m
i
n
w
i
,
j
∗
10
,
w
i
,
j
-
10
=
15. In the final iteration, as the dashed red line in the left-side of Figure 1(a), a
∗
t
+
b
∗
=
-
t
+
25 is alway larger than t
+
5 on [
0,10
), and we have w
i
,
j
∗
(
t
)
=
t
+
5 for t
∈
[
0,10
). Then w
i
,
j
∗
(
t
) is given below and depicted in Figure 1(b)).(6)
w
i
,
j
∗
t
=
t
+
5
,
0
≤
t
<
10
15
,
10
≤
t
<
15
-
t
+
30
,
15
≤
t
≤
25Figure 1
Computingw
i
,
j
∗
(
t
).
(a)
w
i
,
j
(
t
)
(b)
w
i
,
j
∗
(
t
)The following theorem guarantees the correctness of Algorithm1.Theorem 5.
w
i
,
j
∗
(
t
) computed by Algorithm 1 is exactly the n
w
t-function w
i
,
j
∗
(
t
) given by (4).Proof.
We proved it by induction onp.
Basis. We need to prove that w
i
,
j
∗
(
t
) on time interval [
t
p
-
1
,
t
p
] can be correctly computed by Algorithm 1. First, ω
i can only be zero when t
=
t
p; then we have w
i
,
j
(
t
p
)
=
w
i
,
j
∗
(
t
p
) and ϕ
p
=
w
i
,
j
(
t
p
). Next, we consider the case of t
∈
[
t
p
-
1
,
t
p
).
By the definiton ofw
i
,
j
∗
(
t
), we have(7)
w
i
,
j
∗
t
=
m
i
n
ω
i
ω
i
+
w
i
,
j
t
+
ω
i
=
m
i
n
ω
i
ω
i
+
a
p
t
+
ω
i
+
b
p
=
m
i
n
ω
i
a
p
+
1
ω
i
+
a
p
t
+
b
p
=
m
i
n
ω
i
a
p
+
1
ω
i
+
w
i
,
j
tFor t
∈
[
t
p
-
1
,
t
p
), if a
p
≥
-
1, w
i
,
j
∗
(
t
) cannot decrease with ω
i increasing. It means that (
a
p
+
1
)
ω
i
+
w
i
,
j
(
t
) is minimum when ω
i
=
0 and then w
i
,
j
∗
(
t
)
=
w
i
,
j
(
t
). If a
p
<
-
1, w
i
,
j
∗
(
t
) will decrease with ω
i increasing and thus (
a
p
+
1
)
ω
i
+
w
i
,
j
(
t
) is minimum when ω
i
=
t
p
-
t, which is the longest waiting time on v
i for t
∈
[
t
p
-
1
,
t
p
). Then we have(8)
w
i
,
j
∗
t
=
a
p
+
1
t
p
-
t
+
a
p
t
+
b
p
=
-
t
+
t
p
+
ϕ
pObviously, w
i
,
j
(
t
)
≤
-
t
+
t
p
+
ϕ
p when a
p
≥
-
1 and w
i
,
j
(
t
)
≥
-
t
+
t
p
+
ϕ
p when a
p
<
-
1. Then we have w
i
,
j
∗
(
t
)
=
m
i
n
w
i
,
j
t
,
-
t
+
t
p
+
ϕ
p for t
∈
[
t
p
-
1
,
t
p
].
Induction. Assuming that the correct w
i
,
j
∗
(
t
) can be computed by Algorithm 1 for t
∈
[
t
k
,
t
p
], then we need to prove it also can be correctly computed for t
∈
[
t
k
-
1
,
t
k
). We consider the following two cases: (1) ω
i
≥
t
k
-
t and (2) ω
i
<
t
k
-
t.
For case (1), the departure timet
+
ω
i
∈
[
t
k
,
t
p
] because ω
i
≥
t
k
-
t. By the assumption, n
w
t-function w
i
,
j
∗
(
t
) has been correctly computed for t
∈
[
t
k
,
t
p
]; then w
i
,
j
∗
(
t
k
) is the minimum travel time for edge (
v
i
,
v
j
) with departure time t
k. Therefore, w
i
,
j
∗
(
t
) for t
∈
[
t
k
-
1
,
t
k
) can be computed by the following:(9)
w
i
,
j
∗
t
=
t
k
-
t
+
w
i
,
j
∗
t
k
For case (2), becauseω
i
<
t
k
-
t, then t
+
ω
i
∈
[
t
k
-
1
,
t
k
). Similar to the proof of basis, we have(10)
w
i
,
j
∗
t
=
min
⁡
w
i
,
j
t
,
-
t
+
t
k
+
w
i
,
j
-
t
kNote that when a
k
<
-
1, w
i
,
j
∗
(
t
)
=
-
t
+
t
k
+
w
i
,
j
-
(
t
k
) because w
i
,
j
(
t
) may be noncontinous at t
k. Therefore, we have (11)
w
i
,
j
∗
t
=
min
⁡
w
i
,
j
t
,
-
t
+
t
k
+
w
i
,
j
-
t
k
,
-
t
+
t
k
+
w
i
,
j
∗
t
kThe proof is completed.


## 3.2. Computing Minimum Travel Time Function

We adopt a Dijkstra-based algorithm proposed in [13] to compute m
t
t-function for two vertices v
i and v
j in G
T. This algorithm is only used in case the waiting time is not allowed. After converting w
i
,
j
(
t
) to n
w
t-function w
i
,
j
∗
(
t
) for every edge in G
T by Algorithm 1, this algorithm can be used for time-dependent graphs with waiting time.The main idea of this Dijkstra-based algorithm is to refine a functiong
i
,
j
(
t
) iteratively for every v
j
∈
V, where g
i
,
j
(
t
) represents the earliest arrival time on v
j if departing from v
i at time point t. In every iteration, algorithm selects a vertex v
x
∈
V and then refines g
i
,
x
(
t
) by extending a time domain I
x to a larger I
x
′, where I
x
=
[
t
0
,
τ
x
] is a subinterval of the whole time domain T. g
i
,
x
(
t
) is regarded as well refined in I
x if it specifies the earliest arrival time at v
x from v
i for any departure time t
∈
I
x. The algorithm repeats time-refinement process till g
i
,
j
(
t
) of destination v
j has been well refined in the whole time domain T and then m
t
t-function m
i
,
j
(
t
) can be computed as m
i
,
j
(
t
)
=
g
i
,
j
(
t
)
-
t. The more details about this Dijkstra-based algorithm is given in [13]. As shown in [13], the time and space complexities are O
(
(
n
log
⁡
n
+
m
)
α
(
T
)
) and O
(
(
n
+
m
)
α
(
T
)
), respectively, where α
(
T
) is the cost required for each function (defined in interval T) operation.


## 4. The Novel Voronoi-Based Index

We propose a novel voronoi-based index forkNN query over time-dependent road networks. In static road networks, the voronoi diagram divides the network (or space) into a group of disjoint subgraphs (or subspaces) where the nearest object of any vertex inside a subgraph is the object generating this subgraph. However, in time-dependent road networks, the nearest object of a vertex may be dynamic. The nearest object of a vertex v may be o
i for departure time t
∈
[
t
1
,
t
2
] but it may be o
j for t
∈
[
t
3
,
t
4
]. The main idea of our novel voronoi-based index is also to divide the vertex set V into some vertex subsets V
i and every subset V
i is associated with one object o
i
∈
O. Different from static road networks, our voronoi-based index is time-dependent; that is, every vertex v inside a subset is with a time interval indicating when the object o
i is nearest to v. Next, we describe what the novel voronoi-based index is and how to construct it.


### 4.1. What Is the Voronoi-Based Index?

Given a vertexv and an object o
i, I
i
(
v
) is called v’s m
a
x
i
m
u
m
t
i
m
e
i
n
t
e
r
v
a
l about o
i if it satisfies the following two conditions: (1) o
i is the nearest object of v for any departure time t
∈
I
i
(
v
) and (2) there does not exist another I
i
′
(
v
)
⊃
I
i
(
v
) satisfying the condition (1). Note that I
i
(
v
) may not be a continuous time interval; that is, if o
i is nearest to v for two disjoint departure time intervals t
1
,
t
2 and [
t
3
,
t
4
], then [
t
1
,
t
2
]
∪
[
t
3
,
t
4
]
⊆
I
i
(
v
). The voronoi-based index maintains a set C
i for every object o
i
∈
O, where C
i is a set of the tuples (
v
,
I
i
(
v
)
) for all the vertices v with nonempty I
i
(
v
), i.e., (12)
C
i
=
v
,
I
i
v
∣
v
∈
V
∧
I
i
v
≠
∅We call C
i the closest vertex-time pair set (or closest pair set shortly) of o
i. For simplicity, we say v is a vertex in C
i if (
v
,
I
i
(
v
)
)
∈
C
i. Next, we give the definition of the border vertex.Definition 6 (border vertex).
A vertexv
x in C
i is called a border vertex of C
i if there exist v
y
∈
N
+
(
v
x
) such that (
v
y
,
I
y
)
∉
C
i for any I
y
⊇
f
x
,
y
(
I
i
(
v
x
)
), where N
+
(
v
x
) is the outgoing neighbor set of v
x and f
x
,
y
(
I
i
(
v
x
)
) is the time interval mapped from I
i
(
v
x
) by the function f
x
,
y
(
t
)
=
t
+
w
x
,
y
∗
(
t
).The border vertexv
x of C
i indicates that there exists a time point t
∈
f
x
,
y
(
I
i
(
v
x
)
) such that o
i is not the nearest object of v
y if one departs at time point t.We useB
i to denote the set of all the border vertices of C
i. For every C
i, D
i is the set of m
t
t-functions m
x
,
n
+
i
(
t
) for all vertices v
x in C
i, that is,(13)
D
i
=
m
x
,
n
+
i
t
∣
v
x
is  a  vertex  in
C
i
,and M
i is a matrix of size |
C
i
|
×
|
B
i
| to maintain m
t
t-function m
x
,
y
(
t
) for all pairs of vertex v
x and border vertex v
y in C
i, i.e.,(14)
M
i
=
m
x
,
y
t
∣
v
x
∈
C
i
∧
v
y
∈
B
iThe voronoi-based index is {
C
,
B
,
D
,
M
}, where C, B, D, and M are the collections of all C
i, B
i, D
i, and M
i, respectively.


### 4.2. How to Construct The Voronoi-Based Index?

We have explained how to computem
t
t-function in Section 3. Next, we describe how to compute C
i and B
i for every o
i
∈
O.For every vertexv
x
∈
V, I
i
(
v
x
) is initialized as the whole time domain T. We refine I
i
(
v
x
) iteratively by removing the subintervals on which m
x
,
n
+
i
(
t
) is larger than m
x
,
n
+
j
(
t
) for another object o
j. It means o
i is not the nearest object of v
x when departure time is in these subintervals. For every o
j
∈
O
(
o
j
≠
o
i
), let T
j
(
v
x
) denote the maximum time interval on which m
x
,
n
+
j
(
t
)
<
m
x
,
n
+
i
(
t
) and I
i
(
v
x
) is updated as I
i
(
v
x
)
-
T
j
(
v
x
). After removing T
j
(
v
x
) for every other object o
j, if I
i
(
v
x
) is not empty, then the pair (
v
x
,
I
i
(
v
x
)
) is inserted into C
i.For every vertexv
x in C
i, if there exists an outgoing neighbor v
y of v
x, such that v
y is not in C
i or f
x
,
y
I
i
v
x
⊈
I
i
(
v
y
), then v
x must be a border vertex of C
i and it is inserted into B
i.


### 4.3. Query Processing by Voronoi-Based Index

Algorithm2 describes how to find the k nearest objects for a query vertex v
q with departure time t
d. In Algorithm 2, O
(
v
q
) is a set to maintain the objects that have been found so far and Q is a priority queue to maintain a candidate set of C
i whose o
i is possible to be an object in kNN set. All C
i
∈
Q are sorted in an ascending order by the minimum travel time m
q
,
n
+
i from v
q to o
i. The top C
i in Q is with the minimum m
q
,
n
+
i and it can be easily done using Fibonacci Heap. O
(
v
q
) and Q are initialized as ∅ and {
C
q
}, respectively, where C
q contains v
q for the departure time t
d, i.e., (
v
q
,
I
q
(
v
q
)
)
∈
C
q and t
d
∈
I
q
(
v
q
). O
(
v
q
) is expanded iteratively by inserting objects one by one from Q until |
O
(
v
q
)
|
=
k. In each iteration, if |
O
(
v
q
)
|
<
k, Algorithm 2 first dequeues the top C
i from Q with the minimum m
q
,
n
+
i. The object o
i of C
i must be one of k nearest objects of v
q. It can be guaranteed by Theorem 8. Then o
i will be inserted into O
(
v
q
). For every border vertex v
y in C
i, Algorithm 2 computes m
q
,
y as m
i
n
m
q
,
x
+
m
x
,
y
t
d
+
m
q
,
x
∣
v
x
∈
E
i, where E
i is the entry set of C
i. The “entry” means any path entering into C
i must go through a vertex in E
i. E
i will be updated when Algorithm 2 runs. For every v
z
∈
N
+
(
v
y
), if m
q
,
z
>
m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
), then m
q
,
z will be updated as m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
). Next, if v
z is in C
j (C
j
≠
C
i and C
j
∉
O
(
v
q
)) at the time point t
d
+
m
q
,
z, then v
z will be inserted into E
j as an entry of C
j. For the object o
j of C
j, m
q
,
n
+
j will be updated as m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
) when m
q
,
n
+
j
>
m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
). If C
j is not in Q, then C
j will be enqueued into Q. Otherwise, C
j has been in Q and Q will be updated by C
j with new m
q
,
n
+
j. Algorithm 2 terminates when the size of O
(
v
q
) is k.Algorithm 2:kNN-Query (G
T
∗
,
v
q
,
t
d
,
k).
Input
: time-dependent graph G
T
∗, query vertex v
q, departure time t
d and k
Output
: the k nearest neighbor set O
(
v
q
)
1:O
(
v
q
)
←
∅, Q
←
{
C
q
}; E
q
←
{
v
q
}
2:while  |
O
(
v
q
)
|
<
k  do
3:C
i
← Dequeue (Q), O
(
v
q
)
←
O
(
v
q
)
∪
{
o
i
};
4:foreach  v
y
∈
B
i  do
5:foreach  v
x
∈
E
i  do
6:m
q
,
y
←
min
⁡
m
q
,
y
,
m
q
,
x
+
m
x
,
y
t
d
+
m
q
,
x;
7:foreach  v
z
∈
N
+
(
v
y
)  do
8:if  m
q
,
z
>
m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
)  then
9:m
q
,
z
←
m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
);
10:    LetC
j be the set including v
z when t
=
t
d
+
m
q
,
z;
11:if  C
j
∉
O
(
v
q
)  then
12:E
j
←
E
j
∪
{
v
z
};
13:if  m
q
,
n
+
j
>
m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
)  then
14:m
q
,
n
+
j
←
m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
);
15:if  C
j
∉
Q  then
16:      Enqueue
(
Q
,
C
j
);
17:else
18:      Update
(
Q
,
C
j
);
19:return  O
(
v
q
)Example 7.
We use the example in Figure2 to illustrate the kNN querying process for k
=
3. In this example, v
q is the query vertex and it is in C
1 for the departure time t
d. Q and O
(
v
q
) are initialized as {
C
1
} and ∅, respectively. In the first iteration, C
1 is dequeued from Q and then o
1 is inserted into O
(
v
q
). Because v
1 is a border vertex of C
1 and v
3 is an outgoing neighbor of v
1, Algorithm 2 computes m
q
,
1
(
t
d
) and m
q
,
3
(
t
d
)
=
m
q
,
1
(
t
d
)
+
w
1,3
∗
(
t
d
+
m
q
,
1
(
t
d
)
). Note that v
3 is in C
2 when t
=
t
d
+
m
q
,
3
(
t
d
) and then it is an entry of C
2. Therefore, C
2 is enqueued into Q. Similarly, C
3 is also enqueued into Q and Q
=
C
2
,
C
3. Assume that o
2 is nearer to v
q than o
3 and, in the second iteration, C
2 is dequeued and O
(
v
q
) is updated as {
o
1
,
o
2
}. In the same way, C
4 will be enqueued into Q in this iteration. In the final iteration, C
3 will be dequeued due to o
3 being nearer to v
q and then O
(
v
q
)
=
o
1
,
o
2
,
o
3. Because O
v
q
=
3, Algorithm 2 terminates and returns O
(
v
q
).
The next theorem guarantees the correctness of Algorithm2.Figure 2
Query processing.Theorem 8.
In Algorithm2, the object o
i of C
i dequeued from Q in the k-th iteration must be the k-th nearest object of query vertex v
q for the departure time t
d.Proof.
We prove it by induction onk.
Basis. Obviously, C
q is dequeued from Q in the first iteration. By the definition of C
q, o
q is the nearest object of v
q when the departure time is t
d.
Induction. Assume that the i-th nearest neighbor of v
q is dequeued from Q in the i-th iteration for i
<
k. We need to prove it also holds for i
=
k. We prove it by contradiction. Let C
k be the closest pair set dequeued from Q in the k-th iteration and o
k is the object of C
k. Suppose that the k-th nearest object of v
q is o
k
′ and o
k
′
≠
o
k. Let p be the shortest path from v
q to o
k
′ with the departure time t
d. Because k
>
1, then C
k
′ is not C
q and there must exist an entry v
e of C
k
′ in p. Letting v
b be the predecessor of v
e in p, then v
b must be a border vertex of C
b at time points t
d
+
m
q
,
b and C
b
≠
C
k
′. There are two cases for the object o
b of C
b: (1) o
b is not in the k nearest object set of v
q and (2) o
b is in the k nearest object set of v
q.
For case (1), by the definition ofC
b, o
b is the nearest neighbor of v
b at time point t
d
+
m
q
,
b, and then we have(15)
m
q
,
b
+
m
b
,
n
+
b
t
d
+
m
q
,
b
<
m
q
,
b
+
m
b
,
n
+
k
′
t
d
+
m
q
,
bThus o
b is nearer to v
q than o
k
′ when the departure time is t
d. It means o
b must be in the k nearest object set of v
q, which is a contradiction.
For case (2), lettingo
b be the i-th (i
<
k) nearest object of v
q, by the inductive assumption, C
b is dequeued from Q in i-th iteration. According to Algorithm 2, C
k
′ is enqueued into Q in this iteration. Therefore, C
k
′ will be dequeued from Q in k-th iteration instead of C
k, which is a contradiction. The proof is completed.Time and Space Complexities. The time and space complexities of Algorithm 2 are given below. Let b and e be the average size of B
i and E
i, respectively. In every iteration, Algorithm 2 upadates m
q
,
y as m
i
n
m
q
,
y
,
m
q
,
x
+
m
x
,
y
t
d
+
m
q
,
x for every border vertex v
y in C
i. It will cost O
(
b
e
) time. For every outgoing neighbor v
z of border vertex v
y, Algorithm 2 needs to compute m
q
,
z and then it will cost O
(
b
d
) time, where d is the average outdegree of the vertices in G
T. Therefore, the time complexity of Algorithm 2 is O
(
k
b
(
d
+
e
)
). On the other hand, because Algorithm 2 needs to maintain m
q
,
y and m
q
,
z, then the space complexity is O
(
k
(
b
+
e
)
).


## 4.1. What Is the Voronoi-Based Index?

Given a vertexv and an object o
i, I
i
(
v
) is called v’s m
a
x
i
m
u
m
t
i
m
e
i
n
t
e
r
v
a
l about o
i if it satisfies the following two conditions: (1) o
i is the nearest object of v for any departure time t
∈
I
i
(
v
) and (2) there does not exist another I
i
′
(
v
)
⊃
I
i
(
v
) satisfying the condition (1). Note that I
i
(
v
) may not be a continuous time interval; that is, if o
i is nearest to v for two disjoint departure time intervals t
1
,
t
2 and [
t
3
,
t
4
], then [
t
1
,
t
2
]
∪
[
t
3
,
t
4
]
⊆
I
i
(
v
). The voronoi-based index maintains a set C
i for every object o
i
∈
O, where C
i is a set of the tuples (
v
,
I
i
(
v
)
) for all the vertices v with nonempty I
i
(
v
), i.e., (12)
C
i
=
v
,
I
i
v
∣
v
∈
V
∧
I
i
v
≠
∅We call C
i the closest vertex-time pair set (or closest pair set shortly) of o
i. For simplicity, we say v is a vertex in C
i if (
v
,
I
i
(
v
)
)
∈
C
i. Next, we give the definition of the border vertex.Definition 6 (border vertex).
A vertexv
x in C
i is called a border vertex of C
i if there exist v
y
∈
N
+
(
v
x
) such that (
v
y
,
I
y
)
∉
C
i for any I
y
⊇
f
x
,
y
(
I
i
(
v
x
)
), where N
+
(
v
x
) is the outgoing neighbor set of v
x and f
x
,
y
(
I
i
(
v
x
)
) is the time interval mapped from I
i
(
v
x
) by the function f
x
,
y
(
t
)
=
t
+
w
x
,
y
∗
(
t
).The border vertexv
x of C
i indicates that there exists a time point t
∈
f
x
,
y
(
I
i
(
v
x
)
) such that o
i is not the nearest object of v
y if one departs at time point t.We useB
i to denote the set of all the border vertices of C
i. For every C
i, D
i is the set of m
t
t-functions m
x
,
n
+
i
(
t
) for all vertices v
x in C
i, that is,(13)
D
i
=
m
x
,
n
+
i
t
∣
v
x
is  a  vertex  in
C
i
,and M
i is a matrix of size |
C
i
|
×
|
B
i
| to maintain m
t
t-function m
x
,
y
(
t
) for all pairs of vertex v
x and border vertex v
y in C
i, i.e.,(14)
M
i
=
m
x
,
y
t
∣
v
x
∈
C
i
∧
v
y
∈
B
iThe voronoi-based index is {
C
,
B
,
D
,
M
}, where C, B, D, and M are the collections of all C
i, B
i, D
i, and M
i, respectively.


## 4.2. How to Construct The Voronoi-Based Index?

We have explained how to computem
t
t-function in Section 3. Next, we describe how to compute C
i and B
i for every o
i
∈
O.For every vertexv
x
∈
V, I
i
(
v
x
) is initialized as the whole time domain T. We refine I
i
(
v
x
) iteratively by removing the subintervals on which m
x
,
n
+
i
(
t
) is larger than m
x
,
n
+
j
(
t
) for another object o
j. It means o
i is not the nearest object of v
x when departure time is in these subintervals. For every o
j
∈
O
(
o
j
≠
o
i
), let T
j
(
v
x
) denote the maximum time interval on which m
x
,
n
+
j
(
t
)
<
m
x
,
n
+
i
(
t
) and I
i
(
v
x
) is updated as I
i
(
v
x
)
-
T
j
(
v
x
). After removing T
j
(
v
x
) for every other object o
j, if I
i
(
v
x
) is not empty, then the pair (
v
x
,
I
i
(
v
x
)
) is inserted into C
i.For every vertexv
x in C
i, if there exists an outgoing neighbor v
y of v
x, such that v
y is not in C
i or f
x
,
y
I
i
v
x
⊈
I
i
(
v
y
), then v
x must be a border vertex of C
i and it is inserted into B
i.


## 4.3. Query Processing by Voronoi-Based Index

Algorithm2 describes how to find the k nearest objects for a query vertex v
q with departure time t
d. In Algorithm 2, O
(
v
q
) is a set to maintain the objects that have been found so far and Q is a priority queue to maintain a candidate set of C
i whose o
i is possible to be an object in kNN set. All C
i
∈
Q are sorted in an ascending order by the minimum travel time m
q
,
n
+
i from v
q to o
i. The top C
i in Q is with the minimum m
q
,
n
+
i and it can be easily done using Fibonacci Heap. O
(
v
q
) and Q are initialized as ∅ and {
C
q
}, respectively, where C
q contains v
q for the departure time t
d, i.e., (
v
q
,
I
q
(
v
q
)
)
∈
C
q and t
d
∈
I
q
(
v
q
). O
(
v
q
) is expanded iteratively by inserting objects one by one from Q until |
O
(
v
q
)
|
=
k. In each iteration, if |
O
(
v
q
)
|
<
k, Algorithm 2 first dequeues the top C
i from Q with the minimum m
q
,
n
+
i. The object o
i of C
i must be one of k nearest objects of v
q. It can be guaranteed by Theorem 8. Then o
i will be inserted into O
(
v
q
). For every border vertex v
y in C
i, Algorithm 2 computes m
q
,
y as m
i
n
m
q
,
x
+
m
x
,
y
t
d
+
m
q
,
x
∣
v
x
∈
E
i, where E
i is the entry set of C
i. The “entry” means any path entering into C
i must go through a vertex in E
i. E
i will be updated when Algorithm 2 runs. For every v
z
∈
N
+
(
v
y
), if m
q
,
z
>
m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
), then m
q
,
z will be updated as m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
). Next, if v
z is in C
j (C
j
≠
C
i and C
j
∉
O
(
v
q
)) at the time point t
d
+
m
q
,
z, then v
z will be inserted into E
j as an entry of C
j. For the object o
j of C
j, m
q
,
n
+
j will be updated as m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
) when m
q
,
n
+
j
>
m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
). If C
j is not in Q, then C
j will be enqueued into Q. Otherwise, C
j has been in Q and Q will be updated by C
j with new m
q
,
n
+
j. Algorithm 2 terminates when the size of O
(
v
q
) is k.Algorithm 2:kNN-Query (G
T
∗
,
v
q
,
t
d
,
k).
Input
: time-dependent graph G
T
∗, query vertex v
q, departure time t
d and k
Output
: the k nearest neighbor set O
(
v
q
)
1:O
(
v
q
)
←
∅, Q
←
{
C
q
}; E
q
←
{
v
q
}
2:while  |
O
(
v
q
)
|
<
k  do
3:C
i
← Dequeue (Q), O
(
v
q
)
←
O
(
v
q
)
∪
{
o
i
};
4:foreach  v
y
∈
B
i  do
5:foreach  v
x
∈
E
i  do
6:m
q
,
y
←
min
⁡
m
q
,
y
,
m
q
,
x
+
m
x
,
y
t
d
+
m
q
,
x;
7:foreach  v
z
∈
N
+
(
v
y
)  do
8:if  m
q
,
z
>
m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
)  then
9:m
q
,
z
←
m
q
,
y
+
w
y
,
z
∗
(
t
d
+
m
q
,
y
);
10:    LetC
j be the set including v
z when t
=
t
d
+
m
q
,
z;
11:if  C
j
∉
O
(
v
q
)  then
12:E
j
←
E
j
∪
{
v
z
};
13:if  m
q
,
n
+
j
>
m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
)  then
14:m
q
,
n
+
j
←
m
q
,
z
+
m
z
,
n
+
j
(
t
d
+
m
q
,
z
);
15:if  C
j
∉
Q  then
16:      Enqueue
(
Q
,
C
j
);
17:else
18:      Update
(
Q
,
C
j
);
19:return  O
(
v
q
)Example 7.
We use the example in Figure2 to illustrate the kNN querying process for k
=
3. In this example, v
q is the query vertex and it is in C
1 for the departure time t
d. Q and O
(
v
q
) are initialized as {
C
1
} and ∅, respectively. In the first iteration, C
1 is dequeued from Q and then o
1 is inserted into O
(
v
q
). Because v
1 is a border vertex of C
1 and v
3 is an outgoing neighbor of v
1, Algorithm 2 computes m
q
,
1
(
t
d
) and m
q
,
3
(
t
d
)
=
m
q
,
1
(
t
d
)
+
w
1,3
∗
(
t
d
+
m
q
,
1
(
t
d
)
). Note that v
3 is in C
2 when t
=
t
d
+
m
q
,
3
(
t
d
) and then it is an entry of C
2. Therefore, C
2 is enqueued into Q. Similarly, C
3 is also enqueued into Q and Q
=
C
2
,
C
3. Assume that o
2 is nearer to v
q than o
3 and, in the second iteration, C
2 is dequeued and O
(
v
q
) is updated as {
o
1
,
o
2
}. In the same way, C
4 will be enqueued into Q in this iteration. In the final iteration, C
3 will be dequeued due to o
3 being nearer to v
q and then O
(
v
q
)
=
o
1
,
o
2
,
o
3. Because O
v
q
=
3, Algorithm 2 terminates and returns O
(
v
q
).
The next theorem guarantees the correctness of Algorithm2.Figure 2
Query processing.Theorem 8.
In Algorithm2, the object o
i of C
i dequeued from Q in the k-th iteration must be the k-th nearest object of query vertex v
q for the departure time t
d.Proof.
We prove it by induction onk.
Basis. Obviously, C
q is dequeued from Q in the first iteration. By the definition of C
q, o
q is the nearest object of v
q when the departure time is t
d.
Induction. Assume that the i-th nearest neighbor of v
q is dequeued from Q in the i-th iteration for i
<
k. We need to prove it also holds for i
=
k. We prove it by contradiction. Let C
k be the closest pair set dequeued from Q in the k-th iteration and o
k is the object of C
k. Suppose that the k-th nearest object of v
q is o
k
′ and o
k
′
≠
o
k. Let p be the shortest path from v
q to o
k
′ with the departure time t
d. Because k
>
1, then C
k
′ is not C
q and there must exist an entry v
e of C
k
′ in p. Letting v
b be the predecessor of v
e in p, then v
b must be a border vertex of C
b at time points t
d
+
m
q
,
b and C
b
≠
C
k
′. There are two cases for the object o
b of C
b: (1) o
b is not in the k nearest object set of v
q and (2) o
b is in the k nearest object set of v
q.
For case (1), by the definition ofC
b, o
b is the nearest neighbor of v
b at time point t
d
+
m
q
,
b, and then we have(15)
m
q
,
b
+
m
b
,
n
+
b
t
d
+
m
q
,
b
<
m
q
,
b
+
m
b
,
n
+
k
′
t
d
+
m
q
,
bThus o
b is nearer to v
q than o
k
′ when the departure time is t
d. It means o
b must be in the k nearest object set of v
q, which is a contradiction.
For case (2), lettingo
b be the i-th (i
<
k) nearest object of v
q, by the inductive assumption, C
b is dequeued from Q in i-th iteration. According to Algorithm 2, C
k
′ is enqueued into Q in this iteration. Therefore, C
k
′ will be dequeued from Q in k-th iteration instead of C
k, which is a contradiction. The proof is completed.Time and Space Complexities. The time and space complexities of Algorithm 2 are given below. Let b and e be the average size of B
i and E
i, respectively. In every iteration, Algorithm 2 upadates m
q
,
y as m
i
n
m
q
,
y
,
m
q
,
x
+
m
x
,
y
t
d
+
m
q
,
x for every border vertex v
y in C
i. It will cost O
(
b
e
) time. For every outgoing neighbor v
z of border vertex v
y, Algorithm 2 needs to compute m
q
,
z and then it will cost O
(
b
d
) time, where d is the average outdegree of the vertices in G
T. Therefore, the time complexity of Algorithm 2 is O
(
k
b
(
d
+
e
)
). On the other hand, because Algorithm 2 needs to maintain m
q
,
y and m
q
,
z, then the space complexity is O
(
k
(
b
+
e
)
).


## 5. Optimization of Voronoi-Based Index

In Section4, we introduce the voronoi-based index on time-dependent graphs and propose Algorithm 2 to find the k nearest objects with voronoi-based index. Algorithm 2 dequeues the objects iteratively until all k nearest objects have been searched. In each iteration, Algorithm 2 uses a prior queue Q to maintain a candidate set of C
j whose object o
j may be one of the k nearest objects. This candidate set is essentially the set of all the closest pair sets adjacent to all the objects which have been searched in O
(
v
q
). However, for some closest pair set C
j of o
j, even though o
j are not one of k nearest objects, Algorithm 2 also needs to maintain C
j in Q and update the traveling time to o
j and the border vertices in C
j because C
j is adjacent to an object o
i in O
(
v
q
). It makes our algorithm not efficient enough for k nearest object query.In this section, we propose a novel balanced tree structure on voronoi-based index, namedV-t
r
e
e, to organize all the closest pair sets C
j. V-t
r
e
e can be considered as a secondary level index for k nearest object query. By V-t
r
e
e, our algorithm can avoid maintaining the closest pair sets C
j whose objects o
j are not in the set of k nearest objects. The main idea of V-t
r
e
e comes from G-t
r
e
e, which is a balanced tree structure, proposed in [14]. G-t
r
e
e cannot be used for k nearest object query on time-dependent graphs because of the following reasons:(1)
G-t
r
e
e is built on the static graphs where the weight of every edge is a constant value. However, for time-dependent graphs, the weight on every edge is a time function w
i
,
j
(
t
) which is related to the departure time t. The value of w
i
,
j
(
t
) always changes with the change of departure time. Therefore, it is unfeasible to construct G-t
r
e
e for time-dependent graphs.
(2)
G-t
r
e
e organizes all the vertices in a tree shape based on the distance of two vertices in a static graphs. Different from G-t
r
e
e, V-t
r
e
e is a second-level index based on voronoi-based index. It organizes all the closest pair sets C
i in a tree shape. Therefore, we need to define the distance between two closest pair sets C
i and C
j and then V-t
r
e
e can be constructed.
(3)
Because of above two points, the querying algorithm byG-t
r
e
e cannot work for our problem; then we propose a novel querying algorithm by V-t
r
e
e.In the following, we first introduce what isV-t
r
e
e and how to construct it based on voronoi-based index. Then we propose a novel querying algorithm for k nearest object query by V-t
r
e
e. Finally, we utilize an example to explain why V-t
r
e
e is more efficient than voronoi-based index.


### 5.1. What Is V-Tree

V-t
r
e
e is a balanced tree structure to organize all the closest pair sets C
i in voronoi-based index. Specifically, every node in V-t
r
e
e is a collection of some closest pair sets. We first give the definition of λ-partition for voronoi-based index.Definition 9 (λ-partition for voronoi-based index).
Given a collectionC of some closest pair sets, a λ-partition of C is a set {
C
1
⋯
C
λ
} satisfying three following conditions: (1) ∀
C
i
,
C
i
⊂
C; (2) ∀
C
i
,
C
j
(
i
≠
j
)
,
C
i
∩
C
j
=
∅; (3) C
=
⋃
1
≤
i
≤
λ
‍
C
i.Note that everyC
i is a subset of C and it is also a collection of closest pair sets. Every node in V-t
r
e
e represents a collection C and has λ children by λ-partition on C; i.e., every C
i
(
1
≤
i
≤
λ
) is a child of C. Next, we introduce how to get an appropriate λ-partition for a given closest pair set C. An edge (
v
x
,
v
y
) is called a crossing edge from the closest pair sets C
i to C
j if v
x and v
y are the border vertices of C
i and C
j, respectively, i.e., v
x
∈
B
i and v
y
∈
B
j. As our discussion in Section 2, the time function of a crossing edge is modeled as a piecewise linear function w
x
,
y
(
t
). We define the expected traveling time  w
¯
i
,
j for a crossing edge (
v
x
,
v
y
) by the following: (16)
w
¯
x
,
y
=
1
T
∫
T
w
x
,
y
t
d
twhere T is the whole time interval for time function w
x
,
y
(
t
), i.e., T
=
t
p
-
t
0. Because w
x
,
y
(
t
) is a piecewise linear function, w
¯
x
,
y can be calculated as follows:(17)
w
¯
x
,
y
=
1
T
∫
T
w
x
,
y
t
d
t
=
1
t
p
-
t
0
∫
t
0
t
p
w
x
,
y
t
d
t
=
1
t
p
-
t
0
∑
i
=
1
p
∫
t
i
-
1
t
i
w
i
t
d
t
=
∑
i
=
1
p
t
i
-
t
i
-
1
t
p
-
t
0
×
w
i
t
i
-
1
+
w
i
+
1
t
i
2Note that the expected traveling time w
¯
i
,
j is a constant value to estimate the traveling time for crossing edge (
v
x
,
v
y
). Given two closest pair set C
i and C
j, we use E
i
,
j to denote set of all the crossing edges from C
i to C
j, i.e., E
i
,
j
=
v
x
,
v
y
∣
v
x
∈
B
i
∧
v
y
∈
B
j. Every closest pair set C
i can be regarded as a super vertex and there is an edge from C
i to C
j if E
i
,
j
≠
∅. The weight of such edge, denoted as a
i
,
j, is defined by the following: (18)
a
i
,
j
=
1
E
i
,
j
∑
v
x
,
v
y
∈
E
i
,
j
w
¯
x
,
yIt is worth noting that a
i
,
j is the average value of the expected traveling time for all the crossing edge from C
i to C
j. a
i
,
j is called the weight from C
i to C
j. Therefore, the λ-partition {
C
1
,
…
,
C
λ
} for a given collection C of some closest pair sets can be converted into a graph partition problem. For a pair of (
C
i
,
C
j
) with E
i
,
j
≠
∅, if C
i and C
j are in the same collection C
x
(
1
≤
x
≤
λ
), then it is called an inner edge of C
x. Otherwise, C
i and C
j are in two different collections C
x and C
y, respectively, and then it is called an interedge from C
x to C
y. Correspondingly, the weight a
i
,
j is called inner weight or interweight, respectively.InV-t
r
e
e, a parent node C is partitioned into λ children nodes {
C
1
,
…
,
C
λ
}. To facilitate k nearest object query, an appropriate partition is expected such that the inner weights are less and the interweights are more. Thus the optimal λ-partition is to find a group of {
C
1
,
…
,
C
λ
} that minimizes the following objective function:(19)
f
C
1
,
…
,
C
λ
=
∑
C
x
a
C
xwhere a
(
C
x
)
=
∑
a
i
,
j
∈
C
x
‍
a
i
,
j is the summation of all the inner weights a
i
,
j in C
x and f
C
1
,
…
,
C
λ is the summation of a
(
C
x
) for all C
x. The optimal λ-partition on C is similar to the traditional graph partition problem which has been well studied [15–17]. However, the objective function is to minimize the sum of the interweights for the traditional graph partition. Therefore, for any pair (
C
i
,
C
j
) in C, if E
i
,
j
≠
∅, we assign a new weight b
i
,
j
=
a
m
a
x
-
a
i
,
j on it, where a
m
a
x represents the maximum weight for all the inner edges in C. Consider the following objective funtion: (20)
g
C
1
,
…
,
C
λ
=
∑
C
x
,
C
y
b
C
x
,
C
ywhere b
(
C
x
,
C
y
)
=
∑
C
i
∈
C
x
,
C
j
∈
C
y
‍
b
i
,
j is the summation of b
i
,
j for all the inter edges from C
x to C
y and g
C
1
,
…
,
C
λ is the summation of b
(
C
x
,
C
y
) for all the pairs of C
x and C
y. The following theorem guarantees that the optimal λ-partition under objective functions f
(
·
) and g
(
·
) is the same.Theorem 10.
Theλ-partition minimizing f
(
·
) is exactly the λ-partition minimizing g
(
·
).Proof.
Given aλ-partition {
C
1
,
…
,
C
λ
} on C, let a
(
C
x
,
C
y
) denote the summation of all the inter weights a
i
,
j from C
x to C
y, that is, a
(
C
x
,
C
y
)
=
∑
C
i
∈
C
x
,
C
j
∈
C
y
‍
a
i
,
j, and then we have(21)
a
C
=
∑
C
x
,
C
y
a
C
x
,
C
y
+
∑
C
x
a
C
xBecause a
(
C
) is independent of λ-partition on C, then minimizing ∑
C
x
‍
a
(
C
x
) is equivalent to maximizing ∑
C
x
,
C
y
‍
a
(
C
x
,
C
y
). On the other hand, because b
i
,
j
=
a
m
a
x
-
a
i
,
j and b
i
,
j
≥
0, then maximizing ∑
C
x
,
C
y
‍
a
(
C
x
,
C
y
) is equivalent to minimizing ∑
C
x
,
C
y
‍
b
(
C
x
,
C
y
). Therefore, the λ-partition minimizing the objective function f
(
·
) also minimizes the objective function g
(
·
).Thus the optimalλ-partition under objective function g
(
·
) is a traditional graph partition problem. In this paper, we adopt the multilevel graph partitioning technique (METIS) proposed by Metis et al. in [15], which is a classic graph partition algorithm.Next, we introduce the concept of theminimum distance, which is to be maintained in V-t
r
e
e. For two closest pair set C
i and C
j, if E
i
,
j
≠
∅, we defined the minimum weight from C
i to C
j, denoted as w
i
,
j
m
i
n, by the following:(22)
w
i
,
j
m
i
n
=
m
i
n
v
x
,
v
y
∈
E
i
,
j
m
i
n
t
w
x
,
y
twhere (
v
x
,
v
y
)
∈
E
i
,
j is a crossing edge from C
i to C
j and m
i
n
t
w
x
,
y
t is the minimum value of time funtion w
x
,
y
(
t
). Thus w
i
,
j
m
i
n is the minimum value of m
i
n
t
w
x
,
y
t for all the crossing edge in E
i
,
j. A new graph can be constructed from the voronoi-based index; every closest pair set C
i can be regarded as a super vertex. If E
i
,
j
≠
∅, there is an edge from C
i to C
j and its weight is w
i
,
j
m
i
n. Therefore, for any two C
i and C
j, the shortest distance from C
i to C
j in this graph is called the minimum distance from C
i to C
j and we denote it by d
i
,
j. Especially, for a closest pair set C
i and a collection C, the minimum distance from C
i to C is denoted by d
(
C
i
,
C
) and is the minimum value of d
i
,
j for all C
j in C, i.e., d
(
C
i
,
C
)
=
m
i
n
C
j
∈
C
d
i
,
j. The value of d
(
C
i
,
C
) can be calculated easily by existing single-source shortest distance algorithm. Note that d
(
C
i
,
C
)
=
0 when C
i
∈
C. Next, we give the definition of V-t
r
e
e below.Definition 11 (V-tree).
AV-t
r
e
e, denoted as T
V, is a balanced tree T
V that satisfies the following conditions: (1)
Every node inV-t
r
e
e represents a collection C of some closest pair sets. Specially, the root node represents the collection C
r
o
o
t of all the closest pair sets in voronoi-based index;
(2)
Every nonleaf nodeC has λ children {
C
1
,
…
,
C
λ
}. All these children consist of the optimal λ-partition on C.
(3)
Every leaf nodeC has at most σ closest pair sets.InV-t
r
e
e, every leaf node C is associated with a matrix to maintain the minimum distance from every closest pair set C
i in leaf node C to every node C
′ in V-t
r
e
e
T
V, i.e.,(23)
d
C
i
,
C
′
∣
C
i
∈
C
∧
C
′
∈
T
V
,where C
′ and C are different nodes in T
V. It is because C
i
∈
C and then d
(
C
i
,
C
)
=
0. Note that if C
′ is an ancestor C in T
V, we also have d
(
C
i
,
C
′
)
=
0 directly.Example 12.
Figure3 illustrates an example of 2-partition on a voronoi-based index. The corresponding V-t
r
e
e is shown in Figure 4. In this example, C
r
o
o
t is the collection of all the closest pair set and it is partitioned into {
C
1
,
C
2
}. Thus C
1 and C
2 are two children of C
r
o
o
t in V-t
r
e
e. Similarly, C
3 and C
4 are two children of C
1. C
5 and C
6 are two children of C
2. Because C
3, C
4, C
5, and C
6 are four leaf nodes of V-t
r
e
e, then every one of them is associated with a minimum distance matrix. For example, C
1 is a closest pair set in C
4 and the minimum distance from C
1 to every node C
i in T
V is stored in the matrix associated with C
4. In Figure 4, every matrix maintaining the minimum distance is presented next to every node in V-t
r
e
e.Figure 3
A2-Partition on a voronoi-based index.Figure 4
V-tree of the voronoi-based index in Figure3.


### 5.2. How to Construct V-Tree

Algorithm3 describes how to constrcut a V-t
r
e
e  T
V for a given collection C of all the closest pair sets in a voronoi-based index. To construct V-t
r
e
e  T
V, Algorithm 3 utilizes a queue Q to dequeue the nodes in T
V iteratively and expand the children for every node until V-t
r
e
e has been constructed. Both Q and T
V are initialized as {
C
r
o
o
t
}, where C
r
o
o
t is the collection of all the closest pair set in voronoi-based index. In each iteration, a node C is dequeued from Q. If |
C
|
>
σ, C is a nonleaf node and then Algorithm 3 calls function Partition (C) to get the optimal λ-partition on C. Note that C is the number of the closest pair sets in C and Partition (C) is the implementation of METIS algorithm. Assume that the output of Partition (C) is {
C
1
,
…
,
C
λ
}, which will be inserted into T
V as the children set C
h
i
l
d
r
e
n
(
C
) of C. Next, Algorithm 3 enqueues every child C
x of C into Q. Note that if C
≤
σ, node C is a leaf node in T
V and Algorithm 3 will dequeue next top element in Q. When Q is empty, the structure of V-t
r
e
e  T
V has been constructed. Finally, for each leaf node C in T
V, Algorithm 3 calculates the minimum distance matrix {
d
(
C
i
,
C
′
)
∣
C
i
∈
C
∧
C
′
∈
T
v
} and associates it with the leaf node C. Therefore, V-t
r
e
e is constructed and returned.Algorithm 3:Construct-Vtree  (
C
r
o
o
t
,
λ
,
σ
).
Input: a collection C
r
o
o
t of all the closest pair sets in voronoi-based index, λ, σ
Output:  V-tree
T
V
1:Q
←
{
C
r
o
o
t
}, T
V
←
{
C
r
o
o
t
};   /∗  V-tree
T
V only have one node C as its root ∗/
2:while  Q
≠
∅  do
3:C
← Dequeue (Q);
4:if  |
C
|
>
σ  then
5:C
h
i
l
d
r
e
n
(
C
)
←Partition (C);
6:   insertsC
h
i
l
d
r
e
n
(
C
) into T
V as the children of C;
7:for each C
x
∈
C
h
i
l
d
r
e
n(C) do
8:    Enqueue
(
Q
,
C
x
);
9:for each leaf node C in T
V  do
10: calculatesd
C
i
,
C
′
∣
C
i
∈
C
∧
C
′
∈
T
v and maintains it on C;
11:return  T
VExample 13.
We use the example in Figure3 to show how to construct V-t
r
e
e in Figure 4. In this example, λ
=
2 and σ
=
3. At the beginning, Q and T
V are initialized as {
C
r
o
o
t
}; C
r
o
o
t is the collection of all the closest pair set in Figure 3. In the first iteration, the root node C
r
o
o
t is dequeued from Q, because |
C
r
o
o
t
|
=
11
≥
σ and C
r
o
o
t is partitioned into C
1 and C
2. Then C
1 and C
2 are inserted into T
v as two children of C
r
o
o
t. Next, C
1 and C
2 are enqueued into Q. In second and third iteration, C
1 and C
2 are dequeued from Q, respectively. {
C
3
,
C
4
} and {
C
5
,
C
6
} are inserted into T
V and enqueued into Q. Algorithm 3 dequeues C
3, C
4, C
5, and C
6 one by one. Finally, the minimum distance matrices on C
3, C
4, C
5, and C
6 are, respectively, computed and maintained in V-t
r
e
e  T
V. Thus the V-t
r
e
e shown in Figure 4 has been constructed.Space Complexity of V-Tree. The space complexities of V-t
r
e
e are given below. Let h denote the height of a V-t
r
e
e
T
V. Obviously, O
(
h
)
=
O
(
l
o
g
λ
|
O
|
/
σ
+
1
), where |
O
| is the number of objects in G
T. For the i-th level of T
V, there are at most λ
i nodes. Thus the number of nodes in a V-t
r
e
e  T
V is(24)
O
1
-
λ
l
o
g
λ
O
/
σ
+
1
1
-
λ
=
O
λ
O
/
σ
-
1
λ
-
1
=
O
O
σFor each leaf node C in T
V, a matrix is used to maintain the minimum distance from every closest pair set C
i
∈
C to every node C
′
∈
T
V. The size of every matrix is O
σ
×
O
/
σ
=
O
(
|
O
|
). Because there are at most O
(
|
O
|
/
σ
) leaf nodes in T
V, then the space complexity of T
V is O
(
|
O
|
2
/
σ
+
|
O
|
/
σ
)
=
O
(
|
O
|
2
/
σ
).For thetime complexity of V-t
r
e
e construction, Algorithm 3 needs to compute λ-partition using existing partition algorithm for every nonleaf nodes in T
V. We use O
(
P
λ
) to denote the time complexity of λ-partition on all the closest pair sets in voronoi-based index. Therefore, constructing the structure of T
V needs O
(
|
O
|
/
σ
×
P
λ
) time. For every leaf node C in T
V, the minimum distance needs to be calculated. The minimum distances from one C
i
∈
C to all other C
j can be calculated by single-source and multidestination shortest path algorithm, which can be done in O
(
|
O
|
2
) time. Then the time complexity for every matrix on leaf node is σ
|
O
|
2. Therefore, the time complexity of V-t
r
e
e construction is O
(
|
O
|
/
σ
×
P
λ
+
|
O
|
/
σ
×
σ
|
O
|
2
)
=
O
(
P
λ
|
O
|
/
σ
+
|
O
|
3
).


### 5.3. Query Processing with V-Tree

In this section, we propose an efficient algorithm for searchingk nearest objects by V-t
r
e
e. The pseudocode is shown in Algorithm 4. The same as Algorithm 2, O
(
v
q
) is a set of the objects that have been found up to now. Different from Algorithm 2, Algorithm 4 needs two priority queues Q and R, where Q is used to maintain some closest pair sets C
i whose o
i is possible to be one of k nearest objects and R is used to maintain some nodes C of V-t
r
e
e. All C
i in Q are sorted in an ascending order by the minimum travel time m
q
,
n
+
i from v
q to o
i. All C in R are sorted in an ascending order by the minimum distance d
(
C
q
,
C
). Initially, O
(
v
q
)
←
∅, Q
←
∅, and R
←
{
C
r
o
o
t
}. In each iteration, Algorithm 4 first considers the top elements C
i in Q and, C in R, there are two cases: (1) m
q
,
n
+
i
≤
d
(
C
q
,
C
) and (2) m
q
,
n
+
i
>
d
(
C
q
,
C
).Algorithm 4:
kNN-Query (v
q
,
t
d
,
k).
Input: query vertex v
q, departure time t
d and k
Output: the top-k nearest neighbor set O
(
v
q
)
1:Q
←
∅, O
(
v
q
)
←
∅, R
←
{
C
r
o
o
t
};
2:while  |
O
(
v
q
)
|
<
k and Q
≠
∅  do
3:  letC
i and C are the top elements in Q and R respectively;
4:if  m
q
,
n
+
i
≤
d
(
C
q
,
C
)  then
5:C
i
← Dequeue (Q), O
(
v
q
)
←
O
(
v
q
)
∪
{
o
i
};
6:B
(
O
(
v
q
)
)
←
B
(
O
(
v
q
)
)
∪
B
i;
7:for each v
x
∈
B
(
O
(
v
q
)
)  do
8:if  v
x
∈
C
i or v
x
∈
N
+
(
v
y
)
∧
v
y
∈
C
i  then
9:     updatesm
q
,
x;
10:for each C
j
∈
Q  do
11:if  C
j has an entry vertex connected to a border vertex in B
(
O
(
v
q
)
)  then
12:    updatesm
q
,
n
+
j;
13:else
14:C
← Dequeue (R);
15:if  C is a non-leaf node in T
V  then
16:for each C
x
∈
C
h
i
l
d
r
e
n
(
C
)  do
17:    Enqueue
(
R
,
C
x
);
18:else
19:for each C
j
∈
C  do
20:    Enqueue
(
Q
,
C
j
);
21:return  O
(
v
q
)For case (1),C
i is dequeued from Q with m
q
,
n
+
i; the object o
i of C
i must be one of k nearest objects of v
q. It can be guaranteed by Theorem 14 and then o
i will be inserted into O
(
v
q
). Let B
(
O
(
v
q
)
) denote the set of the border vertices for all C
i whose o
i
∈
O
(
v
q
), i.e., B
(
O
(
v
q
)
)
=
⋃
o
i
∈
O
(
v
q
)
‍
B
i. Algorithm 4 first updates B
(
O
(
v
q
)
) by B
(
O
(
v
q
)
)
∪
B
i and then updates the value of m
q
,
x for any v
x
∈
B
(
O
(
v
q
)
) if v
x
∈
C
i or v
x is an outgoing neighbor of v
y, v
y
∈
C
i. Next, Algorithm 4 updates m
q
,
n
+
j for any C
j
∈
Q by the border vertices in B
(
O
(
v
q
)
), if C
j has an entry vertex connected to a border vertex in B
(
O
(
v
q
)
). The order of C
j in Q is also be updated when m
q
,
n
+
j changes. The process for updating m
q
,
x and m
q
,
n
+
j is the same as that in Algorithm 2. Note that in Algorithm 2, when C
i is dequeued, all m
q
,
n
+
j for its neighboring C
j are needed to be updated, but for Algorithm 4, only some neighboring C
j
∈
Q are needed to be updated. Therefore, in each iteration, Algorithm 4 only needs to update m
q
,
n
+
j for a small number of C
j in Q which are a subset of the closest pair sets to be updated in Algorithm 2.For case (2),C is dequeued from R. If C is a nonleaf node in V-t
r
e
e, the children C
x
(
1
≤
x
≤
λ
) of C will be inserted into R with the minimum distance d
(
C
q
,
C
x
). Note that d
(
C
q
,
C
x
) is maintained in the leaf node C
q containing C
q in V-t
r
e
e. If C is a leaf node in V-t
r
e
e, every closest pair set C
i
∈
C will be enqueued into Q with m
q
,
n
+
i. Algorithm 4 calculates m
q
,
n
+
i by the following: (25)
m
i
n
v
x
∈
B
O
v
q
,
v
y
∈
C
i
,
v
x
,
v
y
∈
E
m
q
,
x
+
w
x
,
y
∗
t
d
+
m
q
,
x
+
m
y
,
n
+
iNote that the process to calculate m
q
,
n
+
i is as the same as that in Algorithm 2.Algorithm4 terminates when the size O
(
v
q
) is k. It means that k nearest objects of query vertex v
q have been found.Theorem14 guarantees the correctness of Algorithm 4.Theorem 14.
In Algorithm4, the object node o
i inserted into O
(
v
q
) at the k-th time must be the k-th nearest object of query vertex v
q for the departure time t
d.Proof.
Similar to the proof of Theorem8, we prove it by induction on k.
Basis. Obviously, the object node o
q in C
q is the first object node inserted into O
(
v
q
). By the definition of C
q and o
q, we know that o
q is indeed the nearest object of v
q for the departure time t
d.
Induction. Assume that the i-th nearest neighbor of v
q is inserted into the result set O
(
v
q
) at the i-th time for i
<
k. We need to prove it also hold for i
=
k. We prove it by contradiction. It can be known that the object node inserted into O
(
v
q
) at the i-th time is the object node that dequeued from the priority queue Q at the i-th time. Let C
k be the closest pair set dequeued from Q at the k-th time. Suppose that the k-th nearest object of v
q is o
k
′ and o
k
′
≠
o
k. Let p be the shortest path from v
q to o
k
′ with the departure time t
d. Because k
>
1, C
k
′ is not C
q and there must exist an entry v
e of C
k
′ in p. Let v
b be the predecessor of v
e in p; then v
b must be a border vertex of C
b at time points t
d
+
m
q
,
b and C
b
≠
C
k
′. Obviously, for the object node o
b of C
b, (1) o
b is not in the k nearest object set of v
q and (2) o
b is in the k nearest object set of v
q.
For case (1), it is similar to this case in Theorem8;
For case (2), it is assumed thato
b is the i-th (i
<
k) nearest object of v
q. According to Algorithm 4, we know that B
(
O
(
v
q
)
) will be updated, when o
b is inserted into O
(
v
q
). At this point, m
q
,
n
+
k
′ will be updated by B
(
O
(
v
q
)
) if C
k
′ is in Q. Otherwise, m
q
,
n
+
k
′ will be updated by B
(
O
(
v
q
)
) when C
k
′ is enqueued in Q. So C
k
′ will be dequeued from Q at k-th time with an accurate m
q
,
n
+
k
′, which is a contradiction. The proof is completed.Time and Space Complexities. We first analyze the time complexity of Algorithm 4. For processing priority queue Q, the time complexity is the same as Algorithm 2 in the worst case. For processing priority queue R, all nodes in T
V will be dequeued in the worst case; then the time complexity is O
(
|
O
|
/
σ
). Therefore, the time complexity of Algorithm 4 is O
(
k
b
(
d
+
e
)
+
|
O
|
/
σ
). Next, we analyze the space complexity, the same as Algorithm 2; the space complexity of Algorithm 4 is O
(
k
(
b
+
e
)
).


### 5.4. Effectiveness of V-Tree

We use the example in Figure3 to show Algorithm 4 with V-t
r
e
e being more efficient than Algorithm 2 without V-t
r
e
e. For this example, we set k
=
3, λ
=
2, and σ
=
3. The red five-pointed star represents the query vertex v
q which is in C
1 for the departure time t
d. The minimum distance m
q
,
n
+
i from v
q to every object o
i is shown in the table in Figure 3.For Algorithm2, Q is initialized as {
C
1
}. In the first iteration, C
1 is dequeued from Q. Because C
2, C
4, and C
9 are three neighboring closest pair set of C
1, Algorithm 2 will update their m
q
,
n
+
i and then enqueue them into Q. Similarly, in the second iteration, C
2 is dequeued from Q. C
3 and C
4 are enqueued into Q. C
3 will be dequeued from Q in the final iteration. Note that m
q
,
n
+
i for the object in C
4 will be updated twice in the first and second iteration, respectively; this is because C
4 is the neighboring closest pair set of both C
1 and C
2. Therefore, Algorithm 2 needs to update m
q
,
n
+
i for five times in the whole querying process.For Algorithm4 by V-t
r
e
e, R and Q are initialized as {
C
r
o
o
t
} and {
∅
}, respectively. When C
4 is dequeued from R, C
1,C
2, and C
3 are enqueued into Q. Note that B
(
O
(
v
q
)
)
=
∅; then Algorithm 4 does not need to update m
q
,
n
+
i for C
1, C
2, and C
3. In the following iterations, Algorithm 4 will dequeue C
1, C
2, and C
3 from Q one by one. This is because for the top element C
3 in R, d
(
C
q
,
C
3
)
=
7 is always larger than m
q
,
n
+
i for C
1, C
2, and C
3 which are the top elements in Q. When C
1 is dequeued from Q, m
q
,
n
+
2 is updated and C
2 is enqueued into Q. Similarly, m
q
,
n
+
3 will be updated and C
3 will be enqueued into Q. When C
3 is dequeued from Q, Algorithm 4 terminates and it only needs to update m
q
,
n
+
i twice in the whole querying process, which is obviously more efficient than Algorithm 2.Next, we give the following theorem to guarantee that the Algorithm4 with V-t
r
e
e is at least as good as Algorithm 2.Theorem 15.
The number of updatingm
q
,
n
+
i for all the closest pair sets in Algorithm 4 is no more than that in Algorithm 2.Proof.
In each iteration, for Algorithm2, when C
j is dequeued, all m
q
,
n
+
i for its neighboring C
i are needed to be updated. Obviously, for Algorithm 4, it only needs to update m
q
,
n
+
i for a small number of C
i in Q which are a subset of the closest pair sets to be updated in Algorithm 2. So the number of updating m
q
,
n
+
i for all the closest pair sets in Algorithm 4 is no more than that in Algorithm 2.


## 5.1. What Is V-Tree

V-t
r
e
e is a balanced tree structure to organize all the closest pair sets C
i in voronoi-based index. Specifically, every node in V-t
r
e
e is a collection of some closest pair sets. We first give the definition of λ-partition for voronoi-based index.Definition 9 (λ-partition for voronoi-based index).
Given a collectionC of some closest pair sets, a λ-partition of C is a set {
C
1
⋯
C
λ
} satisfying three following conditions: (1) ∀
C
i
,
C
i
⊂
C; (2) ∀
C
i
,
C
j
(
i
≠
j
)
,
C
i
∩
C
j
=
∅; (3) C
=
⋃
1
≤
i
≤
λ
‍
C
i.Note that everyC
i is a subset of C and it is also a collection of closest pair sets. Every node in V-t
r
e
e represents a collection C and has λ children by λ-partition on C; i.e., every C
i
(
1
≤
i
≤
λ
) is a child of C. Next, we introduce how to get an appropriate λ-partition for a given closest pair set C. An edge (
v
x
,
v
y
) is called a crossing edge from the closest pair sets C
i to C
j if v
x and v
y are the border vertices of C
i and C
j, respectively, i.e., v
x
∈
B
i and v
y
∈
B
j. As our discussion in Section 2, the time function of a crossing edge is modeled as a piecewise linear function w
x
,
y
(
t
). We define the expected traveling time  w
¯
i
,
j for a crossing edge (
v
x
,
v
y
) by the following: (16)
w
¯
x
,
y
=
1
T
∫
T
w
x
,
y
t
d
twhere T is the whole time interval for time function w
x
,
y
(
t
), i.e., T
=
t
p
-
t
0. Because w
x
,
y
(
t
) is a piecewise linear function, w
¯
x
,
y can be calculated as follows:(17)
w
¯
x
,
y
=
1
T
∫
T
w
x
,
y
t
d
t
=
1
t
p
-
t
0
∫
t
0
t
p
w
x
,
y
t
d
t
=
1
t
p
-
t
0
∑
i
=
1
p
∫
t
i
-
1
t
i
w
i
t
d
t
=
∑
i
=
1
p
t
i
-
t
i
-
1
t
p
-
t
0
×
w
i
t
i
-
1
+
w
i
+
1
t
i
2Note that the expected traveling time w
¯
i
,
j is a constant value to estimate the traveling time for crossing edge (
v
x
,
v
y
). Given two closest pair set C
i and C
j, we use E
i
,
j to denote set of all the crossing edges from C
i to C
j, i.e., E
i
,
j
=
v
x
,
v
y
∣
v
x
∈
B
i
∧
v
y
∈
B
j. Every closest pair set C
i can be regarded as a super vertex and there is an edge from C
i to C
j if E
i
,
j
≠
∅. The weight of such edge, denoted as a
i
,
j, is defined by the following: (18)
a
i
,
j
=
1
E
i
,
j
∑
v
x
,
v
y
∈
E
i
,
j
w
¯
x
,
yIt is worth noting that a
i
,
j is the average value of the expected traveling time for all the crossing edge from C
i to C
j. a
i
,
j is called the weight from C
i to C
j. Therefore, the λ-partition {
C
1
,
…
,
C
λ
} for a given collection C of some closest pair sets can be converted into a graph partition problem. For a pair of (
C
i
,
C
j
) with E
i
,
j
≠
∅, if C
i and C
j are in the same collection C
x
(
1
≤
x
≤
λ
), then it is called an inner edge of C
x. Otherwise, C
i and C
j are in two different collections C
x and C
y, respectively, and then it is called an interedge from C
x to C
y. Correspondingly, the weight a
i
,
j is called inner weight or interweight, respectively.InV-t
r
e
e, a parent node C is partitioned into λ children nodes {
C
1
,
…
,
C
λ
}. To facilitate k nearest object query, an appropriate partition is expected such that the inner weights are less and the interweights are more. Thus the optimal λ-partition is to find a group of {
C
1
,
…
,
C
λ
} that minimizes the following objective function:(19)
f
C
1
,
…
,
C
λ
=
∑
C
x
a
C
xwhere a
(
C
x
)
=
∑
a
i
,
j
∈
C
x
‍
a
i
,
j is the summation of all the inner weights a
i
,
j in C
x and f
C
1
,
…
,
C
λ is the summation of a
(
C
x
) for all C
x. The optimal λ-partition on C is similar to the traditional graph partition problem which has been well studied [15–17]. However, the objective function is to minimize the sum of the interweights for the traditional graph partition. Therefore, for any pair (
C
i
,
C
j
) in C, if E
i
,
j
≠
∅, we assign a new weight b
i
,
j
=
a
m
a
x
-
a
i
,
j on it, where a
m
a
x represents the maximum weight for all the inner edges in C. Consider the following objective funtion: (20)
g
C
1
,
…
,
C
λ
=
∑
C
x
,
C
y
b
C
x
,
C
ywhere b
(
C
x
,
C
y
)
=
∑
C
i
∈
C
x
,
C
j
∈
C
y
‍
b
i
,
j is the summation of b
i
,
j for all the inter edges from C
x to C
y and g
C
1
,
…
,
C
λ is the summation of b
(
C
x
,
C
y
) for all the pairs of C
x and C
y. The following theorem guarantees that the optimal λ-partition under objective functions f
(
·
) and g
(
·
) is the same.Theorem 10.
Theλ-partition minimizing f
(
·
) is exactly the λ-partition minimizing g
(
·
).Proof.
Given aλ-partition {
C
1
,
…
,
C
λ
} on C, let a
(
C
x
,
C
y
) denote the summation of all the inter weights a
i
,
j from C
x to C
y, that is, a
(
C
x
,
C
y
)
=
∑
C
i
∈
C
x
,
C
j
∈
C
y
‍
a
i
,
j, and then we have(21)
a
C
=
∑
C
x
,
C
y
a
C
x
,
C
y
+
∑
C
x
a
C
xBecause a
(
C
) is independent of λ-partition on C, then minimizing ∑
C
x
‍
a
(
C
x
) is equivalent to maximizing ∑
C
x
,
C
y
‍
a
(
C
x
,
C
y
). On the other hand, because b
i
,
j
=
a
m
a
x
-
a
i
,
j and b
i
,
j
≥
0, then maximizing ∑
C
x
,
C
y
‍
a
(
C
x
,
C
y
) is equivalent to minimizing ∑
C
x
,
C
y
‍
b
(
C
x
,
C
y
). Therefore, the λ-partition minimizing the objective function f
(
·
) also minimizes the objective function g
(
·
).Thus the optimalλ-partition under objective function g
(
·
) is a traditional graph partition problem. In this paper, we adopt the multilevel graph partitioning technique (METIS) proposed by Metis et al. in [15], which is a classic graph partition algorithm.Next, we introduce the concept of theminimum distance, which is to be maintained in V-t
r
e
e. For two closest pair set C
i and C
j, if E
i
,
j
≠
∅, we defined the minimum weight from C
i to C
j, denoted as w
i
,
j
m
i
n, by the following:(22)
w
i
,
j
m
i
n
=
m
i
n
v
x
,
v
y
∈
E
i
,
j
m
i
n
t
w
x
,
y
twhere (
v
x
,
v
y
)
∈
E
i
,
j is a crossing edge from C
i to C
j and m
i
n
t
w
x
,
y
t is the minimum value of time funtion w
x
,
y
(
t
). Thus w
i
,
j
m
i
n is the minimum value of m
i
n
t
w
x
,
y
t for all the crossing edge in E
i
,
j. A new graph can be constructed from the voronoi-based index; every closest pair set C
i can be regarded as a super vertex. If E
i
,
j
≠
∅, there is an edge from C
i to C
j and its weight is w
i
,
j
m
i
n. Therefore, for any two C
i and C
j, the shortest distance from C
i to C
j in this graph is called the minimum distance from C
i to C
j and we denote it by d
i
,
j. Especially, for a closest pair set C
i and a collection C, the minimum distance from C
i to C is denoted by d
(
C
i
,
C
) and is the minimum value of d
i
,
j for all C
j in C, i.e., d
(
C
i
,
C
)
=
m
i
n
C
j
∈
C
d
i
,
j. The value of d
(
C
i
,
C
) can be calculated easily by existing single-source shortest distance algorithm. Note that d
(
C
i
,
C
)
=
0 when C
i
∈
C. Next, we give the definition of V-t
r
e
e below.Definition 11 (V-tree).
AV-t
r
e
e, denoted as T
V, is a balanced tree T
V that satisfies the following conditions: (1)
Every node inV-t
r
e
e represents a collection C of some closest pair sets. Specially, the root node represents the collection C
r
o
o
t of all the closest pair sets in voronoi-based index;
(2)
Every nonleaf nodeC has λ children {
C
1
,
…
,
C
λ
}. All these children consist of the optimal λ-partition on C.
(3)
Every leaf nodeC has at most σ closest pair sets.InV-t
r
e
e, every leaf node C is associated with a matrix to maintain the minimum distance from every closest pair set C
i in leaf node C to every node C
′ in V-t
r
e
e
T
V, i.e.,(23)
d
C
i
,
C
′
∣
C
i
∈
C
∧
C
′
∈
T
V
,where C
′ and C are different nodes in T
V. It is because C
i
∈
C and then d
(
C
i
,
C
)
=
0. Note that if C
′ is an ancestor C in T
V, we also have d
(
C
i
,
C
′
)
=
0 directly.Example 12.
Figure3 illustrates an example of 2-partition on a voronoi-based index. The corresponding V-t
r
e
e is shown in Figure 4. In this example, C
r
o
o
t is the collection of all the closest pair set and it is partitioned into {
C
1
,
C
2
}. Thus C
1 and C
2 are two children of C
r
o
o
t in V-t
r
e
e. Similarly, C
3 and C
4 are two children of C
1. C
5 and C
6 are two children of C
2. Because C
3, C
4, C
5, and C
6 are four leaf nodes of V-t
r
e
e, then every one of them is associated with a minimum distance matrix. For example, C
1 is a closest pair set in C
4 and the minimum distance from C
1 to every node C
i in T
V is stored in the matrix associated with C
4. In Figure 4, every matrix maintaining the minimum distance is presented next to every node in V-t
r
e
e.Figure 3
A2-Partition on a voronoi-based index.Figure 4
V-tree of the voronoi-based index in Figure3.


## 5.2. How to Construct V-Tree

Algorithm3 describes how to constrcut a V-t
r
e
e  T
V for a given collection C of all the closest pair sets in a voronoi-based index. To construct V-t
r
e
e  T
V, Algorithm 3 utilizes a queue Q to dequeue the nodes in T
V iteratively and expand the children for every node until V-t
r
e
e has been constructed. Both Q and T
V are initialized as {
C
r
o
o
t
}, where C
r
o
o
t is the collection of all the closest pair set in voronoi-based index. In each iteration, a node C is dequeued from Q. If |
C
|
>
σ, C is a nonleaf node and then Algorithm 3 calls function Partition (C) to get the optimal λ-partition on C. Note that C is the number of the closest pair sets in C and Partition (C) is the implementation of METIS algorithm. Assume that the output of Partition (C) is {
C
1
,
…
,
C
λ
}, which will be inserted into T
V as the children set C
h
i
l
d
r
e
n
(
C
) of C. Next, Algorithm 3 enqueues every child C
x of C into Q. Note that if C
≤
σ, node C is a leaf node in T
V and Algorithm 3 will dequeue next top element in Q. When Q is empty, the structure of V-t
r
e
e  T
V has been constructed. Finally, for each leaf node C in T
V, Algorithm 3 calculates the minimum distance matrix {
d
(
C
i
,
C
′
)
∣
C
i
∈
C
∧
C
′
∈
T
v
} and associates it with the leaf node C. Therefore, V-t
r
e
e is constructed and returned.Algorithm 3:Construct-Vtree  (
C
r
o
o
t
,
λ
,
σ
).
Input: a collection C
r
o
o
t of all the closest pair sets in voronoi-based index, λ, σ
Output:  V-tree
T
V
1:Q
←
{
C
r
o
o
t
}, T
V
←
{
C
r
o
o
t
};   /∗  V-tree
T
V only have one node C as its root ∗/
2:while  Q
≠
∅  do
3:C
← Dequeue (Q);
4:if  |
C
|
>
σ  then
5:C
h
i
l
d
r
e
n
(
C
)
←Partition (C);
6:   insertsC
h
i
l
d
r
e
n
(
C
) into T
V as the children of C;
7:for each C
x
∈
C
h
i
l
d
r
e
n(C) do
8:    Enqueue
(
Q
,
C
x
);
9:for each leaf node C in T
V  do
10: calculatesd
C
i
,
C
′
∣
C
i
∈
C
∧
C
′
∈
T
v and maintains it on C;
11:return  T
VExample 13.
We use the example in Figure3 to show how to construct V-t
r
e
e in Figure 4. In this example, λ
=
2 and σ
=
3. At the beginning, Q and T
V are initialized as {
C
r
o
o
t
}; C
r
o
o
t is the collection of all the closest pair set in Figure 3. In the first iteration, the root node C
r
o
o
t is dequeued from Q, because |
C
r
o
o
t
|
=
11
≥
σ and C
r
o
o
t is partitioned into C
1 and C
2. Then C
1 and C
2 are inserted into T
v as two children of C
r
o
o
t. Next, C
1 and C
2 are enqueued into Q. In second and third iteration, C
1 and C
2 are dequeued from Q, respectively. {
C
3
,
C
4
} and {
C
5
,
C
6
} are inserted into T
V and enqueued into Q. Algorithm 3 dequeues C
3, C
4, C
5, and C
6 one by one. Finally, the minimum distance matrices on C
3, C
4, C
5, and C
6 are, respectively, computed and maintained in V-t
r
e
e  T
V. Thus the V-t
r
e
e shown in Figure 4 has been constructed.Space Complexity of V-Tree. The space complexities of V-t
r
e
e are given below. Let h denote the height of a V-t
r
e
e
T
V. Obviously, O
(
h
)
=
O
(
l
o
g
λ
|
O
|
/
σ
+
1
), where |
O
| is the number of objects in G
T. For the i-th level of T
V, there are at most λ
i nodes. Thus the number of nodes in a V-t
r
e
e  T
V is(24)
O
1
-
λ
l
o
g
λ
O
/
σ
+
1
1
-
λ
=
O
λ
O
/
σ
-
1
λ
-
1
=
O
O
σFor each leaf node C in T
V, a matrix is used to maintain the minimum distance from every closest pair set C
i
∈
C to every node C
′
∈
T
V. The size of every matrix is O
σ
×
O
/
σ
=
O
(
|
O
|
). Because there are at most O
(
|
O
|
/
σ
) leaf nodes in T
V, then the space complexity of T
V is O
(
|
O
|
2
/
σ
+
|
O
|
/
σ
)
=
O
(
|
O
|
2
/
σ
).For thetime complexity of V-t
r
e
e construction, Algorithm 3 needs to compute λ-partition using existing partition algorithm for every nonleaf nodes in T
V. We use O
(
P
λ
) to denote the time complexity of λ-partition on all the closest pair sets in voronoi-based index. Therefore, constructing the structure of T
V needs O
(
|
O
|
/
σ
×
P
λ
) time. For every leaf node C in T
V, the minimum distance needs to be calculated. The minimum distances from one C
i
∈
C to all other C
j can be calculated by single-source and multidestination shortest path algorithm, which can be done in O
(
|
O
|
2
) time. Then the time complexity for every matrix on leaf node is σ
|
O
|
2. Therefore, the time complexity of V-t
r
e
e construction is O
(
|
O
|
/
σ
×
P
λ
+
|
O
|
/
σ
×
σ
|
O
|
2
)
=
O
(
P
λ
|
O
|
/
σ
+
|
O
|
3
).


## 5.3. Query Processing with V-Tree

In this section, we propose an efficient algorithm for searchingk nearest objects by V-t
r
e
e. The pseudocode is shown in Algorithm 4. The same as Algorithm 2, O
(
v
q
) is a set of the objects that have been found up to now. Different from Algorithm 2, Algorithm 4 needs two priority queues Q and R, where Q is used to maintain some closest pair sets C
i whose o
i is possible to be one of k nearest objects and R is used to maintain some nodes C of V-t
r
e
e. All C
i in Q are sorted in an ascending order by the minimum travel time m
q
,
n
+
i from v
q to o
i. All C in R are sorted in an ascending order by the minimum distance d
(
C
q
,
C
). Initially, O
(
v
q
)
←
∅, Q
←
∅, and R
←
{
C
r
o
o
t
}. In each iteration, Algorithm 4 first considers the top elements C
i in Q and, C in R, there are two cases: (1) m
q
,
n
+
i
≤
d
(
C
q
,
C
) and (2) m
q
,
n
+
i
>
d
(
C
q
,
C
).Algorithm 4:
kNN-Query (v
q
,
t
d
,
k).
Input: query vertex v
q, departure time t
d and k
Output: the top-k nearest neighbor set O
(
v
q
)
1:Q
←
∅, O
(
v
q
)
←
∅, R
←
{
C
r
o
o
t
};
2:while  |
O
(
v
q
)
|
<
k and Q
≠
∅  do
3:  letC
i and C are the top elements in Q and R respectively;
4:if  m
q
,
n
+
i
≤
d
(
C
q
,
C
)  then
5:C
i
← Dequeue (Q), O
(
v
q
)
←
O
(
v
q
)
∪
{
o
i
};
6:B
(
O
(
v
q
)
)
←
B
(
O
(
v
q
)
)
∪
B
i;
7:for each v
x
∈
B
(
O
(
v
q
)
)  do
8:if  v
x
∈
C
i or v
x
∈
N
+
(
v
y
)
∧
v
y
∈
C
i  then
9:     updatesm
q
,
x;
10:for each C
j
∈
Q  do
11:if  C
j has an entry vertex connected to a border vertex in B
(
O
(
v
q
)
)  then
12:    updatesm
q
,
n
+
j;
13:else
14:C
← Dequeue (R);
15:if  C is a non-leaf node in T
V  then
16:for each C
x
∈
C
h
i
l
d
r
e
n
(
C
)  do
17:    Enqueue
(
R
,
C
x
);
18:else
19:for each C
j
∈
C  do
20:    Enqueue
(
Q
,
C
j
);
21:return  O
(
v
q
)For case (1),C
i is dequeued from Q with m
q
,
n
+
i; the object o
i of C
i must be one of k nearest objects of v
q. It can be guaranteed by Theorem 14 and then o
i will be inserted into O
(
v
q
). Let B
(
O
(
v
q
)
) denote the set of the border vertices for all C
i whose o
i
∈
O
(
v
q
), i.e., B
(
O
(
v
q
)
)
=
⋃
o
i
∈
O
(
v
q
)
‍
B
i. Algorithm 4 first updates B
(
O
(
v
q
)
) by B
(
O
(
v
q
)
)
∪
B
i and then updates the value of m
q
,
x for any v
x
∈
B
(
O
(
v
q
)
) if v
x
∈
C
i or v
x is an outgoing neighbor of v
y, v
y
∈
C
i. Next, Algorithm 4 updates m
q
,
n
+
j for any C
j
∈
Q by the border vertices in B
(
O
(
v
q
)
), if C
j has an entry vertex connected to a border vertex in B
(
O
(
v
q
)
). The order of C
j in Q is also be updated when m
q
,
n
+
j changes. The process for updating m
q
,
x and m
q
,
n
+
j is the same as that in Algorithm 2. Note that in Algorithm 2, when C
i is dequeued, all m
q
,
n
+
j for its neighboring C
j are needed to be updated, but for Algorithm 4, only some neighboring C
j
∈
Q are needed to be updated. Therefore, in each iteration, Algorithm 4 only needs to update m
q
,
n
+
j for a small number of C
j in Q which are a subset of the closest pair sets to be updated in Algorithm 2.For case (2),C is dequeued from R. If C is a nonleaf node in V-t
r
e
e, the children C
x
(
1
≤
x
≤
λ
) of C will be inserted into R with the minimum distance d
(
C
q
,
C
x
). Note that d
(
C
q
,
C
x
) is maintained in the leaf node C
q containing C
q in V-t
r
e
e. If C is a leaf node in V-t
r
e
e, every closest pair set C
i
∈
C will be enqueued into Q with m
q
,
n
+
i. Algorithm 4 calculates m
q
,
n
+
i by the following: (25)
m
i
n
v
x
∈
B
O
v
q
,
v
y
∈
C
i
,
v
x
,
v
y
∈
E
m
q
,
x
+
w
x
,
y
∗
t
d
+
m
q
,
x
+
m
y
,
n
+
iNote that the process to calculate m
q
,
n
+
i is as the same as that in Algorithm 2.Algorithm4 terminates when the size O
(
v
q
) is k. It means that k nearest objects of query vertex v
q have been found.Theorem14 guarantees the correctness of Algorithm 4.Theorem 14.
In Algorithm4, the object node o
i inserted into O
(
v
q
) at the k-th time must be the k-th nearest object of query vertex v
q for the departure time t
d.Proof.
Similar to the proof of Theorem8, we prove it by induction on k.
Basis. Obviously, the object node o
q in C
q is the first object node inserted into O
(
v
q
). By the definition of C
q and o
q, we know that o
q is indeed the nearest object of v
q for the departure time t
d.
Induction. Assume that the i-th nearest neighbor of v
q is inserted into the result set O
(
v
q
) at the i-th time for i
<
k. We need to prove it also hold for i
=
k. We prove it by contradiction. It can be known that the object node inserted into O
(
v
q
) at the i-th time is the object node that dequeued from the priority queue Q at the i-th time. Let C
k be the closest pair set dequeued from Q at the k-th time. Suppose that the k-th nearest object of v
q is o
k
′ and o
k
′
≠
o
k. Let p be the shortest path from v
q to o
k
′ with the departure time t
d. Because k
>
1, C
k
′ is not C
q and there must exist an entry v
e of C
k
′ in p. Let v
b be the predecessor of v
e in p; then v
b must be a border vertex of C
b at time points t
d
+
m
q
,
b and C
b
≠
C
k
′. Obviously, for the object node o
b of C
b, (1) o
b is not in the k nearest object set of v
q and (2) o
b is in the k nearest object set of v
q.
For case (1), it is similar to this case in Theorem8;
For case (2), it is assumed thato
b is the i-th (i
<
k) nearest object of v
q. According to Algorithm 4, we know that B
(
O
(
v
q
)
) will be updated, when o
b is inserted into O
(
v
q
). At this point, m
q
,
n
+
k
′ will be updated by B
(
O
(
v
q
)
) if C
k
′ is in Q. Otherwise, m
q
,
n
+
k
′ will be updated by B
(
O
(
v
q
)
) when C
k
′ is enqueued in Q. So C
k
′ will be dequeued from Q at k-th time with an accurate m
q
,
n
+
k
′, which is a contradiction. The proof is completed.Time and Space Complexities. We first analyze the time complexity of Algorithm 4. For processing priority queue Q, the time complexity is the same as Algorithm 2 in the worst case. For processing priority queue R, all nodes in T
V will be dequeued in the worst case; then the time complexity is O
(
|
O
|
/
σ
). Therefore, the time complexity of Algorithm 4 is O
(
k
b
(
d
+
e
)
+
|
O
|
/
σ
). Next, we analyze the space complexity, the same as Algorithm 2; the space complexity of Algorithm 4 is O
(
k
(
b
+
e
)
).


## 5.4. Effectiveness of V-Tree

We use the example in Figure3 to show Algorithm 4 with V-t
r
e
e being more efficient than Algorithm 2 without V-t
r
e
e. For this example, we set k
=
3, λ
=
2, and σ
=
3. The red five-pointed star represents the query vertex v
q which is in C
1 for the departure time t
d. The minimum distance m
q
,
n
+
i from v
q to every object o
i is shown in the table in Figure 3.For Algorithm2, Q is initialized as {
C
1
}. In the first iteration, C
1 is dequeued from Q. Because C
2, C
4, and C
9 are three neighboring closest pair set of C
1, Algorithm 2 will update their m
q
,
n
+
i and then enqueue them into Q. Similarly, in the second iteration, C
2 is dequeued from Q. C
3 and C
4 are enqueued into Q. C
3 will be dequeued from Q in the final iteration. Note that m
q
,
n
+
i for the object in C
4 will be updated twice in the first and second iteration, respectively; this is because C
4 is the neighboring closest pair set of both C
1 and C
2. Therefore, Algorithm 2 needs to update m
q
,
n
+
i for five times in the whole querying process.For Algorithm4 by V-t
r
e
e, R and Q are initialized as {
C
r
o
o
t
} and {
∅
}, respectively. When C
4 is dequeued from R, C
1,C
2, and C
3 are enqueued into Q. Note that B
(
O
(
v
q
)
)
=
∅; then Algorithm 4 does not need to update m
q
,
n
+
i for C
1, C
2, and C
3. In the following iterations, Algorithm 4 will dequeue C
1, C
2, and C
3 from Q one by one. This is because for the top element C
3 in R, d
(
C
q
,
C
3
)
=
7 is always larger than m
q
,
n
+
i for C
1, C
2, and C
3 which are the top elements in Q. When C
1 is dequeued from Q, m
q
,
n
+
2 is updated and C
2 is enqueued into Q. Similarly, m
q
,
n
+
3 will be updated and C
3 will be enqueued into Q. When C
3 is dequeued from Q, Algorithm 4 terminates and it only needs to update m
q
,
n
+
i twice in the whole querying process, which is obviously more efficient than Algorithm 2.Next, we give the following theorem to guarantee that the Algorithm4 with V-t
r
e
e is at least as good as Algorithm 2.Theorem 15.
The number of updatingm
q
,
n
+
i for all the closest pair sets in Algorithm 4 is no more than that in Algorithm 2.Proof.
In each iteration, for Algorithm2, when C
j is dequeued, all m
q
,
n
+
i for its neighboring C
i are needed to be updated. Obviously, for Algorithm 4, it only needs to update m
q
,
n
+
i for a small number of C
i in Q which are a subset of the closest pair sets to be updated in Algorithm 2. So the number of updating m
q
,
n
+
i for all the closest pair sets in Algorithm 4 is no more than that in Algorithm 2.


## 6. Experiements

We compare ourV-t
r
e
e method (marked as VT) and voronoi-based index method (marked as VI) with FTTI (Fast-Travel-Time Index) method [11] and TLNI (Tight-and-Loose-Network Index) method [9] on the real-life datasets. FTTI and TLNI are the state of the art index-based methods for kNN query over time-dependent road networks. Note that FTTI and TLNI are used on G
T
∗ in which every edge is an n
w
t-function w
i
,
j
∗
(
t
) because FTTI and TLNI do not allow the waiting time. Although some algorithms are proposed in recent works [5, 10], they are only to find the nearest object (i.e., k
=
1) and they cannot be used for general kNN query on time-dependent graphs. All the experiments are conducted on a 2.6GHz Intel Core i7 CPU PC with the 16GB main memory, running on Windows 7.


### 6.1. DataSets and Experiment Setup

We tested the voronoi-based index method on California road network (CARN) (http://snap.stanford.edu/data/roadNet-CA.html) with 196,5206 vertices and 553,3214 edges. We extracted five time-dependent graphs with different size using the CARN dataset. The number of vertices ranges from 100k to 500k. The time domain is set as T
=
[
0,2000
]; i.e., the departure time t can be selected from [
0,2000
] for any vertex. Here, 2000 means 2000 time units. For every w
i
,
j
(
t
), we split the time domain T to p subintervals and assign a linear function randomly for every subinterval and then w
i
,
j
(
t
) is a piecewise linear function.


### 6.2. Experienmental Results

Exp-1. Impact of Network Size. In this group of experiments, we study the impact of time-dependent network size. The number of the vertices increases from 100k to 500k and the number of objects is fixed at 10k. We investigate the querying time for k
=
7. The number of piecewise intervals of w
i
,
j
(
t
) is set as 4. As shown in Figures 5(a) and 5(b), the querying time of our method is always less than FTTI and TLNI. Note that our V-t
r
e
e method has the minimum querying time. Specifically, the querying time of TLNI is always much more than our methods even though TLNI has the smallest index size. The reason TLNI index only maintains the vertices for an object o
i is that the upper bound of travel time to o
i is less than the lower bound to the other objects. It cannnot facilitate query effectively in large networks.Figure 5
Impact of the network size.
(a)
Querying time
(b)
Index sizeExp-2. Impact of Object Set Size. In this group of experiments, the number of the vertices is fixed at 100k and the number of objects ranges from 10k to 50k. As shown in Figures 6(a) and 6(b), the querying time of our methods is always less than FTTI and TLNI. The querying time decreases with the increasing of the object set size. There are two reasons as follows: (1) the average size of C
i and B
i decreases if the object set size increases; (2) the increasing of object size results in that the objects become nearer to v
q and then querying time decreases. The index size for VI, FTTI, and TLNI decreases with increasing of the object size. But for V-t
r
e
e, the index size increases with the object size increasing. This is because more objects result in more nodes in V-t
r
e
e.Figure 6
Impact of the object set size.
(a)
Querying time
(b)
Index sizeExp-3. Impact of the Time Domain. In Figure 7, we study the impact of time domain. In this group of experiments, the number of vertices and objects is fixed at 100k and 10k, repectively. The time domain ranges from [
0,1000
] to [
0,3000
]. We investigate the querying time for k
=
7. As shown in Figures 7(a) and 7(b), the querying time and index size of our methods are not affected by the expanding of time domain. However, for FTTI and TLNI, the querying time increases with the the expanding of time domain. This is because they need to maintain the estimated value about travel time in index to facilitate kNN query. If the time domain becomes larger, the deviation between the estimation and the actual travel time will become larger too. It cannot facilitate query effectively.Figure 7
Impact of the length of time interval.
(a)
Querying time
(b)
Index sizeExp-4. Impact of the Number of Piecewise Intervals. In Figure 8, we investigate the impact of the number of piecewise intervals of w
i
,
j
(
t
). In this group of experiments, the number of piecewise intervals of w
i
,
j
(
t
) increases from 2 to 10. The numbers of the vertices and objects are fixed at 100k and 10k, repectively. As shown in Figures 8(a) and 8(b), the querying time and index size always increase with the increasing of the number of piecewise intervals. The reason is that the more piecewise intervals of w
i
,
j
(
t
), the more piecewise intervals of m
t
t-function and then the more border vertices maintained in the index.Figure 8
Impact of the number of piecewise interval of time function.
(a)
Querying time
(b)
Index sizeExp-5. Impact of the Average Distance to Objects. The impact of the average distance to objects is shown in Figure 9. In this group of experiments, the number of vertices is set as 100k and 500k, respectively. The number of objects is fixed at 10k and k
=
7. The average distance to objects ranges from 4 to 12. Note that the distance means the hops from the query vertex to an object. As shown in Figures 9(a) and 9(b), the querying time increases marginally with the increasing of distance. Our methods are always better than FTTI and TLNI.Figure 9
Impact of the average distance to objects.
(a)
The number of vertices is 100k
(b)
The number of vertices is 500kExp-6. Impact of k. In Figure 10, we study the querying time by varying k from 1 to 10 on two different networks with 10k vertices and 50k vertices, respectively. In this group of experiments, the number of objects is fixed at 10k and 50k for two different networks, respectively. As shown in Figures 10(a) and 10(b), the querying time always increases marginally with the increasing of k for our index method.Figure 10
Impact ofk.
(a)
The number of vertices is 100k
(b)
The number of vertices is 500kExp-7. Impact of
λ
and
σ. In Figure 11, we investigate the impact of the λ and σ for V-t
r
e
e. In this group of experiments, the numbers of the vertices and objects are fixed at 100k and 10k, repectively. The values of λ and σ are selected from [
2,4
,
6,8
,
10
] and [
10,20,30,40
], respectively. The experimental results shows the effectiveness of V-t
r
e
e is the best when λ
=
4. The querying time increases with the increasing of σ. But the index size increases with the decreasing of σ. The index size is not affected by λ varying.Figure 11
Impact ofλ and σ.
(a)
Querying time
(b)
Index size


## 6.1. DataSets and Experiment Setup

We tested the voronoi-based index method on California road network (CARN) (http://snap.stanford.edu/data/roadNet-CA.html) with 196,5206 vertices and 553,3214 edges. We extracted five time-dependent graphs with different size using the CARN dataset. The number of vertices ranges from 100k to 500k. The time domain is set as T
=
[
0,2000
]; i.e., the departure time t can be selected from [
0,2000
] for any vertex. Here, 2000 means 2000 time units. For every w
i
,
j
(
t
), we split the time domain T to p subintervals and assign a linear function randomly for every subinterval and then w
i
,
j
(
t
) is a piecewise linear function.


## 6.2. Experienmental Results

Exp-1. Impact of Network Size. In this group of experiments, we study the impact of time-dependent network size. The number of the vertices increases from 100k to 500k and the number of objects is fixed at 10k. We investigate the querying time for k
=
7. The number of piecewise intervals of w
i
,
j
(
t
) is set as 4. As shown in Figures 5(a) and 5(b), the querying time of our method is always less than FTTI and TLNI. Note that our V-t
r
e
e method has the minimum querying time. Specifically, the querying time of TLNI is always much more than our methods even though TLNI has the smallest index size. The reason TLNI index only maintains the vertices for an object o
i is that the upper bound of travel time to o
i is less than the lower bound to the other objects. It cannnot facilitate query effectively in large networks.Figure 5
Impact of the network size.
(a)
Querying time
(b)
Index sizeExp-2. Impact of Object Set Size. In this group of experiments, the number of the vertices is fixed at 100k and the number of objects ranges from 10k to 50k. As shown in Figures 6(a) and 6(b), the querying time of our methods is always less than FTTI and TLNI. The querying time decreases with the increasing of the object set size. There are two reasons as follows: (1) the average size of C
i and B
i decreases if the object set size increases; (2) the increasing of object size results in that the objects become nearer to v
q and then querying time decreases. The index size for VI, FTTI, and TLNI decreases with increasing of the object size. But for V-t
r
e
e, the index size increases with the object size increasing. This is because more objects result in more nodes in V-t
r
e
e.Figure 6
Impact of the object set size.
(a)
Querying time
(b)
Index sizeExp-3. Impact of the Time Domain. In Figure 7, we study the impact of time domain. In this group of experiments, the number of vertices and objects is fixed at 100k and 10k, repectively. The time domain ranges from [
0,1000
] to [
0,3000
]. We investigate the querying time for k
=
7. As shown in Figures 7(a) and 7(b), the querying time and index size of our methods are not affected by the expanding of time domain. However, for FTTI and TLNI, the querying time increases with the the expanding of time domain. This is because they need to maintain the estimated value about travel time in index to facilitate kNN query. If the time domain becomes larger, the deviation between the estimation and the actual travel time will become larger too. It cannot facilitate query effectively.Figure 7
Impact of the length of time interval.
(a)
Querying time
(b)
Index sizeExp-4. Impact of the Number of Piecewise Intervals. In Figure 8, we investigate the impact of the number of piecewise intervals of w
i
,
j
(
t
). In this group of experiments, the number of piecewise intervals of w
i
,
j
(
t
) increases from 2 to 10. The numbers of the vertices and objects are fixed at 100k and 10k, repectively. As shown in Figures 8(a) and 8(b), the querying time and index size always increase with the increasing of the number of piecewise intervals. The reason is that the more piecewise intervals of w
i
,
j
(
t
), the more piecewise intervals of m
t
t-function and then the more border vertices maintained in the index.Figure 8
Impact of the number of piecewise interval of time function.
(a)
Querying time
(b)
Index sizeExp-5. Impact of the Average Distance to Objects. The impact of the average distance to objects is shown in Figure 9. In this group of experiments, the number of vertices is set as 100k and 500k, respectively. The number of objects is fixed at 10k and k
=
7. The average distance to objects ranges from 4 to 12. Note that the distance means the hops from the query vertex to an object. As shown in Figures 9(a) and 9(b), the querying time increases marginally with the increasing of distance. Our methods are always better than FTTI and TLNI.Figure 9
Impact of the average distance to objects.
(a)
The number of vertices is 100k
(b)
The number of vertices is 500kExp-6. Impact of k. In Figure 10, we study the querying time by varying k from 1 to 10 on two different networks with 10k vertices and 50k vertices, respectively. In this group of experiments, the number of objects is fixed at 10k and 50k for two different networks, respectively. As shown in Figures 10(a) and 10(b), the querying time always increases marginally with the increasing of k for our index method.Figure 10
Impact ofk.
(a)
The number of vertices is 100k
(b)
The number of vertices is 500kExp-7. Impact of
λ
and
σ. In Figure 11, we investigate the impact of the λ and σ for V-t
r
e
e. In this group of experiments, the numbers of the vertices and objects are fixed at 100k and 10k, repectively. The values of λ and σ are selected from [
2,4
,
6,8
,
10
] and [
10,20,30,40
], respectively. The experimental results shows the effectiveness of V-t
r
e
e is the best when λ
=
4. The querying time increases with the increasing of σ. But the index size increases with the decreasing of σ. The index size is not affected by λ varying.Figure 11
Impact ofλ and σ.
(a)
Querying time
(b)
Index size


## 7. Related Work

kNN query has been well studied on static road networks. Most of the existing works propose various index techniques. The main ideas of these methods are to partition the vertices into several clusters, and then the clusters are organized as a voronoi diagram or a tree (e.g., R-tree) [14, 18–25]. These methods precompute and maintain the shortest distances for some pairs of vertices to facilitate kNN query. Unfortunately, these index techniques cannot be used for the time-dependent road networks because the minimum travel time between two vertices always varies with time. kNN query has also been studied on time-dependent road networks [9–12, 26]. Most of these works are based on A∗ algorithm. The authors in [5, 10] study the problem to find nearest (i.e., k
=
1) object on time-dependent networks. In [10], a virtual node v is inserted into the graph G with the zero-cost edges connecting to all the objects. The nearest object can be found on the shortest path from the query vertex to v. The authors in [27] study the problem of finding k POIs that minimize the aggregated travel time from a set of query points. The index-based methods are proposed in [9, 11]. In [9], a ∗ algorithm is utilized to expand the road networks by estimating an upper or lower bound of travel time. An index is built to facilitate kNN query using these estimated bounds. In [11], time domain is divided to several subintervals. For every subinterval, C nearest objects of every vertex are found by an estimation of minimum travel time. There are two main drawbacks of these methods. First, in these works, the FIFO (first in first out) property is required for networks and waiting time is not allowed. Second, the indexes proposed by these works are based on the estimated value of travel time. However, these indexes cannot facilitate query effectively for the large networks because the deviations are always too large between the estimated and the actual travel time.Recently, there are some works about the shortest path query between two given vertices over time-dependent graphs [13, 28–33]. However, these works do not study any index that can be used in kNN query over time-dependent road networks. Note that, in [32, 33], the waiting time is incorporated in arrival function g
i
(
t
) which represents the earliest arrival time for every vertex v
i when the departure time is t. Different to these works, we propose n
w
t-function w
i
,
j
∗
(
t
) to represent the minimum traveling time for every edge when the waiting time is allowed. The arrival function g
i
(
t
) cannot be utilized in our voronoi-based index for k nearest objects problem. Otherwise, the intuitive meaning behind w
i
,
j
∗
(
t
) is more easily comprehended than g
i
(
t
).


## 8. Conclusion

In this paper, we study the problem ofk nearest object query on time-dependent road networks. We first give an algorithm for processing time-dependent road networks such that the waiting time is not necessary to be considered and then propose a novel voronoi-based index to facilitate kNN query. We explain how to construct the index and complete the querying process using our index. Furthermore, we propose a novel balanced tree, named V-t
r
e
e, which is a secondary level index on voronoi-based index to make our querying algorithm more efficient. We confirm the efficiency of our method through extensive experiments on real-life datasets.



---

*Source: 4829164-2019-02-24.xml*