# Efficient Processing of Movingk-Range Nearest Neighbor Queries in Directed and Dynamic Spatial Networks

Authors: Hyung-Ju Cho; Rize Jin
Journal: Mobile Information Systems
 (2016)

---

## Abstract

Ak-range nearest neighbor (kRNN) query in a spatial network finds thek closest objects to each point in the query region. The essential nature of thekRNN query is significant in location-based services (LBSs), where location-aware queries with query regions such askRNN queries are frequently used because of the issue of location privacy and the imprecision of the associated positioning techniques. Existing studies focus on reducing computation costs at the server side while processingkRNN queries. They also consider snapshot queries that are evaluated once and terminated, as opposed to moving queries that require constant updating of their results. However, little attention has been paid to evaluating movingkRNN queries in directed and dynamic spatial networks where every edge is directed and its weight changes in accordance with the traffic conditions. In this paper, we propose an efficient algorithm called MORAN that evaluates movingk-range nearest neighbor (MkRNN) queries in directed and dynamic spatial networks. The results of a simulation conducted using real-life roadmaps indicate that MORAN is more effective than a competitive method based on a shared execution approach.


---

## Body

## 1. Introduction

Recently, positioning devices such as global positioning system (GPS) have become very popular. The use of navigation systems in automobiles is already widespread and this, together with mobile communications, facilitates new exciting applications [1, 2]. In these systems, points of interest (POIs), for example, hotels, campsites, and fuel stations, provided by online map services are located in a spatial network, and their proximity can be defined by the length, for example, the travel time, of the shortest path connecting them [3, 4]. Ak-range nearest neighbor (kRNN) query finds the k closest objects to each point inside a query range, as opposed to a query point [5–8]. Figure 1 gives an example of akRNN query in a spatial network, where a query object q is located inside a query region Q denoted by a rectangle for presentation convenience. Note that the numbers on the arrows in the figure indicate the order of the steps.kRNN queries are widely used in the context of location privacy and location uncertainty in location-based services (LBSs). More specifically, when using a potentially untrusted LBS server, users are reluctant to expose their exact location to the server because of the possibility of privacy leakages [9, 10]. As a result, many privacy-preserving techniques that blur the user location into a spatial region corresponding to query region Q have been proposed. Indeed, location uncertainty is inherent in LBSs because of the imprecision of the utilized positioning system [5].Figure 1
Example of akRNN query whose region is denoted by Q.Depending on the query lifetime, a location-aware query can be classified as either a snapshot query or a moving query. A snapshot query returns a result only once, whereas a moving query returns results continuously for a designated period. Existing algorithms focus on evaluating snapshotkRNN queries. They primarily consider undirected and static spatial networks where every edge is undirected and its weight does not change over time [5–8]. However, their problem scenarios based on undirected and static spatial networks fail to provide a sufficient level of realism for many applications of interest when query objects move freely and constantly.In this paper, we present a new approach for evaluating movingkRNN queries (MkRNN) in directed and dynamic spatial networks where each edge has a particular orientation and its weight changes in accordance with the traffic conditions. Clearly, directed and dynamic spatial network models provide more realistic modeling of urban road networks than undirected and static spatial network models. For example, after entering a highway, a driver must remain on that highway until he/she has reached an exit point, even if he/she has chosen an incorrect path. Thus, a highway can be represented using directed edges. Furthermore, the travel time to a destination selected by a query user frequently changes in accordance with the traffic conditions. In moving objects databases, a safe segment (or safe region) is a popular technique used in the processing of moving queries [11–17]. A safe segment (or safe region) indicates a segment (or region) in which the movement of a query object does not cause the current query result to change. This helps to reduce communication and computation costs.In this paper, we propose an efficient algorithm, called MORAN, for processing movingk-range nearest neighbor queries in directed and dynamic spatial networks, under the assumption that query objects move freely on spatial networks and that data objects are stationary. In our approach, a query region Q is partitioned into safe segments, which are maintained in directed and dynamic spatial networks. Clearly, unless the safe segments are used, the query object should evaluate akNN query at its location using thekRNN query result provided by the server whenever it moves inside the query region. This simple approach places an excessive computational burden on the client side with a high computation frequency. Another considerable approach that can be used to solve this problem is to predict the movement of the query object in order to create the query results beforehand [18, 19]. However, in this paper, we consider a more realistic scenario, in which the query object moves arbitrarily and its path is not known in advance.The contributions made in this paper can be summarized as follows.(i)
We propose a new algorithm called MORAN that partitions query regions into safe segments to facilitate efficient processing of MkRNN queries in directed and dynamic spatial networks.(ii)
We also propose a method that preserves the validity of the safe segments when traffic conditions are updated.(iii)
We outline extensive experiments conducted to demonstrate the effectiveness and efficiency of MORAN under various conditions.The remainder of this paper is organized as follows. Section2 reviews related studies. Section 3 defines the primary terms used in this paper and formulates the research problem. Section 4 presents our proposed method for dividing query regions into safe segments in directed spatial networks. Section 5 presents our proposed method for maintaining the safe segments in dynamic spatial networks. Section 6 analyzes the extensive experimental results obtained. Finally, Section 7 provides concluding remarks regarding the proposed method.


## 2. Related Work

To ensure location privacy in pervasive computing, mobile users frequently issuekRNN queries using cloaked regions, corresponding to the query regions in this study [5–8, 20]. Then, a server performs query processing, assuming that the user can be at any location inside the query region, and thus not knowing the exact location of the query issuer. Several studies on processing ofkRNN queries in Euclidean space have been conducted. Kalnis et al. [21] developed a new algorithm for computingkRNN queries based on circular regions that reduce the number of redundant results, as well as the communication cost. Chow et al. [22] proposed a new approximate range NN query processing algorithm that enables the user to tune the tradeoff between the query response time and the quality of the query answers. The algorithm allows the user to specify an approximation tolerance level, where an answer setA is returned such that each object inA is one of thekNNs of every point in the query region. Xu et al. [23] developed an efficient algorithm for evaluating circular-region-basedkNN queries that applies a filter method based on a distance measure to prune out POIs effectively. However, these techniques based on Euclidean distance cannot be applied to our problem concerning network-constrained mobile users and network distance-based queries.kRNN queries have also been widely studied in the context of privacy-preserving LBSs based on spatial network distance, where the exact location of the query issuer is blurred into the query region [5–8]. The basic idea underlying the processing of akRNN query is to execute a range query to retrieve data objects within the query region and executekNN queries at the boundary points of the query region. Ku et al. [6] developed a privacy-aware spatial network nearest neighbor query algorithm that retrieves all POIs inside a given cloaked region and finds POIs outside the cloaked region using spatial network expansion. Naturally, issuingkNN queries multiple times in order to processkRNN queries leads to a huge redundant search overhead. To rectify this problem, Bao et al. [5] proposed an efficientkRNN query processing algorithm that employs a shared execution approach to eliminate the redundant search overhead.Existing algorithms such as [5–8] deal with snapshotkRNN queries as opposed to the movingkRNN queries considered in this study. Consequently, they focus on reducing the computation time of the server as well as communication costs between the server and query objects. Thus, while processing snapshotkRNN queries, existing algorithms do not have to consider the computation time of the query objects that evaluate the exactkNN set using a set of candidate data objects provided by the server. This is because in processing snapshotkRNN queries, the computation time of the query objects is very small compared to the computation time of the server. However, very little research has focused on supporting MkRNN queries in directed and dynamic spatial networks where the computation time of the query objects is not negligible.Nutanong et al. [16] developed an incremental safe-region-based technique, called the V∗-Diagram, for answering movingkNN queries in Euclidean space as well as in undirected spatial networks. However, V∗-Diagram is not appropriate in our problem scenarios because the distance is transitive in both Euclidean space and undirected spatial networks, whereas the distance is not transitive in directed spatial networks. Yung et al. [17] proposed an algorithm for computing the boundary, referred to as safe exits, of the safe region of moving range queries in spatial networks. Their solution focuses on moving range queries (e.g., find gas stations within r=3km for the next 10 minutes) and is thus inapplicable for the processing of MkRNN queries.MORAN differs from existing studies in several aspects: first, it considers MkRNN queries in directed and dynamic spatial networks; second, it focuses on reducing the computation time and frequency of the query object; and finally, it efficiently determines and maintains safe segments within a query region. In recent years, various types of queries on moving objects have also been studied extensively. They include range queries [14, 17],kNN queries with two predicates [24], and obstructedkNN queries [25]. The associated studies have different problem scenarios from those in our study and their solutions are not appropriate.Finally, Table1 compares our problem scenario with related work in terms of query type, space domain, and mobility of query objects and data objects. Because of space limitations, we shorten the terms “undirected and static spatial network” to “USSN” and “directed and dynamic spatial network” to DDSN.Table 1
Classification of related work.
References
Query type
Space domain
Query object
Data object
[11, 12]
Range
Euclidean
Moving
Static
[4]
Range
USSN
Static
Static
[17]
Range
USSN
Moving
Static
[14]
Range
DDSN
Moving
Static
[15, 16, 18, 19]
kNN
Euclidean
Moving
Static
[2, 13, 16]
kNN
USSN
Moving
Static
[4, 30, 31]
kNN
USSN
Static
Static
[1, 26]
kNN
USSN
Moving
Moving
[20–23]
kRNN
Euclidean
Static
Static
[5–8]
kRNN
USSN
Static
Static
This paper
kRNN
DDSN
Moving
Static


## 3. Background

Section3.1 defines the terms and notations used in this paper. Section 3.2 formulates the problem by using an example.


### 3.1. Definition of Terms and Notations

