# Efficient Shared Execution Processing ofk-Nearest Neighbor Joins in Road Networks

Authors: Hyung-Ju Cho
Journal: Mobile Information Systems
 (2018)

---

## Abstract

We investigate thek-nearest neighbor (kNN) join in road networks to determine the k-nearest neighbors (NNs) from a dataset S to every object in another dataset R. The kNN join is a primitive operation and is widely used in many data mining applications. However, it is an expensive operation because it combines the kNN query and the join operation, whereas most existing methods assume the use of the Euclidean distance metric. We alternatively consider the problem of processing kNN joins in road networks where the distance between two points is the length of the shortest path connecting them. We propose a shared execution-based approach called the group-nested loop (GNL) method that can efficiently evaluate kNN joins in road networks by exploiting grouping and shared execution. The GNL method can be easily implemented using existing kNN query algorithms. Extensive experiments using several real-life roadmaps confirm the superior performance and effectiveness of the proposed method in a wide range of problem settings.


---

## Body

## 1. Introduction

Road networks are often represented as weighted undirected graphs by placing a graph vertex at each road intersection or terminus and connecting vertices by edges that represent each segment of a road between two vertices [1–5]. The distance between two points in a road network is the length of the shortest path between them. In this study, we investigate the k-nearest neighbor (kNN) join in road networks, which combines each object in a dataset with the k objects in another dataset that are closest to it [6–8]. The kNN join is a primitive operation, which is widely used in many data mining and analytic applications, such as kNN classification, k-means clustering, sample assessment and sample post processing, missing value imputation, and k-distance diagrams [6–12].Figure1 presents an example of a kNN join, which we denote as R⋉kNNS, in a road network where R=r1,r2,r3,r4 and S=s1,s2,s3,s4,s5. For convenience, we assume that outer objects r1 through r4 denote hotels represented by rectangles and inner objects s1 through s5 denote tourist attractions represented by triangles. In this example, we can consider a kNN join query for tourists, which could be “find ordered pairs of two tourist attractions closest to each hotel.” Outer objects and inner objects typically correspond to points of interest in different categories such as hotels, tourist attractions, and hospitals.Figure 1
Example ofkNN join R⋉kNNS in a road network where R=r1,r2,r3,r4 and S=s1,s2,s3,s4,s5.ThekNN join is an expensive operation because it combines the kNN query and the join operation. A simple solution to the kNN join R⋉kNNS of datasets R and S requires scanning S once for each object in R while computing the distance between each pair of objects from R and S. This simple solution is not achievable for large datasets due to the complexity of OR×S. Therefore, many studies have been performed to improve the efficiency of the kNN join [6–12]. Most of these previous studies focused on processing the kNN join in the Euclidean space, mainly by designing elegant indexing techniques to avoid scanning the entire dataset repeatedly and to prune as many distance computations as possible. However, few studies have considered processing the kNN join in road networks.In this study, we address the problem of implementing thekNN join operator in road networks by proposing a shared execution-based approach called the group-nested loop (GNL) method, which comprises the following three steps. In the first step, the outer objects in a dataset R are grouped and then converted into a set of outer segments, where each outer segment connects adjacent outer objects. A method for grouping adjacent outer objects into an outer segment is presented in Section 4.1. In the second step, at most two kNN queries are evaluated for the outer segment. In the last step, the kNN join operation based on shared execution is performed for the outer objects in the outer segment. The GNL method is efficient for the following reasons. (1) It inherits the strength of shared execution processing by avoiding the evaluation of redundant kNN queries. (2) It can effectively group neighboring outer objects and consider them as a whole while pruning away unpromising network traversals. (3) It does not require any materialized structures, such as precomputing network Voronoi polygons [13, 14] or precomputing the network distance between every pair of vertices [15]. (4) It can be implemented easily using existing kNN query algorithms (e.g., INE [16], DisBrw [17], ROAD [2], and G-tree [5]), which is highly desirable in practice.We summarize the main contributions of this study as follows:(i)
We propose the GNL method for processingkNN joins efficiently in road networks. To the best of our knowledge, this is the first attempt to evaluate kNN joins efficiently in road networks.(ii)
The GNL method is intuitive and straightforward to implement, thereby allowing its simple integration with existingkNN query processing methods [1, 2, 5, 13, 16–19]. The GNL method employs an optimized number of kNN queries to evaluate kNN joins while exploiting grouping and shared execution.(iii)
We conduct extensive experiments with different setups to demonstrate the superior performance of the GNL method compared with conventional solutions.The remainder of this paper is organized as follows: In Section2, we review related research. In Section 3, we provide some background knowledge. In Section 4, we present the basic GNL method for processing kNN joins in road networks. In Section 5, we present the GNL method to avoid redundant kNN queries for processing kNN joins efficiently in road networks. In Section 6, we present empirical comparisons of the GNL method and conventional solutions with different setups. Finally, we discuss our conclusions in Section 7.


## 2. Related Work

### 2.1.kNN Search in Road Networks

The processing ofkNN queries in road networks has been studied extensively [2, 3, 5, 16, 17, 19, 20]. Papadias et al. [16] introduced incremental Euclidean restriction (IER) and incremental network expansion (INE). IER exploits the Euclidean restriction principle in road networks to achieve better performance. INE conducts network expansion from the query location in a similar manner to Dijkstra’s algorithm and examines the data objects in the sequence in which they are encountered. Shahabi et al. [3] developed an embedding technique for transforming a road network to a constraint-free high-dimensional Euclidean space to approximately retrieve the nearest objects using traditional Euclidean-based algorithms. Kolahdouzan and Shahabi [13, 14] utilized the first degree network Voronoi diagrams to partition the spatial network into network Voronoi polygons (NVP), with one for each data object. They indexed the NVPs by using a spatial access method to reduce the problem to a point location problem in the Euclidean space. This minimizes the online network distance computation by allowing precomputing of the NVPs. Huang et al. [18] addressed the same problem using the island approach where each vertex is associated with all the data points. These islands are considered centers with a given radius r covering the vertex. In their approach, they utilized restricted network expansion from the query point using the precomputed islands.Huang et al. [20] and Samet et al. [17] proposed two different algorithms to address the drawbacks of data object-dependent precomputation. Huang et al. [20] introduced S-GRID for partitioning the spatial network into disjoint subnetworks and precomputing the shortest path for each pair of connected border points. To find the k-nearest neighbors (NNs), network expansion is first performed within the subnetworks before outer expansion between the border points using the precomputed information. Samet et al. [17] proposed a distance browsing (DisBrw) method where they associate a label with each edge to represent all of the vertices with a shortest path starting with a particular edge. They use these labels to traverse the shortest path quadtrees that facilitate geometric pruning to find the network distance between objects.Lee et al. [2] proposed a new system framework called ROAD for processing location-dependent spatial queries. ROAD organizes a large road network as a hierarchy of interconnected regional subnetworks, each of which is augmented with shortcuts and object abstracts to accelerate network traversal and facilitate rapid object lookups, respectively. Inspired by the R-tree [21], Zhong et al. [5] proposed a height-balanced index called G-tree in road networks, which employs graph partitioning to efficiently compute the network distances through a hierarchy of subgraphs. Abeywickrama et al. [1] performed a thorough experimental evaluation of several kNN algorithms for road networks, where they showed that G-tree [5] typically outperformed INE [16], DisBrw [17], and ROAD [2], but not in all cases, thereby demonstrating the impact of an efficient implementation. Finally, other previous studies [15, 16] also processed the distance joins in road networks. For example, an ordered distance join operation returns a set of object pairs, which are reported in increasing order of the distance between the pairs. However, it is not appropriate to extend the existing solutions to solve our problem due to differences in problem definition.


### 2.2.kNN Join in the Euclidean Space

The processing ofkNN join queries in the Euclidean space has been studied extensively [6–10, 12]. Böhm and Krebs [6] developed an R-tree-based method called a multipage index (MuX) to evaluate kNN joins in the Euclidean space. The MuX method organizes the input datasets with large-sized pages in order to reduce the I/O cost. The computational cost is further reduced by carefully designing a secondary structure with a much smaller size within the pages. Xia et al. [7] developed a grid partitioning-based approach called Gorder (an order based on a grid) to evaluate kNN joins in the Euclidean space. Gorder is a block-nested loop join method that employs sorting, join scheduling, and distance computation filtering and reduction to decrease both the I/O and CPU costs. Yu et al. [8] developed an index-based kNN join method called iJoin by using iDistance [22] as the underlying index structure. By splitting the two input datasets into individual sets of partitions, the iJoin method employs a B+-tree to hold the objects in each dataset using the iDistance technique and it evaluates the kNN joins based on the properties of the B+-tree. Yao et al. [10] developed z-kNN as a Z-order-based method to evaluate kNN joins in large relational databases without changing the database engine, thereby allowing the query optimizer to understand and generate the best query plan. The z-kNN method transforms the kNN join operation into a set of kNN search operations where each object in R is a query point. Recently, Lu et al. [9] and Zhang et al. [12] developed novel algorithms using MapReduce to efficiently perform parallel kNN joins on large datasets. However, due to the different problem environments, it is not possible to apply these solutions based on the Euclidean distance to the kNN join problem in road networks. Finally, Li and Taniar [23] presented a taxonomy for distance-based spatial join queries, which are divided into the following three main categories: (1) all-range join (e.g., [24, 25]), (2) all-kNN join (e.g., [6, 26]), and (3) all-reverse NN join. Our study belongs to the all-kNN join category, and to the best of our knowledge, our current study represents the first attempt to evaluate kNN joins efficiently in road networks.


## 2.1.kNN Search in Road Networks

The processing ofkNN queries in road networks has been studied extensively [2, 3, 5, 16, 17, 19, 20]. Papadias et al. [16] introduced incremental Euclidean restriction (IER) and incremental network expansion (INE). IER exploits the Euclidean restriction principle in road networks to achieve better performance. INE conducts network expansion from the query location in a similar manner to Dijkstra’s algorithm and examines the data objects in the sequence in which they are encountered. Shahabi et al. [3] developed an embedding technique for transforming a road network to a constraint-free high-dimensional Euclidean space to approximately retrieve the nearest objects using traditional Euclidean-based algorithms. Kolahdouzan and Shahabi [13, 14] utilized the first degree network Voronoi diagrams to partition the spatial network into network Voronoi polygons (NVP), with one for each data object. They indexed the NVPs by using a spatial access method to reduce the problem to a point location problem in the Euclidean space. This minimizes the online network distance computation by allowing precomputing of the NVPs. Huang et al. [18] addressed the same problem using the island approach where each vertex is associated with all the data points. These islands are considered centers with a given radius r covering the vertex. In their approach, they utilized restricted network expansion from the query point using the precomputed islands.Huang et al. [20] and Samet et al. [17] proposed two different algorithms to address the drawbacks of data object-dependent precomputation. Huang et al. [20] introduced S-GRID for partitioning the spatial network into disjoint subnetworks and precomputing the shortest path for each pair of connected border points. To find the k-nearest neighbors (NNs), network expansion is first performed within the subnetworks before outer expansion between the border points using the precomputed information. Samet et al. [17] proposed a distance browsing (DisBrw) method where they associate a label with each edge to represent all of the vertices with a shortest path starting with a particular edge. They use these labels to traverse the shortest path quadtrees that facilitate geometric pruning to find the network distance between objects.Lee et al. [2] proposed a new system framework called ROAD for processing location-dependent spatial queries. ROAD organizes a large road network as a hierarchy of interconnected regional subnetworks, each of which is augmented with shortcuts and object abstracts to accelerate network traversal and facilitate rapid object lookups, respectively. Inspired by the R-tree [21], Zhong et al. [5] proposed a height-balanced index called G-tree in road networks, which employs graph partitioning to efficiently compute the network distances through a hierarchy of subgraphs. Abeywickrama et al. [1] performed a thorough experimental evaluation of several kNN algorithms for road networks, where they showed that G-tree [5] typically outperformed INE [16], DisBrw [17], and ROAD [2], but not in all cases, thereby demonstrating the impact of an efficient implementation. Finally, other previous studies [15, 16] also processed the distance joins in road networks. For example, an ordered distance join operation returns a set of object pairs, which are reported in increasing order of the distance between the pairs. However, it is not appropriate to extend the existing solutions to solve our problem due to differences in problem definition.


## 2.2.kNN Join in the Euclidean Space

The processing ofkNN join queries in the Euclidean space has been studied extensively [6–10, 12]. Böhm and Krebs [6] developed an R-tree-based method called a multipage index (MuX) to evaluate kNN joins in the Euclidean space. The MuX method organizes the input datasets with large-sized pages in order to reduce the I/O cost. The computational cost is further reduced by carefully designing a secondary structure with a much smaller size within the pages. Xia et al. [7] developed a grid partitioning-based approach called Gorder (an order based on a grid) to evaluate kNN joins in the Euclidean space. Gorder is a block-nested loop join method that employs sorting, join scheduling, and distance computation filtering and reduction to decrease both the I/O and CPU costs. Yu et al. [8] developed an index-based kNN join method called iJoin by using iDistance [22] as the underlying index structure. By splitting the two input datasets into individual sets of partitions, the iJoin method employs a B+-tree to hold the objects in each dataset using the iDistance technique and it evaluates the kNN joins based on the properties of the B+-tree. Yao et al. [10] developed z-kNN as a Z-order-based method to evaluate kNN joins in large relational databases without changing the database engine, thereby allowing the query optimizer to understand and generate the best query plan. The z-kNN method transforms the kNN join operation into a set of kNN search operations where each object in R is a query point. Recently, Lu et al. [9] and Zhang et al. [12] developed novel algorithms using MapReduce to efficiently perform parallel kNN joins on large datasets. However, due to the different problem environments, it is not possible to apply these solutions based on the Euclidean distance to the kNN join problem in road networks. Finally, Li and Taniar [23] presented a taxonomy for distance-based spatial join queries, which are divided into the following three main categories: (1) all-range join (e.g., [24, 25]), (2) all-kNN join (e.g., [6, 26]), and (3) all-reverse NN join. Our study belongs to the all-kNN join category, and to the best of our knowledge, our current study represents the first attempt to evaluate kNN joins efficiently in road networks.


## 3. Preliminaries

In Section3.1, we formally define the kNN join problem in road networks and explain its properties. In Section 3.2, we define the terms and notations used in this study.


### 3.1.kNN Join

We consider outer objects and inner objects in a road networkG where the outer objects and inner objects typically correspond to points of interest in different categories as shown in Figure 1. Given two points p and q, distp,q denotes the network distance between p and q, which is the length of the shortest path connecting them in G.Definition 1. (kNN search): Given an integer k, an outer object r, and a set of inner objects S, the kNNs of r from S, denoted as Skr, constitute a set of k inner objects from S such that distr,s+≤distr,s− holds for ∀s+∈Skr and ∀s−∈S−Skr.Definition 2. (kNN join): Given an integer k and datasets R and S, the kNN join of R and S, denoted as R⋉kNNS, returns ordered pairs of two objects r and s such that s is one of the kNNs of r where r∈R and s∈S. For simplicity, R⋉kNNS is abbreviated as R⋉S. Formally,(1)R⋉S=r,s∀r∈R,∀s∈Skr.ThekNN join has the following properties:(i)
ThekNN join is not commutative, that is, R⋉S≠S⋉R. Without loss of generality, we assume that R⋉S and k≤S in this study.(ii)
The cardinality of the result set of akNN join is R⋉S=k×R because the kNN join returns the k inner objects that are closest to each outer object in R.(iii)
The traversal distances from an outer object to itskNNs are not known in advance, in contrast to the range join.


