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

Authors: Wei Jiang; Fangliang Wei; Guanyu Li; Mei Bai; Yongqiang Ren; Jingmin An
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## 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 thek-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.


---

## Body

## 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 ak-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.Figure1 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 (m12,m13,m11,andm8) 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 (m13,m11,m12,andm14) respond to user q because the moving objects m12 and m14 can turn around on the road intersection nodes v1 and v3, respectively.Figure 1
Segment of an urban road network.Existing research primarily focuses on thek-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-decomposedk-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 thek-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-enhancedk-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 effectivenessThe structure of this paper is as follows. Section2 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 onk-NN search problems for fixed objects (Section 2.1) and moving objects (Section 2.2) on a road network.


### 2.1. Related Works aboutk-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 nodeq. 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 toq, the algorithm’s time complexity can reach O∣W∣log∣V∣, 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 (VN3) 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 VN3 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, VN3 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 asR-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 thek-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 ofR-tree [26] or other improved R-tree indices, such as R∗-tree [27], FNR-tree [28], MON-tree [29], STCode-tree [30], and DBR∗-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.).


## 2.1. Related Works aboutk-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 nodeq. 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 toq, the algorithm’s time complexity can reach O∣W∣log∣V∣, 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 (VN3) 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 VN3 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, VN3 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 asR-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 thek-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 ofR-tree [26] or other improved R-tree indices, such as R∗-tree [27], FNR-tree [28], MON-tree [29], STCode-tree [30], and DBR∗-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 thek-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 graphGV,E,W, where V is the road nodes and V=v1,v2,⋯,vi,⋯,vn. Each node vi represents the intersection of roads on a road network, E is the set of directed edges on a road network, and e1,2=v1,v2 means the edge from vertex v1 to v2. W represents the weights of the edge on the road network, in the paper, which indicates the distance of the edge Distv1,v2, formed as wv1,v2=Distv1,v2.Table 1
Description of the symbols used in this paper.
SymbolMeaningKReturns the number of moving objectsPathv1,v2Path from nodev1tov2Distv1,v2Distance from nodev1tov2SPathv1,v2The shortest path from nodev1tov2SPDistv1,v2The shortest path distance from nodev1tov2MNNumber of objects moved between two nodesVSThe starting node of the edgeVEEnd node of the edgeAdSubviAdjacency subgraph ofviAcNodeGiThe active node ofGim.offsetThe offset of the moving object fromNEq.offsetQuery the offset of pointq from NSCsetCandidate set of moving object resultsRk-NN query result setShortChainvi,vjThe shortest chain from nodevi to vjThis paper studies thek-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 Figure2, Pathv6,v8 represents the path from node v6tov8 (for example, v6‐v2‐v1‐v8andv6‐v7‐v8), and the Euclidean distance corresponding to the edge is Distv6,v8=Distv6,v2+Distv2,v1+Distv1,v8=8 (or Distv6,v8=Distv6,v7+Distv7,v8=5, etc.). On the road network, SPathv6,v8 represents the shortest path from node v6tov8. The shortest path of SPathv6,v8 is v6‐v7‐v8, which corresponds to the shortest distance SPDistv6,v8=5.Definition 2 (moving object).
On the road network, each moving object is expressed asm=<vi,vj,m.offset,t>; that is, at time t, the moving object m is on edge <vi,vj>, and the position offset from the vertex of vj is m.offset.Figure 2
Moving objects under the road network with a query.As shown in Figure2, the offset distance from m13 to the end node v2 on the edge e3,2 is m13.offset=2, and q.offset=1 refers to the offset distance from the query object q to the start node v2 on the edge e1,2 which is 1.Definition 3 (active node).
A moving objectm moves from node vs to node ve, and then, we call ve a moving node of m. The active node of the subgraph Gi is denoted as AcNodeGi.
For example, the moving objectm13 moves from node v3 to node v2 on edge<v3,v2> in Figure 2. Therefore, v2 is called an active node of m13.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 Table2, the moving object m11 exists on edge Ev6,v2, and the distance from the terminal node v2 is 1; meanwhile, the moving object m12 exists on edge Ev3,v2, and the distance from the terminal node v3 is 2. The number of moving objects with terminal node v2 is 2. The moving object m14 exists on edge Ev2,v3, and the distance from the terminal node v3 is 2. Therefore, the number of moving objects with terminal node v2 is 1.Table 2
Moving objects.
VendMVstartOffsetMNV2m11,m13V6,V31,22V3m14V221


## 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 directk-NN query is too high for our algorithm, and thus, we first divide graphs.Definition 5 (k division of graph).
Given a graphG=V,E,W, k division refers to dividing V into k subsets; that is, V=V1∪V2∪⋯∪Vk, and for any i,j∈1,k,i≠j, there is Vi∩Vj=φ, Vi=n/k.In the division of graphs, it is required that the number of edgesE, where the associated vertices belong to different subsets, is minimized.A tree hierarchy is established based on the graph division. The original graph isG, and graph G is divided iteratively as follows. Graph G is divided into f=2 subgraphs G1, G2, G3, and G4; these subgraphs are regarded as subgraphs of G. The subgraph set of G is denoted by CG. G is the parent graph, and Gip represents the parent-child graph of subgraph Gi. Figure 3 shows the division process. For example, G0 is divided into two subsubgraphs G1 and G2, and then, CG0=G1,G2 and G1p=G0, as shown in Figure 3. Figure 4 is a subgraph of the road network.Definition 6 (border).
Given any one subgraphGi, if node vi(vi∈Gi) is a boundary node, it needs to satisfy the following condition: there is a node vj on the subgraph Gj(i≠j), vi∈Gj, such that vi,vj∈E is established. Thus, BGi is the set of boundary nodes of Gi.Figure 3
Subgraph division of road network.Figure 4
Subgraph of road network division.