Now, we define the terms and notations used in this paper for clarification.Spatial Network. A spatial network is represented by a weighted directed graph G=(N,E,W), where N, E, and W denote a node set, edge set, and edge distance matrix, respectively. Each edge connecting two nodes has a weight and a specific orientation. The weight of an edge changes depending on the traffic conditions, and its direction is either bidirectional or unidirectional. Specifically, ninj¯ denotes an undirected edge, where ni and nj are adjacent nodes, whereas ninj→ or ninj← denotes a directed edge. The arrow above the edge denotes the associated direction.Classification of Nodes. Nodes can be classified into three categories according to the node degree: (1) if it is greater than or equal to 3, the node is referred to as an intersection node; (2) if it is equal to 2, the node is an intermediate node; and (3) if it is equal to 1, the node is a terminal node.Edge Sequence and Segment. An edge sequence, denoted by either nsns+1⋯ne¯ or nsns+1⋯ne→, refers to a path connecting two nodes, ns and ne, such that ns (or ne) is either an intersection or terminal node, and the other nodes in the path are intermediate nodes. The two end nodes, ns and ne, are called boundary nodes. Clearly, all edges in the same edge sequence have the same direction. The length of an edge sequence is the total weight of the edges in the edge sequence. One part of an edge sequence is called a segment. Note that by definition, an edge sequence is also a segment defined by the boundary nodes of the edge sequence.To simplify the presentation, Notations and Their Definitions summarizes the notations used in this paper. The distance between two points in a directed spatial networkG is not symmetric; that is, for two points p1,p2∈G, there is no guarantee that distp1,p2 equals distp2,p1. Note that if the algorithms for MORAN operate in the same manner for undirected and directed spatial segments, an undirected segment is used for convenience to describe the algorithms.Figure2 depicts the distances and segment length between two objects o1 and o2 in a directed spatial network. In this figure, the shortest path from o1 to o2 is o1→n2→n5→o2 and thus the distance from o1 to o2 is disto1,o2=6. Conversely, the shortest path from o2 to o1 is o2→n4→n3→o1 and thus the distance from o2 to o1 is disto2,o1=9. This proves that the network distance is not symmetric in a directed spatial network. The segment connecting o1 and o2 in the same edge sequence n2n3n4n5← becomes o1→n3→n4→o2 and thus its length is leno1,o2=9. Recall that lenp1,p2 is defined if and only if the two points, p1 and p2, are located in the same edge sequence.Figure 2
d
i
s
t
o
1
,
o
2
=
6, disto2,o1=9, and leno1,o2=9.


### 3.2. Problem Formulation

Figure3 shows an example of an MkRNN query in a directed and dynamic spatial network. Here, data objects o1 through o5 are represented by the rectangles and a query region Q is represented by a set of bold line segments; that is, Q={n1n3←,n2n3¯,n3n4←}. The boundary point of a query region indicates the point where the query region and nonquery region meet. In this example, query region Q has four boundary points, n1 through n4. The number next to an edge indicates the distance between the two adjacent objects. Suppose that a query object q in query region Q requests two NNs from the server, while hiding its location from the server. Then, thekRNN query result for Q should include the two closest data objects to each point in query region Q. The query result can be represented by a set of S,R tuples, where S is a safe segment in Q and R is the query result for the safe segment S. As shown in Figure 3(a), query region Q can be partitioned into four safe segments; that is, Ω1=n1o3←,o1,o2, Ω2=n3o3→,o2,o3, Ω3=n2s¯,o4,o5, and Ω4=n3s¯∪n3n4←,o3,o4. Clearly, if query object q is located in a safe segment n1o3← (i.e., q∈n1o3←), then thekNN set of q is o1,o2. Similarly, if q∈n3o3→, then thekNN set of q is o2,o3, if q∈n2s¯, then thekNN set for q is o4,o5, and if q∈n3s¯∪n3n4←, then thekNN set of q is o3,o4. As shown in Figure 3(b), if the weight of an edge n1o1→ represented by the bold dotted line is updated from 3 to 5 at time tj, this update may affect the safe segments computed at time ti, which leads to nullifying thekNN set of q∈Q.Figure 3
Example of MkRNN query in a spatial network, where k=2 and ti<tj.
(a)
MkRNN query with k=2 and its safe segments at time ti
(b)
Updated traffic conditions at timetjThe query regionQ consists of a set Qs of l segments and a set Qb of m boundary points; that is, Qs={s1,s2,…,sl} and Qb={b1,b2,…,bm}. Clearly, a query object q is located inside query region Q, while hiding its exact location from the server to ensure location privacy. Note that we use the terms “query object q” and “query point q” interchangeably for convenience of discussion. Clearly, for a query point q∈Q,  Okq⊆(⋃i=1mOkbi)∩(⋃j=1lO(sj)) holds, where Okbi refers to a set of kNNs at a boundary point bi∈Qb and O(sj) refers to a set of objects inside a segment sj∈Qs. It should be noted that processingkRNN queries at the server is orthogonal to this study. Therefore, anykRNN query processing algorithms (e.g., [5, 6]) can be used to evaluate thekRNN queries at the server. The server evaluates akRNN query for a query region Q and then provides a set of candidate data objects to query object q. Finally, q determines safe segments using a set of candidate data objects for the query region Q. Recall that given a safe segment S, for two points q1,q2∈S, Okq1 is equal to Okq2.Figure4 illustrates three scenarios that can arise when a query object q issueskRNN queries. As shown in Figure 4(a), at time ti, a query object q submits akRNN query for a query region Qi to the server. On receiving the query, the server evaluates thekRNN query and returns the query result to q∈Qi. Clearly, q determines safe segments inside query region Qi using thekRNN query result. As shown in Figure 4(b), when q leaves the query region Qi at time tj, it submits akRNN query for an updated query region Qj to the server. Then, the server evaluates thekRNN query and returns the query result to q∈Qj. Clearly, q determines safe segments inside query region Qj. As shown in Figure 4(c), while q is inside Qj at time tk, a query region Qj overlaps a traffic congestion area T, marked by a gray rectangle, in which the weight of the edges changes. The server realizes that the traffic congestion area T invalidates thekRNN query result for Qj and thus requests that q updates the query region. Consequently, q submits akRNN query for an updated query region Qk to the server, which evaluates thekRNN query and returns the query result to q∈Qk. Clearly, q determines the safe segments inside query region Qk. In Section 5, we elaborate on a method to verify that an updated traffic condition invalidates currentkRNN query results.Figure 4
Three scenarios for processing MkRNN queries.
(a)
q submits a kRNN query for a query region Qi to the server at time ti, where q∈Qi
(b)
q submits a kRNN query for an updated query region Qj to the server when q leaves Qi at tj
(c)
Server requests thatq updates the query region when a set of candidate objects is invalidated at tk


## 3.1. Definition of Terms and Notations

Now, we define the terms and notations used in this paper for clarification.Spatial Network. A spatial network is represented by a weighted directed graph G=(N,E,W), where N, E, and W denote a node set, edge set, and edge distance matrix, respectively. Each edge connecting two nodes has a weight and a specific orientation. The weight of an edge changes depending on the traffic conditions, and its direction is either bidirectional or unidirectional. Specifically, ninj¯ denotes an undirected edge, where ni and nj are adjacent nodes, whereas ninj→ or ninj← denotes a directed edge. The arrow above the edge denotes the associated direction.Classification of Nodes. Nodes can be classified into three categories according to the node degree: (1) if it is greater than or equal to 3, the node is referred to as an intersection node; (2) if it is equal to 2, the node is an intermediate node; and (3) if it is equal to 1, the node is a terminal node.Edge Sequence and Segment. An edge sequence, denoted by either nsns+1⋯ne¯ or nsns+1⋯ne→, refers to a path connecting two nodes, ns and ne, such that ns (or ne) is either an intersection or terminal node, and the other nodes in the path are intermediate nodes. The two end nodes, ns and ne, are called boundary nodes. Clearly, all edges in the same edge sequence have the same direction. The length of an edge sequence is the total weight of the edges in the edge sequence. One part of an edge sequence is called a segment. Note that by definition, an edge sequence is also a segment defined by the boundary nodes of the edge sequence.To simplify the presentation, Notations and Their Definitions summarizes the notations used in this paper. The distance between two points in a directed spatial networkG is not symmetric; that is, for two points p1,p2∈G, there is no guarantee that distp1,p2 equals distp2,p1. Note that if the algorithms for MORAN operate in the same manner for undirected and directed spatial segments, an undirected segment is used for convenience to describe the algorithms.Figure2 depicts the distances and segment length between two objects o1 and o2 in a directed spatial network. In this figure, the shortest path from o1 to o2 is o1→n2→n5→o2 and thus the distance from o1 to o2 is disto1,o2=6. Conversely, the shortest path from o2 to o1 is o2→n4→n3→o1 and thus the distance from o2 to o1 is disto2,o1=9. This proves that the network distance is not symmetric in a directed spatial network. The segment connecting o1 and o2 in the same edge sequence n2n3n4n5← becomes o1→n3→n4→o2 and thus its length is leno1,o2=9. Recall that lenp1,p2 is defined if and only if the two points, p1 and p2, are located in the same edge sequence.Figure 2
d
i
s
t
o
1
,
o
2
=
6, disto2,o1=9, and leno1,o2=9.


## 3.2. Problem Formulation