### 3.2. Definition of Terms and Notations

#### 3.2.1. Road Network

A road network can be modeled using a weighted undirected graphG=V,E,W, where V, E, and W indicate the vertex set, edge set, and edge distance matrix, respectively. Each edge has a nonnegative weight to represent the network distance.


#### 3.2.2. Classification of Vertices

Vertices can be divided into three categories based on their degree. (1) If the degree of a vertex is larger than or equal to 3, the vertex is referred to as an intersection vertex. (2) If the degree is 2, the vertex is an intermediate vertex. (3) If the degree is 1, the vertex is a terminal vertex.


#### 3.2.3. Vertex Sequence and Outer Segment

A vertex sequencevlvl+1⋯vm¯ denotes a path between two vertices, vl and vm, such that vl and vm are either an intersection vertex or a terminal vertex, and the other vertices in the path, vl+1,…,vm−1, are intermediate vertices. The length of a vertex sequence is the total weight of the edges in the vertex sequence. An outer segment riri+1⋯rj¯ denotes a path that connects outer objects ri,ri+1,…,rj in the same vertex sequence. Table 1 summarizes the notations used in the study. To simplify the presentation, we use rirj¯ to denote riri+1⋯rj¯ if it causes no confusion, where ri,ri+1,…,rj are outer objects in the same vertex sequence.Table 1
Symbols and their meanings.
Symbol
Definition
k
Number of requested NNs
r
Outer objectr∈R
s
Inner objects∈S
v
l
v
l
+
1
⋯
v
m
¯
Vertex sequence wherevl and vm are either an intersection vertex or a terminal vertex and the other vertices, vl+1,…,vm−1, are intermediate vertices
r
i
r
i
+
1
⋯
r
j
¯
Outer segment generated from outer objectsri,ri+1,…,rj in the same vertex sequence
S
k
r
Set ofk inner objects closest to outer object r from S
S
r
i
r
j
¯
Set of inner objects located in outer segmentrirj¯, that is, Srirj¯=ss∈rirj¯
dist
p
,
q
Length of the shortest path connecting two pointsp and q
len
p
,
q
Length of the segment connecting two pointsp and q such that p and q are located in the same vertex sequenceFigure2 shows the difference in the distance and segment length between two objects r and s in a road network, where the numbers on the edges indicate the distance between two adjacent points (e.g., distv1,v2=6). The shortest path from r to s is r→v2→v5→s, and thus the distance between them is distr,s=6, whereas the segment connecting r and s in the same vertex sequence v2v3v4v5¯ becomes rv3v4s¯, and thus its length is lenr,s=9. We recall that lenr,s is defined if and only if the two objects are located in the same vertex sequence.Figure 2
dist
r
,
s
=
6 and lenr,s=9.


## 3.1.kNN Join

We consider outer objects and inner objects in a road networkG where the outer objects and inner objects typically correspond to points of interest in different categories as shown in Figure 1. Given two points p and q, distp,q denotes the network distance between p and q, which is the length of the shortest path connecting them in G.Definition 1. (kNN search): Given an integer k, an outer object r, and a set of inner objects S, the kNNs of r from S, denoted as Skr, constitute a set of k inner objects from S such that distr,s+≤distr,s− holds for ∀s+∈Skr and ∀s−∈S−Skr.Definition 2. (kNN join): Given an integer k and datasets R and S, the kNN join of R and S, denoted as R⋉kNNS, returns ordered pairs of two objects r and s such that s is one of the kNNs of r where r∈R and s∈S. For simplicity, R⋉kNNS is abbreviated as R⋉S. Formally,(1)R⋉S=r,s∀r∈R,∀s∈Skr.ThekNN join has the following properties:(i)
ThekNN join is not commutative, that is, R⋉S≠S⋉R. Without loss of generality, we assume that R⋉S and k≤S in this study.(ii)
The cardinality of the result set of akNN join is R⋉S=k×R because the kNN join returns the k inner objects that are closest to each outer object in R.(iii)
The traversal distances from an outer object to itskNNs are not known in advance, in contrast to the range join.


## 3.2. Definition of Terms and Notations

### 3.2.1. Road Network

A road network can be modeled using a weighted undirected graphG=V,E,W, where V, E, and W indicate the vertex set, edge set, and edge distance matrix, respectively. Each edge has a nonnegative weight to represent the network distance.


### 3.2.2. Classification of Vertices

Vertices can be divided into three categories based on their degree. (1) If the degree of a vertex is larger than or equal to 3, the vertex is referred to as an intersection vertex. (2) If the degree is 2, the vertex is an intermediate vertex. (3) If the degree is 1, the vertex is a terminal vertex.


### 3.2.3. Vertex Sequence and Outer Segment

A vertex sequencevlvl+1⋯vm¯ denotes a path between two vertices, vl and vm, such that vl and vm are either an intersection vertex or a terminal vertex, and the other vertices in the path, vl+1,…,vm−1, are intermediate vertices. The length of a vertex sequence is the total weight of the edges in the vertex sequence. An outer segment riri+1⋯rj¯ denotes a path that connects outer objects ri,ri+1,…,rj in the same vertex sequence. Table 1 summarizes the notations used in the study. To simplify the presentation, we use rirj¯ to denote riri+1⋯rj¯ if it causes no confusion, where ri,ri+1,…,rj are outer objects in the same vertex sequence.Table 1
Symbols and their meanings.
Symbol
Definition
k
Number of requested NNs
r
Outer objectr∈R
s
Inner objects∈S
v
l
v
l
+
1
⋯
v
m
¯
Vertex sequence wherevl and vm are either an intersection vertex or a terminal vertex and the other vertices, vl+1,…,vm−1, are intermediate vertices
r
i
r
i
+
1
⋯
r
j
¯
Outer segment generated from outer objectsri,ri+1,…,rj in the same vertex sequence
S
k
r
Set ofk inner objects closest to outer object r from S
S
r
i
r
j
¯
Set of inner objects located in outer segmentrirj¯, that is, Srirj¯=ss∈rirj¯
dist
p
,
q
Length of the shortest path connecting two pointsp and q
len
p
,
q
Length of the segment connecting two pointsp and q such that p and q are located in the same vertex sequenceFigure2 shows the difference in the distance and segment length between two objects r and s in a road network, where the numbers on the edges indicate the distance between two adjacent points (e.g., distv1,v2=6). The shortest path from r to s is r→v2→v5→s, and thus the distance between them is distr,s=6, whereas the segment connecting r and s in the same vertex sequence v2v3v4v5¯ becomes rv3v4s¯, and thus its length is lenr,s=9. We recall that lenr,s is defined if and only if the two objects are located in the same vertex sequence.Figure 2
dist
r
,
s
=
6 and lenr,s=9.


## 3.2.1. Road Network

A road network can be modeled using a weighted undirected graphG=V,E,W, where V, E, and W indicate the vertex set, edge set, and edge distance matrix, respectively. Each edge has a nonnegative weight to represent the network distance.


## 3.2.2. Classification of Vertices

Vertices can be divided into three categories based on their degree. (1) If the degree of a vertex is larger than or equal to 3, the vertex is referred to as an intersection vertex. (2) If the degree is 2, the vertex is an intermediate vertex. (3) If the degree is 1, the vertex is a terminal vertex.


## 3.2.3. Vertex Sequence and Outer Segment

A vertex sequencevlvl+1⋯vm¯ denotes a path between two vertices, vl and vm, such that vl and vm are either an intersection vertex or a terminal vertex, and the other vertices in the path, vl+1,…,vm−1, are intermediate vertices. The length of a vertex sequence is the total weight of the edges in the vertex sequence. An outer segment riri+1⋯rj¯ denotes a path that connects outer objects ri,ri+1,…,rj in the same vertex sequence. Table 1 summarizes the notations used in the study. To simplify the presentation, we use rirj¯ to denote riri+1⋯rj¯ if it causes no confusion, where ri,ri+1,…,rj are outer objects in the same vertex sequence.Table 1
Symbols and their meanings.
Symbol
Definition
k
Number of requested NNs
r
Outer objectr∈R
s
Inner objects∈S
v
l
v
l
+
1
⋯
v
m
¯
Vertex sequence wherevl and vm are either an intersection vertex or a terminal vertex and the other vertices, vl+1,…,vm−1, are intermediate vertices
r
i
r
i
+
1
⋯
r
j
¯
Outer segment generated from outer objectsri,ri+1,…,rj in the same vertex sequence
S
k
r
Set ofk inner objects closest to outer object r from S
S
r
i
r
j
¯
Set of inner objects located in outer segmentrirj¯, that is, Srirj¯=ss∈rirj¯
dist
p
,
q
Length of the shortest path connecting two pointsp and q
len
p
,
q
Length of the segment connecting two pointsp and q such that p and q are located in the same vertex sequenceFigure2 shows the difference in the distance and segment length between two objects r and s in a road network, where the numbers on the edges indicate the distance between two adjacent points (e.g., distv1,v2=6). The shortest path from r to s is r→v2→v5→s, and thus the distance between them is distr,s=6, whereas the segment connecting r and s in the same vertex sequence v2v3v4v5¯ becomes rv3v4s¯, and thus its length is lenr,s=9. We recall that lenr,s is defined if and only if the two objects are located in the same vertex sequence.Figure 2
dist
r
,
s
=
6 and lenr,s=9.


## 4. Basic GNL Method forkNN Joins in Road Networks

In Section4.1, we describe the grouping of outer objects in a vertex sequence. In Section 4.2, we explain the shared execution processing of outer objects in a segment. In Section 4.3, we provide algorithms for processing kNN joins efficiently in road networks. Finally, in Section 4.4, we discuss the evaluation of an example kNN join in a road network.


### 4.1. Grouping of Outer Objects in a Vertex Sequence

Figure3 presents an example of the kNN join R⋉S in a road network that we consider in this section, where there are six outer objects, r1 through r6, and four inner objects, s1 through s4, in a road network, with three vertex sequences, v1v2v3¯, v1v3¯, and v1v4v3¯. For simplicity, we consider a 2-NN join R⋉S where R=r1,r2,r3,r4,r5,r6 and S=s1,s2,s3,s4.Figure 3
Example ofkNN join R⋉S in a road network.Figure4 shows a sample grouping of outer objects in a vertex sequence, where the outer objects r1, r4, and r5 in vertex sequence v1v2v3¯ are grouped into r1r5r4¯ and the outer objects r2 and r3 in vertex sequence v1v4v3¯ are grouped into r2r3¯. Note that the outer segments (e.g., r1r5r4¯ and r2r3¯ in Figure 4) are marked by bold lines. Therefore, a set of outer objects R=r1,r2,r3,r4,r5,r6 is transformed into R¯=r1r5r4¯,r2r3¯,r6, where R¯ denotes the set of outer segments generated from the outer objects in R.Figure 4
Grouping outer objects in a vertex sequence.Algorithm 1: Group_outer_objects R,V,E.
Input: R: set of outer objects, V: set of vertices, E: set of edges
Output: R¯: set of outer segments
(1)
V
¯
⁡
←
⁡
∅
,
⁡
R
¯
⁡
←
⁡
∅  // V¯ and R¯ are initialized to the empty sets, where V¯ is a set of vertex sequences
(2)
// step 1:V¯ is generated from V and E
(3)
for each vertex vl∈V do
(4)
if vl is either an intersection vertex or a terminal vertex then
(5)
for each edge vlvl+1¯∈E adjacent to vl do
(6)
vlvl+1⋯vm¯⁡←⁡find_vertex_sequencevl,vl+1,V  // it explores the path from vl toward vl+1 until vm is found
(7)
V¯⁡←⁡V¯⁡∪⁡vlvl+1⋯vm¯            // vm is either an intersection vertex or a terminal vertex
(8)
// step 2:R¯ is generated from R and V¯
(9)
for each vertex sequence vlvl+1⋯vm¯∈V¯ do
(10)
ri,ri+1,…,rj⁡←⁡find_outer_objects_in_vertex_sequencevlvl+1⋯vm¯
(11)
R¯⁡←⁡R¯⁡∪⁡riri+1⋯rj¯ ⁡⁡             // riri+1⋯rj¯ is generated from outer objects ri,ri+1,…,rj
(12)
returnR¯Algorithm1 describes how to group neighboring outer objects into an outer segment in a vertex sequence. This algorithm comprises two steps. In the first step, a set of vertex sequences V¯ is generated from a set of vertices V and a set of edges E. In the second step, a set of outer segments R¯ is generated from a set of outer objects R and V¯. We first examine each vertex to find either an intersection vertex or a terminal vertex. If vl is either an intersection vertex or a terminal vertex, for each edge vlvl+1¯∈E adjacent to vl, we explore the path from vl toward vl+1 until a nonintermediate vertex vm is found. Then, a new vertex sequence vlvl+1⋯vm¯ is added to V¯. We search for outer objects ri,ri+1,…,rj in each vertex sequence vlvl+1⋯vm¯. The outer objects ri,ri+1,…,rj are grouped into an outer segment riri+1⋯rj¯, which is added to R¯.


### 4.2. Shared Execution Processing of Outer Objects in a Segment

