Tree Index Nearest Neighbor Search of Moving Objects along a Road Network

Abstract

With the widespread application of location-based service (LBS) technology in the urban Internet of Things, urban transportation has become a research hotspot. One key issue of urban transportation is the nearest neighbor search of moving objects along a road network. The fast-updating operations of moving objects along a road network suppress the query response time of urban services. Thus, a tree-indexed searching method is proposed to quickly find the answers to user-defined queries on frequently updating road networks. First, a novel index structure, called the double tree-hash index, is designed to reorganize the corresponding relationships of moving objects and road networks. Second, an index-enhanced search algorithm is proposed to quickly find the $k$-nearest neighbors of moving objects along the road network. Finally, an experiment shows that compared with state-of-the-art algorithms, our algorithm shows a significant improvement in search efficiency on frequently updating road networks.

This work is licensed under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.

1. Introduction

The rapid development of mobile communication and spatial positioning technology has extensively promoted the rise of location-based services (LBS). The LBS promotes the vigorous development of user-centric applications on urban transportation, and there has been widespread research in user recommendation systems and road network searching. One key issue of urban transportation is the nearest neighbor search of moving objects along a road network. However, the fast-updating operations of moving objects along a road network hinder the query response time of urban services. Currently, it is still difficult to quickly find the answers to user-defined queries on a frequently updating road network. Thus, an index-enhanced search algorithm is proposed to accelerate the response time to user-defined queries.

The response problem faced by user-defined queries on a road network is generalized as a $k$-nearest neighbor search problem ($k$-NN searching). Research on the $k$-NN problem in road networks has societal and commercial value [1]. For example, when someone uses the Meituan errand business, the system will send the order information to multiple salespersons nearest the user. Furthermore, $k$-NN technology promotes the improvement of mobile travel software, such as Didi and Uber, which frequently dispatches vehicles nearest to requesting users.

Figure 1 shows a simple example of a $k$-NN problem, which is a snapshot at time $t$. Assuming that $k=4$, and there exists a user-defined query point $q$ at time $t$, then, 4-NN searching can be conducted with different calculation strategies. Considering only the pairwise distance of a user and a moving object, then four moving objects ($m_{12},m_{13},m_{11},\text{and}{m}_8$) are the closest to the query point $q$. However, taking into account the road intersection nodes and the moving objects’ driving directions, the four moving objects ($m_{13},m_{11},m_{12},\text{and}{m}_{14}$) respond to user $q$ because the moving objects $m_{12}$ and $m_{14}$ can turn around on the road intersection nodes $v_1$ and $v_3$, respectively.

[figure omitted; refer to PDF]

Existing research primarily focuses on the $k$-NN problem on road networks using Euclidean distance strategies for fixed objects [2–9] and Euclidean distance strategies for road-constrained moving objects [10–17].

The Euclidean distance strategies for fixed objects ignore the complexity of the road network, such as the nearest gas station on a highway, and prefer to calculate the shortest distance in a straight line in space, without considering the driving direction of vehicles and road intersection nodes. Road-constrained distance strategies more suitably address the complexity of transportation conditions and moving objects.

A preliminary work [17] provided an outstanding contribution to road-constrained distance strategies of moving objects. The work proposed a tree-based $k$-NN search algorithm. The method first constructs the balanced search-tree index, divides the whole road network into multiple partial road networks by hierarchical iteration, and then bounds the vertices to calculate the $k$-nearest objects. However, the strong search-tree index of the road network and moving objects results in a high cost to update the active records on the search-tree index.

A state-of-the-art work is the tree-decomposed $k$-NN search algorithm [18], which contains a tree-based decomposition strategy to establish the one-to-one relationship between each vertex and tree node. This method can quickly calculate the shortest distance between any two nodes; however, it needs to recalculate for updated inputs of $k$, resulting in increased time consumption thanks to redundant calculations.

Thus, we propose an index-enhanced search algorithm for the $k$-NN query problem of moving objects in a road network. The contributions of this paper are summarized as follows:

(1) A double tree-hash (DTH) index is designed to reorganize the weak relationships between the moving objects and the road network. The DTH index builds a weak bridge between tree and hash structures. The tree structure encapsulates the nodes, edges, and quantized relationships of intersubgraphs. The hash index records the moving objects. Through the weak bridge, the DTH index can realize the continuous updating-dynamic of moving objects in the road network

(2) An index-enhanced $k$-NN search algorithm is proposed to quickly find the $k$-nearest neighbors of moving objects on the road network. We call this the DMOK algorithm. Firstly, we establish an updating model to maintain the moving object updates while quickly and effectively expanding the positive nodes. Secondly, conditional distance rules are designed to reduce the number of expanded negative nodes. Finally, the $k$ answers are responses to the user-defined requests and obtained using the DTH index

(3) Experiments with real data sets and artificial synthetic data sets verify the proposed algorithm’s effectiveness

The structure of this paper is as follows. Section 2 reviews related work. Section 3 introduces the related definitions of the $k$-NN search problem for moving objects on a road network. A tree-hash index is presented in Section 4. Section 5 presents the index-enhanced $k$-NN search algorithm. Section 6 gives the experimental results and analysis. Conclusions are provided in Section 7.

2. Related Work

This section mainly summarizes the related research on the nearest neighbor search, including the related works on $k$-NN search problems for fixed objects (Section 2.1) and moving objects (Section 2.2) on a road network.

2.1. Related Works about $k$-NN Search Problem of Fixed Objects

The nearest neighbor search problem is one of the critical query types based on location services and was first proposed by Knuth in 1973 [19]. After ongoing research by many scholars, the theoretical knowledge has been enriched. The application field of the nearest neighbor search has also been broadened, such that the nearest neighbor search owns a pivotal position in location-based services. The earliest studies on $k$-NN search problems mainly focused on fixed objects, and two classic $k$-NN search algorithms are IER [20] and INE [20].

Incremental Network Expansion (INE) adopted the greedy idea of Dijkstra’s algorithm and expanded the answer by constantly asking the node closest to node $q$. The advantage of the INE algorithm is that the concept is clear, and the implementation is straightforward. However, its disadvantages are also apparent. For one, it needs to visit all the vertices close to vertex $q$. However, the number of these vertices may be much larger than $k$, and many of the visited nodes may be far away from query point $q$; thus, there is no need to visit them all.

In addition, the time and space complexities of the algorithm are high within large-scale data. For example, when using the priority queues to store the distance from other vertices to $q$, the algorithm’s time complexity can reach $O\mid W\mid \log \mid V\mid$, where $W$ is the number of edges and $V$ is the number of vertices in a graph. Therefore, the INE algorithm has a good time and space complexity within small data sizes; it can easily make a preliminary judgment based on the input data size and then decide whether to choose the INE algorithm.

Kolahdouzan and Shahabi [21] proposed an improved algorithm, the Voronoi Network Nearest Neighbor ($V{N}^3$) algorithm, which answers $k$-NN queries by dividing the spatial network into multiple smaller Voronoi polygons based on the object-driven precalculating network distances. However, the performance of $V{N}^3$ depends on the density and distribution of the specific data set. As the data set becomes denser, the computational cost of calculating the distance each time becomes higher. Therefore, $V{N}^3$ is only suitable for sparse data sets.

The programming complexity of the Incremental Euclidean Restriction (IER) algorithm is higher than that of INE, and it needs to use data structures for preprocessing, such as $R$-tree. The advantage of the IER algorithm is that it avoids redundant nodes, especially nodes far away from query point $q$ that should rarely be visited. The disadvantage of the IER algorithm is that it still needs to check the extreme cases of all nodes, and its worst time and space complexity is no less than that of the INR algorithm.

2.2. Related Works about the $k$-NN Search Problem of Moving Objects on a Road Network

Zhang et al. [22] proposed a keyword clustering query method (AKNN), which used user-specified query keywords to obtain text similarity. They designed a dual index structure (DG) generalized as a tree. The index structure saves the road network information and keeps the detailed knowledge of the network to establish an adjacency table. In literature [23], Huang et al. introduced the S-GRID algorithm to divide the spatial network into disjointed subnets and precalculated the shortest path of each pair within boundary nodes. In order to find $k$-nearest neighbors, network expansion is performed first within the subnet, and then, precalculated information is used to perform external expansion between boundary nodes. Samet et al. [10] proposed the DisBrw method, which precalculates the shortest path between all vertex pairs, and used a quadtree-based encoding for storing distance data. By storing the Euclidean distance as the shortest path distance boundary, they could find the $k$-nearest neighbors. Lee et al. [24] proposed a system framework called “ROAD” for spatial object searching on a road network. This method aimed at different object types effectively handled various location-related spatial queries, avoided the disadvantages that each node in the INE algorithm must be expanded, and directly skipped subnets with no obvious nodes of interest. Zhong et al. [25] proposed a balanced search-tree index ($G$-tree). $G$-tree uses a recursive segmentation method to divide the road network into corresponding subroad networks until the subnetwork is sufficiently small. This method can achieve an efficient search. Each node in $G$-tree is a subnet, and the leaf nodes in $G$-tree are equivalent to the nodes in a road network. If a leaf node and other external leaf nodes have directly connected edges, the leaf is the boundary of its upper network. Thus, $G$-tree calculates the shortest path of any two-leaf node boundaries on each divided network. In this paper, an assembly-based method is designed to calculate the minimum distance from the $G$-tree node to the query location and to reduce the complexity of the $k$-NN search problem.