### 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 Figure5.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 asDisSetGi=Sivi,Sivi=vj,SPDistvj,vi,vi,vj∈Gi,i≠j. For the leaf subgraph, Sivi stores the global shortest distance from other nodes in the subgraph to vi; for nonleaf subgraphs, Sivi stores the global shortest distance from other border nodes to border node vi.Figure 5
Tree structure diagram of the road network.For example, for the leaf subgraphG3 (Table 3), the global shortest distances between all nodes in the subgraph stored in the node distance set are stored in ascending order of DisSetG3=S3v1,S3v2,S3v3,S3v4,S3v5,S3v6,S3v7,S3v8, where S3v1=v8,2,v2,3,v7,4,v6,4,v3,8,v5,10,v4,12.Table 3
S3 node distance collection.
S3V1S3V2S3V7S3V8V82V13V82V12V23V63V63V72V74V35……V14V25V66V85V27V65V38V76V57V59V510V57V49V310V412V49V311V411Tables3 and 4 present the node distance sets of the leaf subgraph G3 and the nonleaf subgraph G2, respectively. The bold numbers in the tables are the distances between the border nodes and the other relevant border nodes.Table 4
S2 node distance collection.
S2V11S2V13S2V23S2V25V105V115V2513V96V96V1010V919V106V136V911……V1019V2610V267V2612V2623V1111V2313V2318V1124V2312V2516V2518V1330V1317Lemma 8 (see [17]).
Given a subgraphGi=Vi,Ei,Wi, and vertices vi∈Vi, vj∉Vj, the shortest distance from vi to vj must include a border node β of Gi. Then,
(1)SPDistvi,vj=SPDistvi,β+SPDistvi,β.Proof.
Proof can be found in our technical report [38].Corollary 9.
For the given two subgraphsGi and Gj, the corresponding two nodes are vi∈Gi,vj∈Gj, and the two border nodes βi∈Gi and βj∈Gj. Similarly,
(2)SPDistvj,viSPDistvi,vj=SPDistvi,βi+SPDistβi,βj+SPDistβj,vj.Corollary 10.
For a given number of subgraphsGi,Gj,andGk, the corresponding nodes are vi∈Gi,vj∈Gj,andvk∈Gk. Gk is the subgraph connecting GiandGj, and each subgraph corresponds to the border node βi∈Gi,βj∈Gj,βk∈Gk. Similarly,
(3)SPDistvi,vj=SPDistvi,βi+SPDistβi,βk+SPDistβk,βj+SPDistβj,vj.Proof.
According to Lemma8 and Corollary 10, it can be proved.An example is shown in Figure3, v14∈G5,v31∈G6, border nodes v11∈G5,v10∈G6, from Corollary 10, we can get SPDistv14,v31=SPDistv14,v11+SPDistv11,v10+SPDistv10,v31.Definition 11 (activity-heap).
Given a heapH, vi∈H, if H satisfies H=vi∣vi∈BGorvi∈AcNodeG, then H is called the active heap. This is denoted as HAc. If H=vi∣vi∉BG,vi∉AcNodeG, then H is called an inactive heap and is denoted as HInAc.Corollary 12.
Assuming graphG=V,E,W, vi∈G, then HAc∪HInAc=GV.Proof.
According to Definition11, it can be proved. Because HAc=vi∣vi∈BGorvi∈AcNodeG, HInAc=vi∣vi∉BG,vi∉AcNodeG, HAc∪HInAc=vi∣vi∈BGorvi∈AcNodeG∪vi∣vi∉BG,vi∉AcNodeG=GV.HAc∪HInAc=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. TheV-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 6
Road network structure diagram.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 atT=t and T=t+1, and details of the moving objects are shown in Figure 7.Figure 7
Position of the moving objects atT=t and T=t+1.The existingk-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 Figure8(a), the moving object is on the left side of the query, which is gradually approaching the query point along the road direction.Figure 8
(a)M is on the left side of q; (b) M is on the right side of q.
(a)(b)WhenDistv2,v1−m12.offset≥q.offset, the distance between the moving object and the query is
(4)Distm12,q=2Distv2,v1−m12.offset–q.offset.Correspondingly, as shown in Figure8(b), the moving object is on the right side of the query request point, that is, away along the road near the query point.WhenDistv2,v1−m12.offset<q.offset, it is necessary to recalculate the information of the nearest k moving objects. The distance between the moving object and the query is
(5)Distq,m12=Distv1,v2+m12.offset+q.offset.Table5 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 timeT=t.
Moving object list (T=t)GiVEMVSOffsetMNG314V1m12V211V2m11,m13V6,V31, 22V3m14V221V5m16V611V6m10,m15V7,V51, 12V7m5,m9,m1,m2V8,V6,V10,V101, 1.5, 2, 44V8m7,m8,m6V18,V1,V70.5, 0.5, 13G43V17m24,m23V9,V92, 32V18m22V172, 32G55V26m20V2711V29m17V1411V11m4,m19V10,V142, 1.52V14m18V1121G63V10m3V741V15m21V100.31V25m25V2431For example,G42 means that at time t, there are two moving objects (m23andm24) in subgraph G4, and they are moving from node v9 to node v17. v17 is both the border node of subgraph G4 and the active node of the moving objects m23andm24.Due to frequent updates of moving objects on the road network, we can establish the hash table as shown in Tables6(a) and 6(b), which use VE as the hash key and use (VS,M,Offset,MN) as the value; the mapping function is the VE⟶VS,M,Offset,MN.Table 6(a)
The hash table of moving objects (T=t)
Hash key (AcNodeVi)Value (T=t)VEMVSOffsetMNV1m12V211V2m11,m13V6,V31, 22V3m14V221V5m16V611V6m10,m15V7,V51, 12V7m5,m9,m1,m2V8,V6,V10,V101, 1.5, 2, 44V8m7,m8,m6V18,V1,V70.5, 0.5, 13……………(b)
The hash table of moving objects (T=t+1)
Hash key (AcNodeVi)Value (T=t+1)VEMVSOffsetMNV1m13V221V2m11V611V4m16,m14V6,V51, 12V6m6,m15V7,V52, 12V7m5,m10V8,V61, 22V8m12V111……………For example, whenkey=V2, value=V6,m11,1,2,V3,m13,2,2, it means the moving object m11 is from V6 to V2, and m11.offset=1, there are two moving objects on edge <v6,v2>.


## 4.1. Division of Graphs

Due to the complexity of the road network, the calculation cost of the directk-NN query is too high for our algorithm, and thus, we first divide graphs.Definition 5 (k division of graph).
Given a graphG=V,E,W, k division refers to dividing V into k subsets; that is, V=V1∪V2∪⋯∪Vk, and for any i,j∈1,k,i≠j, there is Vi∩Vj=φ, Vi=n/k.In the division of graphs, it is required that the number of edgesE, where the associated vertices belong to different subsets, is minimized.A tree hierarchy is established based on the graph division. The original graph isG, and graph G is divided iteratively as follows. Graph G is divided into f=2 subgraphs G1, G2, G3, and G4; these subgraphs are regarded as subgraphs of G. The subgraph set of G is denoted by CG. G is the parent graph, and Gip represents the parent-child graph of subgraph Gi. Figure 3 shows the division process. For example, G0 is divided into two subsubgraphs G1 and G2, and then, CG0=G1,G2 and G1p=G0, as shown in Figure 3. Figure 4 is a subgraph of the road network.Definition 6 (border).
Given any one subgraphGi, if node vi(vi∈Gi) is a boundary node, it needs to satisfy the following condition: there is a node vj on the subgraph Gj(i≠j), vi∈Gj, such that vi,vj∈E is established. Thus, BGi is the set of boundary nodes of Gi.Figure 3
Subgraph division of road network.Figure 4
Subgraph of road network division.