The shared execution strategies in the basic GNL method are motivated by the observation that twokNN queries at most are sufficient to retrieve the kNNs of all outer objects in an outer segment. This observation is formalized in Lemma 1, which states a simple but important fact regarding the shared execution processing of outer objects in an outer segment. If we evaluate two kNN queries for outer objects ri and rj, which are located at the ends of an outer segment riri+1⋯rj¯, then we can determine the kNNs of the other outer objects ri+1,…,rj−1 without evaluating additional kNN queries for them. Thus, the two kNN queries for ri and rj are sufficient to retrieve the kNNs of the other outer objects ri+1,…,rj−1 in a segment.Lemma 1.For every outer object r∈rirj¯, it holds that Skr⁡⊆⁡Skri⁡∪⁡Skrj⁡∪⁡Srirj¯, where Skri Skrj is the set of k inner objects closest to outer object ri rj and Srirj¯ is the set of inner objects located in the outer segment rirj¯ (e.g., s4∈r2r3¯ in Figure 4).Proof. We prove Lemma 1 by contradiction. If we assume that Skr⁡⊆⁡Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ does not hold, i.e., Skr⁡⊈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯, then this implies that there is an inner object s+∈Skr such that s+∉Skri⁡∪⁡Skrj⁡∪⁡Srirj¯. Clearly, s+∉Skri, so s+ is more distant from ri than its kth closest inner object skthri, that is, distri,skthri<distri,s+. Similarly, s+∉Skrj, so s+ is also more distant from rj than its kth closest inner object skthrj, that is, distrj,skthrj<distrj,s+. However, s+∉Srirj¯, so s+ is not located in rirj¯. Therefore, the shortest path from r to s+ passes through either ri or rj and the distance from r to s+ is determined by distr,s+=minlenr,ri+distri,s+,lenr,rj+distrj,s+. From the former conditions, distr,s+>minlenr,ri+distri,skthri,lenr,rj+distrj,skthrj, so s+ cannot belong to Skr, which contradicts the assumption that an inner object s+∈Skr exists such that s+∉Skri⁡∪⁡Skrj⁡∪⁡Srirj¯.We determine thek inner objects that are closest to an outer object r∈rirj¯ by using two kNN sets Skri and Skrj of outer objects ri and rj, respectively. First, we investigate the distance from the outer object r∈rirj¯ to an inner object s. In Figure 5, we assume that ri corresponds to the origin of the XY coordinate system. Then, the Y-axis represents distr,s and the X-axis represents lenri,r. If there is a path of r→ri→s, then the distance from r to s is computed as distr,s=lenr,ri+distri,s, as shown in Figure 5(a). Similarly, if there is a path of r→rj→s, then distr,s is computed as distr,s=lenr,rj+distrj,s, as shown in Figure 5(b). If an inner object s is located in rirj¯, then distr,s is computed as distr,s=lenr,s, as shown in Figure 5(c). Note that min returns the minimum of the values in the input array. Thus, distr,s is the length of the shortest path among multiple paths between r and s, and it is computed as follows:(2)distr,s=minlenr,ri+distri,s,lenr,rj+distrj,s,if⁡s∉rirj¯minlenr,ri+distri,s,lenr,rj+distrj,s,lenr,s,otherwise.Table2 explains how to compute the distance from r to s, where r∈rirj¯ and s∈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯. An inner object s belongs to a combination of Skri, Skrj, and Srirj¯, so seven possible cases are considered in total. Clearly, it is trivial to retrieve a set Srirj¯ of inner objects that is located in rirj¯ compared with retrieving a set Skri Skrj of k inner objects closest to outer object ri rj. Note that distr,s in Table 2 may not necessarily be the length of the shortest path from r to s, as discussed in Section 4.4.Figure 5
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
,
if
s
∉
r
i
r
j
¯
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
,
len
r
,
s
,
otherwise
.
(a)
dist
r
i
,
s
=
len
r
,
r
i
+
dist
r
i
,
s
for  the  path  of
r
→
r
i
→
s
(b)
dist
r
,
s
=
len
r
,
r
j
+
dist
r
j
,
s
for  the  path  of
r
→
r
j
→
s
(c)
dist
r
,
s
=
len
r
,
s
for
s
∈
r
i
r
j
¯Table 2
Computation ofdistr,s for r∈rirj¯ and s∈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯.
Condition
dist
r
,
s
s
∈
S
k
r
i
⁡
∩
⁡
S
k
r
j
⁡
∩
⁡
S
r
i
r
j
¯
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
,
len
r
,
s
s
∈
S
k
r
i
⁡
∩
⁡
S
k
r
j
−
S
r
i
r
j
¯
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
s
∈
S
k
r
i
⁡
∩
⁡
S
r
i
r
j
¯
−
S
k
r
j
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
s
s
∈
S
k
r
j
⁡
∩
⁡
S
r
i
r
j
¯
−
S
k
r
i
dist
r
,
s
=
min
len
r
,
r
j
+
dist
r
j
,
s
,
len
r
,
s
s
∈
S
k
r
i
−
S
k
r
j
⁡
∪
⁡
S
r
i
r
j
¯
dist
r
,
s
=
len
r
,
r
i
+
dist
r
i
,
s
s
∈
S
k
r
j
−
S
k
r
i
⁡
∪
⁡
S
r
i
r
j
¯
dist
r
,
s
=
len
r
,
r
j
+
dist
r
j
,
s
s
∈
S
r
i
r
j
¯
−
S
k
r
i
⁡
∪
⁡
S
k
r
j
dist
r
,
s
=
len
r
,
sAlgorithm 2: Basic_GNL k,R,S.
Input: k: number of inner objects retrieved for an outer object, R: set of outer objects, S: set of inner objects
Output: R⋉S: set of ordered pairs of outer object r∈R and inner object s∈Skr
(1)
Ψ
⁡
←
⁡
∅          ⁡⁡⁡⁡⁡  // kNN join result set Ψ is initialized to the empty set
(2)
// step 1: outer objectsri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯
(3)
R
¯
⁡
←
⁡
group
_
outer
_
objects
R
,
V
,
E  // group_outer_objects is explained in Algorithm 1
(4)
// step 2:kNN join is evaluated for each outer segment rirj¯∈R¯
(5)
for each outer segment rirj¯∈R¯ do
(6)
Ψrirj¯⁡←⁡kNN_joink,rirj¯,S⁡⁡  // kNN_join is explained in Algorithm 3
(7)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯        // Ψrirj¯=r,s∀r∈rirj¯,⁡∀s∈Skr
(8)
return Ψ         ⁡⁡⁡⁡⁡  // Ψ=r,s∀r∈R,∀s∈Skr is returned after all outer segments have been processed


### 4.3.kNN Join Algorithm

Algorithm2 describes the basic GNL algorithm, which employs the grouping of outer objects and shared execution to reduce the processing time. This algorithm comprises two steps. In the first step, the outer objects ri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯ (line 3). In the second step, the kNNs of the outer objects in the outer segment rirj¯ are retrieved using the shared execution method (line 6), as explained in Algorithm 3. An ordered pair comprising an outer object r∈rirj¯ and inner object s∈Skr is then added to the partial join result Ψrirj¯=r,s∀r∈rirj¯,∀s∈Skr. Finally, the kNN join result set Ψ=r,s∀r∈R,∀s∈Skr is returned after all the outer segments have been processed (line 8).Algorithm 3: kNN_joink,rirj¯,S.
Input: k: number of inner objects retrieved for an outer object, rirj¯: outer segment, S: set of inner objects
Output: rirj¯⋉S: set of ordered pairs of outer object r∈rirj¯ and inner object s∈Skr
(1)
if rirj¯=1 then              // rirj¯=1 denotes that rirj¯ contains only an outer object ri, that is, ri=rj
(2)
Skri⁡←⁡kNN_queryk,ri       ⁡⁡   // kNN query from ri is performed and its result is saved to Skri
(3)
Ψri⁡←⁡ri,ss∈Skri       ⁡⁡⁡   // a partial join result Ψri for ri is generated from Skri
(4)
return Ψri         ⁡    ⁡⁡ // a partial join result Ψri for ri is returned
(5)
else if rirj¯=2 then           ⁡ // rirj¯=2 denotes that rirj¯ contains only two outer objects ri and rj
(6)
Skri⁡←⁡kNN_queryk,ri        ⁡⁡  // kNN query from ri is performed, and its result is saved to Skri
(7)
Ψri⁡←⁡ri,ss∈Skri        ⁡⁡⁡  // a partial join result Ψri for ri is generated from Skri
(8)
Skrj⁡←⁡kNN_queryk,rj      ⁡    // kNN query from rj is performed, and its result is saved to Skrj
(9)
Ψrj⁡←⁡rj,ss∈Skrj       ⁡   // a partial join result Ψrj for rj is generated from Skrj
(10)
return Ψri⁡∪⁡Ψrj        ⁡ ⁡  // the union Ψri⁡∪⁡Ψrj of the partial join results for ri and rj is returned
(11)
else if rirj¯≥3 then          ⁡⁡  // rirj¯≥3 denotes that rirj¯ contains more than three outer objects
(12)
Skri⁡←⁡kNN_queryk,ri        ⁡⁡  // kNN query from ri is performed, and its result is saved to Skri
(13)
Ψri⁡←⁡ri,ss∈Skri       ⁡⁡⁡   // a partial join result Ψri for ri is generated from Skri
(14)
Skrj⁡←⁡kNN_queryk,rj       ⁡   // kNN query from rj is performed, and its result is saved to Skrj
(15)
Ψrj⁡←⁡rj,ss∈Skrj      ⁡    // a partial join result Ψrj for rj is generated from Skrj
(16)
Srirj¯⁡←⁡ss∈rirj¯        ⁡   // inner objects located in rirj¯ are retrieved
(17)
for each outer object r∈ri+1,…,rj−1 do  // k NNs of outer objects ri+1,…,rj−1 are retrieved from Skri⁡∪⁡Skrj⁡∪⁡Srirj¯
(18)
Skr⁡←⁡kNN_searchk,r,Skri⁡∪⁡Skrj⁡∪⁡Srirj¯  ⁡⁡// kNN_search is explained in Algorithm 4
(19)
Ψr⁡←⁡r,ss∈Skr           // a partial join result Ψr for r∈ri+1,…,rj−1 is generated from Skr
(20)
return Ψri⁡∪⁡Ψri+1⁡∪⁡⋯⁡∪⁡Ψrj     // the union of the partial join results for ri,ri+1,…,rj is returnedAlgorithm3 describes the kNN join for all outer objects ri,ri+1,…,rj in rirj¯. Three general cases are formally considered depending on the number of outer objects in rirj¯, that is, rirj¯=1, rirj¯=2, and rirj¯≥3, where rirj¯ returns the number of outer objects in rirj¯. rirj¯=1 denotes that rirj¯ contains only one outer object ri, rirj¯=2 denotes that rirj¯ contains only two outer objects ri and rj, and rirj¯≥3 denotes that rirj¯ contains more than three outer objects ri,ri+1,…,rj. If rirj¯=1, then the kNN query from ri is evaluated. In this study, INE [16] is employed to evaluate the kNN query. Naturally, INE can be replaced by other kNN algorithms [1, 2, 5, 13, 17–19]. A partial join result Ψri for ri is generated from Skri and returned (lines 1–4). Similarly, if rirj¯=2, then two kNN queries from ri and rj are evaluated. Partial join results Ψri and Ψrj for ri and rj are generated from Skri and Skrj, respectively; and their union is returned (lines 5–10). Finally, if rirj¯≥3, then two kNN queries from ri and rj are evaluated and a search for the inner objects located in rirj¯ is performed. The partial join results Ψri and Ψrj for ri and rj are generated from Skri and Skrj, respectively. For each outer object r∈ri+1,…,rj−1, the set of kNNs of r is retrieved from Skri, Skrj, and Srirj¯ (lines 17–19), as explained in Algorithm 4. Finally, the union of partial join results Ψri,Ψri+1,…,Ψrj is returned.Algorithm 4: kNN_searchk,r,Skri⁡∪⁡Skrj⁡∪⁡Srirj¯.
Input: k: number of inner objects retrieved for an outer object, r∈rirj¯: outer object, Skri⁡∪⁡Skrj⁡∪⁡Srirj¯: set of candidate inner objects
Output: Skr: set of k inner objects closest to r
(1)
S
k
r
⁡
←
⁡
∅  // Skr is initialized to the empty set
(2)
for each inner object s∈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ do
(3)
// step 1:distr,s is computed according to the condition of s, see Table 2 for details.
(4)
if s∈Skri⁡∩⁡Skrj⁡∩⁡Srirj¯ then distr,s⁡←⁡minlenr,ri+distri,s,lenr,rj+distrj,s,lenr,s
(5)
else if s∈Skri⁡∩⁡Skrj−Srirj¯ then distr,s⁡←⁡minlenr,ri+distri,s,lenr,rj+distrj,s
(6)
else if s∈Skri⁡∩⁡Srirj¯−Skrj then distr,s⁡←⁡minlenr,ri+distri,s,lenr,s
(7)
else if s∈Skrj⁡∩⁡Srirj¯−Skri then distr,s⁡←⁡minlenr,rj+distrj,s,lenr,s
(8)
else if s∈Skri−Skrj⁡∪⁡Srirj¯ then distr,s⁡←⁡lenr,ri+distri,s
(9)
else if s∈Skrj−Skri⁡∪⁡Srirj¯ then distr,s⁡←⁡lenr,rj+distrj,s
(10)
else if s∈Srirj¯−Skri⁡∪⁡Skrj then distr,s⁡←⁡lenr,s
(11)
// step 2:s is added to Skr if it satisfies either of the following two conditions:
(12)
if Skr<k then
(13)
Skr⁡←⁡Skr⁡∪⁡s
(14)
else if Skr=k and distr,s<distr,skth then
(15)
Skr⁡←⁡Skr⁡∪⁡s−skth
(16)
return SkrAlgorithm4 describes the kNN search of an outer object r∈ri+1,…,rj−1. First, the set of kNNs of outer object r, Skr, is initialized to the empty set. The distance from r to a candidate inner object s is computed according to the condition of s (lines 3–10), as explained in Table 2. After computing distr,s, we can determine whether s is added to the candidate set Skr. If Skr<k, then s is simply added to Skr (lines 12-13). If Skr=k and distr,s<distr,skth, then s is added to Skr and skth is removed from Skr accordingly, where skth denotes the kth closest inner object to r, that is, Skr⁡←⁡Skr⁡∪⁡s−skth (lines 14-15). The set Skr of the kNNs of r is returned after all of the candidate inner objects in Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ have been considered (line 16).


### 4.4. Evaluation of an ExamplekNN Join Using the Basic GNL Method