Most studies on the underlying index structure employed the structures of $R$-tree [26] or other improved $R$-tree indices, such as $R\ast$-tree [27], FNR-tree [28], MON-tree [29], STCode-tree [30], and DBR$\ast$-tree [31]. Other works have used the general $R$-tree expansion, which converted two-dimensional space and one-dimensional time data into three-dimensional space data processing; examples include the 3DR-tree [32], RT-tree [33], and STR-tree [34]. Luo et al. [35] proposed a TOAIN algorithm. It used the SCOB index to optimize searching or update processing time and conducted workload analysis to configure SCOB indices to maximize throughput. Tianyang et al. [36] proposed a new algorithm for direction-aware KNN (DAKNN) searching of moving objects on a road network. This method used $R$-tree and a grid as the index structure, and the authors also proposed a novel local network extension method to quickly determine the direction of moving objects, reduce the communication costs, and simplify the calculation of the moving direction between moving objects and query points.

Two main issues should be considered: (1) road network environment representation and (2) moving object processing. Existing works mainly used data graphs to simulate the existing road network in terms of a road network environment [37]. $G=V,E,W$, where $V$ is a node set and represents the connection between road segments, $E$ is an edge set and illustrates the road segment in each road segment, and $W$ means some additional information (road section cost, waiting time, etc.).

3. Problem Description

This paper focuses on quickly performing the $k$-NN search of moving objects on a road network environment and using the division strategy to improve the tree-mapping index mechanism for answering queries. Below, we introduce the definitions of the road network and associated concepts for the $k$-NN search on a road network environment. Table 1 lists and defines the main symbols used in this paper.

Definition 1 (road network).

Given a directed weighted graph $GV,E,W$, where $V$ is the road nodes and $V=v_1,v_2,\cdots ,v_i,\cdots ,v_n$. Each node $v_i$ represents the intersection of roads on a road network, $E$ is the set of directed edges on a road network, and $e_{1,2}=v_1,v_2$ means the edge from vertex $v_1$ to $v_2$. $W$ represents the weights of the edge on the road network, in the paper, which indicates the distance of the edge $\text{Dist}{v}_1,v_2$, formed as $w{v}_1,v_2=\text{Dist}{v}_1,v_2$.

Table 1

Description of the symbols used in this paper.

Symbol	Meaning
$$K$$	Returns the number of moving objects
$$\text{Path}{v}_1,v_2$$	Path from node $v_1\text{to}{v}_2$
$$\text{Dist}{v}_1,v_2$$	Distance from node $v_1\text{to}{v}_2$
$$\text{SPath}{v}_1,v_2$$	The shortest path from node $v_1\text{to}{v}_2$
$$\text{SPDist}{v}_1,v_2$$	The shortest path distance from node $v_1\text{to}{v}_2$
$$M_{\text{N}}$$	Number of objects moved between two nodes
$$V_{\text{S}}$$	The starting node of the edge
$$V_{\text{E}}$$	End node of the edge
$$\text{AdSub}{v}_i$$	Adjacency subgraph of $v_i$
$$\text{AcNode}{G}_i$$	The active node of $G_i$
$$m.\text{offset}$$	The offset of the moving object from $N_{\text{E}}$
$$q.\text{offset}$$	Query the offset of point $q$ from $N_{\text{S}}$
Cset	Candidate set of moving object results
$$R$$	$k$-NN query result set
$$\text{ShortChain}{v}_i,v_j$$	The shortest chain from node $v_i$ to $v_j$

This paper studies the $k$-NN query problem of moving objects on a road network. Before introducing the definition of the $k$-NN query, some definitions of road networks and moving objects are given.

As shown in Figure 2, $\text{Path}{v}_6,v_8$ represents the path from node $v_6\text{to}{v}_8$ (for example, $v_6‐v_2‐v_1‐v_8\text{and}{v}_6‐v_7‐v_8$), and the Euclidean distance corresponding to the edge is $\text{Dist}{v}_6,v_8=\text{Dist}{v}_6,v_2+\text{Dist}{v}_2,v_1+\text{Dist}{v}_1,v_8=8$ (or $\text{Dist}{v}_6,v_8=\text{Dist}{v}_6,v_7+\text{Dist}{v}_7,v_8=5$, etc.). On the road network, $\text{SPath}{v}_6,v_8$ represents the shortest path from node $v_6\text{to}{v}_8$. The shortest path of $\text{SPath}{v}_6,v_8$ is $v_6‐{\text{v}}_7‐v_8$, which corresponds to the shortest distance $\text{SPDist}{v}_6,v_8=5$.

Definition 2 (moving object).

On the road network, each moving object is expressed as $m=<v_i,v_j,m.\text{offset},t>$; that is, at time $t$, the moving object $m$ is on edge $<v_i,v_j>$, and the position offset from the vertex of $v_j$ is $m.\text{offset}$.

[figure omitted; refer to PDF]

As shown in Figure 2, the offset distance from $m_{13}$ to the end node $v_2$ on the edge $e_3,{}_2$ is $m_{13}.\text{offset}=2$, and $q.\text{offset}=1$ refers to the offset distance from the query object $q$ to the start node $v_2$ on the edge $e_{1,2}$ which is 1.

Definition 3 (active node).

A moving object $m$ moves from node $v_{\text{s}}$ to node $v_{\text{e}}$, and then, we call $v_{\text{e}}$ a moving node of $m$. The active node of the subgraph $G_i$ is denoted as $\text{AcNode}{G}_i$.

For example, the moving object $m_{13}$ moves from node $v_3$ to node $v_2$ on $\text{edge}<v_3,v_2>$ in Figure 2. Therefore, $v_2$ is called an active node of $m_{13}$.

Definition 4 (moving object list).

On a road network, a moving object is constantly moving, and its location information is regularly updated. The moving object list stores the positions of moving objects on the road network at a certain timestamp.

In Table 2, the moving object $m_{11}$ exists on edge $E{v}_6,v_2$, and the distance from the terminal node $v_2$ is 1; meanwhile, the moving object $m_{12}$ exists on edge $E{v}_3,v_2$, and the distance from the terminal node $v_3$ is 2. The number of moving objects with terminal node $v_2$ is 2. The moving object $m_{14}$ exists on edge $E{v}_2,v_3$, and the distance from the terminal node $v_3$ is 2. Therefore, the number of moving objects with terminal node $v_2$ is 1.

Table 2

Moving objects.

$V_{\text{end}}$	$M$	$V_{\text{start}}$	Offset	$M_{\text{N}}$
$$V_2$$	$$m_{11},m_{13}$$	$$V_6,V_3$$	1,2	2
$$V_3$$	$$m_{14}$$	$$V_2$$	2	1

4. Tree-Hash Index

This section introduces the double tree-hash (DTH) index proposed in this article, as well as the moving object update model (MOU-Model) based on the design of moving objects. We then introduce the processing method of moving object query on a road network, including the rapid solution of the road network distance and the fast processing of a query. Finally, a detailed introduction of the algorithm is given.

4.1. Division of Graphs

Due to the complexity of the road network, the calculation cost of the direct $k$-NN query is too high for our algorithm, and thus, we first divide graphs.

Definition 5 ($k$ division of graph).

Given a graph $G=V,E,W$, $k$ division refers to dividing $V$ into $k$ subsets; that is, $V=V_1\cup V_2\cup \cdots \cup V_k$, and for any $i,j\in 1,k,i\ne j$, there is $V_i\cap V_j=\phi$, $V_i=n/k$.

In the division of graphs, it is required that the number of edges E, where the associated vertices belong to different subsets, is minimized.