## 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 Figure5.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 asDisSetGi=Sivi,Sivi=vj,SPDistvj,vi,vi,vj∈Gi,i≠j. For the leaf subgraph, Sivi stores the global shortest distance from other nodes in the subgraph to vi; for nonleaf subgraphs, Sivi stores the global shortest distance from other border nodes to border node vi.Figure 5
Tree structure diagram of the road network.For example, for the leaf subgraphG3 (Table 3), the global shortest distances between all nodes in the subgraph stored in the node distance set are stored in ascending order of DisSetG3=S3v1,S3v2,S3v3,S3v4,S3v5,S3v6,S3v7,S3v8, where S3v1=v8,2,v2,3,v7,4,v6,4,v3,8,v5,10,v4,12.Table 3
S3 node distance collection.
S3V1S3V2S3V7S3V8V82V13V82V12V23V63V63V72V74V35……V14V25V66V85V27V65V38V76V57V59V510V57V49V310V412V49V311V411Tables3 and 4 present the node distance sets of the leaf subgraph G3 and the nonleaf subgraph G2, respectively. The bold numbers in the tables are the distances between the border nodes and the other relevant border nodes.Table 4
S2 node distance collection.
S2V11S2V13S2V23S2V25V105V115V2513V96V96V1010V919V106V136V911……V1019V2610V267V2612V2623V1111V2313V2318V1124V2312V2516V2518V1330V1317Lemma 8 (see [17]).
Given a subgraphGi=Vi,Ei,Wi, and vertices vi∈Vi, vj∉Vj, the shortest distance from vi to vj must include a border node β of Gi. Then,
(1)SPDistvi,vj=SPDistvi,β+SPDistvi,β.Proof.
Proof can be found in our technical report [38].Corollary 9.
For the given two subgraphsGi and Gj, the corresponding two nodes are vi∈Gi,vj∈Gj, and the two border nodes βi∈Gi and βj∈Gj. Similarly,
(2)SPDistvj,viSPDistvi,vj=SPDistvi,βi+SPDistβi,βj+SPDistβj,vj.Corollary 10.
For a given number of subgraphsGi,Gj,andGk, the corresponding nodes are vi∈Gi,vj∈Gj,andvk∈Gk. Gk is the subgraph connecting GiandGj, and each subgraph corresponds to the border node βi∈Gi,βj∈Gj,βk∈Gk. Similarly,
(3)SPDistvi,vj=SPDistvi,βi+SPDistβi,βk+SPDistβk,βj+SPDistβj,vj.Proof.
According to Lemma8 and Corollary 10, it can be proved.An example is shown in Figure3, v14∈G5,v31∈G6, border nodes v11∈G5,v10∈G6, from Corollary 10, we can get SPDistv14,v31=SPDistv14,v11+SPDistv11,v10+SPDistv10,v31.Definition 11 (activity-heap).
Given a heapH, vi∈H, if H satisfies H=vi∣vi∈BGorvi∈AcNodeG, then H is called the active heap. This is denoted as HAc. If H=vi∣vi∉BG,vi∉AcNodeG, then H is called an inactive heap and is denoted as HInAc.Corollary 12.
Assuming graphG=V,E,W, vi∈G, then HAc∪HInAc=GV.Proof.
According to Definition11, it can be proved. Because HAc=vi∣vi∈BGorvi∈AcNodeG, HInAc=vi∣vi∉BG,vi∉AcNodeG, HAc∪HInAc=vi∣vi∈BGorvi∈AcNodeG∪vi∣vi∉BG,vi∉AcNodeG=GV.HAc∪HInAc=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. TheV-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 6
Road network structure diagram.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 atT=t and T=t+1, and details of the moving objects are shown in Figure 7.Figure 7
Position of the moving objects atT=t and T=t+1.The existingk-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 Figure8(a), the moving object is on the left side of the query, which is gradually approaching the query point along the road direction.Figure 8
(a)M is on the left side of q; (b) M is on the right side of q.
(a)(b)WhenDistv2,v1−m12.offset≥q.offset, the distance between the moving object and the query is
(4)Distm12,q=2Distv2,v1−m12.offset–q.offset.Correspondingly, as shown in Figure8(b), the moving object is on the right side of the query request point, that is, away along the road near the query point.WhenDistv2,v1−m12.offset<q.offset, it is necessary to recalculate the information of the nearest k moving objects. The distance between the moving object and the query is
(5)Distq,m12=Distv1,v2+m12.offset+q.offset.Table5 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 timeT=t.
Moving object list (T=t)GiVEMVSOffsetMNG314V1m12V211V2m11,m13V6,V31, 22V3m14V221V5m16V611V6m10,m15V7,V51, 12V7m5,m9,m1,m2V8,V6,V10,V101, 1.5, 2, 44V8m7,m8,m6V18,V1,V70.5, 0.5, 13G43V17m24,m23V9,V92, 32V18m22V172, 32G55V26m20V2711V29m17V1411V11m4,m19V10,V142, 1.52V14m18V1121G63V10m3V741V15m21V100.31V25m25V2431For example,G42 means that at time t, there are two moving objects (m23andm24) in subgraph G4, and they are moving from node v9 to node v17. v17 is both the border node of subgraph G4 and the active node of the moving objects m23andm24.Due to frequent updates of moving objects on the road network, we can establish the hash table as shown in Tables6(a) and 6(b), which use VE as the hash key and use (VS,M,Offset,MN) as the value; the mapping function is the VE⟶VS,M,Offset,MN.Table 6(a)
The hash table of moving objects (T=t)
Hash key (AcNodeVi)Value (T=t)VEMVSOffsetMNV1m12V211V2m11,m13V6,V31, 22V3m14V221V5m16V611V6m10,m15V7,V51, 12V7m5,m9,m1,m2V8,V6,V10,V101, 1.5, 2, 44V8m7,m8,m6V18,V1,V70.5, 0.5, 13……………(b)
The hash table of moving objects (T=t+1)
Hash key (AcNodeVi)Value (T=t+1)VEMVSOffsetMNV1m13V221V2m11V611V4m16,m14V6,V51, 12V6m6,m15V7,V52, 12V7m5,m10V8,V61, 22V8m12V111……………For example, whenkey=V2, value=V6,m11,1,2,V3,m13,2,2, it means the moving object m11 is from V6 to V2, and m11.offset=1, there are two moving objects on edge <v6,v2>.


## 5. Index-Enhancedk-NN Search Algorithm