We now discuss the evaluation of thekNN join example shown in Figure 3. We recall that R=r1,r2,r3,r4,r5,r6, S=s1,s2,s3,s4, and k=2 are given. Table 3 summarizes the computation of the kNN join R⋉S.Table 3
Computation of the examplekNN join R⋉S using the basic GNL method.
r
i
r
j
¯
r
i
r
j
S
k
r
i
S
k
r
j
S
r
i
r
j
¯
r
i
+
1
,
…
,
r
j
−
1
S
k
r
i
⁡
∪
⁡
S
k
r
j
⁡
∪
⁡
S
r
i
r
j
¯
r
1
r
5
r
4
¯
r
1
r
4
S
k
r
1
=
s
1
,
s
2
S
k
r
4
=
s
2
,
s
3
S
r
1
r
5
r
4
¯
=
∅
r
5
s
1
,
s
2
,
s
3
r
2
r
3
¯
r
2
r
3
S
k
r
2
=
s
3
,
s
4
S
k
r
3
=
s
3
,
s
4
S
r
2
r
3
¯
=
s
4
∅
Not applicable
r
6
r
6
r
6
S
k
r
6
=
s
2
,
s
3
S
k
r
6
=
s
2
,
s
3
S
r
6
=
∅
∅
Not applicableAs explained in Algorithm2, the basic GNL method first groups the outer objects in a vertex sequence into an outer segment. Therefore, R¯=r1r5r4¯,r2r3¯,r6 is generated from R=r1,r2,r3,r4,r5,r6, as shown in Figure 4. In this example, we process r1r5r4¯, r2r3¯, and r6 in this order. As explained in Algorithm 3, we process the outer segment differently according to the number of outer objects in the outer segment. Outer segment r1r5r4¯ contains three outer objects r1, r5, and r4, so two kNN queries are issued from r1 and r4, and the inner objects located in r1r5r4¯ are retrieved. We have Skr1=s1,s2, Skr4=s2,s3, and Sr1r5r4¯=∅, as shown in Table 3. Thus, Skr1=s1,s2 and Skr4=s2,s3 simply generate the partial join results Ψr1=r1,s1,r1,s2 and Ψr4=r4,s2,r4,s3, respectively.According to Lemma 1, we can retrieve thekNNs of outer object r5 from a set of candidate inner objects Skr1⁡∪⁡Skr4⁡∪⁡Sr1r5r4¯=s1,s2,s3 without issuing a kNN query for r5. Thus, we need to compute the distance from r5 to each candidate inner object s∈s1,s2,s3. Clearly, s1∈Skr1−Skr4⁡∪⁡Sr1r5r4¯ according to Table 3, so the distance from r5 to s1 is distr5,s1=lenr5,r1⁡+⁡distr1,s1=3, as shown in Figure 6(a). Similarly, s2∈Skr1⁡∩⁡Skr4−Sr1r5r4¯ according to Table 3, so the distance from r5 to s2 is distr5,s2=minlenr5,r1+distr1,s2,lenr5,r4+distr4,s2=min6,16=6, as shown in Figure 6(b). Finally, s3∈Skr4−Skr1⁡∪⁡Sr1r5r4¯ according to Table 3, so the distance from r5 to s3 is distr5,s3=lenr5,r4+distr4,s3=15, as shown in Figure 6(c). It should be noted that the shortest path from r5 to s3 is r5→r1→s3 rather than r5→r4→s3, and thus the shortest distance from r5 to s3 is distr5,s3=lenr5,r1⁡+⁡distr1,s3=9. However, this does not affect the correctness of the set of the kNNs of r5 because s3 does not belong to Skr1=s1,s2 so the path r5→r1→s3 does not have to be considered. Consequently, we have Skr5=s1,s2 from distr5,s1=3, distr5,s2=6, and distr5,s3=15, which generates the partial join result Ψr5=r5,s1,r5,s2.Figure 6
Computation of the distance fromr5 to s∈s1,s2,s3.
(a)
dist
r
5
,
s
1
=
3
for
s
1
∈
S
k
r
1
−
S
k
r
4
⁡
∪
⁡
S
r
1
r
5
r
4
¯
(b)
dist
r
5
,
s
2
=
6
for
s
2
∈
S
k
r
1
⁡
∩
⁡
S
k
r
4
−
S
r
1
r
5
r
4
¯
(c)
dist
r
5
,
s
3
=
15
for
s
3
∈
S
k
r
4
−
S
k
r
1
⁡
∪
⁡
S
r
1
r
5
r
4
¯Next, we compute the partial join results for the outer objects inr2r3¯. Outer segment r2r3¯ only contains two outer objects r2 and r3, so two kNN queries are issued from r2 and r3. Therefore, as shown in Table 3, we obtain Skr2=s3,s4 and Skr3=s3,s4, which directly generate the partial join results Ψr2=r2,s3,r2,s4 and Ψr3=r3,s3,r3,s4, respectively. Finally, we compute the partial join result for outer object r6, where a single kNN query is simply issued from r6. Therefore, as shown in Table 3, we obtain Skr6=s2,s3, which generates the partial join result Ψr6=r6,s2,r6,s3. Finally, we obtain the kNN join result that is the union of the partial join results for outer objects r1 to r6, as follows: (3)Ψ=Ψr1r5r4¯⁡∪⁡Ψr2r3¯⁡∪⁡Ψr6=r1,s1,r1,s2,r2,s3,r2,s4,r3,s3,r3,s4,r4,s2,r4,s3,r5,s1,r5,s2,r6,s2,r6,s3,where Ψr1r5r4¯=Ψr1⁡∪⁡Ψr5⁡∪⁡Ψr4 and Ψr2r3¯=Ψr2⁡∪⁡Ψr3.


## 4.1. Grouping of Outer Objects in a Vertex Sequence

Figure3 presents an example of the kNN join R⋉S in a road network that we consider in this section, where there are six outer objects, r1 through r6, and four inner objects, s1 through s4, in a road network, with three vertex sequences, v1v2v3¯, v1v3¯, and v1v4v3¯. For simplicity, we consider a 2-NN join R⋉S where R=r1,r2,r3,r4,r5,r6 and S=s1,s2,s3,s4.Figure 3
Example ofkNN join R⋉S in a road network.Figure4 shows a sample grouping of outer objects in a vertex sequence, where the outer objects r1, r4, and r5 in vertex sequence v1v2v3¯ are grouped into r1r5r4¯ and the outer objects r2 and r3 in vertex sequence v1v4v3¯ are grouped into r2r3¯. Note that the outer segments (e.g., r1r5r4¯ and r2r3¯ in Figure 4) are marked by bold lines. Therefore, a set of outer objects R=r1,r2,r3,r4,r5,r6 is transformed into R¯=r1r5r4¯,r2r3¯,r6, where R¯ denotes the set of outer segments generated from the outer objects in R.Figure 4
Grouping outer objects in a vertex sequence.Algorithm 1: Group_outer_objects R,V,E.
Input: R: set of outer objects, V: set of vertices, E: set of edges
Output: R¯: set of outer segments
(1)
V
¯
⁡
←
⁡
∅
,
⁡
R
¯
⁡
←
⁡
∅  // V¯ and R¯ are initialized to the empty sets, where V¯ is a set of vertex sequences
(2)
// step 1:V¯ is generated from V and E
(3)
for each vertex vl∈V do
(4)
if vl is either an intersection vertex or a terminal vertex then
(5)
for each edge vlvl+1¯∈E adjacent to vl do
(6)
vlvl+1⋯vm¯⁡←⁡find_vertex_sequencevl,vl+1,V  // it explores the path from vl toward vl+1 until vm is found
(7)
V¯⁡←⁡V¯⁡∪⁡vlvl+1⋯vm¯            // vm is either an intersection vertex or a terminal vertex
(8)
// step 2:R¯ is generated from R and V¯
(9)
for each vertex sequence vlvl+1⋯vm¯∈V¯ do
(10)
ri,ri+1,…,rj⁡←⁡find_outer_objects_in_vertex_sequencevlvl+1⋯vm¯
(11)
R¯⁡←⁡R¯⁡∪⁡riri+1⋯rj¯ ⁡⁡             // riri+1⋯rj¯ is generated from outer objects ri,ri+1,…,rj
(12)
returnR¯Algorithm1 describes how to group neighboring outer objects into an outer segment in a vertex sequence. This algorithm comprises two steps. In the first step, a set of vertex sequences V¯ is generated from a set of vertices V and a set of edges E. In the second step, a set of outer segments R¯ is generated from a set of outer objects R and V¯. We first examine each vertex to find either an intersection vertex or a terminal vertex. If vl is either an intersection vertex or a terminal vertex, for each edge vlvl+1¯∈E adjacent to vl, we explore the path from vl toward vl+1 until a nonintermediate vertex vm is found. Then, a new vertex sequence vlvl+1⋯vm¯ is added to V¯. We search for outer objects ri,ri+1,…,rj in each vertex sequence vlvl+1⋯vm¯. The outer objects ri,ri+1,…,rj are grouped into an outer segment riri+1⋯rj¯, which is added to R¯.


## 4.2. Shared Execution Processing of Outer Objects in a Segment

The shared execution strategies in the basic GNL method are motivated by the observation that twokNN queries at most are sufficient to retrieve the kNNs of all outer objects in an outer segment. This observation is formalized in Lemma 1, which states a simple but important fact regarding the shared execution processing of outer objects in an outer segment. If we evaluate two kNN queries for outer objects ri and rj, which are located at the ends of an outer segment riri+1⋯rj¯, then we can determine the kNNs of the other outer objects ri+1,…,rj−1 without evaluating additional kNN queries for them. Thus, the two kNN queries for ri and rj are sufficient to retrieve the kNNs of the other outer objects ri+1,…,rj−1 in a segment.Lemma 1.For every outer object r∈rirj¯, it holds that Skr⁡⊆⁡Skri⁡∪⁡Skrj⁡∪⁡Srirj¯, where Skri Skrj is the set of k inner objects closest to outer object ri rj and Srirj¯ is the set of inner objects located in the outer segment rirj¯ (e.g., s4∈r2r3¯ in Figure 4).Proof. We prove Lemma 1 by contradiction. If we assume that Skr⁡⊆⁡Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ does not hold, i.e., Skr⁡⊈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯, then this implies that there is an inner object s+∈Skr such that s+∉Skri⁡∪⁡Skrj⁡∪⁡Srirj¯. Clearly, s+∉Skri, so s+ is more distant from ri than its kth closest inner object skthri, that is, distri,skthri<distri,s+. Similarly, s+∉Skrj, so s+ is also more distant from rj than its kth closest inner object skthrj, that is, distrj,skthrj<distrj,s+. However, s+∉Srirj¯, so s+ is not located in rirj¯. Therefore, the shortest path from r to s+ passes through either ri or rj and the distance from r to s+ is determined by distr,s+=minlenr,ri+distri,s+,lenr,rj+distrj,s+. From the former conditions, distr,s+>minlenr,ri+distri,skthri,lenr,rj+distrj,skthrj, so s+ cannot belong to Skr, which contradicts the assumption that an inner object s+∈Skr exists such that s+∉Skri⁡∪⁡Skrj⁡∪⁡Srirj¯.We determine thek inner objects that are closest to an outer object r∈rirj¯ by using two kNN sets Skri and Skrj of outer objects ri and rj, respectively. First, we investigate the distance from the outer object r∈rirj¯ to an inner object s. In Figure 5, we assume that ri corresponds to the origin of the XY coordinate system. Then, the Y-axis represents distr,s and the X-axis represents lenri,r. If there is a path of r→ri→s, then the distance from r to s is computed as distr,s=lenr,ri+distri,s, as shown in Figure 5(a). Similarly, if there is a path of r→rj→s, then distr,s is computed as distr,s=lenr,rj+distrj,s, as shown in Figure 5(b). If an inner object s is located in rirj¯, then distr,s is computed as distr,s=lenr,s, as shown in Figure 5(c). Note that min returns the minimum of the values in the input array. Thus, distr,s is the length of the shortest path among multiple paths between r and s, and it is computed as follows:(2)distr,s=minlenr,ri+distri,s,lenr,rj+distrj,s,if⁡s∉rirj¯minlenr,ri+distri,s,lenr,rj+distrj,s,lenr,s,otherwise.Table2 explains how to compute the distance from r to s, where r∈rirj¯ and s∈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯. An inner object s belongs to a combination of Skri, Skrj, and Srirj¯, so seven possible cases are considered in total. Clearly, it is trivial to retrieve a set Srirj¯ of inner objects that is located in rirj¯ compared with retrieving a set Skri Skrj of k inner objects closest to outer object ri rj. Note that distr,s in Table 2 may not necessarily be the length of the shortest path from r to s, as discussed in Section 4.4.Figure 5
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
,
if
s
∉
r
i
r
j
¯
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
,
len
r
,
s
,
otherwise
.
(a)
dist
r
i
,
s
=
len
r
,
r
i
+
dist
r
i
,
s
for  the  path  of
r
→
r
i
→
s
(b)
dist
r
,
s
=
len
r
,
r
j
+
dist
r
j
,
s
for  the  path  of
r
→
r
j
→
s
(c)
dist
r
,
s
=
len
r
,
s
for
s
∈
r
i
r
j
¯Table 2
Computation ofdistr,s for r∈rirj¯ and s∈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯.
Condition
dist
r
,
s
s
∈
S
k
r
i
⁡
∩
⁡
S
k
r
j
⁡
∩
⁡
S
r
i
r
j
¯
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
,
len
r
,
s
s
∈
S
k
r
i
⁡
∩
⁡
S
k
r
j
−
S
r
i
r
j
¯
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
r
j
+
dist
r
j
,
s
s
∈
S
k
r
i
⁡
∩
⁡
S
r
i
r
j
¯
−
S
k
r
j
dist
r
,
s
=
min
len
r
,
r
i
+
dist
r
i
,
s
,
len
r
,
s
s
∈
S
k
r
j
⁡
∩
⁡
S
r
i
r
j
¯
−
S
k
r
i
dist
r
,
s
=
min
len
r
,
r
j
+
dist
r
j
,
s
,
len
r
,
s
s
∈
S
k
r
i
−
S
k
r
j
⁡
∪
⁡
S
r
i
r
j
¯
dist
r
,
s
=
len
r
,
r
i
+
dist
r
i
,
s
s
∈
S
k
r
j
−
S
k
r
i
⁡
∪
⁡
S
r
i
r
j
¯
dist
r
,
s
=
len
r
,
r
j
+
dist
r
j
,
s
s
∈
S
r
i
r
j
¯
−
S
k
r
i
⁡
∪
⁡
S
k
r
j
dist
r
,
s
=
len
r
,
sAlgorithm 2: Basic_GNL k,R,S.
Input: k: number of inner objects retrieved for an outer object, R: set of outer objects, S: set of inner objects
Output: R⋉S: set of ordered pairs of outer object r∈R and inner object s∈Skr
(1)
Ψ
⁡
←
⁡
∅          ⁡⁡⁡⁡⁡  // kNN join result set Ψ is initialized to the empty set
(2)
// step 1: outer objectsri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯
(3)
R
¯
⁡
←
⁡
group
_
outer
_
objects
R
,
V
,
E  // group_outer_objects is explained in Algorithm 1
(4)
// step 2:kNN join is evaluated for each outer segment rirj¯∈R¯
(5)
for each outer segment rirj¯∈R¯ do
(6)
Ψrirj¯⁡←⁡kNN_joink,rirj¯,S⁡⁡  // kNN_join is explained in Algorithm 3
(7)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯        // Ψrirj¯=r,s∀r∈rirj¯,⁡∀s∈Skr
(8)
return Ψ         ⁡⁡⁡⁡⁡  // Ψ=r,s∀r∈R,∀s∈Skr is returned after all outer segments have been processed


## 4.3.kNN Join Algorithm