A tree hierarchy is established based on the graph division. The original graph is $G$, and graph $G$ is divided iteratively as follows. Graph $G$ is divided into $f=2$ subgraphs $G_1$, $G_2$, $G_3$, and $G_4$; these subgraphs are regarded as subgraphs of $G$. The subgraph set of $G$ is denoted by $CG$. $G$ is the parent graph, and $G_i^p$ represents the parent-child graph of subgraph $G_i$. Figure 3 shows the division process. For example, $G_0$ is divided into two subsubgraphs $G_1$ and $G_2$, and then, $C{G}_0=G_1,G_2$ and $G_1^p=G_0$, as shown in Figure 3. Figure 4 is a subgraph of the road network.

Definition 6 (border).

Given any one subgraph $G_i$, if node $v_i$($v_i\in G_i$) is a boundary node, it needs to satisfy the following condition: there is a node $v_j$ on the subgraph $G_j$($i\ne j$), $v_i\in G_j$, such that $v_i,v_j\in E$ is established. Thus, $B{G}_{\text{i}}$ is the set of boundary nodes of $G_i$.

[figure omitted; refer to PDF][figure omitted; refer to PDF]

4.2. DTH Index Construction

The double tree-hash (DTH) index is based on the characteristics of the road network structure and the characteristics of moving objects. By constructing a tree index structure, the shortest path of any two nodes in the road network can be quickly determined using the static and complex road network information; moreover, by constructing a distance hash table index structure, fast batch updates can be made for the frequently updated moving object information.

The divided subgraph information and the subgraph border nodes construct the road network tree structure, as shown in Figure 5.

Definition 7 (DisSet).

The node distance set stores the global shortest distance between all nodes in each leaf subgraph and stores the global shortest distance between all border nodes in the nonleaf subgraphs with common ancestors. This is denoted as $\text{DisSet}{G}_i=S_i{v}_i,S_i{v}_i=v_j,\text{SPDist}{v}_j,v_i,v_i,v_j\in G_i,i\ne j$. For the leaf subgraph, $S_i{v}_i$ stores the global shortest distance from other nodes in the subgraph to $v_i$; for nonleaf subgraphs, $S_i{v}_i$ stores the global shortest distance from other border nodes to border node $v_i$.

[figure omitted; refer to PDF]

For example, for the leaf subgraph $G_3$ (Table 3), the global shortest distances between all nodes in the subgraph stored in the node distance set are stored in ascending order of $\text{DisSet}{G}_3=S_3{v}_1,S_3{v}_2,S_3{v}_3,S_3{v}_4,S_3{v}_5,S_3{v}_6,S_3{v}_7,S_3{v}_8$, where $S_3{v}_1=v_8,2,v_2,3,v_7,4,v_6,4,v_3,8,v_5,10,v_4,12$.

Table 3

S₃ node distance collection.

S3	V1	S3	V2		S3	V7	S3	V8
V8	2	V1	3		V8	2	V1	2
V2	3	V6	3		V6	3	V7	2
V7	4	V3	5	……	V1	4	V2	5
V6	6	V8	5		V2	7	V6	5
V3	8	V7	6		V5	7	V5	9
V5	10	V5	7		V4	9	V3	10
V4	12	V4	9		V3	11	V4	11

Tables 3 and 4 present the node distance sets of the leaf subgraph $G_3$ and the nonleaf subgraph $G_2$, respectively. The bold numbers in the tables are the distances between the border nodes and the other relevant border nodes.

Table 4

S₂ node distance collection.

S2	V11	S2	V13		S2	V23	S2	V25
V10	5	V11	5		V25	13	V9	6
V9	6	V10	10		V9	19	V10	6
V13	6	V9	11	……	V10	19	V26	10
V26	7	V26	12		V26	23	V11	11
V23	13	V23	18		V11	24	V23	12
V25	16	V25	18		V13	30	V13	17

Lemma 8 (see [17]).

Given a subgraph $G_i=V_i,E_i,W_i$, and vertices $v_i\in V_i$, $v_j\notin V_j$, the shortest distance from $v_i$ to $v_j$ must include a border node $\beta$ of $G_i$. Then, $$\begin{array}{}\text{(1)}& \text{SPDist}{v}_i,v_j=\text{SPDist}{v}_i,\beta +\text{SPDist}{v}_i,\beta .\end{array}$$

Proof.

Proof can be found in our technical report [38].

Corollary 9.

For the given two subgraphs $G_i$ and $G_j$, the corresponding two nodes are $v_i\in G_i,v_j\in G_j$, and the two border nodes ${\beta }_i\in G_i$ and ${\beta }_j\in G_j$. Similarly, $$\begin{array}{}\text{(2)}& \text{SPDist}{v}_j,v_i\text{SPDist}{v}_i,v_j=\text{SPDist}{v}_i,{\beta }_i+\text{SPDist}{\beta }_i,{\beta }_j+\text{SPDist}{\beta }_j,v_j.\end{array}$$

Corollary 10.

For a given number of subgraphs $G_i,G_j,\text{and}{G}_k$, the corresponding nodes are $v_i\in G_i,v_j\in G_j,\text{and}{v}_k\in G_k$. $G_k$ is the subgraph connecting $G_i\text{and}{G}_j$, and each subgraph corresponds to the border node ${\beta }_i\in G_i,{\beta }_j\in G_j,{\beta }_k\in G_k$. Similarly, $$\begin{array}{}\text{(3)}& \text{SPDist}{v}_i,v_j=\text{SPDist}{v}_i,{\beta }_i+\text{SPDist}{\beta }_i,{\beta }_k+\text{SPDist}{\beta }_k,{\beta }_j+\text{SPDist}{\beta }_j,v_j.\end{array}$$

Proof.

According to Lemma 8 and Corollary 10, it can be proved.

An example is shown in Figure 3, $v_{14}\in G_5,v_{31}\in G_6$, border nodes $v_{11}\in G_5,v_{10}\in G_6$, from Corollary 10, we can get $\text{SPDist}{v}_{14},v_{31}=\text{SPDist}{v}_{14},v_{11}+\text{SPDist}{v}_{11},v_{10}+\text{SPDist}{v}_{10},v_{31}$.

Definition 11 (activity-heap).

Given a heap $H$, $v_i\in H$, if $H$ satisfies $H=v_i\mid v_i\in BG\text{or}{v}_i\in \text{AcNode}G$, then $H$ is called the active heap. This is denoted as $H_{\text{Ac}}$. If $H=v_i\mid v_i\notin BG,v_i\notin \text{AcNode}G$, then $H$ is called an inactive heap and is denoted as $H_{\text{InAc}}$.

Corollary 12.

Assuming graph $G=V,E,W$, $v_i\in G$, then $H_{\text{Ac}}\cup H_{\text{InAc}}=GV$.

Proof.

According to Definition 11, it can be proved. Because $H_{\text{Ac}}=v_i\mid v_i\in BG\text{or}{v}_i\in \text{AcNode}G$, $H_{\text{InAc}}=v_i\mid v_i\notin BG,v_i\notin \text{AcNode}G$, $H_{\text{Ac}}\cup H_{\text{InAc}}=v_i\mid v_i\in BG\text{or}{v}_i\in \text{AcNode}G\cup v_i\mid v_i\notin BG,v_i\notin \text{AcNode}G=GV.H_{\text{Ac}}\cup H_{\text{InAc}}=GV$.

4.3. DTH Index Process of Moving Objects

On the road network, the location information of moving objects (such as vehicles) is updated constantly. The $V$-tree index structure proposed in [17] needs to rerecord the states of the active vertices and update the recent global activities. In a busy road section, the position of moving vehicles changes frequently in this environment. This update cost is very high, which is not conducive to query processing when moving objects change significantly. Thus, we propose a method based on updating moving objects. The road network structure diagram can be seen in Figure 6.

[figure omitted; refer to PDF]

For example, in the bustling section of the city center, the number of moving vehicles is large, and the range of position changes is relatively large. The position of the moving object at $T=t$ and $T=t+1$, and details of the moving objects are shown in Figure 7.

[figure omitted; refer to PDF]

The existing $k$-NN algorithm only returns the $k$-nearest moving objects, regardless of their moving direction. After dividing the graph, according to the location relationship between the moving object and the query, it can be divided into the following situations.

As shown in Figure 8(a), the moving object is on the left side of the query, which is gradually approaching the query point along the road direction.

[figures omitted; refer to PDF]

When $\text{Dist}{v}_2,v_1-m_{12}.\text{offset}\ge q.\text{offset}$, the distance between the moving object and the query is $$\begin{array}{}\text{(4)}& \text{Dist}{m}_{12},q=2\text{Dist}{v}_2,v_1-m_{12}.\text{offset}–q.\text{offset}.\end{array}$$

Correspondingly, as shown in Figure 8(b), the moving object is on the right side of the query request point, that is, away along the road near the query point.