Figure3 shows an example of an MkRNN query in a directed and dynamic spatial network. Here, data objects o1 through o5 are represented by the rectangles and a query region Q is represented by a set of bold line segments; that is, Q={n1n3←,n2n3¯,n3n4←}. The boundary point of a query region indicates the point where the query region and nonquery region meet. In this example, query region Q has four boundary points, n1 through n4. The number next to an edge indicates the distance between the two adjacent objects. Suppose that a query object q in query region Q requests two NNs from the server, while hiding its location from the server. Then, thekRNN query result for Q should include the two closest data objects to each point in query region Q. The query result can be represented by a set of S,R tuples, where S is a safe segment in Q and R is the query result for the safe segment S. As shown in Figure 3(a), query region Q can be partitioned into four safe segments; that is, Ω1=n1o3←,o1,o2, Ω2=n3o3→,o2,o3, Ω3=n2s¯,o4,o5, and Ω4=n3s¯∪n3n4←,o3,o4. Clearly, if query object q is located in a safe segment n1o3← (i.e., q∈n1o3←), then thekNN set of q is o1,o2. Similarly, if q∈n3o3→, then thekNN set of q is o2,o3, if q∈n2s¯, then thekNN set for q is o4,o5, and if q∈n3s¯∪n3n4←, then thekNN set of q is o3,o4. As shown in Figure 3(b), if the weight of an edge n1o1→ represented by the bold dotted line is updated from 3 to 5 at time tj, this update may affect the safe segments computed at time ti, which leads to nullifying thekNN set of q∈Q.Figure 3
Example of MkRNN query in a spatial network, where k=2 and ti<tj.
(a)
MkRNN query with k=2 and its safe segments at time ti
(b)
Updated traffic conditions at timetjThe query regionQ consists of a set Qs of l segments and a set Qb of m boundary points; that is, Qs={s1,s2,…,sl} and Qb={b1,b2,…,bm}. Clearly, a query object q is located inside query region Q, while hiding its exact location from the server to ensure location privacy. Note that we use the terms “query object q” and “query point q” interchangeably for convenience of discussion. Clearly, for a query point q∈Q,  Okq⊆(⋃i=1mOkbi)∩(⋃j=1lO(sj)) holds, where Okbi refers to a set of kNNs at a boundary point bi∈Qb and O(sj) refers to a set of objects inside a segment sj∈Qs. It should be noted that processingkRNN queries at the server is orthogonal to this study. Therefore, anykRNN query processing algorithms (e.g., [5, 6]) can be used to evaluate thekRNN queries at the server. The server evaluates akRNN query for a query region Q and then provides a set of candidate data objects to query object q. Finally, q determines safe segments using a set of candidate data objects for the query region Q. Recall that given a safe segment S, for two points q1,q2∈S, Okq1 is equal to Okq2.Figure4 illustrates three scenarios that can arise when a query object q issueskRNN queries. As shown in Figure 4(a), at time ti, a query object q submits akRNN query for a query region Qi to the server. On receiving the query, the server evaluates thekRNN query and returns the query result to q∈Qi. Clearly, q determines safe segments inside query region Qi using thekRNN query result. As shown in Figure 4(b), when q leaves the query region Qi at time tj, it submits akRNN query for an updated query region Qj to the server. Then, the server evaluates thekRNN query and returns the query result to q∈Qj. Clearly, q determines safe segments inside query region Qj. As shown in Figure 4(c), while q is inside Qj at time tk, a query region Qj overlaps a traffic congestion area T, marked by a gray rectangle, in which the weight of the edges changes. The server realizes that the traffic congestion area T invalidates thekRNN query result for Qj and thus requests that q updates the query region. Consequently, q submits akRNN query for an updated query region Qk to the server, which evaluates thekRNN query and returns the query result to q∈Qk. Clearly, q determines the safe segments inside query region Qk. In Section 5, we elaborate on a method to verify that an updated traffic condition invalidates currentkRNN query results.Figure 4
Three scenarios for processing MkRNN queries.
(a)
q submits a kRNN query for a query region Qi to the server at time ti, where q∈Qi
(b)
q submits a kRNN query for an updated query region Qj to the server when q leaves Qi at tj
(c)
Server requests thatq updates the query region when a set of candidate objects is invalidated at tk


## 4. Processing MkRNN Queries in Directed Spatial Networks

In Section4.1, we give an overview of MORAN. In Section 4.2, we present an algorithm for determining safe segments in a query region. Finally, in Section 4.3, we discuss the construction of the safe segments of an MkRNN query for the example of directed spatial network.


### 4.1. Overview

As stated before, we focus on query processing at the client side while processing MkRNN queries in a directed and dynamic spatial network. If either of the two events in Figure 5 occurs, the server should evaluate thekRNN query and provide query object q with an updatedkRNN query result. The first event is q leaving the current query region. For example, as shown in Figure 5(a), if q moves to q′ outside of Q, akRNN query should be reevaluated with the updated query region. The second event is invalidation of the currentkRNN query result provided to query object q because of an updated traffic condition. For example, as shown in Figure 5(b), if query region Q overlaps traffic congestion area T, thekRNN query should be reevaluated to reflect the updated traffic condition. When the query object receives an updatedkRNN query result from the server, it should reevaluate safe segments inside the query region. Using safe segments reduces the computation time and frequency because the query object does not have to evaluatekNN queries while inside the safe segments.Figure 5
Two events that trigger the evaluation of MkRNN queries.
(a)
q leaves query region Q
(b)
Congestion areaT nullifies kRNN query result for QAlgorithm1 outlines the process of determining the safe segments in a query region Q in a directed spatial network. The algorithm starts by initializing Ω to an empty set, which stores the safe segments found thus far. Each segment αβ- in query region Q is explored sequentially to find the safe segments in segment αβ-. For this purpose, MORAN evaluates twokNN queries issued at boundary points α and β of segment αβ-. The query results are stored to Okα and Okβ, respectively. The objects in αβ- are explored and stored to Oαβ¯. The function find_safe_segments is called with Okα, Okβ, and Oαβ¯ in order to find safe segments in segment αβ-. The found safe segments are added to the result set Ω. When all the segments in Q have been examined, a set Ω of safe segments in query region Q is returned to the query issuer. It should be noted that if updates in the weight of edges frequently occur in a spatial network, it is better to determine the safe segments in the current segment including the query point rather than all the safe segments in the query region. We employ a shared execution approach [5], which is widely used to avoid multiple visits to the same nodes and edges. This clearly reduces the query processing time while determining safe segments in a query region.Algorithm 1:MORAN (Q,k).
Input: Q: query region, k: the number of requested NNs
Output: Ω: the set of safe segments in Q
(1)Ω←∅                        // Ω is initialized to an empty set
(2)for each segment αβ-∈Q  do
(3)Okα← evaluate_kNN_query_at_point (α, k)      // a kNN query is evaluated at a boundary point α
(4)Okβ← evaluate_kNN_query_at_point (β, k)      // a kNN query is evaluated at a boundary point β
(5)Oαβ¯← evaluate_range_query (αβ¯)          // a range query is evaluated for a segment αβ¯
(6)Ωαβ¯← find_safe_segments (Okα, Okβ, O(αβ¯))    // the function is detailed in Section 4.2
(7)Ω←Ω∪Ωαβ¯
(8)return  Ω                      // the set of safe segments is provided to the query issuer


### 4.2. Partitioning Query Region into Safe Segments

We consider an undirected segmentαβ¯ followed by a directed segment αβ→. We present a method for finding safe segments in segment αβ¯ by using Okα, Okβ, and O(αβ¯). Here, Okα and Okβ refer to sets of kNNs at boundary points α and β, respectively, and O(αβ¯) refers to a set of objects inside segment αβ¯. An object o that belongs to the union of Okα, Okβ, and O(αβ¯), that is, o∈Okα∪Okβ∪O(αβ¯), is referred to as a qualifying object. Clearly, the set Okq of kNNs at a query point q∈αβ¯ is a subset of the union of Okα, Okβ, and O(αβ¯) [5, 13, 26]; that is, Okq⊆(Okα∪Okβ∪O(αβ¯)). If Okα equals Okβ and O(αβ¯) is a subset of Okα, segment αβ¯ becomes a safe segment. Otherwise, it has two or more safe segments.We first explore the change in a network distancedistq,o for a qualifying object o∈Okα∪Okβ∪O(αβ¯) when a query point q is located in an undirected segment αβ¯ [13, 14]. Figure 6 shows the change in distq,o for three cases: o∈Okα, o∈Okβ, and o∈O(αβ¯). In this figure, the y-axis represents distq,o and the x-axis represents lenα,q for 0≤lenα,q≤lenα,β. If o∈Okα, then distq,o=lenq,α+distα,o, as shown in Figure 6(a). Similarly, if o∈Okβ, then distq,o=lenq,β+distβ,o, as shown in Figure 6(b). Finally, if o∈O(αβ¯), then distq,o=lenq,o, as shown in Figure 6(c).Figure 6
Evaluation ofdistq,o, where q∈αβ¯ and o∈Okα∪Okβ∪O(αβ¯).
(a)
Ifo∈Okα, then distq,o=lenq,α+distα,o
(b)
Ifo∈Okβ, then distq,o=lenq,β+distβ,o
(c)
Ifo∈O(αβ¯), then distq,o=lenq,oTable2 summarizes the evaluation of distq,o for q∈αβ¯ and o∈Okα∪Okβ∪O(αβ¯), where MIN returns the minimum of the values in the input array. Because a qualifying object o belongs to a combination of Okα, Okβ, or O(αβ¯), a total of seven possible cases are considered. Note that distα,o, distβ,o, lenα,o, and lenβ,o are given constants and distq,o is the length of the shortest path among multiple paths from q and o.Table 2
Computation ofdist⁡q,o, where q∈αβ¯ and o∈Okα∪Okβ∪O(αβ¯).
Condition
dist
⁡
q
,
o
o
∈
O
k
α
-
(
O
k
β
∪
O
(
α
β
¯
)
)
dist
⁡
q
,
o
=
len
q
,
α
+
dist
⁡
α
,
o
o
∈
O
k
β
-
(
O
k
α
∪
O
(
α
β
¯
)
)
dist
⁡
q
,
o
=
len
q
,
β
+
dist
⁡
β
,
o
o
∈
O
(
α
β
¯
)
-
(
O
k
α
∪
O
k
β
)
dist
⁡
q
,
o
=
len
q
,
o
o
∈
O
k
α
∩
O
k
β
-
O
(
α
β
¯
)
dist
⁡
q
,
o
=
min
⁡
len
q
,
α
+
dist
⁡
α
,
o
,
len
q
,
β
+
dist
⁡
β
,
o
o
∈
O
k
α
∩
O
(
α
β
¯
)
-
O
k
β
dist
⁡
q
,
o
=
min
⁡
len
q
,
α
+
dist
⁡
α
,
o
,
len
q
,
o
o
∈
O
k
β
∩
O
(
α
β
¯
)
-
O
k
α
dist
⁡
q
,
o
=
min
⁡
len
q
,
β
+
dist
⁡
β
,
o
,
len
q
,
o
o
∈
O
k
α
∩
O
k
β
∩
O
(
α
β
¯
)
dist
⁡
q
,
o
=
min
⁡
len
q
,
α
+
dist
⁡
α
,
o
,
len
q
,
β
+
dist
⁡
β
,
o
,
len
q
,
oFigure7 shows an example of the change in distq,o depending on the location of query point q∈n2n5n6n3-. For simplicity, we assume that the number of NNs requested at query point q is k=1. Then, as shown in Figure 7(a), Okn2, Okn3, and O(n2n5n6n3-) are evaluated as Okn2={o}, Okn3={o}, and On2n5n6n3-={o}, respectively. As shown in Figure 7(b), the distance from q to o, represented by the bold lines, is distq,o=lenq,o if q∈n2n5n6-; otherwise, it is distq,o=lenq,n3+3 because distn2,o=1, distn3,o=3, and lenn2,o=1 are given.Figure 7
Computation ofistq,o, where q∈n2n5n6n3¯ and o∈Okn2∩Okn3∩O(n2n5n6n3¯).Next, we explore the change in network distancedistq,o for object o∈Okα∪Okβ∪O(αβ→) when a query point q is located in a directed segment αβ→. Figure 8 shows the change in distq,o for three cases: o∈Okα, o∈Okβ, and o∈O(αβ→). Note that the dotted lines indicate that no paths exist from q to o for the corresponding intervals, which are denoted by distq,o=∞. For object o∈Okα, as shown in Figure 8(a), if q=α, then distq,o=distα,o; otherwise (i.e., q∈αβ→-{α}), distq,o=∞. Similarly, if o∈Okβ, then distq,o=lenq,β+distβ,o, as shown in Figure 8(b). Finally, for object o∈O(αβ→), as shown in Figure 8(c), if q∈αo→, then distq,o=lenq,o; otherwise (i.e., q∈βo←), distq,o=∞. Here, distq,o is the length of the shortest path from q and o where query point q∈αβ→ and is thus determined using Table 2 in the same way as q∈αβ-.Figure 8
Evaluation ofdistq,o, where q∈αβ→ and o∈Okα∪Okβ∪O(αβ→).Figure9 shows an example of the change in distq,o depending on the location of query point q∈n2n5n3→. For simplicity, we assume that the number of NNs requested at query point q is k=1. Then, as shown in Figure 9(a), Okn2, Okn3, and O(n2n5n3→) are evaluated as Okn2={o}, Okn3={o}, and On2n5n3→={o}, respectively. As shown in Figure 9(b), the distance from q to o, represented by the bold lines, is distq,o=lenq,o if q∈n2o→; otherwise, it is distq,o=lenq,n3+3 because distn2,o=1, distn3,o=3, and lenn2,o=1 are given.Figure 9
Computation ofdistq,o, where q∈n2n5n3→ and o∈Okn2∩Okn3∩O(n2n5n3→).