Algorithm2 describes the basic GNL algorithm, which employs the grouping of outer objects and shared execution to reduce the processing time. This algorithm comprises two steps. In the first step, the outer objects ri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯ (line 3). In the second step, the kNNs of the outer objects in the outer segment rirj¯ are retrieved using the shared execution method (line 6), as explained in Algorithm 3. An ordered pair comprising an outer object r∈rirj¯ and inner object s∈Skr is then added to the partial join result Ψrirj¯=r,s∀r∈rirj¯,∀s∈Skr. Finally, the kNN join result set Ψ=r,s∀r∈R,∀s∈Skr is returned after all the outer segments have been processed (line 8).Algorithm 3: kNN_joink,rirj¯,S.
Input: k: number of inner objects retrieved for an outer object, rirj¯: outer segment, S: set of inner objects
Output: rirj¯⋉S: set of ordered pairs of outer object r∈rirj¯ and inner object s∈Skr
(1)
if rirj¯=1 then              // rirj¯=1 denotes that rirj¯ contains only an outer object ri, that is, ri=rj
(2)
Skri⁡←⁡kNN_queryk,ri       ⁡⁡   // kNN query from ri is performed and its result is saved to Skri
(3)
Ψri⁡←⁡ri,ss∈Skri       ⁡⁡⁡   // a partial join result Ψri for ri is generated from Skri
(4)
return Ψri         ⁡    ⁡⁡ // a partial join result Ψri for ri is returned
(5)
else if rirj¯=2 then           ⁡ // rirj¯=2 denotes that rirj¯ contains only two outer objects ri and rj
(6)
Skri⁡←⁡kNN_queryk,ri        ⁡⁡  // kNN query from ri is performed, and its result is saved to Skri
(7)
Ψri⁡←⁡ri,ss∈Skri        ⁡⁡⁡  // a partial join result Ψri for ri is generated from Skri
(8)
Skrj⁡←⁡kNN_queryk,rj      ⁡    // kNN query from rj is performed, and its result is saved to Skrj
(9)
Ψrj⁡←⁡rj,ss∈Skrj       ⁡   // a partial join result Ψrj for rj is generated from Skrj
(10)
return Ψri⁡∪⁡Ψrj        ⁡ ⁡  // the union Ψri⁡∪⁡Ψrj of the partial join results for ri and rj is returned
(11)
else if rirj¯≥3 then          ⁡⁡  // rirj¯≥3 denotes that rirj¯ contains more than three outer objects
(12)
Skri⁡←⁡kNN_queryk,ri        ⁡⁡  // kNN query from ri is performed, and its result is saved to Skri
(13)
Ψri⁡←⁡ri,ss∈Skri       ⁡⁡⁡   // a partial join result Ψri for ri is generated from Skri
(14)
Skrj⁡←⁡kNN_queryk,rj       ⁡   // kNN query from rj is performed, and its result is saved to Skrj
(15)
Ψrj⁡←⁡rj,ss∈Skrj      ⁡    // a partial join result Ψrj for rj is generated from Skrj
(16)
Srirj¯⁡←⁡ss∈rirj¯        ⁡   // inner objects located in rirj¯ are retrieved
(17)
for each outer object r∈ri+1,…,rj−1 do  // k NNs of outer objects ri+1,…,rj−1 are retrieved from Skri⁡∪⁡Skrj⁡∪⁡Srirj¯
(18)
Skr⁡←⁡kNN_searchk,r,Skri⁡∪⁡Skrj⁡∪⁡Srirj¯  ⁡⁡// kNN_search is explained in Algorithm 4
(19)
Ψr⁡←⁡r,ss∈Skr           // a partial join result Ψr for r∈ri+1,…,rj−1 is generated from Skr
(20)
return Ψri⁡∪⁡Ψri+1⁡∪⁡⋯⁡∪⁡Ψrj     // the union of the partial join results for ri,ri+1,…,rj is returnedAlgorithm3 describes the kNN join for all outer objects ri,ri+1,…,rj in rirj¯. Three general cases are formally considered depending on the number of outer objects in rirj¯, that is, rirj¯=1, rirj¯=2, and rirj¯≥3, where rirj¯ returns the number of outer objects in rirj¯. rirj¯=1 denotes that rirj¯ contains only one outer object ri, rirj¯=2 denotes that rirj¯ contains only two outer objects ri and rj, and rirj¯≥3 denotes that rirj¯ contains more than three outer objects ri,ri+1,…,rj. If rirj¯=1, then the kNN query from ri is evaluated. In this study, INE [16] is employed to evaluate the kNN query. Naturally, INE can be replaced by other kNN algorithms [1, 2, 5, 13, 17–19]. A partial join result Ψri for ri is generated from Skri and returned (lines 1–4). Similarly, if rirj¯=2, then two kNN queries from ri and rj are evaluated. Partial join results Ψri and Ψrj for ri and rj are generated from Skri and Skrj, respectively; and their union is returned (lines 5–10). Finally, if rirj¯≥3, then two kNN queries from ri and rj are evaluated and a search for the inner objects located in rirj¯ is performed. The partial join results Ψri and Ψrj for ri and rj are generated from Skri and Skrj, respectively. For each outer object r∈ri+1,…,rj−1, the set of kNNs of r is retrieved from Skri, Skrj, and Srirj¯ (lines 17–19), as explained in Algorithm 4. Finally, the union of partial join results Ψri,Ψri+1,…,Ψrj is returned.Algorithm 4: kNN_searchk,r,Skri⁡∪⁡Skrj⁡∪⁡Srirj¯.
Input: k: number of inner objects retrieved for an outer object, r∈rirj¯: outer object, Skri⁡∪⁡Skrj⁡∪⁡Srirj¯: set of candidate inner objects
Output: Skr: set of k inner objects closest to r
(1)
S
k
r
⁡
←
⁡
∅  // Skr is initialized to the empty set
(2)
for each inner object s∈Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ do
(3)
// step 1:distr,s is computed according to the condition of s, see Table 2 for details.
(4)
if s∈Skri⁡∩⁡Skrj⁡∩⁡Srirj¯ then distr,s⁡←⁡minlenr,ri+distri,s,lenr,rj+distrj,s,lenr,s
(5)
else if s∈Skri⁡∩⁡Skrj−Srirj¯ then distr,s⁡←⁡minlenr,ri+distri,s,lenr,rj+distrj,s
(6)
else if s∈Skri⁡∩⁡Srirj¯−Skrj then distr,s⁡←⁡minlenr,ri+distri,s,lenr,s
(7)
else if s∈Skrj⁡∩⁡Srirj¯−Skri then distr,s⁡←⁡minlenr,rj+distrj,s,lenr,s
(8)
else if s∈Skri−Skrj⁡∪⁡Srirj¯ then distr,s⁡←⁡lenr,ri+distri,s
(9)
else if s∈Skrj−Skri⁡∪⁡Srirj¯ then distr,s⁡←⁡lenr,rj+distrj,s
(10)
else if s∈Srirj¯−Skri⁡∪⁡Skrj then distr,s⁡←⁡lenr,s
(11)
// step 2:s is added to Skr if it satisfies either of the following two conditions:
(12)
if Skr<k then
(13)
Skr⁡←⁡Skr⁡∪⁡s
(14)
else if Skr=k and distr,s<distr,skth then
(15)
Skr⁡←⁡Skr⁡∪⁡s−skth
(16)
return SkrAlgorithm4 describes the kNN search of an outer object r∈ri+1,…,rj−1. First, the set of kNNs of outer object r, Skr, is initialized to the empty set. The distance from r to a candidate inner object s is computed according to the condition of s (lines 3–10), as explained in Table 2. After computing distr,s, we can determine whether s is added to the candidate set Skr. If Skr<k, then s is simply added to Skr (lines 12-13). If Skr=k and distr,s<distr,skth, then s is added to Skr and skth is removed from Skr accordingly, where skth denotes the kth closest inner object to r, that is, Skr⁡←⁡Skr⁡∪⁡s−skth (lines 14-15). The set Skr of the kNNs of r is returned after all of the candidate inner objects in Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ have been considered (line 16).


## 4.4. Evaluation of an ExamplekNN Join Using the Basic GNL Method

We now discuss the evaluation of thekNN join example shown in Figure 3. We recall that R=r1,r2,r3,r4,r5,r6, S=s1,s2,s3,s4, and k=2 are given. Table 3 summarizes the computation of the kNN join R⋉S.Table 3
Computation of the examplekNN join R⋉S using the basic GNL method.
r
i
r
j
¯
r
i
r
j
S
k
r
i
S
k
r
j
S
r
i
r
j
¯
r
i
+
1
,
…
,
r
j
−
1
S
k
r
i
⁡
∪
⁡
S
k
r
j
⁡
∪
⁡
S
r
i
r
j
¯
r
1
r
5
r
4
¯
r
1
r
4
S
k
r
1
=
s
1
,
s
2
S
k
r
4
=
s
2
,
s
3
S
r
1
r
5
r
4
¯
=
∅
r
5
s
1
,
s
2
,
s
3
r
2
r
3
¯
r
2
r
3
S
k
r
2
=
s
3
,
s
4
S
k
r
3
=
s
3
,
s
4
S
r
2
r
3
¯
=
s
4
∅
Not applicable
r
6
r
6
r
6
S
k
r
6
=
s
2
,
s
3
S
k
r
6
=
s
2
,
s
3
S
r
6
=
∅
∅
Not applicableAs explained in Algorithm2, the basic GNL method first groups the outer objects in a vertex sequence into an outer segment. Therefore, R¯=r1r5r4¯,r2r3¯,r6 is generated from R=r1,r2,r3,r4,r5,r6, as shown in Figure 4. In this example, we process r1r5r4¯, r2r3¯, and r6 in this order. As explained in Algorithm 3, we process the outer segment differently according to the number of outer objects in the outer segment. Outer segment r1r5r4¯ contains three outer objects r1, r5, and r4, so two kNN queries are issued from r1 and r4, and the inner objects located in r1r5r4¯ are retrieved. We have Skr1=s1,s2, Skr4=s2,s3, and Sr1r5r4¯=∅, as shown in Table 3. Thus, Skr1=s1,s2 and Skr4=s2,s3 simply generate the partial join results Ψr1=r1,s1,r1,s2 and Ψr4=r4,s2,r4,s3, respectively.According to Lemma 1, we can retrieve thekNNs of outer object r5 from a set of candidate inner objects Skr1⁡∪⁡Skr4⁡∪⁡Sr1r5r4¯=s1,s2,s3 without issuing a kNN query for r5. Thus, we need to compute the distance from r5 to each candidate inner object s∈s1,s2,s3. Clearly, s1∈Skr1−Skr4⁡∪⁡Sr1r5r4¯ according to Table 3, so the distance from r5 to s1 is distr5,s1=lenr5,r1⁡+⁡distr1,s1=3, as shown in Figure 6(a). Similarly, s2∈Skr1⁡∩⁡Skr4−Sr1r5r4¯ according to Table 3, so the distance from r5 to s2 is distr5,s2=minlenr5,r1+distr1,s2,lenr5,r4+distr4,s2=min6,16=6, as shown in Figure 6(b). Finally, s3∈Skr4−Skr1⁡∪⁡Sr1r5r4¯ according to Table 3, so the distance from r5 to s3 is distr5,s3=lenr5,r4+distr4,s3=15, as shown in Figure 6(c). It should be noted that the shortest path from r5 to s3 is r5→r1→s3 rather than r5→r4→s3, and thus the shortest distance from r5 to s3 is distr5,s3=lenr5,r1⁡+⁡distr1,s3=9. However, this does not affect the correctness of the set of the kNNs of r5 because s3 does not belong to Skr1=s1,s2 so the path r5→r1→s3 does not have to be considered. Consequently, we have Skr5=s1,s2 from distr5,s1=3, distr5,s2=6, and distr5,s3=15, which generates the partial join result Ψr5=r5,s1,r5,s2.Figure 6
Computation of the distance fromr5 to s∈s1,s2,s3.
(a)
dist
r
5
,
s
1
=
3
for
s
1
∈
S
k
r
1
−
S
k
r
4
⁡
∪
⁡
S
r
1
r
5
r
4
¯
(b)
dist
r
5
,
s
2
=
6
for
s
2
∈
S
k
r
1
⁡
∩
⁡
S
k
r
4
−
S
r
1
r
5
r
4
¯
(c)
dist
r
5
,
s
3
=
15
for
s
3
∈
S
k
r
4
−
S
k
r
1
⁡
∪
⁡
S
r
1
r
5
r
4
¯Next, we compute the partial join results for the outer objects inr2r3¯. Outer segment r2r3¯ only contains two outer objects r2 and r3, so two kNN queries are issued from r2 and r3. Therefore, as shown in Table 3, we obtain Skr2=s3,s4 and Skr3=s3,s4, which directly generate the partial join results Ψr2=r2,s3,r2,s4 and Ψr3=r3,s3,r3,s4, respectively. Finally, we compute the partial join result for outer object r6, where a single kNN query is simply issued from r6. Therefore, as shown in Table 3, we obtain Skr6=s2,s3, which generates the partial join result Ψr6=r6,s2,r6,s3. Finally, we obtain the kNN join result that is the union of the partial join results for outer objects r1 to r6, as follows: (3)Ψ=Ψr1r5r4¯⁡∪⁡Ψr2r3¯⁡∪⁡Ψr6=r1,s1,r1,s2,r2,s3,r2,s4,r3,s3,r3,s4,r4,s2,r4,s3,r5,s1,r5,s2,r6,s2,r6,s3,where Ψr1r5r4¯=Ψr1⁡∪⁡Ψr5⁡∪⁡Ψr4 and Ψr2r3¯=Ψr2⁡∪⁡Ψr3.


## 5. GNL Method forkNN Joins in Road Networks

### 5.1. Avoiding RedundantkNN Queries