When $\text{Dist}{v}_2,v_1-m_{12}.\text{offset}<q.\text{offset}$, it is necessary to recalculate the information of the nearest $k$ moving objects. The distance between the moving object and the query is $$\begin{array}{}\text{(5)}& \text{Dist}q,m_{12}=\text{Dist}{v}_1,v_2+m_{12}.\text{offset}+q.\text{offset}.\end{array}$$

Table 5 lists the moving objects at time $T=t$. The gray entries denote nodes that are both a border node in the subgraph and an active node of the moving object.

Table 5

Moving objects at time $T=t$.

Moving object list ($T=t$)
$$G_i$$	$$V_{\text{E}}$$	$$M$$	$$V_{\text{S}}$$	Offset	$$M_{\text{N}}$$
$$G_{3}14$$	$$V_1$$	$$m_{12}$$	$$V_2$$	1	1
	$$V_2$$	$$m_{11},m_{13}$$	$$V_6,V_3$$	1, 2	2
	$$V_3$$	$$m_{14}$$	$$V_2$$	2	1
	$$V_5$$	$$m_{16}$$	$$V_6$$	1	1
	$$V_6$$	$$m_{10},m_{15}$$	$$V_7,V_5$$	1, 1	2
	$$V_7$$	$$m_5,m_9,m_1,m_2$$	$$V_8,V_6,V_{10},V_{10}$$	1, 1.5, 2, 4	4
	$$V_8$$	$$m_7,m_8,m_6$$	$$V_{18},V_1,V_7$$	0.5, 0.5, 1	3
$$G_{4}3$$	$$V_{17}$$	$$m_{24},m_{23}$$	$$V_9,V_9$$	2, 3	2
	$$V_{18}$$	$$m_{22}$$	$$V_{17}$$	2, 3	2
$$G_{5}5$$	$$V_{26}$$	$$m_{20}$$	$$V_{27}$$	1	1
	$$V_{29}$$	$$m_{17}$$	$$V_{14}$$	1	1
	$$V_{11}$$	$$m_4,m_{19}$$	$$V_{10},V_{14}$$	2, 1.5	2
	$$V_{14}$$	$$m_{18}$$	$$V_{11}$$	2	1
$$G_{6}3$$	$$V_{10}$$	$$m_3$$	$$V_7$$	4	1
	$$V_{15}$$	$$m_{21}$$	$$V_{10}$$	0.3	1
	$$V_{25}$$	$$m_{25}$$	$$V_{24}$$	3	1

For example, $G_{4}2$ means that at time $t$, there are two moving objects ($m_{23}\text{and}{m}_{24}$) in subgraph $G_4$, and they are moving from node $v_9$ to node $v_{17}$. $v_{17}$ is both the border node of subgraph $G_4$ and the active node of the moving objects $m_{23}\text{and}{m}_{24}$.

Due to frequent updates of moving objects on the road network, we can establish the hash table as shown in Tables 6(a) and 6(b), which use $V_{\text{E}}$ as the hash key and use ($V_{\text{S}},M,\text{Offset},M_{\text{N}}$) as the value; the mapping function is the $V_{\text{E}}⟶V_{\text{S}},M,\text{Offset},M_{\text{N}}$.

Table 6

(a)

The hash table of moving objects ($T=t$)

Hash key ($\text{AcNode}{V}_i$)	Value ($T=t$)
$$V_{\text{E}}$$	$$M$$	$$V_{\text{S}}$$	Offset	$$M_{\text{N}}$$
$$V_1$$	$$m_{12}$$	$$V_2$$	1	1
$$V_2$$	$$m_{11},m_{13}$$	$$V_6,V_3$$	1, 2	2
$$V_3$$	$$m_{14}$$	$$V_2$$	2	1
$$V_5$$	$$m_{16}$$	$$V_6$$	1	1
$$V_6$$	$$m_{10},m_{15}$$	$$V_7,V_5$$	1, 1	2
$$V_7$$	$$m_5,m_9,m_1,m_2$$	$$V_8,V_6,V_{10},V_{10}$$	1, 1.5, 2, 4	4
$$V_8$$	$$m_7,m_8,m_6$$	$$V_{18},V_1,V_7$$	0.5, 0.5, 1	3
…	…	…	…	…

(b)

The hash table of moving objects ($T=t+1$)

Hash key ($\text{AcNode}{V}_i$)	Value ($T=t+1$)
$$V_{\text{E}}$$	$$M$$	$$V_{\text{S}}$$	Offset	$$M_{\text{N}}$$
$$V_1$$	$$m_{13}$$	$$V_2$$	2	1
$$V_2$$	$$m_{11}$$	$$V_6$$	1	1
$$V_4$$	$$m_{16},m_{14}$$	$$V_6,V_5$$	1, 1	2
$$V_6$$	$$m_6,m_{15}$$	$$V_7,V_5$$	2, 1	2
$$V_7$$	$$m_5,m_{10}$$	$$V_8,V_6$$	1, 2	2
$$V_8$$	$$m_{12}$$	$$V_1$$	1	1
…	…	…	…	…

For example, when $\text{key}=V_2$, $\text{value}=V_6,m_{11},1,2,V_3,m_{13},2,2$, it means the moving object $m_{11}$ is from $V_6$ to $V_2$, and $m_{11}.\text{offset}=1$, there are two moving objects on edge $<v_6,v_2>$.

5. Index-Enhanced $k$-NN Search Algorithm

This section mainly describes the proposed $k$-NN algorithm.

We present the calculation of the distance interval between two nodes and then the k-NN algorithm as a whole.

5.1. Node Expansion Strategy

Due to the complexity of the road network environment, calculating the global shortest distance between nodes requires an enormous time cost. This paper uses an inverted index structure to manage the distance calculated on the road network. Specifically, we sort the distance between two nodes from small to large and insert this information into the heap. When the distance between two nodes is an interval, we sort from small to large according to the upper bound of the interval. During subsequent calculations, we always process the first element in the heap $H$.

Given two nodes $v_i$ and $v_j$, $v_i\in G_i,v_j\in G_j$, we quickly determine the global shortest distance between the two nodes.

Definition 13 (ShortChain).

Given a subgraph $G_i=V_i,E_i,W_i$, for two nodes $v_i\in G_i\text{and}{v}_j\in G_j$, the shortest chain of $v_i,v_j$ refers to the DTH index. The path taken by the smallest common ancestor is denoted as $\text{ShortChain}{v}_i,v_j=G_i⟶G_{i+1}⟶\cdots ⟶G_j$, where $G_i$ is the leaf subgraph to which $v_i$ belongs and $G_j$ is the leaf subgraph to which $v_j$ belongs. The middle subgraph is the path of the divided subgraph (except for the common smallest ancestor) that $G_i\text{to}{G}_j$ traverses.

For example, given two nodes $v_{31}\text{and}{v}_2$, the shortest chain from $v_{31}\text{to}{v}_2$ is $\text{ShortChain}{v}_{31},v_2=G_6⟶G_2⟶G_1⟶G_3$, because $v_{31}\in G_6,v_2\in G_3$, and $G_6\ne G_3,{G_6}^p=G_2,{G_3}^p=G_1$, and $G_2\ne G_1,{G_2}^p=G_0,{G_1}^p=G_0$, the node $v_{31}\text{and}{v}_2$ have the smallest common ancestor $G_0$. The shortest chain is shown in Figure 9.

[figure omitted; refer to PDF]

Given two different nodes $v_i\text{and}{v}_j$, we have $v_i\in G_i,v_j\in G_j,\text{and}{G}_i\ne G_j$.

(1) We determine the leaf subgraph $G_j$ where $v_j$ is located and add the distances from all border nodes in $G_j\text{to}{v}_j$ into the heap $H$, in ascending order

(2) We then process the first element $v_{j-1}$ of the heap $H$ and determine the next ShortChain subgraph as $G_{j-1}$ according to the shortest chain $\text{ShortChain}{v}_j,v_i$ sequence from $v_j$ to $v_i$. Next, we calculate the respective border nodes of $G_{j-1}$ to $v_{j-1}$ and add them to the heap $H$ in ascending order

(3) We end the expansion when the node expansion stop condition is met

When the node is expanded, the expansion is observed in heap $H$. When the following conditions are met for heap $H$, the node expansion ends:

(1) When the nodes in heap $H$ are expanded in sequence

(2) When the nodes in the heap $H$ have not been expanded, but the value of the first element of the heap $H$ from the query point is greater than the set threshold or the maximum value in the candidate set

Given two nodes, the calculation of the shortest chain is as shown in Algorithm 1.

Algorithm 1: The algorithm for calculating the shortest chain.

 Input: $v_i\in G_i,v_j\in G_j$

 Output: $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}{v}_i,v_j$

1 Initialize $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}{v}_i,v_j=\varnothing$;