### 4.3. Partitioning Example Query Region into Safe Segments

We now discuss the construction of safe segments for query regionQ in Figure 3(a). Recall that the number of requested NNs is k=2 and the query region includes three segments; that is, Q={n1n3←,n2n3¯,n3n4←}. Table 3 summarizes the computation of the safe segments in query region Q. Clearly, thekNN set at a node n3 is evaluated only once, and it is reused multiple times.Table 3
Computation of safe segments for the example query region.
α
β
¯
α
β
O
k
α
O
k
β
O
(
α
β
¯
)
Ω
(
α
β
¯
)
n
1
n
3
←
n
1
n
3
{
o
1
,
o
2
}
{
o
3
,
o
4
}
{
o
3
}
n
1
o
3
←
,
o
1
,
o
2
,
n
3
o
3
→
,
o
2
,
o
3
,
n
3
,
o
3
,
o
4
n
2
n
3
¯
n
2
n
3
{
o
4
,
o
5
}
{
o
3
,
o
4
}
{
o
4
}
n
2
s
¯
,
o
4
,
o
5
,
n
3
s
¯
,
o
3
,
o
4
n
3
n
4
←
n
3
n
4
{
o
3
,
o
4
}
{
o
3
,
o
4
}
∅
n
3
n
4
←
,
o
3
,
o
4As shown in Algorithm1, MORAN determines the safe segments for each segment in query region Q. Therefore, we show the successive determination of the safe segments in n1n3←, n2n3¯, and n3n4←. It is clear that adjacent safe segments with the same query result can be merged. Recall that we can draw dist(q,o) by using a query point q∈αβ¯ and an object o∈Okα∪Okβ∪O(αβ¯).Figure10 depicts dist(q,o) using a query point q∈n1n3← and each object o∈Okn1∪Okn3∪O(n1n3←). Here, the union of Okn1, Okn3, and On1n3← becomes Okn1∪Okn3∪O(n1n3←)={o1,o2,o3,o4}, because Okn1={o1,o2}, Okn3={o3,o4}, and On1n3←={o3} are given. Figures 10(a), 10(b), 10(c), and 10(d) illustrate dist(q,o1), dist(q,o2), dist(q,o3), and dist(q,o4), respectively. Recall that o1∈Okn1, o2∈Okn1, o3∈Okn3∪O(n1n3←), and o4∈Okn3 hold.Figure 10
Plot ofistq,o, where q∈n1n3← and o∈{o1,o2,o3,o4}.To partition a segmentαβ- into safe segments, it is essential to identify the kth NN okth at a query point q∈αβ- among the qualifying objects o∈Okα∪Okβ∪O(αβ-). Algorithm 2 determines the skyline Okth that consists of (x,y) pairs such that x=len(α,q) and y=dist(q,okth) hold for each query point q∈αβ-. The variablecount keeps the number of qualifying objects processed thus far, which is initialized to 0 (line (1)). Ifcount is less than k, then the skyline for okth is determined by Okth={(x,y)∣x=lenα,q,y=maxdistq,θkth,distq,o for q∈αβ-}, where θkth keeps the kth NN determined thus far (lines (4)-(5)). Otherwise (i.e., count≥k), the skyline for okth is determined by Okth={x,y∣x=lenα,q,y=mindistq,θkth,distq,o for q∈αβ-} (lines (6)-(7)). Naturally,count increases by 1 whenever an objecto is processed (line (8)).Algorithm 2:Determine_skyline_for_kth_NN (k, Okα∪Okβ∪O(αβ-)).
Input: k: the number of requested NNs, Okα∪Okβ∪O(αβ-): the set of qualifying objects for a segment αβ-
Output: Okth: the set of distances from q to its kth NN okth (i.e., Okth={x,y∣x=lenα,q,y=dist⁡q,okth})
(1)count←0                   // count keeps the number of objects processed thus far
(2)Okth={x,y∣x=lenα,q,y=0forq∈αβ-}    // y=dist⁡q,okth is initialized to 0 for q∈αβ-
(3)for each object o∈Okα∪Okβ∪O(αβ-)  do                // qualifying objects are handled sequentially
(4)if  count<k  then                        // if the number of objects processed thus far is less than k
(5)Okth={(x,y)∣x=lenα,q,y=max⁡dist⁡q,θkth,dist⁡q,oforq∈αβ-}   // θkth is the kth NN thus far
(6)else
(7)Okth={x,y∣x=lenα,q,y=min⁡dist⁡q,θkth,dist⁡q,oforq∈αβ-}
(8)count←count+1                       // count increases by 1 whenever an object o is processed
(9)return  OkthFigure11 illustrates the partitioning of a segment n1n3← into three safe segments using distq,o for each object o∈Okn1∪Okn3∪O(n1n3←). Figure 11(a) shows the plot of distq,o for each object o∈{o1,o2,o3,o4}. Note that, to simplify the presentation, the interval in which distq,o=∞ holds is not represented. When a query point q moves in a segment n1n3←, its kth NN okth is determined using Algorithm 2 and is represented by the bold lines in Figure 11(b). Specifically, for q∈n1o3←, the kth NN okth is o1 and thus thekNN set is {o1,o2}. Similarly, for q∈n3o3→, the kth NN okth is o2 and thus thekNN set is {o2,o3}. Finally, for q=n3, the kth NN okth is o3 and thus thekNN set is {o3,o4}. Consequently, a segment n1n3← is divided into three safe segments, represented by Ω(n1n3←)={n1o3←,o1,o2,n3o3→,o2,o3,n3,o3,o4}.Figure 11
Partitioning of a segmentn1n3← into three safe segments.
(a)
Plot ofdistq,o for o∈{o1,o2,o3,o4}
(b)
Ω
(
n
1
n
3
←
)
=
{
n
1
o
3
←
,
o
1
,
o
2, n3o3→,o2,o3, n3,o3,o4}Figures12(a), 12(b), and 12(c) illustrate dist(q,o3), dist(q,o4), and dist(q,o5), respectively, where q refers to a query point in a segment n2n3¯ and o3, o4, and o5 refer to qualifying objects for the segment n2n3¯. Note that o3∈Okn3, o4∈Okn2∪Okn3∪O(n2n3¯), and o5∈Okn2 hold.Figure 12
Plot ofdistq,o, where q∈n2n3¯ and o∈{o3,o4,o5}.
(a)
d
i
s
t
q
,
o
3
=
l
e
n
q
,
n
3
+
4
(b)
d
i
s
t
q
,
o
4
=
l
e
n
q
,
o
4
(c)
d
i
s
t
q
,
o
5
=
l
e
n
q
,
n
2
+
4Figure13 illustrates the partitioning of a segment n2n3¯ into two safe segments using distq,o for each object o∈Okn2∪Okn3∪O(n2n3¯). Figure 13(a) shows the plot of distq,o for each object o∈{o3,o4,o5}. When a query point q moves in a segment n2n3¯, its kth NN okth is represented by the bold lines in Figure 13(b), where a point s marked by a five-pointed star indicates the middle of the segment n2n3¯. Specifically, for q∈n2s¯, the kth NN okth is o5 and thus thekNN set is {o4,o5}. Similarly, for q∈n3s¯, the kth NN okth is o3 and thus thekNN set is {o3,o4}. Consequently, a segment n2n3¯ is divided into two safe segments, which are represented as Ω(n2n3¯)={n2s¯,o4,o5,n3s¯,o3,o4}. Finally, a segment n3n4← becomes a safe segment; that is, Ω(n3n4←)={n3n4←,o3,o4}. This is because Okn3 equals Okn4 and O(n3n4←) is a subset of Okn3; that is, Okn3=Okn4 and O(n3n4←)⊂Okn3.Figure 13
Partitioning of a segmentn2n3¯ into two safe segments.
(a)
Plot ofdistq,o for o∈{o3,o4,o5}
(b)
Ω
(
n
2
n
3
¯
)
=
{
n
2
s
¯
,
o
4
,
o
5, n3s¯,o3,o4}