This section mainly describes the proposedk-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 heapH.Given two nodesvi and vj, vi∈Gi,vj∈Gj, we quickly determine the global shortest distance between the two nodes.Definition 13 (ShortChain).
Given a subgraphGi=Vi,Ei,Wi, for two nodes vi∈Giandvj∈Gj, the shortest chain of vi,vj refers to the DTH index. The path taken by the smallest common ancestor is denoted as ShortChainvi,vj=Gi⟶Gi+1⟶⋯⟶Gj, where Gi is the leaf subgraph to which vi belongs and Gj is the leaf subgraph to which vj belongs. The middle subgraph is the path of the divided subgraph (except for the common smallest ancestor) that GitoGj traverses.For example, given two nodesv31andv2, the shortest chain from v31tov2 is ShortChainv31,v2=G6⟶G2⟶G1⟶G3, because v31∈G6,v2∈G3, and G6≠G3,G6p=G2,G3p=G1, and G2≠G1,G2p=G0,G1p=G0, the node v31andv2 have the smallest common ancestor G0. The shortest chain is shown in Figure 9.Figure 9
The shortest chain graph of nodesv31tov2.Given two different nodesviandvj, we have vi∈Gi,vj∈Gj,andGi≠Gj.
(1)
We determine the leaf subgraphGj where vj is located and add the distances from all border nodes in Gjtovj into the heap H, in ascending order(2)
We then process the first elementvj−1 of the heap H and determine the next ShortChain subgraph as Gj−1 according to the shortest chain ShortChainvj,vi sequence from vj to vi. Next, we calculate the respective border nodes of Gj−1 to vj−1 and add them to the heap H in ascending order(3)
We end the expansion when the node expansion stop condition is metWhen the node is expanded, the expansion is observed in heapH. When the following conditions are met for heap H, the node expansion ends:
(1)
When the nodes in heapH are expanded in sequence(2)
When the nodes in the heapH 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 setGiven two nodes, the calculation of the shortest chain is as shown in Algorithm1.Algorithm 1: The algorithm for calculating the shortest chain.
Input:vi∈Gi,vj∈GjOutput:ShortChainvi,vj1 InitializeShortChainvi,vj=∅;2 Make sure the subgraphsGi, Gj where vi, vj are located;3 whileGi≠Gj do4 AddGi, Gj to ShortChainvi,vj, get ShortChainvi,vj=Gi⟶Gj;5 Determine the parent nodeGipGjp of Gi,Gj;6Gi=Gip;Gj=Gjp;7 OutputShortChainvi,vj


### 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 nodesvi,vj,andvk, vi∈Gi,BGi=vk,BGj=vj,andGi≠Gj. The distance from vi through Gi’s border node vk to vj in the subgraph Gj is called the distance from node vi to vj under the condition of passing node vk. It is denoted as Distvi,vj∣vk.For example, forv31∈G6, we have BG6=v25andBG5=v11. The distance from node v11 to node v31 through border node v25 is expressed as Distv11,v31∣v25.Lemma 16.
Given two nodesvi and vj, the shortest path must pass through the border nodes of the divided subgraphs corresponding to ShortChainvi,vj, where multiple divided subgraphs can fit the same border node.In the above example,ShortChainv31,v2=G6⟶G2⟶G1⟶G3. Then, the shortest path from v31tov2isv31G6⟶v9G6,G2⟶v7G1,G3⟶v2G3.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 Algorithm1.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 (vs,ve):
(a)
Use Algorithm1 to calculate the shortest chain ShortChainve,vs between ve and vs; calculate the distance from the subgraph where vs 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 elementVcur of the heap H and expand according to the node expansion strategy(c)
Iterate successively until the next chain subgraph of the first elementVi of the first heap H is the same as the subgraph where ve is located. Calculate Distvs,ve, and temporarily store its value in Dist’vs,Vi(d)
Calculate other elements in heapH in turn. When Distvs,Vcur<Dist’vs,Vi,SPDistvs,ve=Distvs,Vcur; when Distvs,Vcur≥Dist’vs,Vi, terminate the algorithmIn Section5.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 SPDistv31,v2 solution process is shown in Figure 10. The specific description is given in Algorithm 2.Algorithm 2: DCDP algorithm().
Input: Given two nodes vs,ve, Distvs,ve=∞Output:SPDistvs,ve1 Ifvs,ve belong to the same subgraph, directly output SPDistvs,veaccording to the node distance set;2 Determine the shortest chainShortChainvs,ve;3V′=∅;Vcur=∅; Let Distvs,V′=∞;4 Addve to heap H;5 Make sure the subgraphsGi,Gj where vi,vj are located;6whileHis not emptydo7 TakeVcur, the first element of H;8ifDistvs,Vcur<Distvs,V′then9  break;10 GetGi’s next chain graph Gj according to ShortChain;11forevery border pointVi of Gjdo12  ifDistvs,Vcur<Distvs,Vi then13Dist′vs,Vi<Distvs,Vcur+Distvs,Vi14ifDist′vs,Vi<Distvs,Vithen15Distvs,Vi=Dist′vs,Vi16  AddViDistvs,Vi to the heap H in descending order ofvalue;17V′=Vcur;18SPDistvs,ve=Distvs,VCurFigure 10
SPDistv31,v2 solution process.For example, the process of solvingSPDistv31,v2 is as follows:
(1)
According to Algorithm1, the shortest chain from v2tov31 is ShortChainv2,v31=G3⟶G1⟶G2⟶G6(2)
According to the order of the shortest chainShortChainv2,v31, expand using the node expansion strategy(3)
When the first element of heapH is v9, calculate Distv31,v2=22(4)
When the expansion node is the first elementv23 of heap H, Distv23,v2=23>Distv31,v2=22, stop node expansion and terminate the algorithm(5)
OutputSPDistv31,v2=22For any nodesvi,vj,vk and subgraph Gj,Gj, the node distance set DisSetDj, where vi∉Gj,vj∈Gj,vk∈Gj, and SPDistvi,vj can be directly calculated by Algorithm 2. Through the node distance set DisSetDj, we can obtain the distance SPDistvj,vk between any two nodes in the subgraph. Then,
(6)SPDistvi,vk=SPDistvi,vj+SPDistvj,vk.