2 Make sure the subgraphs $G_i$, $G_j$ where $v_i$, $v_j$ are located;

3 while $G_i\ne G_j$ do

4 Add $G_i$, $G_j$ to $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}{v}_i,v_j$, get $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}{v}_i,v_j=G_i⟶G_j$;

5 Determine the parent node $G_i^p{G}_j^p$ of $G_i,G_j$;

6 $G_i=G_i^p;G_j=G_j^p$;

7 Output $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}{v}_i,v_j$

5.2. DTH-Enhanced Nodewise Distance Calculation

This section mainly describes the algorithm for calculating the shortest distance between any two nodes in the road network environment based on the DTH index structure. This DTH-based algorithm to calculate the distance between two nodes (called DCDP) combines the advantages of the DTH index and can complete a search quickly. At the same time, we use the node expansion strategy to reduce unnecessary node expansion and network overhead.

Definition 15 (conditional distance).

Given three different nodes $v_i,v_j,\text{and}{v}_k$, $v_i\in G_i,B{G}_i=v_k,B{G}_j=v_j,\text{and}{G}_i\ne G_j$. The distance from $v_i$ through $G_i$’s border node $v_k$ to $v_j$ in the subgraph $G_j$ is called the distance from node $v_i$ to $v_j$ under the condition of passing node $v_k$. It is denoted as $\text{Dist}{v}_i,v_j\mid v_k$.

For example, for $v_{31}\in G_6$, we have $B{G}_6=v_{25}\text{and}B{G}_5=v_{11}$. The distance from node $v_{11}$ to node $v_{31}$ through border node $v_{25}$ is expressed as $\text{Dist}{v}_{11},v_{31}\mid v_{25}$.

Lemma 16.

Given two nodes $v_i$ and $v_j$, the shortest path must pass through the border nodes of the divided subgraphs corresponding to $\text{ShortChain}{v}_i,v_j$, where multiple divided subgraphs can fit the same border node.

In the above example, $\text{ShortChain}{v}_{31},v_2=G_6⟶G_2⟶G_1⟶G_3$. Then, the shortest path from $v_{31}\text{to}{v}_2\text{is}{v}_{31}{G}_6⟶v_9{G}_6,G_2⟶v_7{G}_1,G_3⟶v_2{G}_3$.

We can directly obtain the distance between two nodes in the same subgraph through the node distance set, and thus, there is no need to calculate the shortest chain. For nodes in two different subgraphs, the process of calculating the shortest chain is as in Algorithm 1.

The process of calculating the global shortest distance between any two nodes is given below. According to the node distance set, the global shortest distance can be quickly obtained for two nodes in the same leaf subgraph ($v_{\text{s}},v_{\text{e}}$):

(a) Use Algorithm 1 to calculate the shortest chain $\text{ShortChain}{v}_{\text{e}},v_{\text{s}}$ between $v_{\text{e}}$ and $v_{\text{s}}$; calculate the distance from the subgraph where $v_{\text{s}}$ is located to the border node of the next chain subgraph according to the shortest chain sequence, and store it in heap $H$ (whose elements are sorted from small to large)

(b) Take the first element $V_{\text{cur}}$ of the heap $H$ and expand according to the node expansion strategy

(c) Iterate successively until the next chain subgraph of the first element $V_i$ of the first heap $H$ is the same as the subgraph where $v_{\text{e}}$ is located. Calculate $\text{Dist}{v}_{\text{s}},v_{\text{e}}$, and temporarily store its value in $\text{Dis}{\text{t}}^{\text{’}}{v}_{\text{s}},V_i$

(d) Calculate other elements in heap $H$ in turn. When $\text{Dist}{v}_{\text{s}},V_{\text{cur}}<\text{Dis}{\text{t}}^{\text{’}}{v}_{\text{s}},V_i,\text{SPDist}{v}_{\text{s}},v_{\text{e}}=\text{Dist}{v}_{\text{s}},V_{\text{cur}}$; when $\text{Dist}{v}_{\text{s}},V_{\text{cur}}\ge \text{Dis}{\text{t}}^{\text{’}}{v}_{\text{s}},V_i$, terminate the algorithm

In Section 5.1, we introduce the algorithm used to calculate the shortest chain. Based on the DTH index and Algorithm 1, we propose the DCDP algorithm to calculate the shortest distance between any two nodes quickly. The $\text{SPDist}{v}_{31},v_2$ solution process is shown in Figure 10. The specific description is given in Algorithm 2.

Algorithm 2: DCDP algorithm().

 Input: Given two nodes $v_s,v_e$, $\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,v_e=\infty$

 Output:$\mathbf{S}\mathbf{P}\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,v_e$

1 If $v_s,v_e$ belong to the same subgraph, directly output $\mathbf{S}\mathbf{P}\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,v_e$

 according to the node distance set;

2 Determine the shortest chain $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}{v}_s,v_e$;

3 $V^{\prime }=\varnothing ;V_{cur}=\varnothing ;$ Let $\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V^{\prime }=\infty$;

4 Add $v_e$ to heap $H$;

5 Make sure the subgraphs $G_i,G_j$ where $v_i,v_j$ are located;

6 while$H$is not emptydo

7 Take $V_{cur}$, the first element of $H$;

8 if$\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_{cur}<\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V^{\prime }$then

9  break;

10 Get $G_i$’s next chain graph $G_j$ according to $\mathbf{S}\mathbf{h}\mathbf{o}\mathbf{r}\mathbf{t}\mathbf{C}\mathbf{h}\mathbf{a}\mathbf{i}\mathbf{n}$;

11 forevery border point$V_i$ of $G_j$do

12  if $\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_{cur}<\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_i$ then

13   $\mathbf{D}\mathbf{i}\mathbf{s}{\mathbf{t}}^{\prime }{v}_s,V_i<\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_{cur}+Dist{v}_s,V_i$

14  if$\mathbf{D}\mathbf{i}\mathbf{s}{\mathbf{t}}^{\prime }{v}_s,V_i<\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_i$then

15   $\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_i=\mathbf{D}\mathbf{i}\mathbf{s}{\mathbf{t}}^{\prime }{v}_s,V_i$

16  Add $V_i\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_i$ to the heap H in descending order of

   value;

17  $V^{\prime }=V_{cur}$;

18 $\mathbf{S}\mathbf{P}\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,v_e=\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}{v}_s,V_{Cur}$

[figure omitted; refer to PDF]

For example, the process of solving $\text{SPDist}{v}_{31},v_2$ is as follows:

(1) According to Algorithm 1, the shortest chain from $v_2\text{to}{v}_{31}$ is $\text{ShortChain}{v}_2,v_{31}=G_3⟶G_1⟶G_2⟶G_6$

(2) According to the order of the shortest chain $\text{ShortChain}{v}_2,v_{31}$, expand using the node expansion strategy

(3) When the first element of heap $H$ is $v_9$, calculate $\text{Dist}{v}_{31},v_2=22$

(4) When the expansion node is the first element $v_{23}$ of heap $H$, $\text{Dist}{v}_{23},v_2=23>\text{Dist}{v}_{31},v_2=22$, stop node expansion and terminate the algorithm

(5) Output $\text{SPDist}{v}_{31},v_2=22$

For any nodes $v_i,v_j,v_k$ and subgraph $G_j,G_j$, the node distance set $\text{DisSet}{D}_j$, where $v_i\notin G_j,v_j\in G_j,v_k\in G_j$, and $\text{SPDist}{v}_i,v_j$ can be directly calculated by Algorithm 2. Through the node distance set $\text{DisSet}{D}_j$, we can obtain the distance $\text{SPDist}{v}_j,v_k$ between any two nodes in the subgraph. Then, $$\begin{array}{}\text{(6)}& \text{SPDist}{v}_i,v_k=\text{SPDist}{v}_i,v_j+\text{SPDist}{v}_j,v_k.\end{array}$$

5.3. Conditional Rules

To reduce the calculations required to obtain the distance between two nodes and perform node expansion, we propose a reduction strategy. First, through the expansion of the node, a distance interval is approximated, and the upper and lower bounds of the distance between the two nodes are determined. Then, in the expansion calculation, according to the upper and lower bounds determined above, we reduce the amount of calculation.

Definition 18 (distance interval).

Given two nodes $v_i\text{and}{v}_j{v}_i\in G_i,v_j\in G_j$ in different subgraphs, the maximum distance between node $v_i$ and node $v_j$ in subgraph $G_j$ is called the upper bound of $\text{Dist}{v}_i,v_j$ and is denoted as $\text{upDist}{v}_i,v_j$. The minimum value of this distance is called the lower bound of $\text{Dist}{v}_i,v_j$ and is represented as $\text{lowDist}{v}_i,v_m$. The distance interval from node $v_i$ to node $v_j$ is $\text{Dist}{v}_i,v_j=\text{lowDist}{v}_i,v_m,\text{upDist}{v}_i,v_j$.