## 4.1. Overview

As stated before, we focus on query processing at the client side while processing MkRNN queries in a directed and dynamic spatial network. If either of the two events in Figure 5 occurs, the server should evaluate thekRNN query and provide query object q with an updatedkRNN query result. The first event is q leaving the current query region. For example, as shown in Figure 5(a), if q moves to q′ outside of Q, akRNN query should be reevaluated with the updated query region. The second event is invalidation of the currentkRNN query result provided to query object q because of an updated traffic condition. For example, as shown in Figure 5(b), if query region Q overlaps traffic congestion area T, thekRNN query should be reevaluated to reflect the updated traffic condition. When the query object receives an updatedkRNN query result from the server, it should reevaluate safe segments inside the query region. Using safe segments reduces the computation time and frequency because the query object does not have to evaluatekNN queries while inside the safe segments.Figure 5
Two events that trigger the evaluation of MkRNN queries.
(a)
q leaves query region Q
(b)
Congestion areaT nullifies kRNN query result for QAlgorithm1 outlines the process of determining the safe segments in a query region Q in a directed spatial network. The algorithm starts by initializing Ω to an empty set, which stores the safe segments found thus far. Each segment αβ- in query region Q is explored sequentially to find the safe segments in segment αβ-. For this purpose, MORAN evaluates twokNN queries issued at boundary points α and β of segment αβ-. The query results are stored to Okα and Okβ, respectively. The objects in αβ- are explored and stored to Oαβ¯. The function find_safe_segments is called with Okα, Okβ, and Oαβ¯ in order to find safe segments in segment αβ-. The found safe segments are added to the result set Ω. When all the segments in Q have been examined, a set Ω of safe segments in query region Q is returned to the query issuer. It should be noted that if updates in the weight of edges frequently occur in a spatial network, it is better to determine the safe segments in the current segment including the query point rather than all the safe segments in the query region. We employ a shared execution approach [5], which is widely used to avoid multiple visits to the same nodes and edges. This clearly reduces the query processing time while determining safe segments in a query region.Algorithm 1:MORAN (Q,k).
Input: Q: query region, k: the number of requested NNs
Output: Ω: the set of safe segments in Q
(1)Ω←∅                        // Ω is initialized to an empty set
(2)for each segment αβ-∈Q  do
(3)Okα← evaluate_kNN_query_at_point (α, k)      // a kNN query is evaluated at a boundary point α
(4)Okβ← evaluate_kNN_query_at_point (β, k)      // a kNN query is evaluated at a boundary point β
(5)Oαβ¯← evaluate_range_query (αβ¯)          // a range query is evaluated for a segment αβ¯
(6)Ωαβ¯← find_safe_segments (Okα, Okβ, O(αβ¯))    // the function is detailed in Section 4.2
(7)Ω←Ω∪Ωαβ¯
(8)return  Ω                      // the set of safe segments is provided to the query issuer


## 4.2. Partitioning Query Region into Safe Segments

We consider an undirected segmentαβ¯ followed by a directed segment αβ→. We present a method for finding safe segments in segment αβ¯ by using Okα, Okβ, and O(αβ¯). Here, Okα and Okβ refer to sets of kNNs at boundary points α and β, respectively, and O(αβ¯) refers to a set of objects inside segment αβ¯. An object o that belongs to the union of Okα, Okβ, and O(αβ¯), that is, o∈Okα∪Okβ∪O(αβ¯), is referred to as a qualifying object. Clearly, the set Okq of kNNs at a query point q∈αβ¯ is a subset of the union of Okα, Okβ, and O(αβ¯) [5, 13, 26]; that is, Okq⊆(Okα∪Okβ∪O(αβ¯)). If Okα equals Okβ and O(αβ¯) is a subset of Okα, segment αβ¯ becomes a safe segment. Otherwise, it has two or more safe segments.We first explore the change in a network distancedistq,o for a qualifying object o∈Okα∪Okβ∪O(αβ¯) when a query point q is located in an undirected segment αβ¯ [13, 14]. Figure 6 shows the change in distq,o for three cases: o∈Okα, o∈Okβ, and o∈O(αβ¯). In this figure, the y-axis represents distq,o and the x-axis represents lenα,q for 0≤lenα,q≤lenα,β. If o∈Okα, then distq,o=lenq,α+distα,o, as shown in Figure 6(a). Similarly, if o∈Okβ, then distq,o=lenq,β+distβ,o, as shown in Figure 6(b). Finally, if o∈O(αβ¯), then distq,o=lenq,o, as shown in Figure 6(c).Figure 6
Evaluation ofdistq,o, where q∈αβ¯ and o∈Okα∪Okβ∪O(αβ¯).
(a)
Ifo∈Okα, then distq,o=lenq,α+distα,o
(b)
Ifo∈Okβ, then distq,o=lenq,β+distβ,o
(c)
Ifo∈O(αβ¯), then distq,o=lenq,oTable2 summarizes the evaluation of distq,o for q∈αβ¯ and o∈Okα∪Okβ∪O(αβ¯), where MIN returns the minimum of the values in the input array. Because a qualifying object o belongs to a combination of Okα, Okβ, or O(αβ¯), a total of seven possible cases are considered. Note that distα,o, distβ,o, lenα,o, and lenβ,o are given constants and distq,o is the length of the shortest path among multiple paths from q and o.Table 2
Computation ofdist⁡q,o, where q∈αβ¯ and o∈Okα∪Okβ∪O(αβ¯).
Condition
dist
⁡
q
,
o
o
∈
O
k
α
-
(
O
k
β
∪
O
(
α
β
¯
)
)
dist
⁡
q
,
o
=
len
q
,
α
+
dist
⁡
α
,
o
o
∈
O
k
β
-
(
O
k
α
∪
O
(
α
β
¯
)
)
dist
⁡
q
,
o
=
len
q
,
β
+
dist
⁡
β
,
o
o
∈
O
(
α
β
¯
)
-
(
O
k
α
∪
O
k
β
)
dist
⁡
q
,
o
=
len
q
,
o
o
∈
O
k
α
∩
O
k
β
-
O
(
α
β
¯
)
dist
⁡
q
,
o
=
min
⁡
len
q
,
α
+
dist
⁡
α
,
o
,
len
q
,
β
+
dist
⁡
β
,
o
o
∈
O
k
α
∩
O
(
α
β
¯
)
-
O
k
β
dist
⁡
q
,
o
=
min
⁡
len
q
,
α
+
dist
⁡
α
,
o
,
len
q
,
o
o
∈
O
k
β
∩
O
(
α
β
¯
)
-
O
k
α
dist
⁡
q
,
o
=
min
⁡
len
q
,
β
+
dist
⁡
β
,
o
,
len
q
,
o
o
∈
O
k
α
∩
O
k
β
∩
O
(
α
β
¯
)
dist
⁡
q
,
o
=
min
⁡
len
q
,
α
+
dist
⁡
α
,
o
,
len
q
,
β
+
dist
⁡
β
,
o
,
len
q
,
oFigure7 shows an example of the change in distq,o depending on the location of query point q∈n2n5n6n3-. For simplicity, we assume that the number of NNs requested at query point q is k=1. Then, as shown in Figure 7(a), Okn2, Okn3, and O(n2n5n6n3-) are evaluated as Okn2={o}, Okn3={o}, and On2n5n6n3-={o}, respectively. As shown in Figure 7(b), the distance from q to o, represented by the bold lines, is distq,o=lenq,o if q∈n2n5n6-; otherwise, it is distq,o=lenq,n3+3 because distn2,o=1, distn3,o=3, and lenn2,o=1 are given.Figure 7
Computation ofistq,o, where q∈n2n5n6n3¯ and o∈Okn2∩Okn3∩O(n2n5n6n3¯).Next, we explore the change in network distancedistq,o for object o∈Okα∪Okβ∪O(αβ→) when a query point q is located in a directed segment αβ→. Figure 8 shows the change in distq,o for three cases: o∈Okα, o∈Okβ, and o∈O(αβ→). Note that the dotted lines indicate that no paths exist from q to o for the corresponding intervals, which are denoted by distq,o=∞. For object o∈Okα, as shown in Figure 8(a), if q=α, then distq,o=distα,o; otherwise (i.e., q∈αβ→-{α}), distq,o=∞. Similarly, if o∈Okβ, then distq,o=lenq,β+distβ,o, as shown in Figure 8(b). Finally, for object o∈O(αβ→), as shown in Figure 8(c), if q∈αo→, then distq,o=lenq,o; otherwise (i.e., q∈βo←), distq,o=∞. Here, distq,o is the length of the shortest path from q and o where query point q∈αβ→ and is thus determined using Table 2 in the same way as q∈αβ-.Figure 8
Evaluation ofdistq,o, where q∈αβ→ and o∈Okα∪Okβ∪O(αβ→).Figure9 shows an example of the change in distq,o depending on the location of query point q∈n2n5n3→. For simplicity, we assume that the number of NNs requested at query point q is k=1. Then, as shown in Figure 9(a), Okn2, Okn3, and O(n2n5n3→) are evaluated as Okn2={o}, Okn3={o}, and On2n5n3→={o}, respectively. As shown in Figure 9(b), the distance from q to o, represented by the bold lines, is distq,o=lenq,o if q∈n2o→; otherwise, it is distq,o=lenq,n3+3 because distn2,o=1, distn3,o=3, and lenn2,o=1 are given.Figure 9
Computation ofdistq,o, where q∈n2n5n3→ and o∈Okn2∩Okn3∩O(n2n5n3→).