We present the GNL method to evaluate a smaller number ofkNN queries than the basic GNL method. To this end, we investigate the number of outer segments in vertex sequences that are adjacent to an intersection vertex. Let Ωvx be the number of outer segments in vertex sequences that are adjacent to an intersection vertex vx. If Ωvx=0, no kNN query is issued at vx. If Ωvx=1, a kNN is evaluated at ri, where it is assumed that an outer segment rirj¯ is in a vertex sequence adjacent to vx and that ri is closer to vx than rj. If Ωvx≥2, a kNN query is evaluated at vx instead of at ri. Figure 7 illustrates a simple example of the shared query processing to reduce the number of kNN queries used to evaluate the kNN join. Observe that there are two intersection vertices v2 and v5, both of which are adjacent to three vertex sequences v2v1v4v5¯, v2v5¯, and v2v3v6v5¯. In Figure 7(a), an outer segment r1r2¯ is in a vertex sequence v2v5¯ and we have Ωv2=1 and Ωv5=1. Therefore, two kNN queries are evaluated at r1 and r2. However, in Figure 7(b), outer segments r1r2¯ and r3r4¯ are in vertex sequences v2v5¯ and v2v3v6v5¯, respectively, both of which are adjacent to v2 and v5, and we have Ωv2=2 and Ωv5=2. Therefore, the GNL method evaluates only two kNN queries at v2 and v5, instead of evaluating four kNN queries at r1, r2, r3, and r4.Figure 7
Example of sharedkNN query processing of the GNL method: (a) evaluating two kNN queries at r1 and r2 and (b) evaluating two kNN queries at v2 and v5.
(a)
(b)Algorithm 5: GNL k,R,S.
Input: k: number of inner objects retrieved for an outer object, R: set of outer objects, S: set of inner objects
Output: R⋉S: set of ordered pairs of outer object r∈R and inner object s∈Skr
(1)
Ψ
⁡
←
⁡
∅              ⁡⁡⁡  // kNN join result set Ψ is initialized to the empty set
(2)
// step 1: outer objectsri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯
(3)
R
¯
⁡
←
⁡
group
_
outer
_
objects
R
,
V
,
E   ⁡⁡⁡⁡  // group_outer_objects is explained in Algorithm 1
(4)
// step 2:kNN join is evaluated for each outer segment rirj¯∈R¯
(5)
for each outer segmentrirj¯∈R¯ do
(6)
if rirj¯=1 then         ⁡⁡⁡  // see Figures 8(a) to 8(d)
(7)
Skri⁡←⁡kNN_queryk,ri        // kNN query from ri is performed, and its result is saved to Skri
(8)
Ψri⁡←⁡ri,ss∈Skri       ⁡ // a partial join result Ψri for ri is generated from Skri
(9)
Ψ⁡←⁡Ψ⁡∪⁡Ψri
(10)
else if rirj¯≥2 then          // it is assumed that rirj¯ belongs to vlvm¯ and that ri (rj) is close to vl vm
(11)
if Ωvl≥2 and Ωvm≥2 then   ⁡ // see Figure 9(a)
(12)
Skvl⁡←⁡kNN_queryk,vl       // result of kNN query at vl is reused for other outer segment(s)
(13)
Skvm⁡←⁡kNN_queryk,vm     ⁡⁡ // result of kNN query at vm is reused for other outer segment(s)
(14)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skvl⁡∪⁡Skvm⁡∪⁡Svlvm¯  // refer to Algorithm 6
(15)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯
(16)
else if Ωvl≥2 and Ωvm=1 then ⁡ // see Figure 9(b)
(17)
Skvl⁡←⁡kNN_queryk,vl       // result of kNN query at vl is reused for other outer segment(s)
(18)
Skrj⁡←⁡kNN_queryk,rj    ⁡⁡⁡⁡  // result of kNN query at rj is not reused
(19)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skvl⁡∪⁡Skrj⁡∪⁡Svlrj¯⁡⁡  // refer to Algorithm 6
(20)
Ψ⁡←⁡Ψ∪Ψrirj¯
(21)
else if Ωvl=1 and Ωvm≥2 then ⁡ // see Figure 9(c)
(22)
Skri⁡←⁡kNN_queryk,ri       // result of kNN query at ri is not reused
(23)
Skvm⁡←⁡kNN_queryk,vm    ⁡  // result of kNN query at vm is reused for other outer segment(s)
(24)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skri⁡∪⁡Skvm⁡∪⁡Srivm¯  // refer to Algorithm 6
(25)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯
(26)
else if Ωvl=1 and Ωvm=1 then  // see Figure 9(d)
(27)
Skri⁡←⁡kNN_queryk,ri       // result of kNN query at ri is not reused
(28)
Skrj⁡←⁡kNN_queryk,rj     ⁡⁡⁡⁡ // result of kNN query at rj is not reused
(29)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ ⁡⁡⁡ // refer to Algorithm 6
(30)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯
(31)
return Ψ  // Ψ=r,s∀r∈R,∀s∈Skr is returned after all outer segments have been processedAlgorithm5 describes the GNL algorithm that employs an optimized number of kNN queries to evaluate kNN joins by exploiting grouping and shared execution. Similar to the basic GNL algorithm, this algorithm comprises two steps. In the first step, the outer objects ri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯ (line 3). In the second step, the GNL algorithm considers rirj¯=1 and rirj¯≥2 as shown in Figures 8 and 9, respectively, to use the shared execution for avoiding redundant kNN queries.Figure8 shows that rirj¯ contains an outer object only, that is, rirj¯=1. For the case of rirj¯=1, a kNN query is evaluated at ri, whose result is not reused (lines 6–9).Figure9 shows that rirj¯ contains more than two outer objects, that is, rirj¯≥2, meaning that two kNN queries are required to retrieve the k inner objects closest to each outer object r∈rirj¯. As shown in Figure 9(a), for the case of Ωvl≥2 and Ωvm≥2, two kNN queries at vl and vm are evaluated, whose results are reused for the other outer segments adjacent to vl or vm (lines 11–15). As shown in Figure 9(b), for the case of Ωvl≥2 and Ωvm=1, two kNN queries at vl and rj are evaluated, and the query result at vl is reused for the other outer segment(s) adjacent to vl (lines 16–20). As shown in Figure 9(c), for the case of Ωvl=1 and Ωvm≥2, two kNN queries at ri and vm are evaluated, and the query result at vm is reused for the other outer segment(s) adjacent to vm (lines 21–25). Finally, as shown in Figure 9(d), for the case of Ωvl=1 and Ωvm=1, two kNN queries at ri and rj are evaluated, whose results are not reused (lines 26–30).Figure 8
r
i
r
j
¯
=
1. (a) Ωvl≥2andΩvm≥2, (b) Ωvl≥2andΩvm=1, (c) Ωvl=1andΩvm≥2,and(d) Ωvl=1andΩvm=1.
(a)
(b)
(c)
(d)Figure 9
r
i
r
j
¯
≥
2. (a) Ωvl≥2andΩvm≥2, (b) Ωvl≥2andΩvm=1, (c) Ωvl=1andΩvm≥2,and(d) Ωvl=1andΩvm=1.
(a)
(b)
(c)
(d)Algorithm 6: kNN_search_of_outer_objectsk,rirj¯,Skcnd.
Input: k: number of inner objects retrieved for an outer object, rirj¯: outer segment, Skcnd: set of candidate inner objects
Output: Ψrirj¯: a partial join result for outer objects in rirj¯
(1)
Ψ
r
i
r
j
¯
⁡
←
⁡
∅      ⁡   // Ψrirj¯ is initialized to the empty set
(2)
for each outer object r∈rirj¯ do
(3)
Skr⁡←⁡kNN_searchk,r,Skcnd  // kNN_search in Algorithm 4 is performed
(4)
Ψr⁡←⁡r,ss∈Skr ⁡⁡⁡⁡   // a partial join result Ψr for r is generated from Skr
(5)
Ψrirj¯⁡←⁡Ψrirj¯⁡∪⁡Ψr
(6)
return Ψrirj¯  // Ψrirj¯=r,s∀r∈rirj¯,∀s∈Skr is returned after all outer objects in rirj¯ have been processedAlgorithm6 describes how to find the k inner objects closest to each outer object r∈rirj¯, where the kNN search of the outer object is performed using Algorithm 4.To avoid evaluating redundantkNN queries, we present a simple heuristic so that the redundant kNN queries are not evaluated at locations close to terminal vertices. For example, as shown in Figure 10, the graph has one intersection vertex vx and three terminal vertices v1, v2, and v3. In this example, the kNN query at ri is redundant because it holds that Skr⁡⊆⁡Skrj⁡∪⁡Sv1rj¯ for each outer object r∈rirj¯.The GNL method employs an optimized number ofkNN queries to evaluate kNN joins while exploiting grouping and shared execution. For this, we consider the eight cases in Figures 8 and 9. For each case, Table 4 investigates the number NGNL of kNN queries evaluated by the GNL method and the minimum number NOPT of kNN queries evaluated by the virtual optimal method. The values in parentheses indicate locations of kNN queries evaluated by the GNL and virtual optimal methods. In Figure 8(a), the GNL algorithm evaluates three kNN queries at vl, vm, and ri. However, the kNN query at ri is redundant because the query results at vl and vm can be reused to find the k inner objects closest to ri. This shows that the GNL algorithm does not always use the minimum number of kNN queries to evaluate the kNN join, as previously mentioned. However, for Figures 8(b) to 8(d) and 9(a) to 9(d), the GNL method evaluates the same number of kNN queries as the virtual optimal method.Figure 10
S
k
r
⁡
⊆
⁡
S
k
r
j
⁡
∪
⁡
S
v
1
r
j
¯ for each outer object r∈rirj¯.Table 4
Investigation ofNGNL and NOPT.
Condition
N
GNL (query locations)
N
OPT (query locations)
DoesNGNL equal NOPT?
Figure8(a)
3 (vl, vm, ri)
2 (vl,vm)
No
Figure8(b)
2 (vl, ri)
2 (vl, ri)
Yes
Figure8(c)
2 (ri, vm)
2 (ri, vm)
Yes
Figure8(d)
1 (ri)
1 (ri)
Yes
Figure9(a)
2 (vl, vm)
2 (vl, vm)
Yes
Figure9(b)
2 (vl, rj)
2 (vl, rj)
Yes
Figure9(c)
2 (ri, vm)
2 (ri, vm)
Yes
Figure9(d)
2 (ri, rj)
2 (ri, rj)
Yes


### 5.2. Evaluation of an ExamplekNN Join Using the GNL Method

Returning to the examplekNN join in Figure 3, we reevaluate the kNN join to show that the GNL method evaluates a smaller number of kNN queries than the basic GNL method. We recall that the basic GNL method evaluates five kNN queries at r1, r2, r3, r4, and r6 to evaluate the kNN join, as described in Section 4.4. However, the GNL method evaluates three kNN queries at intersection vertices v1 and v3, and an outer object r6 because Ωv1=Ωv3=3 and r6¯=1 are given. Specifically, the kNN query at v1 replaces the two kNN queries that the basic GNL method issues at r3 and r4. Similarly, the kNN query at v3 replaces the two kNN queries that the basic GNL method issues at r1 and r2.We processr1r5r4¯, r2r3¯, and r6 in this order. We retrieve kNNs of each outer object in the segments r1r5r4¯, r2r3¯, and r6 from a set of candidate inner objects. First, we retrieve two NNs of an outer object r1 in r1r5r4¯. For this, we should determine distr1,s1, distr1,s2, and distr1,s3 to retrieve two inner objects closest to r1. According to Table 5, s1∈Sv1v2v3¯−Skv1⁡∪⁡Skv3, and the distance from r1 to s1 is distr1,s1=lenr1,s1=2. Similarly, according to Table 5, s2∈Skv1⁡∩⁡Skv3⁡∩⁡Sv1v2v3¯, and the distance from r1 to s2 is distr1,s2=minlenr1,v1+distv1,s2,lenr1,v3⁡+⁡distv3,s2,lenr1,s2=17,9,5=5. Finally, according to Table 5, s3∈Skv1⁡∩⁡Skv3−Sv1v2v3¯, and the distance from r1 to s3 is distr1,s3=minlenr1,v1+distv1,s3,lenr1,v3+distv3,s3=16,8=8. Consequently, we have Skr1=s1,s2 from distr1,s1=2, distr1,s2=5, and distr1,s3=8, which generates the partial join result Ψr1=r1,s1,r1,s2. In the same manner, we can compute the distance from an outer object r∈r2,r3,r4,r5,r6 to each of its candidate objects and determine the two inner objects closest to r. Table 6 presents a summary of computing the distances from an outer object r∈r1,r2,r3,r4,r5,r6 to its candidate objects and determining the two inner objects closest to r. Note that the two inner objects s2 and s3 closest to r6 are retrieved directly from the kNN query at r6. Finally, using the GNL method, we can obtain the kNN join result Ψ=r1,s1,r1,s2,r2,s3,r2,s4,r3,s3,r3,s4,r4,s2,r4,s3,r5,s1,r5,s2,r6,s2,r6,s3.Table 5
Computation of the examplekNN join R⋉S using the GNL method.
r
i
r
j
¯
v
l
v
m
S
k
v
l
S
k
v
m
S
v
l
⋯
v
m
¯
r
i
,
r
i
+
1
,
…
,
r
j
S
k
v
l
⁡
∪
⁡
S
k
v
m
⁡
∪
⁡
S
v
l
…
v
m
¯
r
1
r
5
r
4
¯
v
1
v
3
S
k
v
1
=
s
2
,
s
3
S
k
v
3
=
s
2
,
s
3
S
v
1
v
2
v
3
¯
=
s
1
,
s
2
r
1
,
r
5
,
r
4
S
k
v
1
⁡
∪
⁡
S
k
v
3
⁡
∪
⁡
S
v
1
v
2
v
3
¯
=
s
1
,
s
2
,
s
3
r
2
r
3
¯
v
1
v
3
S
k
v
1
=
s
2
,
s
3
S
k
v
3
=
s
2
,
s
3
S
v
1
v
4
v
3
¯
=
s
3
,
s
4
r
2
,
r
3
S
k
v
1
⁡
∪
⁡
S
k
v
3
⁡
∪
⁡
S
v
1
v
4
v
3
¯
=
s
2
,
s
3
,
s
4Table 6
Summary of computing the examplekNN join R⋉S.
r
i
r
j
¯
r
∈
r
i
r
j
¯
s
Condition ofs
dist
r
,
s
S
k
r
Ψ
r
r
1
r
5
r
4
¯
r
1
s
1
s
1
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∪
⁡
S
k
v
3
dist
r
1
,
s
1
=
2
S
k
r
1
=
s
1
,
s
2
Ψ
r
1
=
r
1
,
s
1
,
r
1
,
s
2
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
1
,
s
2
=
5
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
1
,
s
3
=
8
r
5
s
1
s
1
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∪
⁡
S
k
v
3
dist
r
5
,
s
1
=
3
S
k
r
5
=
s
1
,
s
2
Ψ
r
5
=
r
5
,
s
1
,
r
5
,
s
2
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
5
,
s
2
=
6
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
5
,
s
3
=
9
r
4
s
1
s
1
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∪
⁡
S
k
v
3
dist
r
4
,
s
1
=
10
S
k
r
4
=
s
2
,
s
3
Ψ
r
4
=
r
4
,
s
2
,
r
4
,
s
3
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
4
,
s
2
=
9
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
4
,
s
3
=
8
r
2
r
3
¯
r
2
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
2
,
s
2
=
9
S
k
r
2
=
s
3
,
s
4
Ψ
r
2
=
r
2
,
s
3
,
r
2
,
s
4
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
2
,
s
3
=
6
s
4
s
4
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∩
⁡
S
k
v
3
dist
r
2
,
s
4
=
3
r
3
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
3
,
s
2
=
13
S
k
r
3
=
s
3
,
s
4
Ψ
r
3
=
r
3
,
s
3
,
r
3
,
s
4
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
3
,
s
3
=
12
s
4
s
4
∈
S
v
1
v
4
v
3
¯
−
S
k
v
1
⁡
∩
⁡
S
k
v
3
dist
r
3
,
s
4
=
3
r
6
r
6
s
2
s
2
∈
S
k
r
6
dist
r
6
,
s
2
=
5
S
k
r
6
=
s
2
,
s
3
Ψ
r
6
=
r
6
,
s
2
,
r
6
,
s
3
s
3
s
3
∈
S
k
r
6
dist
r
6
,
s
3
=
4


## 5.1. Avoiding RedundantkNN Queries