Lemma 19 (conditional distance interval).

Given nodes $v_i\text{and}{v}_j$, and $v_i\in G_i,v_j\in G_j,\text{and}{v}_k\in B{G}_j$, through node $v_k$, the conditional distance interval from node $v_i$ to node $v_j$ is as follows: $$\begin{array}{}\text{(7)}& \text{lowDist}{v_i,v_j\mid v_k}_d=\min \text{Dist}{v}_i,B{G}_j+\text{Dist}{v}_k,v_j,\text{upDist}{v}_i,v_j\mid v_k=\text{Dist}{v}_i,v_k+\text{Dist}{v}_k,v_j,\end{array}$$and thus, $\text{Dist}{v}_i,v_j\mid v_k=\text{lowDist}{v}_i,v_j\mid v_k,\text{upDist}{v}_i,v_j\mid v_k$.

For example, to solve the distance interval between the node in $G_5$ through the border node $v_{25}$ to $v_{31}$, that is, $\text{Dist}B{G}_5,v_{31}\mid v_{25}$, the distances to the border nodes between $G_5$ and $G_6$ are showed in Table 7.

Table 7

Distances to the border nodes between $G_5$ and $G_6$.

$B{G}_5\backslash B{G}_6$	$v_{9}8$	$v_{10}8$	$v_{23}14$	$v_{25}2$
$$v_{11}$$	6	5	24	11
$$v_{13}$$	12	11	30	17
$$v_{26}$$	13	12	23	10

$v_{31}\in G_6,v_{25}\in G_6$, according to Lemma 8, the distance from node to node $v_{31}$ in subgraph $G_5$ must pass through the border node of $G_5$. $B{G}_5=v_{11},v_{13},v_{26},B{G}_6=v_9,v_{10},v_{23},v_{25},\text{SPDist}{v}_{25},v_{31}=2$. The distances of the $G_5$ border node $B{G}_5=v_{11},v_{13},v_{26}$ to node $v_{25}$ are $\text{SPDist}{v}_{11},v_{25}=11,\text{SPDist}{v}_{13},v_{25}=17,\text{and}\text{SPDist}{v}_{26},v_{25}=10.\text{SPDist}{v}_{11},v_9=6,\text{SPDist}{v}_{11},v_{10}=5,\text{SPDist}{v}_{11},v_{23}=24,\text{and}\text{SPDist}{v}_{11},v_{25}=11$. Therefore, the distance of border nodes $v_{11},v_{13},\text{and}{v}_{26}\text{to}{v}_{31}\text{through}{v}_{25}$ is $$\begin{array}{c}\text{(8)}& \text{Dist}{v_{11},v_{31}\mid v_{25}}_d=\min \text{Dist}{v}_i,v_k+\text{Dist}{v}_k,v_j=\text{SPDist}{v}_{11},v_{10}+\text{SPDist}{v}_{25},v_{31}=7,\text{Dist}{v_{11},v_{31}\mid v_{25}}_u=\text{Dist}{v}_i,v_k+\text{Dist}{v}_k,v_j=\text{SPDist}{v}_{11},v_{25}+\text{SPDist}{v}_{25},v_{31}=13.\end{array}$$

$\text{Dist}{v}_{11},v_{31}\mid v_{25}=7,13$, expressed. The lower bound of the distance of $v_{11}$ through node $v_{25}\text{to}{v}_{31}$ is 7, and the upper bound is 13. Similarly, $\text{Dist}{v}_{13},v_{31}\mid v_{25}=13,19$, and $\text{Dist}{v}_{26},v_{31}\mid v_{25}=12$.

Definition 20 (minimum value of subgraph).

Given node $v_i,v_i\in G_i,\text{and}\text{subgraph}{G}_j$, the minimum distance between node $v_i$ and $B{G}_j$ is called the minimum value of the subgraph and is denoted as $\text{minDist}{v}_i,G_j$.

Corollary 21.

Given the subgraphs $G_i$ and $G_j$, where $i\ne j$, then $\text{minDist}{G}_i,G_j=\min \text{Dist}B{G}_i,B{G}_j$.

Proof.

We know from Corollary 9 that the distance from node $v_i$ outside the subgraph to the subgraph $G_j$ must pass through the border node $B{G}_j$ of the subgraph $G_j$. Similarly, the distance between the node of the subgraph $G_j$ and the subgraph $G_i$ must pass through the border node $B{G}_i$ of the subgraph $G_i$. Therefore, $\text{minDist}{G}_i,G_j=\min \text{Dist}B{G}_i,B{G}_j$, which can be obtained from the node distance set. The proof is complete.

For example, from Table 7, it can be seen that $\text{minDist}{G}_5,G_6=\text{Dist}{v}_5,v_{10}=5$; that is, the shortest distance from subgraph $G_5$ to subgraph $G_6$ is 5.

For distance interval values with the same starting node and ending node, the upper bound takes a smaller value, and the lower bound takes a more considerable value.

Theorem 22.

Given that the nodes $v_i\in G_i,v_j\in G_j,\text{and}{v}_k\in B{G}_k,\text{and}{G_i}^p={G_k}^p,\text{and}\text{Dist}{v}_k,v_j=K$, for the first determined value node $v_k$ of the heap $H$, if $\text{lowDist}{v}_i,v_j\mid v_k=\text{upDist}{v}_i,v_j\mid v_k$, that is, $\text{Dist}{v}_i,v_j\mid v_k$ is a certain value, then $\text{Dist}{v}_i,v_j\mid v_k$ is the shortest distance through node $v_k$. Moreover, node $v_i$ does not need to be expanded in subsequent node expansion.

Proof.

Suppose that there are nodes ${v_i}^{\prime },v_j,\text{and}{v}_k,{v_i}^{\prime }\in G_i,v_j\in G_j,\text{and}{v}_k\in B{G}_k$. $\text{Dist}{v_i}^{\prime },v_j\mid v_k$ is the smallest value because $\text{lowDist}{v_i}^{\prime },v_j\mid v_k=\min \text{Dist}{v_i}^{\prime },B{G}_j+\text{Dist}{v}_k,v_j$. Only $\text{Dist}{v_i}^{\prime },B{G}_{\text{j}}$ takes the minimum value, so $\text{Dist}{v_i}^{\prime },v_k$ takes the minimum value, because $\text{Dist}{v}_i,v_j\mid v_k$ takes the minimum value. Similarly, $\text{Dist}{v}_i,v_k$ takes the minimum value; that is, $v_i$ makes $\text{Dist}{v}_i,B{G}_j$ take the minimum value. Since $v_i\text{and}{v_i}^{\prime }$ are both in the same subgraph $G_i$, the uniqueness of the node shows that the assumption that there is node ${v_i}^{\prime }$ in the $G_i$ is wrong; that is, the value of $\text{Dist}{v}_i,v_j\mid v_k$ passes through the shortest distance of node $v_k$. Furthermore, to reduce the redundant calculations in node expansion, the minimum node does not need to be expanded repeatedly.

Figure 11 shows the query process for $\text{Query}q,5$. The number, which lies on the left of the box, means the query processing steps. The solid lines represent the $q$ expansion process using the distance interval method, and the dotted lines represent the calculation amount using the expansion method compared to the standard calculation method, which is not using the expansion method. There are 40 solid lines and 12 dotted lines; the calculation efficiency of the expansion method is increased by $12/40+12=23\%$.

[figure omitted; refer to PDF]

According to the node expansion strategy, and combined with the updating model, the set of moving objects that meet the query criteria can be quickly determined. Algorithm 3 shows the specific process.

For example, the process of solving $\text{query}q,4$ according to Algorithm 3 is as follows:

(1) Query point is $q{V}_{\text{S}},q.\text{offset},V_{\text{s}}=v_{31}$, and the offset from the starting node $v_{31}$ is $q.\text{offset}=0.5$

(2) $q\in G_6$, and according to the moving object table, the number of moving objects in the subgraph $G_6$ is 3 because the number of the moving objects $M_{\text{N}}=3<k=4$; it needs to further expand to adjacent subgraphs. Determine the distance from the end node $V_{\text{e}}$ of the moving object in the subgraph $G_6$ to the start node $v_{31}$ of the query point $q$, calculate the distance from the border node of $G_6\text{to}{v}_{31}$, and add nodes to $H_{\text{Ac}}$. In the same way, add the node from the inactive node in the subgraph $G_6$ to the starting node $v_{31}$ of the query point $q$ and add them to the heap $H_{\text{InAc}}$