### 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 nodesviandvjvi∈Gi,vj∈Gj in different subgraphs, the maximum distance between node vi and node vj in subgraph Gj is called the upper bound of Distvi,vj and is denoted as upDistvi,vj. The minimum value of this distance is called the lower bound of Distvi,vj and is represented as lowDistvi,vm. The distance interval from node vi to node vj is Distvi,vj=lowDistvi,vm,upDistvi,vj.Lemma 19 (conditional distance interval).
Given nodesviandvj, and vi∈Gi,vj∈Gj,andvk∈BGj, through node vk, the conditional distance interval from node vi to node vj is as follows:
(7)lowDistvi,vj∣vkd=minDistvi,BGj+Distvk,vj,upDistvi,vj∣vk=Distvi,vk+Distvk,vj,and thus, Distvi,vj∣vk=lowDistvi,vj∣vk,upDistvi,vj∣vk.For example, to solve the distance interval between the node inG5 through the border node v25 to v31, that is, DistBG5,v31∣v25, the distances to the border nodes between G5 and G6 are showed in Table 7.Table 7
Distances to the border nodes betweenG5 and G6.
BG5\BG6v98v108v2314v252v11652411v1312113017v2613122310v31∈G6,v25∈G6, according to Lemma 8, the distance from node to node v31 in subgraph G5 must pass through the border node of G5. BG5=v11,v13,v26,BG6=v9,v10,v23,v25,SPDistv25,v31=2. The distances of the G5 border node BG5=v11,v13,v26 to node v25 are SPDistv11,v25=11,SPDistv13,v25=17,andSPDistv26,v25=10.SPDistv11,v9=6,SPDistv11,v10=5,SPDistv11,v23=24,andSPDistv11,v25=11. Therefore, the distance of border nodes v11,v13,andv26tov31throughv25 is
(8)Distv11,v31∣v25d=minDistvi,vk+Distvk,vj=SPDistv11,v10+SPDistv25,v31=7,Distv11,v31∣v25u=Distvi,vk+Distvk,vj=SPDistv11,v25+SPDistv25,v31=13.Distv11,v31∣v25=7,13, expressed. The lower bound of the distance of v11 through node v25tov31 is 7, and the upper bound is 13. Similarly, Distv13,v31∣v25=13,19, and Distv26,v31∣v25=12.Definition 20 (minimum value of subgraph).
Given nodevi,vi∈Gi,andsubgraphGj, the minimum distance between node vi and BGj is called the minimum value of the subgraph and is denoted as minDistvi,Gj.Corollary 21.
Given the subgraphsGi and Gj, where i≠j, then minDistGi,Gj=minDistBGi,BGj.Proof.
We know from Corollary9 that the distance from node vi outside the subgraph to the subgraph Gj must pass through the border node BGj of the subgraph Gj. Similarly, the distance between the node of the subgraph Gj and the subgraph Gi must pass through the border node BGi of the subgraph Gi. Therefore, minDistGi,Gj=minDistBGi,BGj, which can be obtained from the node distance set. The proof is complete.For example, from Table7, it can be seen that minDistG5,G6=Distv5,v10=5; that is, the shortest distance from subgraph G5 to subgraph G6 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 nodesvi∈Gi,vj∈Gj,andvk∈BGk,andGip=Gkp,andDistvk,vj=K, for the first determined value node vk of the heap H, if lowDistvi,vj∣vk=upDistvi,vj∣vk, that is, Distvi,vj∣vk is a certain value, then Distvi,vj∣vk is the shortest distance through node vk. Moreover, node vi does not need to be expanded in subsequent node expansion.Proof.
Suppose that there are nodesvi′,vj,andvk,vi′∈Gi,vj∈Gj,andvk∈BGk. Distvi′,vj∣vk is the smallest value because lowDistvi′,vj∣vk=minDistvi′,BGj+Distvk,vj. Only Distvi′,BGj takes the minimum value, so Distvi′,vk takes the minimum value, because Distvi,vj∣vk takes the minimum value. Similarly, Distvi,vk takes the minimum value; that is, vi makes Distvi,BGj take the minimum value. Since viandvi′ are both in the same subgraph Gi, the uniqueness of the node shows that the assumption that there is node vi′ in the Gi is wrong; that is, the value of Distvi,vj∣vk passes through the shortest distance of node vk. Furthermore, to reduce the redundant calculations in node expansion, the minimum node does not need to be expanded repeatedly.Figure11 shows the query process for Queryq,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 11
The expansion process ofqueryq,5.


### 5.4. Tree-Basedk-NN Search Algorithm