We present the GNL method to evaluate a smaller number ofkNN queries than the basic GNL method. To this end, we investigate the number of outer segments in vertex sequences that are adjacent to an intersection vertex. Let Ωvx be the number of outer segments in vertex sequences that are adjacent to an intersection vertex vx. If Ωvx=0, no kNN query is issued at vx. If Ωvx=1, a kNN is evaluated at ri, where it is assumed that an outer segment rirj¯ is in a vertex sequence adjacent to vx and that ri is closer to vx than rj. If Ωvx≥2, a kNN query is evaluated at vx instead of at ri. Figure 7 illustrates a simple example of the shared query processing to reduce the number of kNN queries used to evaluate the kNN join. Observe that there are two intersection vertices v2 and v5, both of which are adjacent to three vertex sequences v2v1v4v5¯, v2v5¯, and v2v3v6v5¯. In Figure 7(a), an outer segment r1r2¯ is in a vertex sequence v2v5¯ and we have Ωv2=1 and Ωv5=1. Therefore, two kNN queries are evaluated at r1 and r2. However, in Figure 7(b), outer segments r1r2¯ and r3r4¯ are in vertex sequences v2v5¯ and v2v3v6v5¯, respectively, both of which are adjacent to v2 and v5, and we have Ωv2=2 and Ωv5=2. Therefore, the GNL method evaluates only two kNN queries at v2 and v5, instead of evaluating four kNN queries at r1, r2, r3, and r4.Figure 7
Example of sharedkNN query processing of the GNL method: (a) evaluating two kNN queries at r1 and r2 and (b) evaluating two kNN queries at v2 and v5.
(a)
(b)Algorithm 5: GNL k,R,S.
Input: k: number of inner objects retrieved for an outer object, R: set of outer objects, S: set of inner objects
Output: R⋉S: set of ordered pairs of outer object r∈R and inner object s∈Skr
(1)
Ψ
⁡
←
⁡
∅              ⁡⁡⁡  // kNN join result set Ψ is initialized to the empty set
(2)
// step 1: outer objectsri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯
(3)
R
¯
⁡
←
⁡
group
_
outer
_
objects
R
,
V
,
E   ⁡⁡⁡⁡  // group_outer_objects is explained in Algorithm 1
(4)
// step 2:kNN join is evaluated for each outer segment rirj¯∈R¯
(5)
for each outer segmentrirj¯∈R¯ do
(6)
if rirj¯=1 then         ⁡⁡⁡  // see Figures 8(a) to 8(d)
(7)
Skri⁡←⁡kNN_queryk,ri        // kNN query from ri is performed, and its result is saved to Skri
(8)
Ψri⁡←⁡ri,ss∈Skri       ⁡ // a partial join result Ψri for ri is generated from Skri
(9)
Ψ⁡←⁡Ψ⁡∪⁡Ψri
(10)
else if rirj¯≥2 then          // it is assumed that rirj¯ belongs to vlvm¯ and that ri (rj) is close to vl vm
(11)
if Ωvl≥2 and Ωvm≥2 then   ⁡ // see Figure 9(a)
(12)
Skvl⁡←⁡kNN_queryk,vl       // result of kNN query at vl is reused for other outer segment(s)
(13)
Skvm⁡←⁡kNN_queryk,vm     ⁡⁡ // result of kNN query at vm is reused for other outer segment(s)
(14)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skvl⁡∪⁡Skvm⁡∪⁡Svlvm¯  // refer to Algorithm 6
(15)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯
(16)
else if Ωvl≥2 and Ωvm=1 then ⁡ // see Figure 9(b)
(17)
Skvl⁡←⁡kNN_queryk,vl       // result of kNN query at vl is reused for other outer segment(s)
(18)
Skrj⁡←⁡kNN_queryk,rj    ⁡⁡⁡⁡  // result of kNN query at rj is not reused
(19)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skvl⁡∪⁡Skrj⁡∪⁡Svlrj¯⁡⁡  // refer to Algorithm 6
(20)
Ψ⁡←⁡Ψ∪Ψrirj¯
(21)
else if Ωvl=1 and Ωvm≥2 then ⁡ // see Figure 9(c)
(22)
Skri⁡←⁡kNN_queryk,ri       // result of kNN query at ri is not reused
(23)
Skvm⁡←⁡kNN_queryk,vm    ⁡  // result of kNN query at vm is reused for other outer segment(s)
(24)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skri⁡∪⁡Skvm⁡∪⁡Srivm¯  // refer to Algorithm 6
(25)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯
(26)
else if Ωvl=1 and Ωvm=1 then  // see Figure 9(d)
(27)
Skri⁡←⁡kNN_queryk,ri       // result of kNN query at ri is not reused
(28)
Skrj⁡←⁡kNN_queryk,rj     ⁡⁡⁡⁡ // result of kNN query at rj is not reused
(29)
Ψrirj¯⁡←⁡kNN_search_of_outer_objectsk,rirj¯,Skri⁡∪⁡Skrj⁡∪⁡Srirj¯ ⁡⁡⁡ // refer to Algorithm 6
(30)
Ψ⁡←⁡Ψ⁡∪⁡Ψrirj¯
(31)
return Ψ  // Ψ=r,s∀r∈R,∀s∈Skr is returned after all outer segments have been processedAlgorithm5 describes the GNL algorithm that employs an optimized number of kNN queries to evaluate kNN joins by exploiting grouping and shared execution. Similar to the basic GNL algorithm, this algorithm comprises two steps. In the first step, the outer objects ri,ri+1,…,rj in a vertex sequence are grouped into an outer segment rirj¯ (line 3). In the second step, the GNL algorithm considers rirj¯=1 and rirj¯≥2 as shown in Figures 8 and 9, respectively, to use the shared execution for avoiding redundant kNN queries.Figure8 shows that rirj¯ contains an outer object only, that is, rirj¯=1. For the case of rirj¯=1, a kNN query is evaluated at ri, whose result is not reused (lines 6–9).Figure9 shows that rirj¯ contains more than two outer objects, that is, rirj¯≥2, meaning that two kNN queries are required to retrieve the k inner objects closest to each outer object r∈rirj¯. As shown in Figure 9(a), for the case of Ωvl≥2 and Ωvm≥2, two kNN queries at vl and vm are evaluated, whose results are reused for the other outer segments adjacent to vl or vm (lines 11–15). As shown in Figure 9(b), for the case of Ωvl≥2 and Ωvm=1, two kNN queries at vl and rj are evaluated, and the query result at vl is reused for the other outer segment(s) adjacent to vl (lines 16–20). As shown in Figure 9(c), for the case of Ωvl=1 and Ωvm≥2, two kNN queries at ri and vm are evaluated, and the query result at vm is reused for the other outer segment(s) adjacent to vm (lines 21–25). Finally, as shown in Figure 9(d), for the case of Ωvl=1 and Ωvm=1, two kNN queries at ri and rj are evaluated, whose results are not reused (lines 26–30).Figure 8
r
i
r
j
¯
=
1. (a) Ωvl≥2andΩvm≥2, (b) Ωvl≥2andΩvm=1, (c) Ωvl=1andΩvm≥2,and(d) Ωvl=1andΩvm=1.
(a)
(b)
(c)
(d)Figure 9
r
i
r
j
¯
≥
2. (a) Ωvl≥2andΩvm≥2, (b) Ωvl≥2andΩvm=1, (c) Ωvl=1andΩvm≥2,and(d) Ωvl=1andΩvm=1.
(a)
(b)
(c)
(d)Algorithm 6: kNN_search_of_outer_objectsk,rirj¯,Skcnd.
Input: k: number of inner objects retrieved for an outer object, rirj¯: outer segment, Skcnd: set of candidate inner objects
Output: Ψrirj¯: a partial join result for outer objects in rirj¯
(1)
Ψ
r
i
r
j
¯
⁡
←
⁡
∅      ⁡   // Ψrirj¯ is initialized to the empty set
(2)
for each outer object r∈rirj¯ do
(3)
Skr⁡←⁡kNN_searchk,r,Skcnd  // kNN_search in Algorithm 4 is performed
(4)
Ψr⁡←⁡r,ss∈Skr ⁡⁡⁡⁡   // a partial join result Ψr for r is generated from Skr
(5)
Ψrirj¯⁡←⁡Ψrirj¯⁡∪⁡Ψr
(6)
return Ψrirj¯  // Ψrirj¯=r,s∀r∈rirj¯,∀s∈Skr is returned after all outer objects in rirj¯ have been processedAlgorithm6 describes how to find the k inner objects closest to each outer object r∈rirj¯, where the kNN search of the outer object is performed using Algorithm 4.To avoid evaluating redundantkNN queries, we present a simple heuristic so that the redundant kNN queries are not evaluated at locations close to terminal vertices. For example, as shown in Figure 10, the graph has one intersection vertex vx and three terminal vertices v1, v2, and v3. In this example, the kNN query at ri is redundant because it holds that Skr⁡⊆⁡Skrj⁡∪⁡Sv1rj¯ for each outer object r∈rirj¯.The GNL method employs an optimized number ofkNN queries to evaluate kNN joins while exploiting grouping and shared execution. For this, we consider the eight cases in Figures 8 and 9. For each case, Table 4 investigates the number NGNL of kNN queries evaluated by the GNL method and the minimum number NOPT of kNN queries evaluated by the virtual optimal method. The values in parentheses indicate locations of kNN queries evaluated by the GNL and virtual optimal methods. In Figure 8(a), the GNL algorithm evaluates three kNN queries at vl, vm, and ri. However, the kNN query at ri is redundant because the query results at vl and vm can be reused to find the k inner objects closest to ri. This shows that the GNL algorithm does not always use the minimum number of kNN queries to evaluate the kNN join, as previously mentioned. However, for Figures 8(b) to 8(d) and 9(a) to 9(d), the GNL method evaluates the same number of kNN queries as the virtual optimal method.Figure 10
S
k
r
⁡
⊆
⁡
S
k
r
j
⁡
∪
⁡
S
v
1
r
j
¯ for each outer object r∈rirj¯.Table 4
Investigation ofNGNL and NOPT.
Condition
N
GNL (query locations)
N
OPT (query locations)
DoesNGNL equal NOPT?
Figure8(a)
3 (vl, vm, ri)
2 (vl,vm)
No
Figure8(b)
2 (vl, ri)
2 (vl, ri)
Yes
Figure8(c)
2 (ri, vm)
2 (ri, vm)
Yes
Figure8(d)
1 (ri)
1 (ri)
Yes
Figure9(a)
2 (vl, vm)
2 (vl, vm)
Yes
Figure9(b)
2 (vl, rj)
2 (vl, rj)
Yes
Figure9(c)
2 (ri, vm)
2 (ri, vm)
Yes
Figure9(d)
2 (ri, rj)
2 (ri, rj)
Yes


## 5.2. Evaluation of an ExamplekNN Join Using the GNL Method

Returning to the examplekNN join in Figure 3, we reevaluate the kNN join to show that the GNL method evaluates a smaller number of kNN queries than the basic GNL method. We recall that the basic GNL method evaluates five kNN queries at r1, r2, r3, r4, and r6 to evaluate the kNN join, as described in Section 4.4. However, the GNL method evaluates three kNN queries at intersection vertices v1 and v3, and an outer object r6 because Ωv1=Ωv3=3 and r6¯=1 are given. Specifically, the kNN query at v1 replaces the two kNN queries that the basic GNL method issues at r3 and r4. Similarly, the kNN query at v3 replaces the two kNN queries that the basic GNL method issues at r1 and r2.We processr1r5r4¯, r2r3¯, and r6 in this order. We retrieve kNNs of each outer object in the segments r1r5r4¯, r2r3¯, and r6 from a set of candidate inner objects. First, we retrieve two NNs of an outer object r1 in r1r5r4¯. For this, we should determine distr1,s1, distr1,s2, and distr1,s3 to retrieve two inner objects closest to r1. According to Table 5, s1∈Sv1v2v3¯−Skv1⁡∪⁡Skv3, and the distance from r1 to s1 is distr1,s1=lenr1,s1=2. Similarly, according to Table 5, s2∈Skv1⁡∩⁡Skv3⁡∩⁡Sv1v2v3¯, and the distance from r1 to s2 is distr1,s2=minlenr1,v1+distv1,s2,lenr1,v3⁡+⁡distv3,s2,lenr1,s2=17,9,5=5. Finally, according to Table 5, s3∈Skv1⁡∩⁡Skv3−Sv1v2v3¯, and the distance from r1 to s3 is distr1,s3=minlenr1,v1+distv1,s3,lenr1,v3+distv3,s3=16,8=8. Consequently, we have Skr1=s1,s2 from distr1,s1=2, distr1,s2=5, and distr1,s3=8, which generates the partial join result Ψr1=r1,s1,r1,s2. In the same manner, we can compute the distance from an outer object r∈r2,r3,r4,r5,r6 to each of its candidate objects and determine the two inner objects closest to r. Table 6 presents a summary of computing the distances from an outer object r∈r1,r2,r3,r4,r5,r6 to its candidate objects and determining the two inner objects closest to r. Note that the two inner objects s2 and s3 closest to r6 are retrieved directly from the kNN query at r6. Finally, using the GNL method, we can obtain the kNN join result Ψ=r1,s1,r1,s2,r2,s3,r2,s4,r3,s3,r3,s4,r4,s2,r4,s3,r5,s1,r5,s2,r6,s2,r6,s3.Table 5
Computation of the examplekNN join R⋉S using the GNL method.
r
i
r
j
¯
v
l
v
m
S
k
v
l
S
k
v
m
S
v
l
⋯
v
m
¯
r
i
,
r
i
+
1
,
…
,
r
j
S
k
v
l
⁡
∪
⁡
S
k
v
m
⁡
∪
⁡
S
v
l
…
v
m
¯
r
1
r
5
r
4
¯
v
1
v
3
S
k
v
1
=
s
2
,
s
3
S
k
v
3
=
s
2
,
s
3
S
v
1
v
2
v
3
¯
=
s
1
,
s
2
r
1
,
r
5
,
r
4
S
k
v
1
⁡
∪
⁡
S
k
v
3
⁡
∪
⁡
S
v
1
v
2
v
3
¯
=
s
1
,
s
2
,
s
3
r
2
r
3
¯
v
1
v
3
S
k
v
1
=
s
2
,
s
3
S
k
v
3
=
s
2
,
s
3
S
v
1
v
4
v
3
¯
=
s
3
,
s
4
r
2
,
r
3
S
k
v
1
⁡
∪
⁡
S
k
v
3
⁡
∪
⁡
S
v
1
v
4
v
3
¯
=
s
2
,
s
3
,
s
4Table 6
Summary of computing the examplekNN join R⋉S.
r
i
r
j
¯
r
∈
r
i
r
j
¯
s
Condition ofs
dist
r
,
s
S
k
r
Ψ
r
r
1
r
5
r
4
¯
r
1
s
1
s
1
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∪
⁡
S
k
v
3
dist
r
1
,
s
1
=
2
S
k
r
1
=
s
1
,
s
2
Ψ
r
1
=
r
1
,
s
1
,
r
1
,
s
2
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
1
,
s
2
=
5
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
1
,
s
3
=
8
r
5
s
1
s
1
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∪
⁡
S
k
v
3
dist
r
5
,
s
1
=
3
S
k
r
5
=
s
1
,
s
2
Ψ
r
5
=
r
5
,
s
1
,
r
5
,
s
2
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
5
,
s
2
=
6
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
5
,
s
3
=
9
r
4
s
1
s
1
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∪
⁡
S
k
v
3
dist
r
4
,
s
1
=
10
S
k
r
4
=
s
2
,
s
3
Ψ
r
4
=
r
4
,
s
2
,
r
4
,
s
3
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
4
,
s
2
=
9
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
4
,
s
3
=
8
r
2
r
3
¯
r
2
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
2
,
s
2
=
9
S
k
r
2
=
s
3
,
s
4
Ψ
r
2
=
r
2
,
s
3
,
r
2
,
s
4
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
2
,
s
3
=
6
s
4
s
4
∈
S
v
1
v
2
v
3
¯
−
S
k
v
1
⁡
∩
⁡
S
k
v
3
dist
r
2
,
s
4
=
3
r
3
s
2
s
2
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
−
S
v
1
v
2
v
3
¯
dist
r
3
,
s
2
=
13
S
k
r
3
=
s
3
,
s
4
Ψ
r
3
=
r
3
,
s
3
,
r
3
,
s
4
s
3
s
3
∈
S
k
v
1
⁡
∩
⁡
S
k
v
3
⁡
∩
⁡
S
v
1
v
2
v
3
¯
dist
r
3
,
s
3
=
12
s
4
s
4
∈
S
v
1
v
4
v
3
¯
−
S
k
v
1
⁡
∩
⁡
S
k
v
3
dist
r
3
,
s
4
=
3
r
6
r
6
s
2
s
2
∈
S
k
r
6
dist
r
6
,
s
2
=
5
S
k
r
6
=
s
2
,
s
3
Ψ
r
6
=
r
6
,
s
2
,
r
6
,
s
3
s
3
s
3
∈
S
k
r
6
dist
r
6
,
s
3
=
4