(3) Expand according to the node expansion strategy. When the distance between the same two nodes is an interval, the lower bound of the distance interval takes a larger value, and the upper bound takes a smaller value. At the same time, the nodes in the heap $H_{\text{Ac}}$ follow the upper bound of the distance interval and are sorted in ascending order

(4) When the candidate set of moving objects $\text{Cset}.\text{size}=4$, use the maximum value in Cset at this time as the distance threshold $\text{Dth}=13$

(5) When the first element $V_{\text{cur}}$ of heap $H_{\text{Ac}}$, the distance from $v_{11}$ to $v_{31}$, $\text{Dist}{v}_{11},v_{31}=13$ is less than or equal to $\text{Dth}=13$, continue to expand the node for the first element $V_{\text{cur}}$ of the heap $H_{\text{Ac}}$, and update the distance threshold $\text{Dth}$. When the distance from the first element in $H_{\text{Ac}}\text{to}{v}_{31}\text{Dist}{v}_{11},v_{31}\ge \text{Dth}$, the node expansion ends

(6) Output the result set of moving objects $R=m_{25},m_{21},m_{22},m_4$, and terminate the algorithm

Algorithm 3: DMOK algorithm().

 Input:$q{v}_s,q.offset$

 Output: moving object result set $R$

1 Determine the starting node $v_s$ of $q$ and its subgraph;

2 $V_{cur}=\varnothing$; $Dth=0$; $Cset=\varnothing$;

3 Calculate the distance between $v_s$ and its border nodes and active

 nodes in the subgraph, and add these distances to the $H_{Ac}$ i order

 from small to large, calculate the distance between $v_s$ and the

 inactive nodes in the subgraph, and add these distances to the heap

 of $H_{InAc}$ in order from small to large;

4 while$H_{Ac}$is not emptydo

5 Take the first element $V_{cur}$ of $H_{Ac}$;

6 if$V_{cur}$is the border pointthen

7  if$V_{cur}$ and $v_s$are not in the same subgraphthen

8    Calculate the distance between the active node of the

     subgraph where $V_{cur}$ is located and $v_s$, and add it to the

     heap $H_{Ac}$

9  if$Cset.size<k$then

10   Calculate the distance between the border node of the

    $V_{cur}$ adjacency subgraph and $v_s$, and add it to the heap

    $H_{Ac}$

11  else

12   According to the expansion strategy, the nodes that meet

    the conditions are added to the $H_{Ac}$

13 else if$V_{cur}$ is the active node then

14  Obtain the set $M$ of moving objects corresponding to $V_{cur}$

   through the Moving Object List and sort them in descending

   order of the distance from $V_{cur}$;

15  forTake each moving object$m\in M$and process ifdo

16   Calculate $\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}m,v_s$;

17   if$Cset,size<k$then

18    Continue to Line 10;

19   else

20    ifDth value is emptythen

21     Determine the initial threshold Dth;

22    else

23     if$\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}m,v_s<Dth$then

24      Use $m$ and $\mathbf{D}\mathbf{i}\mathbf{s}\mathbf{t}m,v_s$ to update $Cset$ and

       threshold $Dth$ respectively;

25     else

26      The algorithm ends;

27 Output $R=Cset$

6. Results and Discussion

The experimental environment is configured as a PC with Intel Core i7-6700 CPU @ 3.40 GHz, with 16 GB memory, 2 T hard disk, and Windows 10 operating system. The algorithm is written in C++ language.

The data set used in this experiment is a real-world road network from an urban road network [39]. In order to verify the effectiveness of the algorithm proposed in this paper, we selected four data sets of them for experimental comparison. The detailed information is shown in Table 8.

Table 8

Road network data statistics.

Data set	$V$	$E$
Pune (PN)	28649	36925
Baghdad (BD)	60108	88876
Tehran (TR)	110580	147339
Bangkok (BK)	154352	187798

For $V$-tree and $G\ast$-tree ($G\ast$-tree means the algorithm in the $G$-tree paper [25]), we set $f=4$ and $\tau =32$. We evaluated the $k$-NN search efficiency of DMOK and used TEN-Index, $V$-tree, and $G^{\ast }$-tree as baselines. We vary $k$ as 10, 20, 50, and 100. We present the search time of the four algorithms on the BK data set. The abscissa is the variation range of $k$.

As can be seen from Figure 13, for different values of $k$, the search time of our algorithms is the least compared with the other two algorithms; this is due to the node processing strategy proposed in this algorithm. Because the TEN-Index can only query $k$-NN within the preset $k$ value of the index, the query cannot be processed when the $k$ value of $k$-NN is greater than the preset $k$ value; the query is not compared to it in this set of experiments.

[figure omitted; refer to PDF]

In Figures 14 and 15, we compared the DTH index construction time and space consumption with $V$-tree, TEN-Index, and $G^{\ast }$-tree on the four data sets. Object density $\theta =\text{candidate}\text{nodes}/\text{total}\text{number}\text{of}\text{vertices}$. In the experiment, $k=10$, and $\theta =0.3$. We randomly generate 1000 vertices as query points and take the average total query time as the final query time. From the histogram, we can clearly see that building the DTH index proposed in the paper takes less time than other indices. Conversely, the building index times of $V$-tree and $G\ast$-tree are high; the main reason for this is that they set up an index of structural information such as nodes, edges, active nodes, and moving objects. Meanwhile, our algorithm constructs indices separately for road network information and moving objects. When moving objects are updated, we only need to update locally, which saves a lot of time. TEN-Index built the index the fastest because it uses H2H-Index for the shortest distance calculation of the road networks, unlike the other algorithms that use Dijkstra. The disadvantage of TEN-Index is that it depends on the value of $k$; that is, the value of $k$ needs to be specified when building the index, and only queries within the value of $k$ can be processed. Therefore, when the value of $k$ is fixed, TEN-Index is relatively fast. In addition, its constructed index consumes much space and needs to be stored during tree decomposition. Considering a large amount of information, the index structure proposed in this article has certain advantages.

[figure omitted; refer to PDF]

It can be seen from Figure 16 that the TEN-Index algorithm has weak adaptability to the value $k$, and the method proposed in this paper has advantages over the other algorithms in terms of search time. The reason for this is that in the initial stage of index construction, although a certain amount of space consumption is sacrificed, in the latter search, the proposed algorithm dramatically improves the search time due to its node strategy and avoidance of redundant calculations.

[figure omitted; refer to PDF]

7. Conclusions

This paper studies a fast tree-indexed $k$-NN search algorithm of moving objects on a road network. Firstly, a novel index structure, called the double tree-hash index, is designed to reorganize the relationships between moving objects and the road network. The DTH index builds a weak bridge between tree and hash structures. The tree structure encapsulates the nodes, edges, and quantized relationships of intersubgraphs. The hash index records the moving objects. Through the weak bridge, the DTH index can realize activity-oriented updates of moving objects in the road network. Secondly, an index-enhanced $k$-NN search algorithm is proposed to quickly find the $k$-nearest neighbors of moving objects on the road network. This algorithm is called the DMOK algorithm. An updating model is established to quickly update the moving object and effectively expand the positive nodes. Through the conditional distance rules, the number of expanded negative nodes can be reduced. Then, multiple answers are provided to queries based on the DTH index. Finally, experiments with real data sets and artificial synthetic data sets verify the algorithm’s effectiveness.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grant 61602076, Grant 61702072, Grant 62002039, and Grant 61976032; in part by the China Postdoctoral Science Foundation funded projects under Grant 2017M611211, Grant 2017M621122, and Grant 2019M661077; in part by the Natural Science Foundation of Liaoning Province under Grant 20180540003; and in part by the CERNET Innovation Project under Grant NGII20190902.

References

[1] N. Saeed, H. Nam, T. Y. al-Naffouri, M. S. Alouini, "A state-of-the-art survey on multidimensional scaling-based localization techniques," IEEE Communications Surveys & Tutorials, vol. 21 no. 4, pp. 3565-3583, DOI: 10.1109/COMST.2019.2921972, 2019.

[2] J. Q. Xu, R. H. Güting, Y. Zheng, O. Ouri Wolfson, "Moving Objects with Transportation Modes: A Survey," Journal of Computer Science and Technology, vol. 34 no. 4, pp. 709-726, DOI: 10.1007/s11390-019-1938-4, 2019.

[3] G. R. Hjaltason, H. Samet, "Distance browsing in spatial databases," ACM Transactions on Database Systems, vol. 24 no. 2, pp. 265-318, DOI: 10.1145/320248.320255, 1999.