## 4.3. Partitioning Example Query Region into Safe Segments

We now discuss the construction of safe segments for query regionQ in Figure 3(a). Recall that the number of requested NNs is k=2 and the query region includes three segments; that is, Q={n1n3←,n2n3¯,n3n4←}. Table 3 summarizes the computation of the safe segments in query region Q. Clearly, thekNN set at a node n3 is evaluated only once, and it is reused multiple times.Table 3
Computation of safe segments for the example query region.
α
β
¯
α
β
O
k
α
O
k
β
O
(
α
β
¯
)
Ω
(
α
β
¯
)
n
1
n
3
←
n
1
n
3
{
o
1
,
o
2
}
{
o
3
,
o
4
}
{
o
3
}
n
1
o
3
←
,
o
1
,
o
2
,
n
3
o
3
→
,
o
2
,
o
3
,
n
3
,
o
3
,
o
4
n
2
n
3
¯
n
2
n
3
{
o
4
,
o
5
}
{
o
3
,
o
4
}
{
o
4
}
n
2
s
¯
,
o
4
,
o
5
,
n
3
s
¯
,
o
3
,
o
4
n
3
n
4
←
n
3
n
4
{
o
3
,
o
4
}
{
o
3
,
o
4
}
∅
n
3
n
4
←
,
o
3
,
o
4As shown in Algorithm1, MORAN determines the safe segments for each segment in query region Q. Therefore, we show the successive determination of the safe segments in n1n3←, n2n3¯, and n3n4←. It is clear that adjacent safe segments with the same query result can be merged. Recall that we can draw dist(q,o) by using a query point q∈αβ¯ and an object o∈Okα∪Okβ∪O(αβ¯).Figure10 depicts dist(q,o) using a query point q∈n1n3← and each object o∈Okn1∪Okn3∪O(n1n3←). Here, the union of Okn1, Okn3, and On1n3← becomes Okn1∪Okn3∪O(n1n3←)={o1,o2,o3,o4}, because Okn1={o1,o2}, Okn3={o3,o4}, and On1n3←={o3} are given. Figures 10(a), 10(b), 10(c), and 10(d) illustrate dist(q,o1), dist(q,o2), dist(q,o3), and dist(q,o4), respectively. Recall that o1∈Okn1, o2∈Okn1, o3∈Okn3∪O(n1n3←), and o4∈Okn3 hold.Figure 10
Plot ofistq,o, where q∈n1n3← and o∈{o1,o2,o3,o4}.To partition a segmentαβ- into safe segments, it is essential to identify the kth NN okth at a query point q∈αβ- among the qualifying objects o∈Okα∪Okβ∪O(αβ-). Algorithm 2 determines the skyline Okth that consists of (x,y) pairs such that x=len(α,q) and y=dist(q,okth) hold for each query point q∈αβ-. The variablecount keeps the number of qualifying objects processed thus far, which is initialized to 0 (line (1)). Ifcount is less than k, then the skyline for okth is determined by Okth={(x,y)∣x=lenα,q,y=maxdistq,θkth,distq,o for q∈αβ-}, where θkth keeps the kth NN determined thus far (lines (4)-(5)). Otherwise (i.e., count≥k), the skyline for okth is determined by Okth={x,y∣x=lenα,q,y=mindistq,θkth,distq,o for q∈αβ-} (lines (6)-(7)). Naturally,count increases by 1 whenever an objecto is processed (line (8)).Algorithm 2:Determine_skyline_for_kth_NN (k, Okα∪Okβ∪O(αβ-)).
Input: k: the number of requested NNs, Okα∪Okβ∪O(αβ-): the set of qualifying objects for a segment αβ-
Output: Okth: the set of distances from q to its kth NN okth (i.e., Okth={x,y∣x=lenα,q,y=dist⁡q,okth})
(1)count←0                   // count keeps the number of objects processed thus far
(2)Okth={x,y∣x=lenα,q,y=0forq∈αβ-}    // y=dist⁡q,okth is initialized to 0 for q∈αβ-
(3)for each object o∈Okα∪Okβ∪O(αβ-)  do                // qualifying objects are handled sequentially
(4)if  count<k  then                        // if the number of objects processed thus far is less than k
(5)Okth={(x,y)∣x=lenα,q,y=max⁡dist⁡q,θkth,dist⁡q,oforq∈αβ-}   // θkth is the kth NN thus far
(6)else
(7)Okth={x,y∣x=lenα,q,y=min⁡dist⁡q,θkth,dist⁡q,oforq∈αβ-}
(8)count←count+1                       // count increases by 1 whenever an object o is processed
(9)return  OkthFigure11 illustrates the partitioning of a segment n1n3← into three safe segments using distq,o for each object o∈Okn1∪Okn3∪O(n1n3←). Figure 11(a) shows the plot of distq,o for each object o∈{o1,o2,o3,o4}. Note that, to simplify the presentation, the interval in which distq,o=∞ holds is not represented. When a query point q moves in a segment n1n3←, its kth NN okth is determined using Algorithm 2 and is represented by the bold lines in Figure 11(b). Specifically, for q∈n1o3←, the kth NN okth is o1 and thus thekNN set is {o1,o2}. Similarly, for q∈n3o3→, the kth NN okth is o2 and thus thekNN set is {o2,o3}. Finally, for q=n3, the kth NN okth is o3 and thus thekNN set is {o3,o4}. Consequently, a segment n1n3← is divided into three safe segments, represented by Ω(n1n3←)={n1o3←,o1,o2,n3o3→,o2,o3,n3,o3,o4}.Figure 11
Partitioning of a segmentn1n3← into three safe segments.
(a)
Plot ofdistq,o for o∈{o1,o2,o3,o4}
(b)
Ω
(
n
1
n
3
←
)
=
{
n
1
o
3
←
,
o
1
,
o
2, n3o3→,o2,o3, n3,o3,o4}Figures12(a), 12(b), and 12(c) illustrate dist(q,o3), dist(q,o4), and dist(q,o5), respectively, where q refers to a query point in a segment n2n3¯ and o3, o4, and o5 refer to qualifying objects for the segment n2n3¯. Note that o3∈Okn3, o4∈Okn2∪Okn3∪O(n2n3¯), and o5∈Okn2 hold.Figure 12
Plot ofdistq,o, where q∈n2n3¯ and o∈{o3,o4,o5}.
(a)
d
i
s
t
q
,
o
3
=
l
e
n
q
,
n
3
+
4
(b)
d
i
s
t
q
,
o
4
=
l
e
n
q
,
o
4
(c)
d
i
s
t
q
,
o
5
=
l
e
n
q
,
n
2
+
4Figure13 illustrates the partitioning of a segment n2n3¯ into two safe segments using distq,o for each object o∈Okn2∪Okn3∪O(n2n3¯). Figure 13(a) shows the plot of distq,o for each object o∈{o3,o4,o5}. When a query point q moves in a segment n2n3¯, its kth NN okth is represented by the bold lines in Figure 13(b), where a point s marked by a five-pointed star indicates the middle of the segment n2n3¯. Specifically, for q∈n2s¯, the kth NN okth is o5 and thus thekNN set is {o4,o5}. Similarly, for q∈n3s¯, the kth NN okth is o3 and thus thekNN set is {o3,o4}. Consequently, a segment n2n3¯ is divided into two safe segments, which are represented as Ω(n2n3¯)={n2s¯,o4,o5,n3s¯,o3,o4}. Finally, a segment n3n4← becomes a safe segment; that is, Ω(n3n4←)={n3n4←,o3,o4}. This is because Okn3 equals Okn4 and O(n3n4←) is a subset of Okn3; that is, Okn3=Okn4 and O(n3n4←)⊂Okn3.Figure 13
Partitioning of a segmentn2n3¯ into two safe segments.
(a)
Plot ofdistq,o for o∈{o3,o4,o5}
(b)
Ω
(
n
2
n
3
¯
)
=
{
n
2
s
¯
,
o
4
,
o
5, n3s¯,o3,o4}


## 5. Monitoring Safe Segments in Dynamic Spatial Networks