Definition 23 (adjacent subgraph).
Take two subgraphsGiandGj, and Gi≠Gj,BGi=vi,andBGj=vj. GiandGj have a common ancestor, i.e., Gip=Gjp. We call GiandGj adjacent subgraphs. The adjacent subgraph of border node vi is Gj and is denoted by AdSubvi=Gj.For example, in Figure6, v23 is the border node of G6, and v23∈G6,G6p=G2,andG5p=G2. Therefore, G5andG6 are adjacent subgraphs, and the adjacent subgraph of v23isG5. Furthermore, because v23∈G2,andG2p=G1p=G0, G1 is the v23 adjacency subgraph; that is, the adjacency subgraph of v23 is G1. This is then denoted by AdSubv23=G5,G1.Definition 24 (road networkk-NN query).
Given a directed weighted graphGV,E,W, M is the moving object set, and M=m1,m2,m3,⋯,mk. The result of the query set is R. In the road network environment, the k-NN query at time t is expressed as k‐NN=q,k,t, where k is a natural number and q is the query point. These variables are expressed as follows:
(9)R=k,R⊂M,∀x∈R,∀y∈M–R,SPDistq,x≤SPDistq,y.When giving a query pointq, we query the k-nearest moving objects to q. First, we determine the subgraph Gi in which q is located. The subgraph contains the number of moving objects MN and the starting node vi of the edge. According to the node distance set DisSetDi, we then find the distance between vi and the end node ve where each moving object is located. Next, we sort the items in heap H from small to large and process the first element of the heap.For example, when given the query pointq, k=3 means that q is in the subgraph G6, and G6 contains 5 moving objects. The starting node of its edge is v31, and we need to find the 3 moving objects closest to v31.Here, we introduce the calculation for thek-NN for moving objects on the road network. In the existing k-NN algorithm for moving objects on the road network, there are redundant calculations. For this reason, we propose the DCDP-based moving object k-NN (DMOK) algorithm.In the road network environment, for a given query pointqvs,q.offset, the k moving objects closest to the query point q are found, namely, Queryq,k. Figure 12 shows the processing of Queryq,4. The specific calculation process is as follows:
(1)
Determine the subgraphGi of the starting node vsofq(2)
Calculate the distance between the border node and the active node tovs in Gi, and add the distance to HAc. Calculate the distance from the inactive node in Gi to vs, and add the distance to HInAc(3)
Expand according to the expansion strategy. According to the first elementVcur of heap HAc, if Vcur is the border node, calculate the distance between the border node of the adjacent subgraph and vs, and add the node to HAc (whose elements are sorted from smallest to largest). If Vcur is the active node, calculate the distance between the moving object m and vs, and add m to the moving object candidate set Cset(4)
According to the order of heapHAc, the first element Vcur of the heap is processed. When the number of moving object candidate set elements Cset.size≥k, take the distance between the kth m and vs in the moving object candidate set as the moving object distance threshold Dth, update Dth. When DistVcur,vs≥Dth, the processing of heap HAc ends(5)
Output the result setR of moving objectsFigure 12
Processing ofQueryq,4.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. Algorithm3 shows the specific process.For example, the process of solvingqueryq,4 according to Algorithm 3 is as follows:
(1)
Query point isqVS,q.offset,Vs=v31, and the offset from the starting node v31 is q.offset=0.5(2)
q∈G6, and according to the moving object table, the number of moving objects in the subgraph G6 is 3 because the number of the moving objects MN=3<k=4; it needs to further expand to adjacent subgraphs. Determine the distance from the end node Ve of the moving object in the subgraph G6 to the start node v31 of the query point q, calculate the distance from the border node of G6tov31, and add nodes to HAc. In the same way, add the node from the inactive node in the subgraph G6 to the starting node v31 of the query point q and add them to the heap HInAc(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 heapHAc follow the upper bound of the distance interval and are sorted in ascending order(4)
When the candidate set of moving objectsCset.size=4, use the maximum value in Cset at this time as the distance threshold Dth=13(5)
When the first elementVcur of heap HAc, the distance from v11 to v31, Distv11,v31=13 is less than or equal to Dth=13, continue to expand the node for the first element Vcur of the heap HAc, and update the distance threshold Dth. When the distance from the first element in HActov31Distv11,v31≥Dth, the node expansion ends(6)
Output the result set of moving objectsR=m25,m21,m22,m4, and terminate the algorithmAlgorithm 3: DMOK algorithm().
Input:qvs,q.offsetOutput: moving object result set R1 Determine the starting nodevs of q and its subgraph;2Vcur=∅; Dth=0; Cset=∅;3 Calculate the distance betweenvs and its border nodes and activenodes in the subgraph, and add these distances to theHAc i orderfrom small to large, calculate the distance betweenvs and theinactive nodes in the subgraph, and add these distances to the heapofHInAc in order from small to large;4whileHAcis not emptydo5 Take the first elementVcur of HAc;6ifVcuris the border pointthen7ifVcur and vsare not in the same subgraphthen8    Calculate the distance between the active node of thesubgraph whereVcur is located and vs, and add it to theheapHAc9ifCset.size<kthen10   Calculate the distance between the border node of theVcur adjacency subgraph and vs, and add it to the heapHAc11  else12   According to the expansion strategy, the nodes that meetthe conditions are added to theHAc13else ifVcur is the active node then14  Obtain the setM of moving objects corresponding to Vcurthrough the Moving Object List and sort them in descendingorder of the distance fromVcur;15forTake each moving objectm∈Mand process ifdo16   CalculateDistm,vs;17ifCset,size<kthen18    Continue to Line 10;19else20ifDth value is emptythen21     Determine the initial thresholdDth;22else23ifDistm,vs<Dththen24      Usem and Distm,vs to update Cset andthresholdDth respectively;25else26      The algorithm ends;27 OutputR=Cset


## 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 heapH.Given two nodesvi and vj, vi∈Gi,vj∈Gj, we quickly determine the global shortest distance between the two nodes.Definition 13 (ShortChain).
Given a subgraphGi=Vi,Ei,Wi, for two nodes vi∈Giandvj∈Gj, the shortest chain of vi,vj refers to the DTH index. The path taken by the smallest common ancestor is denoted as ShortChainvi,vj=Gi⟶Gi+1⟶⋯⟶Gj, where Gi is the leaf subgraph to which vi belongs and Gj is the leaf subgraph to which vj belongs. The middle subgraph is the path of the divided subgraph (except for the common smallest ancestor) that GitoGj traverses.For example, given two nodesv31andv2, the shortest chain from v31tov2 is ShortChainv31,v2=G6⟶G2⟶G1⟶G3, because v31∈G6,v2∈G3, and G6≠G3,G6p=G2,G3p=G1, and G2≠G1,G2p=G0,G1p=G0, the node v31andv2 have the smallest common ancestor G0. The shortest chain is shown in Figure 9.Figure 9
The shortest chain graph of nodesv31tov2.Given two different nodesviandvj, we have vi∈Gi,vj∈Gj,andGi≠Gj.
(1)
We determine the leaf subgraphGj where vj is located and add the distances from all border nodes in Gjtovj into the heap H, in ascending order(2)
We then process the first elementvj−1 of the heap H and determine the next ShortChain subgraph as Gj−1 according to the shortest chain ShortChainvj,vi sequence from vj to vi. Next, we calculate the respective border nodes of Gj−1 to vj−1 and add them to the heap H in ascending order(3)
We end the expansion when the node expansion stop condition is metWhen the node is expanded, the expansion is observed in heapH. When the following conditions are met for heap H, the node expansion ends:
(1)
When the nodes in heapH are expanded in sequence(2)
When the nodes in the heapH 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 setGiven two nodes, the calculation of the shortest chain is as shown in Algorithm1.Algorithm 1: The algorithm for calculating the shortest chain.
Input:vi∈Gi,vj∈GjOutput:ShortChainvi,vj1 InitializeShortChainvi,vj=∅;2 Make sure the subgraphsGi, Gj where vi, vj are located;3 whileGi≠Gj do4 AddGi, Gj to ShortChainvi,vj, get ShortChainvi,vj=Gi⟶Gj;5 Determine the parent nodeGipGjp of Gi,Gj;6Gi=Gip;Gj=Gjp;7 OutputShortChainvi,vj


## 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 nodesvi,vj,andvk, vi∈Gi,BGi=vk,BGj=vj,andGi≠Gj. The distance from vi through Gi’s border node vk to vj in the subgraph Gj is called the distance from node vi to vj under the condition of passing node vk. It is denoted as Distvi,vj∣vk.For example, forv31∈G6, we have BG6=v25andBG5=v11. The distance from node v11 to node v31 through border node v25 is expressed as Distv11,v31∣v25.Lemma 16.
Given two nodesvi and vj, the shortest path must pass through the border nodes of the divided subgraphs corresponding to ShortChainvi,vj, where multiple divided subgraphs can fit the same border node.In the above example,ShortChainv31,v2=G6⟶G2⟶G1⟶G3. Then, the shortest path from v31tov2isv31G6⟶v9G6,G2⟶v7G1,G3⟶v2G3.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 Algorithm1.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 (vs,ve):
(a)
Use Algorithm1 to calculate the shortest chain ShortChainve,vs between ve and vs; calculate the distance from the subgraph where vs 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 elementVcur of the heap H and expand according to the node expansion strategy(c)
Iterate successively until the next chain subgraph of the first elementVi of the first heap H is the same as the subgraph where ve is located. Calculate Distvs,ve, and temporarily store its value in Dist’vs,Vi(d)
Calculate other elements in heapH in turn. When Distvs,Vcur<Dist’vs,Vi,SPDistvs,ve=Distvs,Vcur; when Distvs,Vcur≥Dist’vs,Vi, terminate the algorithmIn Section5.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 SPDistv31,v2 solution process is shown in Figure 10. The specific description is given in Algorithm 2.Algorithm 2: DCDP algorithm().
Input: Given two nodes vs,ve, Distvs,ve=∞Output:SPDistvs,ve1 Ifvs,ve belong to the same subgraph, directly output SPDistvs,veaccording to the node distance set;2 Determine the shortest chainShortChainvs,ve;3V′=∅;Vcur=∅; Let Distvs,V′=∞;4 Addve to heap H;5 Make sure the subgraphsGi,Gj where vi,vj are located;6whileHis not emptydo7 TakeVcur, the first element of H;8ifDistvs,Vcur<Distvs,V′then9  break;10 GetGi’s next chain graph Gj according to ShortChain;11forevery border pointVi of Gjdo12  ifDistvs,Vcur<Distvs,Vi then13Dist′vs,Vi<Distvs,Vcur+Distvs,Vi14ifDist′vs,Vi<Distvs,Vithen15Distvs,Vi=Dist′vs,Vi16  AddViDistvs,Vi to the heap H in descending order ofvalue;17V′=Vcur;18SPDistvs,ve=Distvs,VCurFigure 10
SPDistv31,v2 solution process.For example, the process of solvingSPDistv31,v2 is as follows:
(1)
According to Algorithm1, the shortest chain from v2tov31 is ShortChainv2,v31=G3⟶G1⟶G2⟶G6(2)
According to the order of the shortest chainShortChainv2,v31, expand using the node expansion strategy(3)
When the first element of heapH is v9, calculate Distv31,v2=22(4)
When the expansion node is the first elementv23 of heap H, Distv23,v2=23>Distv31,v2=22, stop node expansion and terminate the algorithm(5)
OutputSPDistv31,v2=22For any nodesvi,vj,vk and subgraph Gj,Gj, the node distance set DisSetDj, where vi∉Gj,vj∈Gj,vk∈Gj, and SPDistvi,vj can be directly calculated by Algorithm 2. Through the node distance set DisSetDj, we can obtain the distance SPDistvj,vk between any two nodes in the subgraph. Then,
(6)SPDistvi,vk=SPDistvi,vj+SPDistvj,vk.


## 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 nodesviandvjvi∈Gi,vj∈Gj in different subgraphs, the maximum distance between node vi and node vj in subgraph Gj is called the upper bound of Distvi,vj and is denoted as upDistvi,vj. The minimum value of this distance is called the lower bound of Distvi,vj and is represented as lowDistvi,vm. The distance interval from node vi to node vj is Distvi,vj=lowDistvi,vm,upDistvi,vj.Lemma 19 (conditional distance interval).
Given nodesviandvj, and vi∈Gi,vj∈Gj,andvk∈BGj, through node vk, the conditional distance interval from node vi to node vj is as follows:
(7)lowDistvi,vj∣vkd=minDistvi,BGj+Distvk,vj,upDistvi,vj∣vk=Distvi,vk+Distvk,vj,and thus, Distvi,vj∣vk=lowDistvi,vj∣vk,upDistvi,vj∣vk.For example, to solve the distance interval between the node inG5 through the border node v25 to v31, that is, DistBG5,v31∣v25, the distances to the border nodes between G5 and G6 are showed in Table 7.Table 7
Distances to the border nodes betweenG5 and G6.
BG5\BG6v98v108v2314v252v11652411v1312113017v2613122310v31∈G6,v25∈G6, according to Lemma 8, the distance from node to node v31 in subgraph G5 must pass through the border node of G5. BG5=v11,v13,v26,BG6=v9,v10,v23,v25,SPDistv25,v31=2. The distances of the G5 border node BG5=v11,v13,v26 to node v25 are SPDistv11,v25=11,SPDistv13,v25=17,andSPDistv26,v25=10.SPDistv11,v9=6,SPDistv11,v10=5,SPDistv11,v23=24,andSPDistv11,v25=11. Therefore, the distance of border nodes v11,v13,andv26tov31throughv25 is
(8)Distv11,v31∣v25d=minDistvi,vk+Distvk,vj=SPDistv11,v10+SPDistv25,v31=7,Distv11,v31∣v25u=Distvi,vk+Distvk,vj=SPDistv11,v25+SPDistv25,v31=13.Distv11,v31∣v25=7,13, expressed. The lower bound of the distance of v11 through node v25tov31 is 7, and the upper bound is 13. Similarly, Distv13,v31∣v25=13,19, and Distv26,v31∣v25=12.Definition 20 (minimum value of subgraph).
Given nodevi,vi∈Gi,andsubgraphGj, the minimum distance between node vi and BGj is called the minimum value of the subgraph and is denoted as minDistvi,Gj.Corollary 21.
Given the subgraphsGi and Gj, where i≠j, then minDistGi,Gj=minDistBGi,BGj.Proof.
We know from Corollary9 that the distance from node vi outside the subgraph to the subgraph Gj must pass through the border node BGj of the subgraph Gj. Similarly, the distance between the node of the subgraph Gj and the subgraph Gi must pass through the border node BGi of the subgraph Gi. Therefore, minDistGi,Gj=minDistBGi,BGj, which can be obtained from the node distance set. The proof is complete.For example, from Table7, it can be seen that minDistG5,G6=Distv5,v10=5; that is, the shortest distance from subgraph G5 to subgraph G6 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 nodesvi∈Gi,vj∈Gj,andvk∈BGk,andGip=Gkp,andDistvk,vj=K, for the first determined value node vk of the heap H, if lowDistvi,vj∣vk=upDistvi,vj∣vk, that is, Distvi,vj∣vk is a certain value, then Distvi,vj∣vk is the shortest distance through node vk. Moreover, node vi does not need to be expanded in subsequent node expansion.Proof.
Suppose that there are nodesvi′,vj,andvk,vi′∈Gi,vj∈Gj,andvk∈BGk. Distvi′,vj∣vk is the smallest value because lowDistvi′,vj∣vk=minDistvi′,BGj+Distvk,vj. Only Distvi′,BGj takes the minimum value, so Distvi′,vk takes the minimum value, because Distvi,vj∣vk takes the minimum value. Similarly, Distvi,vk takes the minimum value; that is, vi makes Distvi,BGj take the minimum value. Since viandvi′ are both in the same subgraph Gi, the uniqueness of the node shows that the assumption that there is node vi′ in the Gi is wrong; that is, the value of Distvi,vj∣vk passes through the shortest distance of node vk. Furthermore, to reduce the redundant calculations in node expansion, the minimum node does not need to be expanded repeatedly.Figure11 shows the query process for Queryq,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 11
The expansion process ofqueryq,5.


## 5.4. Tree-Basedk-NN Search Algorithm

Definition 23 (adjacent subgraph).
Take two subgraphsGiandGj, and Gi≠Gj,BGi=vi,andBGj=vj. GiandGj have a common ancestor, i.e., Gip=Gjp. We call GiandGj adjacent subgraphs. The adjacent subgraph of border node vi is Gj and is denoted by AdSubvi=Gj.For example, in Figure6, v23 is the border node of G6, and v23∈G6,G6p=G2,andG5p=G2. Therefore, G5andG6 are adjacent subgraphs, and the adjacent subgraph of v23isG5. Furthermore, because v23∈G2,andG2p=G1p=G0, G1 is the v23 adjacency subgraph; that is, the adjacency subgraph of v23 is G1. This is then denoted by AdSubv23=G5,G1.Definition 24 (road networkk-NN query).
Given a directed weighted graphGV,E,W, M is the moving object set, and M=m1,m2,m3,⋯,mk. The result of the query set is R. In the road network environment, the k-NN query at time t is expressed as k‐NN=q,k,t, where k is a natural number and q is the query point. These variables are expressed as follows:
(9)R=k,R⊂M,∀x∈R,∀y∈M–R,SPDistq,x≤SPDistq,y.When giving a query pointq, we query the k-nearest moving objects to q. First, we determine the subgraph Gi in which q is located. The subgraph contains the number of moving objects MN and the starting node vi of the edge. According to the node distance set DisSetDi, we then find the distance between vi and the end node ve where each moving object is located. Next, we sort the items in heap H from small to large and process the first element of the heap.For example, when given the query pointq, k=3 means that q is in the subgraph G6, and G6 contains 5 moving objects. The starting node of its edge is v31, and we need to find the 3 moving objects closest to v31.Here, we introduce the calculation for thek-NN for moving objects on the road network. In the existing k-NN algorithm for moving objects on the road network, there are redundant calculations. For this reason, we propose the DCDP-based moving object k-NN (DMOK) algorithm.In the road network environment, for a given query pointqvs,q.offset, the k moving objects closest to the query point q are found, namely, Queryq,k. Figure 12 shows the processing of Queryq,4. The specific calculation process is as follows:
(1)
Determine the subgraphGi of the starting node vsofq(2)
Calculate the distance between the border node and the active node tovs in Gi, and add the distance to HAc. Calculate the distance from the inactive node in Gi to vs, and add the distance to HInAc(3)
Expand according to the expansion strategy. According to the first elementVcur of heap HAc, if Vcur is the border node, calculate the distance between the border node of the adjacent subgraph and vs, and add the node to HAc (whose elements are sorted from smallest to largest). If Vcur is the active node, calculate the distance between the moving object m and vs, and add m to the moving object candidate set Cset(4)
According to the order of heapHAc, the first element Vcur of the heap is processed. When the number of moving object candidate set elements Cset.size≥k, take the distance between the kth m and vs in the moving object candidate set as the moving object distance threshold Dth, update Dth. When DistVcur,vs≥Dth, the processing of heap HAc ends(5)
Output the result setR of moving objectsFigure 12
Processing ofQueryq,4.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. Algorithm3 shows the specific process.For example, the process of solvingqueryq,4 according to Algorithm 3 is as follows:
(1)
Query point isqVS,q.offset,Vs=v31, and the offset from the starting node v31 is q.offset=0.5(2)
q∈G6, and according to the moving object table, the number of moving objects in the subgraph G6 is 3 because the number of the moving objects MN=3<k=4; it needs to further expand to adjacent subgraphs. Determine the distance from the end node Ve of the moving object in the subgraph G6 to the start node v31 of the query point q, calculate the distance from the border node of G6tov31, and add nodes to HAc. In the same way, add the node from the inactive node in the subgraph G6 to the starting node v31 of the query point q and add them to the heap HInAc(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 heapHAc follow the upper bound of the distance interval and are sorted in ascending order(4)
When the candidate set of moving objectsCset.size=4, use the maximum value in Cset at this time as the distance threshold Dth=13(5)
When the first elementVcur of heap HAc, the distance from v11 to v31, Distv11,v31=13 is less than or equal to Dth=13, continue to expand the node for the first element Vcur of the heap HAc, and update the distance threshold Dth. When the distance from the first element in HActov31Distv11,v31≥Dth, the node expansion ends(6)
Output the result set of moving objectsR=m25,m21,m22,m4, and terminate the algorithmAlgorithm 3: DMOK algorithm().
Input:qvs,q.offsetOutput: moving object result set R1 Determine the starting nodevs of q and its subgraph;2Vcur=∅; Dth=0; Cset=∅;3 Calculate the distance betweenvs and its border nodes and activenodes in the subgraph, and add these distances to theHAc i orderfrom small to large, calculate the distance betweenvs and theinactive nodes in the subgraph, and add these distances to the heapofHInAc in order from small to large;4whileHAcis not emptydo5 Take the first elementVcur of HAc;6ifVcuris the border pointthen7ifVcur and vsare not in the same subgraphthen8    Calculate the distance between the active node of thesubgraph whereVcur is located and vs, and add it to theheapHAc9ifCset.size<kthen10   Calculate the distance between the border node of theVcur adjacency subgraph and vs, and add it to the heapHAc11  else12   According to the expansion strategy, the nodes that meetthe conditions are added to theHAc13else ifVcur is the active node then14  Obtain the setM of moving objects corresponding to Vcurthrough the Moving Object List and sort them in descendingorder of the distance fromVcur;15forTake each moving objectm∈Mand process ifdo16   CalculateDistm,vs;17ifCset,size<kthen18    Continue to Line 10;19else20ifDth value is emptythen21     Determine the initial thresholdDth;22else23ifDistm,vs<Dththen24      Usem and Distm,vs to update Cset andthresholdDth respectively;25else26      The algorithm ends;27 OutputR=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 inC++ 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 setVEPune (PN)2864936925Baghdad (BD)6010888876Tehran (TR)110580147339Bangkok (BK)154352187798ForV-tree and G∗-tree (G∗-tree means the algorithm in the G-tree paper [25]), we set f=4 and τ=32. We evaluated the k-NN search efficiency of DMOK and used TEN-Index, V-tree, and G∗-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 Figure13, 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 13
Comparison of various algorithms under differentk values.In Figures14 and 15, we compared the DTH index construction time and space consumption with V-tree, TEN-Index, and G∗-tree on the four data sets. Object density θ=candidatenodes/totalnumberofvertices. In the experiment, k=10, and θ=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∗-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 14
Comparison of index construction time.Figure 15
Index construction space.It can be seen from Figure16 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 16
Comparison of search time.


## 7. Conclusions

This paper studies a fast tree-indexedk-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.



---

*Source: 2050489-2021-09-29.xml*