[4] M. Sharifzadeh, C. Shahabi, "Vor-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries," Proceedings of the VLDB Endowment, vol. 3 no. 1-2, pp. 1231-1242, DOI: 10.14778/1920841.1920994, 2010.

[5] S. Ji, C. Li, "Location-based instant search," Scientific and Statistical Database Management. SSDBM 2011, vol. 6809, pp. 17-36, DOI: 10.1007/978-3-642-22351-8_2, 2011.

[6] K. C. K. Lee, W. C. Lee, B. Zheng, "Fast object search on road networks," Proceedings of the 12th International Conference on Extending Database Technology Advances in Database Technology - EDBT '09, pp. 1018-1029, DOI: 10.1145/1516360.1516476, .

[7] J. Sankaranarayanan, H. Alborzi, H. Samet, "Efficient query processing on spatial networks," Proceedings of the 2005 international workshop on Geographic information systems - GIS '05, pp. 200-209, DOI: 10.1145/1097064.1097093, .

[8] S. Rogers, P. Langley, C. Wilson, "Mining GPS data to augment road models," Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '99, pp. 104-113, DOI: 10.1145/312129.312208, .

[9] S. Berchtold, B. Ertl, D. A. Keim, "Fast nearest neighbor search in high-dimensional space," Proceedings 14th International Conference on Data Engineering, pp. 209-218, DOI: 10.1109/ICDE.1998.655779, .

[10] H. Samet, J. Sankaranarayanan, H. Alborzi, "Scalable network distance browsing in spatial databases," Proceedings of the 2008 ACM SIGMOD international conference on Management of data - SIGMOD '08, pp. 43-54, DOI: 10.1145/1376616.1376623, .

[11] H. J. Cho, R. Jin, "Efficient processing of moving k-range nearest neighbor queries in directed and dynamic spatial networks," Mobile Information Systems, vol. 2016,DOI: 10.1155/2016/2406142, 2016.

[12] H. J. Cho, R. Jin, T. S. Chung, "A collaborative approach to moving-nearest neighbor queries in directed and dynamic road networks," Pervasive and Mobile Computing, vol. 17, Part A, pp. 139-156, 2015.

[13] G. Li, P. Fan, Y. Li, J. Du, "An efficient technique for continuous k-nearest neighbor query processing on moving objects in a road network," 2010 10th IEEE International Conference on Computer and Information Technology, pp. 627-634, DOI: 10.1109/CIT.2010.127, .

[14] Z. Yu, Y. Liu, X. Yu, K. Q. Pu, "Scalable distributed processing of k nearest neighbor queries over moving objects," IEEE Transactions on Knowledge and Data Engineering, vol. 27 no. 5, pp. 1383-1396, DOI: 10.1109/TKDE.2014.2364046, 2015.

[15] L. Heendaliya, M. Wisely, D. Lin, S. S. Sarvestani, A. Hurson, "Indexing and querying techniques for moving objects in both euclidean space and road network[M]," Advances in Computers, vol. 102, pp. 111-170, DOI: 10.1016/bs.adcom.2016.05.003, 2016.

[16] D. He, S. Wang, X. Zhou, R. Cheng, "An efficient framework for correctness-aware kNN queries on road networks," 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1298-1309, DOI: 10.1109/icde.2019.00118, .

[17] B. Shen, Y. Zhao, G. Li, W. Zheng, Y. Qin, B. Yuan, Y. Rao, "V-tree: efficient knn search on moving objects with road-network constraints," 2017 IEEE 33rd International Conference on Data Engineering (ICDE),DOI: 10.1109/icde.2017.115, .

[18] D. Ouyang, D. Wen, L. Qin, L. Chang, Y. Zhang, X. Lin, "Progressive top-K nearest neighbors search in large road networks," Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1781-1795, DOI: 10.1145/3318464.3389746, .

[19] M. B. Wells, E. Donald, "Book review: the art of computer programming, volume 1. Fundamental algorithms and volume 2. Seminumerical algorithms," Bulletin of the American Mathematical Society, vol. 79 no. 3, pp. 501-510, DOI: 10.1090/S0002-9904-1973-13173-8, 1973.

[20] A. Mahmood, W. G. Aref, "Query processing techniques for big spatial-keyword data," Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1777-1782, DOI: 10.1145/3035918.3054773, .

[21] M. Kolahdouzan, C. Shahabi, "Voronoi-based K nearest search in spatial network databases," Proceedings of the 30th International Conference on Very Large DataBases, pp. 840-851, .

[22] P. Zhang, H. Lin, Y. Gao, D. Lu, "Aggregate keyword nearest neighbor queries on road networks," GeoInformatica, vol. 22 no. 2, pp. 237-268, DOI: 10.1007/s10707-017-0315-0, 2018.

[23] X. Huang, C. S. Jensen, H. Lu, S. Šaltenis, "S-GRID: a versatile approach to efficient query processing in spatial networks," Advances in Spatial and Temporal Databases. SSTD 2007, vol. 4605, pp. 93-111, DOI: 10.1007/978-3-540-73540-3_6, 2007.

[24] K. C. K. Lee, W. C. Lee, B. Zheng, Y. Tian, "ROAD: a new spatial object search framework for road networks," IEEE Transactions on Knowledge and Data Engineering, vol. 24 no. 3, pp. 547-560, DOI: 10.1109/TKDE.2010.243, 2012.

[25] R. Zhong, G. Li, K. L. Tan, L. Zhou, Z. Gong, "G-tree: an efficient and scalable index for spatial search on road networks," IEEE Transactions on Knowledge and Data Engineering, vol. 27 no. 8, pp. 2175-2189, DOI: 10.1109/TKDE.2015.2399306, 2015.

[26] N. Roussopoulos, S. Kelley, F. Vincent, "Nearest neighbor queries," Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95, pp. 71-79, DOI: 10.1145/223784.223794, .

[27] Y. Liu, G. Liu, Z. He, "Spatial index technology for multi-scale and large scale spatial data," 2010 18th International Conference on Geoinformatics,DOI: 10.1109/geoinformatics.2010.5567757, .

[28] E. Frentzos, "Indexing objects moving on fixed networks," Advances in Spatial and Temporal Databases. SSTD 2003, vol. 2750, pp. 289-305, DOI: 10.1007/978-3-540-45072-6_17, 2003.

[29] V. T. de Almeida, R. H. Güting, "Indexing the trajectories of moving objects in networks," GeoInformatica, vol. 9 no. 1, pp. 33-60, DOI: 10.1007/s10707-004-5621-7, 2005.

[30] N. Du, J. Zhan, M. Zhao, D. Xiao, Y. Xie, "Spatio-temporal data index model of moving objects on fixed networks using hbase," 2015 IEEE International Conference on Computational Intelligence & Communication Technology, pp. 247-251, DOI: 10.1109/CICT.2015.32, .

[31] L. Liu, W. Li, Y. Guo, J. Le, "Supporting high updates disk-based index in road network," 2008 IEEE International Conference on e-Business Engineering, pp. 517-522, DOI: 10.1109/ICEBE.2008.39, .

[32] Y. Theodoridis, M. Vazirgiannis, T. Sellis, "Spatio-temporal indexing for large multimedia applications," Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems, pp. 441-448, DOI: 10.1109/mmcs.1996.535011, .

[33] I. Kamel, C. Faloutsos, Hilbert R-Tree: An Improved R-Tree Using Fractals, 1993.

[34] S. T. Leutenegger, M. A. Lopez, J. Edgington, "STR: a simple and efficient algorithm for R-tree packing," Proceedings 13th International Conference on Data Engineering, pp. 497-506, DOI: 10.1109/ICDE.1997.582015, .

[35] S. Luo, B. Kao, G. Li, J. Hu, R. Cheng, Y. Zheng, "TOAIN: a throughput optimizing adaptive index for answering dynamic k-nn queries on road networks," Proceedings of the VLDB Endowment, vol. 11 no. 5, pp. 594-606, DOI: 10.1145/3187009.3177736, 2018.

[36] D. Tianyang, Y. Lulu, C. Qiang, C. Bin, F. Jing, "Direction-aware KNN queries for moving objects in a road network," World Wide Web, vol. 22 no. 4, pp. 1765-1797, DOI: 10.1007/s11280-019-00657-1, 2019.

[37] R. H. Güting, V. T. De Almeida, Z. Ding, "Modeling and querying moving objects in networks," The VLDB Journal, vol. 15 no. 2, pp. 165-190, DOI: 10.1007/s00778-005-0152-x, 2006.

[38] "V-tree: efficient knn search on moving objects with road-network constraints," . http://dbgroup.cs.tsinghua.edu.cn/ligl/v-tree.pdf

[39] https://figshare.com/articles/dataset/Urban_Road_Network_Data/2061897/1