Figure14 illustrates an example of changing the weight of an edge n1o1→ in a spatial network where it is assumed that k=2 is given. For convenience, we consider the query region Q that consists of an edge n1n3←; that is, Q={n1n3←}. As shown in Figure 14(b), when the weight of an edge n1o1→ has been updated from 3 to 5 at time tj, this update may invalidate the safe segments in the query region Q. Therefore, it is necessary to monitor the validity of safe segments in a query region when the change occurs. To this end, we introduce an influential region to monitor the validity of safe segments. The influential region Ψq for a query point q is defined as a set of points p such that distq,p≤dist(q,okth) holds. If the weight of an edge changes inside influential region Ψq, thekNN query at query point q should be reevaluated to reflect the change in the weight. However, if the weight of an edge changes outside influential region Ψq, the change can be safely ignored. Suppose that a query region Q is represented by a set Qs of l connected segments and a set Qb of m boundary points; that is, Qs={s1,s2,…,sl} and Qb={b1,b2,…,bm}. Then, the influential region ΨQ for query region Q becomes the union of the influential region for each query point q∈Q; that is, ΨQ=⋃q∈QΨq. This can be represented simply as ΨQ=Q∪(⋃i=1mΨbi), where Ψbi refers to the influential region at each boundary point bi of the query region Q. Specifically, Ψbi is the set of points p such that distbi,p≤dist(bi,okthbi) holds. Here, okthbi is the farthest answer object from boundary point bi; that is, for each answer object o∈Okbi, distbi,o≤dist(bi,okthbi) holds.Figure 14
Changing the weight of an edge in a dynamic spatial network, whereti<tj.
(a)
Query regionQ={n1n3←} at time ti
(b)
Updating the weight ofn1o1→ at time tjFigure15(a) illustrates the influential region for the query region Q at time ti, where the dotted line and square brackets mark the influential region and its boundary points, respectively. A set of the two NNs at boundary point n1 is Okn1={o1,o2} and the kth NN of n1 is okthn1=o1. Thus, the distance from n1 to its kth NN o1 is distn1,o1=3 and thus the influential region Ψn1 for a boundary point n1 becomes Ψn1={n1o1→,n1o2n4→}. Similarly, the influential region Ψn3 for a boundary point n3 evaluates Ψn3={n3o3→,n3o4ψ1¯,n3n5¯,n5ψ2¯,n5ψ3¯}, because Okn3={o3,o4},  okthn3=o3, and distn3,o3=4 are given. Consequently, the influential region ΨQ for query region Q becomes ΨQ=n1n3←∪Ψn1∪Ψn3={n1n3←,n1o2n4→,n3o3→,n3o4ψ1¯,n3n5¯,n5ψ2¯,n5ψ3¯}. As shown in Figure 15(b), updating the weight of edge n1o1→ from 3 to 5 may affect the safe segments for the query region Q. This is because updated edge n1o1→ overlaps the influential region ΨQ for query region Q. In this case, the server reevaluates the qualifying objects for query region Q and provides updated qualifying objects so that the user can update safe segments. If the safe segments are updated, the influential region should be also updated accordingly. Thus, the influential region for query region Q is updated at time tj, as shown in Figure 15(b). Finally, updates to the weights of the edges, for example, n2o1←, n2o5-, n3n4←, and n4n6-, that do not overlap the influential region can be safely ignored.Figure 15
Updating the influence region forQ.
(a)
Influence regionΨQ at time ti
(b)
Updated influence regionΨQ at time tjAlgorithm3 monitors the validity of safe segments in a query region when the weight of edges changes over time. Assume that the weight of edge ninj¯ is updated. Subsequently, the server checks if edge ninj¯ overlaps the influential region ΨQ for query region Q. If the edge with the updated weight does not overlap the influential region, the update is safely ignored (lines (1)-(2)). Otherwise (i.e., ΨQ∩ninj¯≠∅), the server requests that query object q updates the query region (line (4)). Consequently, q submits akRNN query for updated query region Qupd. The server then evaluates thekRNN query for Qupd and returns thekRNN query result ΣQupd to q (line (5)). The query object then determines safe segments using ΣQupd (line (6)). Finally, the server updates the influential region accordingly (line (7)).Algorithm 3:Monitor_safe_segments (ΨQ, ninj¯).
Input: ΨQ: influential region, ninj¯: updated edge
Output: none
(1)if  ΨQ∩ninj¯=∅  then                               // an update to edge ninj¯ that does not overlap ΨQ is ignored.
(2)  ignore the update in the weight of edgeninj¯
(3)else                     // this means that ΨQ∩ninj¯≠∅
(4)Qupd← Update_query_region ()      // server requests that q update the query region
(5)ΣQupd← Evaluate_kRNN_query (Qupd, k)       // server evaluates kRNN query for an updated query region
(6)ΩQupd← Update_safe_segments (ΣQupd, k)        // q determines safe segments inside the updated query region
(7)ΨQupd← Update_influential_region (Qupd, k)      // server updates influential region accordingly.


## 6. Performance Evaluation

We describe our experimental settings in Section6.1 and present the results of our experiments using real-life road maps in Section 6.2.


### 6.1. Experimental Settings

In the experiments, we use two real-life road maps, obtained from [27], to explore the impact of the edge sequence length on the performance of MORAN. The first road map, comprising 175,813 nodes and 179,179 edges, includes major roads in North America (NA) and corresponds approximately to a data universe of 2.5×107 km2. The second road map, comprising 18,263 nodes and 23,874 edges, includes major roads in San Joaquin County (SJ), California, and corresponds approximately to a data universe of 3.6×103 km2. For the first road map NA, the number of edge sequences and their average length are 12,416 and 29,052 m, respectively. For the second road map SJ, the number of edge sequences and their average length are 20,040 and 248 m, respectively. Table 4 summarizes the parameters used in the experiments. In each experiment, we vary a single parameter in the range shown and set the other parameters to the default values marked in bold. We simulate moving query points using a network-based moving objects generator [28]. The number of query objects is set to 1,000. The size of a query region is determined by the number of edge sequences that constitute the query region. The directed and updated edge sequences are selected randomly, irrespective of the locations of the data and query objects. The length of an updated edge sequence is selected randomly to be between 0.1 and 10 times the original length. For example, if Rupd is set to 0.5% and the number of edge sequences is 12,416, then 62 edge sequences are selected randomly every timestamp and their weights are updated.Table 4
Experimental parameter settings.
Parameter
Range
Number of requested NNs (k)
2, 4,8, 16, 32
Ratio of directed edge sequences to total edge sequences (Rdir)
0, 5,10, 20, 50 (%)
Ratio of updated edge sequences to total edge sequences per timestamp (Rupd)
0, 0.3,0.5, 0.7, 1 (%)
Size of query region (Qsz)
1, 2,4, 8, 16
Number of data points (Ndata)
1, 3,5, 7, 10 (×104) for NA
1, 3,5, 7, 10 (×103) for SJ
Speed of query points (Vqry)
20, 40, 60, 80,100 (km/h) for NA
20, 40,60, 80, 100 (km/h) for SJ
Distribution of data points (Ddata)
Uniform
Distribution of query points (Dqry)
Uniform
Number of query points (Nqry)
1000
Road map
NA, SJAs a benchmark against MORAN, we usekRNN-E [5] without information of the precomputed shortest distances, based on a shared execution paradigm to remove the redundant search overhead. We choosekRNN-E instead ofkRNN-F [5] with information of all the precomputed shortest distances, althoughkRNN-F typically outperformskRNN-E. The reason for this is that the precomputed distances among nodes are frequently invalidated by the updates to the weights of the edges, which makes it difficult to maintain the precomputed distances. To makekRNN-F applicable to our problem scenarios, we can consider applying hierarchical and goal-directed speed-up techniques [29] for Dijkstra’s algorithm. This approach can help to reduce the computation time only at the server side and thus would not affect our experimental results. Recall that the query processing at the server is orthogonal to this study and that MORAN focuses on reducing the computation frequency and time taken at the client side to evaluate MkRNN queries. Our experimental results provide the average values per timestamp while 1,000 query points run for 600 timestamps. Note that, for road map NA, the speed of the query points is 100 km/h by default, whereas, for road map SJ, the speed is 60 km/h by default. All algorithms are implemented in C++ and executed on a desktop PC with a 3.4 GHz processor and 16 GB of memory.


### 6.2. Experimental Results

Figure16 shows a comparison of the query processing times at the client side of MORAN andkRNN-E for evaluating MkRNN queries in road map NA, where each chart illustrates the effect of varying a single parameter in Table 4. The values in the parentheses indicate the computation frequency per timestamp. Clearly, the computation frequency ofkRNN-E equals the number of query points and thus is omitted. It should be noted that the server evaluates the MkRNN queries whenever the query points exit their query regions and thus the query processing times at the server side are the same for MORAN andkRNN-E. Therefore, we focus on comparing the query processing times at the client side.Figure 16
Comparison of CPU time at the client side for road map NA.
(a)
Effect ofk
(b)
Effect ofRdir
(c)
Effect ofRupd
(d)
Effect ofQsz
(e)
Effect ofNdata
(f)
Effect ofVqryFigure16(a) shows the query processing time as a function of the number of requested NNs, that is,k. Clearly, the query processing time at the client side increases withk. However, the query processing time of MORAN is significantly shorter than that ofkRNN-E for all cases. The reason for this is thatkRNN-E evaluateskNN queries whenever query points move. Conversely, MORAN determines safe segments when query points enter new edge sequences or when the query results provided by the server become invalidated because of updated traffic conditions.Figure16(b) shows the query processing time as a function of the ratio of directed edge sequences to the total number of edge sequences, that is, Rdir. Clearly, Rdir = 0% refers to an undirected spatial network. The query processing times at the client side of both methods are insensitive to the value of Rdir. The query processing time of MORAN is shorter than that ofkRNN-E, regardless of the value of Rdir.Figure16(c) shows the query processing time as a function of the ratio of updated edge sequences to the total number of edge sequences per timestamp, that is, Rupd. Here, Rupd = 0% refers to a static spatial network. The length of an updated edge sequence is selected randomly from between 0.1 and 10 times the original length. Clearly, the query processing time ofkRNN-E is almost constant regardless of the value of Rupd because query points inkRNN-E issuekNN queries at each timestamp. However, the query processing time of MORAN increases linearly with Rupd because the probability that the influential region of a query region overlaps any updated edge sequence increases with Rupd. Therefore, a larger value of Rupd leads to a longer query processing time.Figure16(d) shows the query processing time as a function of the size of the query region, that is, Qsz. Clearly, the query processing time increases with Qsz. However, the query processing time of MORAN is clearly shorter than that ofkRNN-E, regardless of the value of Qsz.Figure16(e) shows the query processing time as a function of the number of data points, that is, Ndata. In general, as Ndata increases, the search space decreases, and thus, the query processing time at the server side decreases accordingly. However, the query processing time at the client side increases with Ndata. This is because the number of qualifying data points handled at the client side increases with Ndata. Although the query processing time of MORAN increases more rapidly with Ndata than that ofkRNN-E, the query processing time of MORAN is still shorter than that ofkRNN-E for 10k≤Ndata≤70k. However, for Ndata = 100 k, the query processing time of MORAN is 1.29 times longer than that ofkRNN-E.Figure16(f) shows the query processing time as a function of the speed of the query points, that is, Vqry. The query processing time of MORAN is more sensitive to Vqry than that ofkRNN-E. However, the query processing time of MORAN is clearly shorter than that ofkRNN-E for all cases.Figure17 shows a comparison of the query processing times at the client side of MORAN andkRNN-E for evaluating MkRNN queries in road map SJ. As when road map NA is used, when road map SJ is used, the query processing time of MORAN is clearly shorter than that ofkRNN-E. As shown in Figure 17(a), the query processing time increases withk for the same reason as discussed earlier in the case of Figure 16(a). As shown in Figure 17(b), the query processing times are not sensitive to the value of Rdir. As shown in Figure 17(c), the query processing time ofkRNN-E remains stable regardless of the value of Rupd. Conversely, the query processing time of MORAN increases with Rupd, because a larger value of Rupd affects the influential regions of more query points. As shown in Figure 17(d), the query processing time increases with Qsz, because the number of qualifying data points handled at the client side also increases with Qsz. As shown in Figure 17(e), as Ndata increases, the query processing times decrease. This is closely related to the size of the influential regions. Specifically, as Ndata increases, the influential region decreases and thus updating weights of edge sequences affects the influential regions of more query points. As shown in Figure 17(f), the query processing time of MORAN increases with Vqry for the same reason as discussed earlier in the case of Figure 16(f), whereas the query processing time ofkRNN-E remains stable, regardless of the value of Vqry.Figure 17
Comparison of CPU time at the client side for road map SJ.
(a)
Effect ofk
(b)
Effect ofRdir
(c)
Effect ofRupd
(d)
Effect ofQsz
(e)
Effect ofNdata
(f)
Effect ofVqry