## 6. Performance Evaluation

In this section, we present our empirical analysis of the GNL method, where the experimental settings are given in Section6.1 and the experimental results in Section 6.2.


### 6.1. Experimental Settings

In the experiments, we use three real-life roadmaps freely available in [27]. The first road map comprising 175,813 vertices and 179,179 edges includes major roads (e.g., highways) in North America (NA). The second road map comprising 174,956 vertices and 223,001 edges includes major roads (e.g., city streets) in San Francisco (SF), California. The third road map comprising 18,263 vertices and 23,874 edges includes major roads (e.g., city streets) in San Joaquin County (SJ), California. The numbers of vertex sequences in NA, SF, and SJ are 12,416, 192,276, and 20,040, respectively. The settings of the experimental parameters are given in Table 7.Table 7
Experimental parameter settings.
Parameter
Range
Number of requested NNs (k)
1, 10,30, 50, 100 for NA and SF
1, 5,10, 30, 50 for SJ
Numbers of outer objectsR and inner objects S
1, 3,5, 7, 10 ×104 for NA and SF
1, 3,5, 7, 10 ×103 for SJ
Distributions of outer objects and inner objects
(C)entroid, (U)niform
Real-life roadmaps
NA, SF, SJThe positions of both the outer objects and inner objects follow either a centroid or uniform distribution. The centroid dataset is generated so that it resembles real-world data. First, 10 centroids are selected randomly, and the objects around each centroid follow the Gaussian distribution, where the mean is set to the centroid and the standard deviation is set to 1% of the side length of the data universe. In each experiment, we vary a single parameter within the range shown in Table7, while keeping the other parameters at the default values shown in bold. The outer objects and inner objects follow a centroid distribution unless stated otherwise.We implement and evaluate two versions of the GNL method, that is, the basic GNL and GNL methods. As a benchmark for our proposed method, we use a baseline method that computes thekNNs of every outer object using INE [16]. The three methods are implemented with the maximize speed option using C++ in Visual Studio 2015 and run on a desktop PC running Windows 10 operating system with 32 GB RAM and a quad-core processor (i7-6700 K) at 4 GHz. We consider that the indexing structures of all techniques should be memory resident to ensure responsive query processing, which is assumed recently in many studies [1, 4] and is crucial to online map services and commercial navigation systems. We determine the average values based on 10 experiments.


### 6.2. Experimental Results

Figure11 compares the query processing times using the baseline, basic GNL, and GNL methods when evaluating kNN joins in the NA road map, where each chart illustrates the effect of changing one of the parameters in Table 7. The values in parentheses indicate the numbers of kNN queries that are evaluated by the basic GNL and GNL methods to compute the kNN joins. The numbers of kNN queries evaluated by the baseline method to compute the kNN joins are omitted because the numbers of the kNN queries using this method equal the numbers of the outer objects. Figure 11(a) shows the query processing time as a function of the number of requested NNs, that is, k. The processing times using all the methods increase slightly with k. However, the GNL method shows the best performance, and the processing times using the GNL method are up to 80 times shorter than those using the baseline method in all cases. During the shared execution, the basic GNL method only evaluates two kNN queries to retrieve the kNNs of all the outer objects in a segment, which decreases the processing time significantly. The baseline, basic GNL, and GNL methods evaluate a total of 50,000 kNN queries, 1,509 kNN queries, and 743 kNN queries, respectively. This means that the numbers of kNN queries evaluated by the basic GNL and GNL methods represent 3% and 1.5% of the kNN queries evaluated by the baseline method, respectively. This indicates a strong relationship between the query processing times and the numbers of the kNN queries evaluated to compute the kNN joins. Figure 11(b) shows the query processing time as a function of the number of outer objects, that is, R. The GNL method performs better than the other methods in all cases. The number of kNN queries in the baseline method increases linearly with R. However, because of the benefits of shared execution processing, the numbers of kNN queries evaluated by the basic GNL and GNL methods increase slightly with R. Figure 11(c) shows the query processing time as a function of the number of inner objects, that is, S. The GNL method performs better than the other methods in all cases. The numbers of kNN queries evaluated by the basic GNL and GNL methods are independent of S. Figure 11(d) shows the query processing time for various distributions of outer objects and inner objects, where each ordered pair (i.e., C,C, C,U, U,C, and U,U) denotes a combination of the distributions of outer objects and inner objects. The processing time is very long for the baseline method, particularly when the inner objects follow a centroid distribution (i.e., C,C and U,C). The processing time is also long with the basic GNL and GNL methods for U,C because the outer objects are widely scattered and most of the outer segments are generated with a few outer objects, which hinders the shared execution processing.Figure 11
Comparison of the baseline, basic GNL, and GNL methods for NA: (a) varyingk, (b) varying R, (c) varying S, and (d) varying the distribution of objects.
bottom(a)
(b)
(c)
(d)Figure12 compares the query processing times of the three methods when evaluating kNN joins in the SF road map. Figure 12(a) shows the query processing time as a function of k between 1 and 100. The GNL method shows the best performance in all cases because the GNL method evaluates the smallest number of kNN queries among the three methods. The baseline, basic GNL, and GNL methods evaluate 50,000 kNN queries, 9,420 kNN queries, and 5,070 kNN queries, respectively. Figure 12(b) shows the query processing time as a function of R between 104 and 105. The processing time with the baseline method increases in a linear manner with the value of R. However, the basic GNL and GNL methods are not sensitive to increases in the value of R due to the shared execution processing. The GNL evaluates the smallest number of kNN queries in all cases. Figure 12(c) shows the query processing time as a function of S between 104 and 105. The GNL method outperforms the basic GNL method in all cases because the GNL method evaluates 5,070 kNN queries compared to 9,420 kNN queries for the basic GNL method. Figure 12(d) shows the query processing time for various distributions of outer objects and inner objects. The basic GNL and GNL methods outperform the baseline method for C,C and C,U. However, the basic GNL and GNL methods show similar performance to the baseline method for U,C and U,U. This is because the uniform distribution of outer objects obstructs the shared execution processing of the basic GNL and GNL methods.Figure 12
Comparison of the baseline, basic GNL, and GNL methods for SF: (a) varyingk, (b) varying R, (c) varying S, and (d) varying the distribution of objects.
(a)
(b)
(c)
(d)Figure13 compares the query processing times of the three methods when evaluating kNN joins in the SJ road map. Figure 13(a) shows the query processing time as a function of k between 1 and 50. The GNL method outperforms the other methods in all cases because it evaluates 1,210 kNN queries, which are fewer than the other two methods. Figure 13(b) shows the query processing time as a function of R between 103 and 104. The processing time using the basic GNL and GNL methods increases less with increasing values of R than the baseline method. Figure 13(c) shows the query processing time as a function of S between 103 and 104. The GNL method outperforms the other methods in all cases. Figure 13(d) shows the query processing time for various distributions of outer objects and inner objects. The GNL method outperforms the other methods when the outer objects follow a centroid distribution, that is, C,C and C,U. However, all methods show a similar performance when the outer objects follow a uniform distribution, that is, U,C and U,U.Figure 13
Comparison of the baseline, basic GNL, and GNL methods for SJ: (a) varyingk, (b) varying R, (c) varying S, and (d) varying the distribution of objects.
(a)
(b)
(c)
(d)


## 6.1. Experimental Settings

In the experiments, we use three real-life roadmaps freely available in [27]. The first road map comprising 175,813 vertices and 179,179 edges includes major roads (e.g., highways) in North America (NA). The second road map comprising 174,956 vertices and 223,001 edges includes major roads (e.g., city streets) in San Francisco (SF), California. The third road map comprising 18,263 vertices and 23,874 edges includes major roads (e.g., city streets) in San Joaquin County (SJ), California. The numbers of vertex sequences in NA, SF, and SJ are 12,416, 192,276, and 20,040, respectively. The settings of the experimental parameters are given in Table 7.Table 7
Experimental parameter settings.
Parameter
Range
Number of requested NNs (k)
1, 10,30, 50, 100 for NA and SF
1, 5,10, 30, 50 for SJ
Numbers of outer objectsR and inner objects S
1, 3,5, 7, 10 ×104 for NA and SF
1, 3,5, 7, 10 ×103 for SJ
Distributions of outer objects and inner objects
(C)entroid, (U)niform
Real-life roadmaps
NA, SF, SJThe positions of both the outer objects and inner objects follow either a centroid or uniform distribution. The centroid dataset is generated so that it resembles real-world data. First, 10 centroids are selected randomly, and the objects around each centroid follow the Gaussian distribution, where the mean is set to the centroid and the standard deviation is set to 1% of the side length of the data universe. In each experiment, we vary a single parameter within the range shown in Table7, while keeping the other parameters at the default values shown in bold. The outer objects and inner objects follow a centroid distribution unless stated otherwise.We implement and evaluate two versions of the GNL method, that is, the basic GNL and GNL methods. As a benchmark for our proposed method, we use a baseline method that computes thekNNs of every outer object using INE [16]. The three methods are implemented with the maximize speed option using C++ in Visual Studio 2015 and run on a desktop PC running Windows 10 operating system with 32 GB RAM and a quad-core processor (i7-6700 K) at 4 GHz. We consider that the indexing structures of all techniques should be memory resident to ensure responsive query processing, which is assumed recently in many studies [1, 4] and is crucial to online map services and commercial navigation systems. We determine the average values based on 10 experiments.


## 6.2. Experimental Results

Figure11 compares the query processing times using the baseline, basic GNL, and GNL methods when evaluating kNN joins in the NA road map, where each chart illustrates the effect of changing one of the parameters in Table 7. The values in parentheses indicate the numbers of kNN queries that are evaluated by the basic GNL and GNL methods to compute the kNN joins. The numbers of kNN queries evaluated by the baseline method to compute the kNN joins are omitted because the numbers of the kNN queries using this method equal the numbers of the outer objects. Figure 11(a) shows the query processing time as a function of the number of requested NNs, that is, k. The processing times using all the methods increase slightly with k. However, the GNL method shows the best performance, and the processing times using the GNL method are up to 80 times shorter than those using the baseline method in all cases. During the shared execution, the basic GNL method only evaluates two kNN queries to retrieve the kNNs of all the outer objects in a segment, which decreases the processing time significantly. The baseline, basic GNL, and GNL methods evaluate a total of 50,000 kNN queries, 1,509 kNN queries, and 743 kNN queries, respectively. This means that the numbers of kNN queries evaluated by the basic GNL and GNL methods represent 3% and 1.5% of the kNN queries evaluated by the baseline method, respectively. This indicates a strong relationship between the query processing times and the numbers of the kNN queries evaluated to compute the kNN joins. Figure 11(b) shows the query processing time as a function of the number of outer objects, that is, R. The GNL method performs better than the other methods in all cases. The number of kNN queries in the baseline method increases linearly with R. However, because of the benefits of shared execution processing, the numbers of kNN queries evaluated by the basic GNL and GNL methods increase slightly with R. Figure 11(c) shows the query processing time as a function of the number of inner objects, that is, S. The GNL method performs better than the other methods in all cases. The numbers of kNN queries evaluated by the basic GNL and GNL methods are independent of S. Figure 11(d) shows the query processing time for various distributions of outer objects and inner objects, where each ordered pair (i.e., C,C, C,U, U,C, and U,U) denotes a combination of the distributions of outer objects and inner objects. The processing time is very long for the baseline method, particularly when the inner objects follow a centroid distribution (i.e., C,C and U,C). The processing time is also long with the basic GNL and GNL methods for U,C because the outer objects are widely scattered and most of the outer segments are generated with a few outer objects, which hinders the shared execution processing.Figure 11
Comparison of the baseline, basic GNL, and GNL methods for NA: (a) varyingk, (b) varying R, (c) varying S, and (d) varying the distribution of objects.
bottom(a)
(b)
(c)
(d)Figure12 compares the query processing times of the three methods when evaluating kNN joins in the SF road map. Figure 12(a) shows the query processing time as a function of k between 1 and 100. The GNL method shows the best performance in all cases because the GNL method evaluates the smallest number of kNN queries among the three methods. The baseline, basic GNL, and GNL methods evaluate 50,000 kNN queries, 9,420 kNN queries, and 5,070 kNN queries, respectively. Figure 12(b) shows the query processing time as a function of R between 104 and 105. The processing time with the baseline method increases in a linear manner with the value of R. However, the basic GNL and GNL methods are not sensitive to increases in the value of R due to the shared execution processing. The GNL evaluates the smallest number of kNN queries in all cases. Figure 12(c) shows the query processing time as a function of S between 104 and 105. The GNL method outperforms the basic GNL method in all cases because the GNL method evaluates 5,070 kNN queries compared to 9,420 kNN queries for the basic GNL method. Figure 12(d) shows the query processing time for various distributions of outer objects and inner objects. The basic GNL and GNL methods outperform the baseline method for C,C and C,U. However, the basic GNL and GNL methods show similar performance to the baseline method for U,C and U,U. This is because the uniform distribution of outer objects obstructs the shared execution processing of the basic GNL and GNL methods.Figure 12
Comparison of the baseline, basic GNL, and GNL methods for SF: (a) varyingk, (b) varying R, (c) varying S, and (d) varying the distribution of objects.
(a)
(b)
(c)
(d)Figure13 compares the query processing times of the three methods when evaluating kNN joins in the SJ road map. Figure 13(a) shows the query processing time as a function of k between 1 and 50. The GNL method outperforms the other methods in all cases because it evaluates 1,210 kNN queries, which are fewer than the other two methods. Figure 13(b) shows the query processing time as a function of R between 103 and 104. The processing time using the basic GNL and GNL methods increases less with increasing values of R than the baseline method. Figure 13(c) shows the query processing time as a function of S between 103 and 104. The GNL method outperforms the other methods in all cases. Figure 13(d) shows the query processing time for various distributions of outer objects and inner objects. The GNL method outperforms the other methods when the outer objects follow a centroid distribution, that is, C,C and C,U. However, all methods show a similar performance when the outer objects follow a uniform distribution, that is, U,C and U,U.Figure 13
Comparison of the baseline, basic GNL, and GNL methods for SJ: (a) varyingk, (b) varying R, (c) varying S, and (d) varying the distribution of objects.
(a)
(b)
(c)
(d)


## 7. Conclusions

In this study, we investigated thekNN join problem in road networks. The kNN join is an operation that combines each object of a dataset with its kNNs in another dataset and is used to facilitate data mining tasks such as clustering, classification, and outlier detection. The kNN join can also provide more meaningful query results than the range join. We proposed the GNL method as an efficient kNN join algorithm, which employs grouping of adjacent outer objects and distance computations based on shared execution to avoid evaluating redundant kNN queries. We evaluated the performance of the GNL method based on several real-life roadmaps in a wide range of problem settings. The empirical results confirmed that the GNL method is efficient and scalable with the number of outer objects and is significantly superior to the baseline method and that the GNL method outperforms the basic GNL method, particularly when the outer objects follow a nonuniform distribution.



---

*Source: 1243289-2018-04-12.xml*