## 6.1. Experimental Settings

In the experiments, we use two real-life road maps, obtained from [27], to explore the impact of the edge sequence length on the performance of MORAN. The first road map, comprising 175,813 nodes and 179,179 edges, includes major roads in North America (NA) and corresponds approximately to a data universe of 2.5×107 km2. The second road map, comprising 18,263 nodes and 23,874 edges, includes major roads in San Joaquin County (SJ), California, and corresponds approximately to a data universe of 3.6×103 km2. For the first road map NA, the number of edge sequences and their average length are 12,416 and 29,052 m, respectively. For the second road map SJ, the number of edge sequences and their average length are 20,040 and 248 m, respectively. Table 4 summarizes the parameters used in the experiments. In each experiment, we vary a single parameter in the range shown and set the other parameters to the default values marked in bold. We simulate moving query points using a network-based moving objects generator [28]. The number of query objects is set to 1,000. The size of a query region is determined by the number of edge sequences that constitute the query region. The directed and updated edge sequences are selected randomly, irrespective of the locations of the data and query objects. The length of an updated edge sequence is selected randomly to be between 0.1 and 10 times the original length. For example, if Rupd is set to 0.5% and the number of edge sequences is 12,416, then 62 edge sequences are selected randomly every timestamp and their weights are updated.Table 4
Experimental parameter settings.
Parameter
Range
Number of requested NNs (k)
2, 4,8, 16, 32
Ratio of directed edge sequences to total edge sequences (Rdir)
0, 5,10, 20, 50 (%)
Ratio of updated edge sequences to total edge sequences per timestamp (Rupd)
0, 0.3,0.5, 0.7, 1 (%)
Size of query region (Qsz)
1, 2,4, 8, 16
Number of data points (Ndata)
1, 3,5, 7, 10 (×104) for NA
1, 3,5, 7, 10 (×103) for SJ
Speed of query points (Vqry)
20, 40, 60, 80,100 (km/h) for NA
20, 40,60, 80, 100 (km/h) for SJ
Distribution of data points (Ddata)
Uniform
Distribution of query points (Dqry)
Uniform
Number of query points (Nqry)
1000
Road map
NA, SJAs a benchmark against MORAN, we usekRNN-E [5] without information of the precomputed shortest distances, based on a shared execution paradigm to remove the redundant search overhead. We choosekRNN-E instead ofkRNN-F [5] with information of all the precomputed shortest distances, althoughkRNN-F typically outperformskRNN-E. The reason for this is that the precomputed distances among nodes are frequently invalidated by the updates to the weights of the edges, which makes it difficult to maintain the precomputed distances. To makekRNN-F applicable to our problem scenarios, we can consider applying hierarchical and goal-directed speed-up techniques [29] for Dijkstra’s algorithm. This approach can help to reduce the computation time only at the server side and thus would not affect our experimental results. Recall that the query processing at the server is orthogonal to this study and that MORAN focuses on reducing the computation frequency and time taken at the client side to evaluate MkRNN queries. Our experimental results provide the average values per timestamp while 1,000 query points run for 600 timestamps. Note that, for road map NA, the speed of the query points is 100 km/h by default, whereas, for road map SJ, the speed is 60 km/h by default. All algorithms are implemented in C++ and executed on a desktop PC with a 3.4 GHz processor and 16 GB of memory.


## 6.2. Experimental Results

Figure16 shows a comparison of the query processing times at the client side of MORAN andkRNN-E for evaluating MkRNN queries in road map NA, where each chart illustrates the effect of varying a single parameter in Table 4. The values in the parentheses indicate the computation frequency per timestamp. Clearly, the computation frequency ofkRNN-E equals the number of query points and thus is omitted. It should be noted that the server evaluates the MkRNN queries whenever the query points exit their query regions and thus the query processing times at the server side are the same for MORAN andkRNN-E. Therefore, we focus on comparing the query processing times at the client side.Figure 16
Comparison of CPU time at the client side for road map NA.
(a)
Effect ofk
(b)
Effect ofRdir
(c)
Effect ofRupd
(d)
Effect ofQsz
(e)
Effect ofNdata
(f)
Effect ofVqryFigure16(a) shows the query processing time as a function of the number of requested NNs, that is,k. Clearly, the query processing time at the client side increases withk. However, the query processing time of MORAN is significantly shorter than that ofkRNN-E for all cases. The reason for this is thatkRNN-E evaluateskNN queries whenever query points move. Conversely, MORAN determines safe segments when query points enter new edge sequences or when the query results provided by the server become invalidated because of updated traffic conditions.Figure16(b) shows the query processing time as a function of the ratio of directed edge sequences to the total number of edge sequences, that is, Rdir. Clearly, Rdir = 0% refers to an undirected spatial network. The query processing times at the client side of both methods are insensitive to the value of Rdir. The query processing time of MORAN is shorter than that ofkRNN-E, regardless of the value of Rdir.Figure16(c) shows the query processing time as a function of the ratio of updated edge sequences to the total number of edge sequences per timestamp, that is, Rupd. Here, Rupd = 0% refers to a static spatial network. The length of an updated edge sequence is selected randomly from between 0.1 and 10 times the original length. Clearly, the query processing time ofkRNN-E is almost constant regardless of the value of Rupd because query points inkRNN-E issuekNN queries at each timestamp. However, the query processing time of MORAN increases linearly with Rupd because the probability that the influential region of a query region overlaps any updated edge sequence increases with Rupd. Therefore, a larger value of Rupd leads to a longer query processing time.Figure16(d) shows the query processing time as a function of the size of the query region, that is, Qsz. Clearly, the query processing time increases with Qsz. However, the query processing time of MORAN is clearly shorter than that ofkRNN-E, regardless of the value of Qsz.Figure16(e) shows the query processing time as a function of the number of data points, that is, Ndata. In general, as Ndata increases, the search space decreases, and thus, the query processing time at the server side decreases accordingly. However, the query processing time at the client side increases with Ndata. This is because the number of qualifying data points handled at the client side increases with Ndata. Although the query processing time of MORAN increases more rapidly with Ndata than that ofkRNN-E, the query processing time of MORAN is still shorter than that ofkRNN-E for 10k≤Ndata≤70k. However, for Ndata = 100 k, the query processing time of MORAN is 1.29 times longer than that ofkRNN-E.Figure16(f) shows the query processing time as a function of the speed of the query points, that is, Vqry. The query processing time of MORAN is more sensitive to Vqry than that ofkRNN-E. However, the query processing time of MORAN is clearly shorter than that ofkRNN-E for all cases.Figure17 shows a comparison of the query processing times at the client side of MORAN andkRNN-E for evaluating MkRNN queries in road map SJ. As when road map NA is used, when road map SJ is used, the query processing time of MORAN is clearly shorter than that ofkRNN-E. As shown in Figure 17(a), the query processing time increases withk for the same reason as discussed earlier in the case of Figure 16(a). As shown in Figure 17(b), the query processing times are not sensitive to the value of Rdir. As shown in Figure 17(c), the query processing time ofkRNN-E remains stable regardless of the value of Rupd. Conversely, the query processing time of MORAN increases with Rupd, because a larger value of Rupd affects the influential regions of more query points. As shown in Figure 17(d), the query processing time increases with Qsz, because the number of qualifying data points handled at the client side also increases with Qsz. As shown in Figure 17(e), as Ndata increases, the query processing times decrease. This is closely related to the size of the influential regions. Specifically, as Ndata increases, the influential region decreases and thus updating weights of edge sequences affects the influential regions of more query points. As shown in Figure 17(f), the query processing time of MORAN increases with Vqry for the same reason as discussed earlier in the case of Figure 16(f), whereas the query processing time ofkRNN-E remains stable, regardless of the value of Vqry.Figure 17
Comparison of CPU time at the client side for road map SJ.
(a)
Effect ofk
(b)
Effect ofRdir
(c)
Effect ofRupd
(d)
Effect ofQsz
(e)
Effect ofNdata
(f)
Effect ofVqry


## 7. Conclusion

We proposed a new algorithm, called MORAN, for processing MkRNN queries in directed and dynamic spatial networks. Existing studies focus on reducing redundant computation costs at the server side while processing snapshotkRNN queries in undirected and static spatial networks. However, MORAN clearly decreases the computation time and frequency at the client side by dividing the query region into safe segments while processing MkRNN queries in directed and dynamic spatial networks. The influential region for a query region is introduced to monitor the impact of the updated traffic conditions on the safe segments. The results of experiments using real-life road maps demonstrate that MORAN clearly outperformskRNN-E for various workloads in terms of the computation time and frequency. We plan to extend our approach to processing sophisticated queries such askNN joins and top-k spatial preference queries in directed and dynamic spatial networks.



---

*Source: 2406142-2016-01-17.xml*