# Path–Based Continuous Spatial Keyword Queries

Authors: Fangshu Chen; Pengfei Zhang; Chengcheng Yu; Huaizhong Lin; Shan Tang; Xiaoming Hu
Journal: Complexity
 (2022)

---

## Abstract

In this paper, we study the path based continuous spatial keyword queries, which find the answer set continuously when the query point moves on a given path. Under this setting, we explore two primitive spatial keyword queries, namelyk nearest neighbor query and range query. The technical challenges lie in that: (1) retrieving qualified vertices in large road networks efficiently, and (2) issuing the query continuously for points on the path, which turns out to be inapplicable. To overcome the above challenges, we first propose a backbone road network index structure (BNI), which supports the distance computation efficiently and offers a global insights of the whole road network. Motivated by the safe zone technique, we then transform our queries to the issue of finding event points, which capture the changes of answer set. By this transformation, our queries are to be simple and feasible. To answer the queries, we propose a Two-Phase Progressive (TPP) computing framework, which first computes the answer sets for some crucial vertices on the path, and then identifies the event points by the retrieved answer sets. Extensive experiments on both real and synthetic data sets are conducted to evaluate the performance of our proposed algorithms, and the results show that our algorithms outperform competitors by several orders of magnitude.


---

## Body

## 1. Introduction

With the prevalence of smartphones and other mobile devices, continuous spatial queries have gained increasing attention from the research community [1–12]. Previous works can be roughly classified into two categories by the query model: (1) snapshot based model [2, 3, 7, 8]. In this model, snapshot query processing techniques are periodically invoked, which either yields excessive costs or outdated results as pointed out in [6]; (2) safe zone based model [1, 4, 6, 9, 12, 13]. When the query point moves within the safe zone, it can be guaranteed that the answer set will not change. This property encourages to identify the safe zone, rather than periodically invoking the query processing techniques.Traditional spatial keyword query models usually suppose that the query point is static or moves randomly, however, in real life a user (query point) may be moving on a navigation path or a public transport line, thus an data point is relevant only if it covers all query keywords (capturing user needs) and is on the query path at the same time.Consider the following scenario as shown in Figure1, there are 10 vertices v1,v2,…v10) on the road network, specifically, each vertex is associated with a set of keywords (the abbreviations of the keywords are defined on the top right corner in Figure 1), and each edge is associated with a real-valued distance. Given a query path P (the red arrow in Figure 1), a tourist (described as a blue car in the figure) monitors Chinese food restaurant with car parking service within 1 km continuously when driving on path P, the demand of the tourist can be expressed by keyword set C,P. As another example, a passenger may continuously query the nearest Chinese food restaurant with car parking service. The first example can be answered by issuing the path based continuous range query, and the second one can be answered by issuing the path based continuous k NN query. As shown in 1, when the query point is q1, the answer set for path based continuous range query is v3, since v3 is the only vertex within the query range and cover the query keywords C,P at the same time. And as the car moving on the query path, the answer set keeps changing, when it moves to q2, the answer set for path based continuous range query is v7. And in the same way, we can find that the answer of k NN query k=2 for q1 is v3,v7, since these two points are on the query path and cover the keywords at the same time. Notice that, v5 is nearer to q1 compared to v7 and it also satisfies the keyword constraint, however, it is not on the query path P, thus it is not in the answer set.Figure 1
Example of the path based continuous spatial keyword query.Motivated by the above examples, we propose to study the continuous spatial keyword queries with path based paradigm. Particularly, we focus on studying two fundamental types of queries, namely path based continuous range keyword (PCR) query and path based continuousk NN keyword (PC k NN) query.From the technical perspective, we encounter two major challenges. The first challenge is how to compute distance on large scale road networks, which incurs prohibitive computation overhead. Various techniques are developed [14–17] to facilitate the distance computation. However, they either incur prohibitive pre-computation overhead or are short of global insights of the whole network. To make the road network distance computation more efficiently, we propose a dual-index structure, namely backbone network index (BNI). Concretely, we first reduce the original network to a backbone network using a simple but effective strategy. We then maintain the skeleton and detailed information of the road network by two structures, namely the modified G-tree [18] (in memory) and modified adjacent list [19] (on disk). As pointed out in [18], G-tree enables to facilitate the distance computation by assembly-based method, whilst offering the global insights of the road network.Another challenge arises when considering infinite number of query points on the path. Obviously, issuing query at each query point is infeasible. Inspired by the observation that the answer set will not change when query point moves within the safe zone, we target to find the event points on the path which capture the changes of answer set. This transformation makes our queries simple and feasible.Given a query path, [20] investigates the continuous nearest neighbor queries. To enable efficient query processing, they precompute k NN sets for a fraction of intersection points. Nevertheless, one may request various k NN sets for different needs (expressed by different keywords set). As a result, computing all the k NN sets for different query keywords is infeasible. LARC [9] studies the continuous k nearest neighbor keyword queries on the road network. However, LARC suffers from two problems when it is applied to answer our queries. First, it has to precompute and reserve much information for each vertex, which incurs prohibitive computation and space overhead in large scale road networks. Second, the safe zone computed by LARC is approximate and redundant for our path based queries.To answer the queries, we develop a Two-Phase Progressive query framework (TPP) on the top of our proposed index structure BNI. We first compute and maintain the answer sets for some crucial vertices on the given path when receiving queries. This can be achieved by only issuing one query. Then, we identify the event points on the path progressively with the reserved answer sets.This paper is a significant extension to its preliminary conference version [21]. Compared to the preliminary version, we extend the path based continuous range keyword query to the k nn keyword query, and propose two new effective algorithms. And the previous work in [21] lacks of theoretical analysis of the effectiveness and efficiency of the proposed index structure and algorithms.Our major contributions (excluding the contributions in conference version [21]) can be summarized as follows:(i)
We extend the spatial keyword query to thek nearest neighbor query and propose two new effective algorithms including IssuingkNNQuery and PCkNN−IdentifyingEventPoint to solve the Path Based Continuous kNN Query (PCkNN) (in Section 4 and Section 5).(ii)
Some detailed proofs and definitions that have not been included int the conference version have been added here;(iii)
We add an analysis section to present the theoretical analysis of the effectiveness of proposed BNI index structure, and give out the time complexity and space complexity for all the proposed algorithms (in Section6);(iv)
We extend the experimental part to verify the effectiveness and efficiency of our proposed PCkNN algorithms (in Section7). And we also extend the experiment results to evaluate the algorithms’ page access number for both queries.The rest of this paper is organized as follows. Section2 reviews the related work. Section 3 formally defines the problem and introduce the backbone network. We describe the proposed index structure in Section 4 and introduce our proposed algorithms in Section 5. Section 6 offers the theoretical analysis of proposed algorithms, and we give the experimental study in Section 7. This paper is concluded in Section 8.


## 2. Related Work

We review works related to the path based continuous spatial keyword queries, mainly focusing on the continuous/moving spatial queries and the road network index structures.


### 2.1. Continuous/Moving Spatial Queries

Spatial queries have been extensively studied in database community. Specifically, enormous focuses have shifted to range queries [16, 23–27] and k nearest neighbor queries [2, 4–6, 9, 18]. Next, we will introduce the works on them respectively.Cheema et al. [22] explore the continuous range queries on both the Euclidean space and the road network. They adopt the concept of safe zone for monitoring the query position updating. Literature [23, 24] studied the problem in context of road network. Du et al. [23] answer the continuous spatial keyword range queries by two steps. They first build the range tree for the query, which maintains the shortest path from query point to all qualified objects. Then, the up-to-date results are obtained by adjusting the range tree accordingly. To alleviate the effect the frequent object updates, Wang et al. [24] develop the Shortest-Distance-based Tree (SD-Tree), which supports incremental computation of answer sets using retrieved paths. Literature [25–28] explore the range queries with the assumption that objects move on the Euclidean space. Specifically, [26, 28] consider an uncertainty model, in which the motion of objects is uncertainty. Chung et al. [28] propose to transform moving objects into points by hough transform, and then index them with R-tree. In [26], by transforming the irregular motion areas to polygon regions, the initial problem can be reduced to a simplified version. Wu et al. [27] study the continuous range queries over moving objects but stationary queries. They propose the containment-encoded squares (CESs), which decompose query regions and store precomputed search results. Zhang et al. [25] study the predictive range query and the predictive k nearest neighbor query. In fact, they distinguish from our work by two major aspects. On one hand, they model the motion of objects as a linear function of time but not the road network. On the other hand, they retrieve one answer set for whole querying period, while we keep searching the up-to-date answer set. Transformed minkowski sum (TMS) are used to determine whether the moving objects intersect the moving query point.Given a query path, [20] investigates the problem of continuous nearest neighbor queries. To enable efficient query processing, they precompute k NN sets for a fraction of intersection points. Nevertheless, in practice, one may require different k NN sets due to different needs when considering keywords. As a result, computing all the k NN sets for different query keywords is infeasible. Literature [1, 6] try to answer the k NN queries by safe region technique, which is motivated by V-Diagram [27]. To avoid prohibitive computation cost, Li et al. [1] utilize influential sets to restrict the safe zone. Note that, it can achieve the same large safe zone as order-k Voronoi cell [29] while minimizing the computation overhead. In [3], Mouratidis et al. study the continuous k NN queries on road networks. Different from our setting, they consider both the moving objects and queries without making assumption on the motion patterns. Two methods are developed, namely incremental monitoring algorithm (IMA) and group monitoring algorithm (GMA). The former monitors the answer set of individual query by maintaining an expansion tree from query point. With this tree, only object updating that may affect the answer set is considered. GMA groups all queries lying on the same edge, and then gets the answer sets for them based on the answer sets of end points of corresponding edge and the objects lying on this edge. [4] studies the continuous k nearest neighbor queries on the context of both Euclidean space and spatial network. They propose to construct the safe zone based on the objects, query points and the search space. However, this method has to recompute the safe regions more frequently and has higher validation overhead as pointed by [1]. Zheng et al. [9] utilize the 2-hop label to facilitate the distance computation. But this work suffers from extensive computation overhead and storage overhead. More importantly, the retrieved safe regions are too large and inaccurate when applied to our problem. Mouratidis et al. [2] develop the conceptual partitioning (CPM) technique, which handling location updates only from objects that fall in the vicinity of some query (and ignoring the rest). In [7], to support various scenarios, Object-Indexing and Query-Indexing are developed. Specifically, both of them are based on the grid index. Specifically, [8, 11, 30] retrieve the k NN set in the context of distributed environment. To be adaptable to dynamic environment, [8] develops the dynamic strip index (DSI), which enables to merge or split objects dynamically. Besides, [31, 32] consider querying trajectories/routes that a composed of a sequence of geo-locations associated with text descriptions, Cong et al. [31] proposes the Bck-tree index integrating spatial information and text information for the top-k spatial keyword query on trajectories. Feng et al. [32] focus on the indoor top-k keyword-aware routing query.


### 2.2. Road Index Structure

Distance computation brings great challenge in the presence of large scale road network. To address this problem, various index structures have been studied. In general, previous works on the road network index structure can be roughly classified into two categories: (1) some maintain the precomputed distances in flat structure [14, 15]. Literature [14] utilizes the lab technique to facilitate the distance computation. In particular, the distance between each pair of vertices can be computed easily by looking up the precomputed results. Hu et al. [15] propose the distance signature structure. Each vertex in the road network maintains a distance signature. Intuitively, distance signature needs to store all the distances between other vertices to current vertex. To minimize the storage cost, it maps the distances between objects and network nodes into categories and then encodes these categories. (2) others consider the hierarchical structure [16–18, 33, 34]. CH [33] provides a method to generate a hierarchical structure by iteratively contracting the least important node. That is, replacing these nodes with shortest cuts. This strategy relies heavily on the weight of edges, thus the whole index structure is needed to be recomputed when the weight of edges changes. In [17], they pre-compute all pairs of distance and organize the computed results in different subsets. This is motivated by the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Literature [16, 18] devise the hierarchical structures to organize the road network by partitioning the road network into multiple sub-networks. In [18], authors build a multi-level index structure called G-tree. It is constructed by iteratively partitioning the road networks into equal-size sub networks until the size of each leaf node is within the given threshold. Specifically, each node in G-tree is associated with a distance matrix that records the distance between borders (for non-leaf nodes) or the distance between borders and vertices (for leaf nodes). With G-tree, the distance between each pair of vertices can be computed by assembly-based method.Summary of the related works can be found in Table1.Table 1
Summary of the related works.
TechniquesNetworkPathMovingKeywordSafe zoneKNNRangeDBRQ [22]YNYNYNYCMRSK [23]YNYYNNYC-MNDR [24]YNYNNNYTMS [25]NNYNNYYCSPRQ [26]NNYNNNYUNICONS [20]YYYNYYNMk NN [1]NNYNYYNGMA [3]YNYNNYNV∗-digram [4]YNYNYYNMkSK [6]NNYYYYNLARC [9]YNYYYYNCPM [2],YPK-CNN [7], DKNN [8]NNYNNYN


## 2.1. Continuous/Moving Spatial Queries

Spatial queries have been extensively studied in database community. Specifically, enormous focuses have shifted to range queries [16, 23–27] and k nearest neighbor queries [2, 4–6, 9, 18]. Next, we will introduce the works on them respectively.Cheema et al. [22] explore the continuous range queries on both the Euclidean space and the road network. They adopt the concept of safe zone for monitoring the query position updating. Literature [23, 24] studied the problem in context of road network. Du et al. [23] answer the continuous spatial keyword range queries by two steps. They first build the range tree for the query, which maintains the shortest path from query point to all qualified objects. Then, the up-to-date results are obtained by adjusting the range tree accordingly. To alleviate the effect the frequent object updates, Wang et al. [24] develop the Shortest-Distance-based Tree (SD-Tree), which supports incremental computation of answer sets using retrieved paths. Literature [25–28] explore the range queries with the assumption that objects move on the Euclidean space. Specifically, [26, 28] consider an uncertainty model, in which the motion of objects is uncertainty. Chung et al. [28] propose to transform moving objects into points by hough transform, and then index them with R-tree. In [26], by transforming the irregular motion areas to polygon regions, the initial problem can be reduced to a simplified version. Wu et al. [27] study the continuous range queries over moving objects but stationary queries. They propose the containment-encoded squares (CESs), which decompose query regions and store precomputed search results. Zhang et al. [25] study the predictive range query and the predictive k nearest neighbor query. In fact, they distinguish from our work by two major aspects. On one hand, they model the motion of objects as a linear function of time but not the road network. On the other hand, they retrieve one answer set for whole querying period, while we keep searching the up-to-date answer set. Transformed minkowski sum (TMS) are used to determine whether the moving objects intersect the moving query point.Given a query path, [20] investigates the problem of continuous nearest neighbor queries. To enable efficient query processing, they precompute k NN sets for a fraction of intersection points. Nevertheless, in practice, one may require different k NN sets due to different needs when considering keywords. As a result, computing all the k NN sets for different query keywords is infeasible. Literature [1, 6] try to answer the k NN queries by safe region technique, which is motivated by V-Diagram [27]. To avoid prohibitive computation cost, Li et al. [1] utilize influential sets to restrict the safe zone. Note that, it can achieve the same large safe zone as order-k Voronoi cell [29] while minimizing the computation overhead. In [3], Mouratidis et al. study the continuous k NN queries on road networks. Different from our setting, they consider both the moving objects and queries without making assumption on the motion patterns. Two methods are developed, namely incremental monitoring algorithm (IMA) and group monitoring algorithm (GMA). The former monitors the answer set of individual query by maintaining an expansion tree from query point. With this tree, only object updating that may affect the answer set is considered. GMA groups all queries lying on the same edge, and then gets the answer sets for them based on the answer sets of end points of corresponding edge and the objects lying on this edge. [4] studies the continuous k nearest neighbor queries on the context of both Euclidean space and spatial network. They propose to construct the safe zone based on the objects, query points and the search space. However, this method has to recompute the safe regions more frequently and has higher validation overhead as pointed by [1]. Zheng et al. [9] utilize the 2-hop label to facilitate the distance computation. But this work suffers from extensive computation overhead and storage overhead. More importantly, the retrieved safe regions are too large and inaccurate when applied to our problem. Mouratidis et al. [2] develop the conceptual partitioning (CPM) technique, which handling location updates only from objects that fall in the vicinity of some query (and ignoring the rest). In [7], to support various scenarios, Object-Indexing and Query-Indexing are developed. Specifically, both of them are based on the grid index. Specifically, [8, 11, 30] retrieve the k NN set in the context of distributed environment. To be adaptable to dynamic environment, [8] develops the dynamic strip index (DSI), which enables to merge or split objects dynamically. Besides, [31, 32] consider querying trajectories/routes that a composed of a sequence of geo-locations associated with text descriptions, Cong et al. [31] proposes the Bck-tree index integrating spatial information and text information for the top-k spatial keyword query on trajectories. Feng et al. [32] focus on the indoor top-k keyword-aware routing query.


## 2.2. Road Index Structure

Distance computation brings great challenge in the presence of large scale road network. To address this problem, various index structures have been studied. In general, previous works on the road network index structure can be roughly classified into two categories: (1) some maintain the precomputed distances in flat structure [14, 15]. Literature [14] utilizes the lab technique to facilitate the distance computation. In particular, the distance between each pair of vertices can be computed easily by looking up the precomputed results. Hu et al. [15] propose the distance signature structure. Each vertex in the road network maintains a distance signature. Intuitively, distance signature needs to store all the distances between other vertices to current vertex. To minimize the storage cost, it maps the distances between objects and network nodes into categories and then encodes these categories. (2) others consider the hierarchical structure [16–18, 33, 34]. CH [33] provides a method to generate a hierarchical structure by iteratively contracting the least important node. That is, replacing these nodes with shortest cuts. This strategy relies heavily on the weight of edges, thus the whole index structure is needed to be recomputed when the weight of edges changes. In [17], they pre-compute all pairs of distance and organize the computed results in different subsets. This is motivated by the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Literature [16, 18] devise the hierarchical structures to organize the road network by partitioning the road network into multiple sub-networks. In [18], authors build a multi-level index structure called G-tree. It is constructed by iteratively partitioning the road networks into equal-size sub networks until the size of each leaf node is within the given threshold. Specifically, each node in G-tree is associated with a distance matrix that records the distance between borders (for non-leaf nodes) or the distance between borders and vertices (for leaf nodes). With G-tree, the distance between each pair of vertices can be computed by assembly-based method.Summary of the related works can be found in Table1.Table 1
Summary of the related works.
TechniquesNetworkPathMovingKeywordSafe zoneKNNRangeDBRQ [22]YNYNYNYCMRSK [23]YNYYNNYC-MNDR [24]YNYNNNYTMS [25]NNYNNYYCSPRQ [26]NNYNNNYUNICONS [20]YYYNYYNMk NN [1]NNYNYYNGMA [3]YNYNNYNV∗-digram [4]YNYNYYNMkSK [6]NNYYYYNLARC [9]YNYYYYNCPM [2],YPK-CNN [7], DKNN [8]NNYNNYN


## 3. Preliminary

### 3.1. Problem Statement

In this work, we model a road network as an undirected and edge weighted graphG=<V,E>, where V refers to the set of vertices and E refers to the set of edges. Each vertex v∈V is comprised of a location v.ℓ and a set of keywords v.ψ. Each edge ei,j connecting the vertices vi and vj is associated with a real-valued number wi,jwi,j>0 to capture the weight, e.g., the distance or travel time, of this edge. For ease of discussion, we refer to the weight as distance hereafter. Given two vertices vi, vj∈V, we denote by vi,vj the shortest distance among all paths between them. Without loss of generality, we denote the path by a sequence of adjacent vertices on the road network, e.g., P=vi1,vi2,…,vik. Table 2: lists the frequently used notations. Next, we formally define our problem.Table 2
Summary of the notations.
NotationExplanationGV,ERoad network with node setV and edge set Eva vertex of the road networkei,jAn edge of the road networkvi,vjNetwork distance betweenvi and vjPa path on the road networkQrPath based range queryQkPath basedk NN queryBNIBackbone network index structureDefinition 1.
Path Based Continuous Range (PCR) Queries. Given a road networkG, a path based continuous range query is of the form Qr=<P,T,ψ>, where P is the query path, T is the distance threshold, and ψ is the set of query keywords. The query asks for a set of vertices Sqr=v|ψ⊆v.ψ∧v,q⩽T for each query point q on P.Definition 2.
Path Based ContinuouskNN (PCk NN) Queries. Given a road network G, a path based continuous k NN query is of the form Qk=<P,k,ψ>, where P is the query path, k is the retrieved size, and ψ is the set of query keywords. The query asks for a set of vertices Sqk for each query point q on P. Specifically, Sqk satisfies the following three conditions:(i)
Sqk=k.(ii)
∀v∈Sqk, ∀v′∉Sqk, v,q≤v′,q.(iii)
for eachv∈Sqk, it covers the query keywords set, i.e. ψ⊆v.ψ.Intuitively, there are infinite number of points on the query path, which renders issuing query at each point infeasible. We will show how to transform our queries to an equivalent problem in Section5.


### 3.2. Backbone Network

We notice that all the proposed road network index structures are built over the original road network. When the road network is large, the index construction overhead and the query evaluation overhead are expensive. To address this challenge, we propose to build the index over the backbone network based on the following observation.


#### 3.2.1. Observation 1

For any vertexv with two adjacent edges, we can treat v as an internal vertex on a virtual edge.Figure2(a) depicts the instance of an original road network with 8 vertices, i.e., v1,v2,…,v8. Since v2, v3, …, v7 only have two adjacent edges, we can introduce a virtual edge e1,8 and take them as the internal vertices as shown in Figure 2(b).Figure 2
Illustration of observation 1. (a) Original edge. (b) Virtual edge.
(a)(b)


#### 3.2.2. Simplifying Strategy

Observation 1 offers a simple but powerful insight for us to simplify the road network. That is, if a vertex only has two adjacent edges, we can introduce a virtual edge and take it as an internal vertex on the virtual edge. This strategy is similar to CH [33]. We observe that CH is computationally expensive and relies heavily on the weight of edges. It needs to be rebuilt when the weight of edges changes. Hereafter, we denote by backbone network the simplified network. We call the remaining vertices on the backbone network as backbone vertex (e.g.), and vertices lying on the virtual edges as internal vertex.Figure3 presents an instance of the backbone network. We denote by the black (white) circle the backbone (internal) vertex in the original network (Figure 3(a)). We present the retrieved backbone network in Figure 3(b). Furthermore, we denote by the dotted line the virtual edge. Clearly, the backbone network achieves a compact structure compared with the original road network (Experimental results in Section 7 show that the size of road network can be cut off from 50% to 95%). It is obvious that there may be more than one edge between two vertices. For instance, there are two paths, namely v1,v10 and v1,v15,v4,v10, between v1 and v10 (one is the virtual edge and the other is the original edge). In this case, we take the one with smallest distance as the edge in the backbone network, whist maintaining all edges in our index structure (to be shown later). We denote by ei,jB the edge that connects the vertices vi,vj. Note that, ei,jB is either an original edge or a virtual edge comprising of multiple original edges. For two internal vertices vi,vj, we denote by vi,vj the direct distance between them on the corresponding virtual edge.Figure 3
Backbone network. (a) Original network. (b) Backbone network
(a)(b)Theorem 1.
∀vm,vn∈V, the shortest distance between them is defined as:
ifvm,vn are on the same virtual edge ei,jB, then:(1)vm,vn=minvm,vn,vi,vj+vi,vm+vn,vj.
ifvm,vn are not on the same virtual edge ei,jB, then:(2)vm,vn=minvm,vi+vi,vn,vm,vj+vn,vj.Proof.
This theorem is self-evident, we omit the proof here due to the space consideration, the illustration of this theorem can be found in Figure4.Figure 4
Illustration of Theorem1. (a) Internal distance computation. (b) External distance computation.
(a)(b)


## 3.1. Problem Statement

In this work, we model a road network as an undirected and edge weighted graphG=<V,E>, where V refers to the set of vertices and E refers to the set of edges. Each vertex v∈V is comprised of a location v.ℓ and a set of keywords v.ψ. Each edge ei,j connecting the vertices vi and vj is associated with a real-valued number wi,jwi,j>0 to capture the weight, e.g., the distance or travel time, of this edge. For ease of discussion, we refer to the weight as distance hereafter. Given two vertices vi, vj∈V, we denote by vi,vj the shortest distance among all paths between them. Without loss of generality, we denote the path by a sequence of adjacent vertices on the road network, e.g., P=vi1,vi2,…,vik. Table 2: lists the frequently used notations. Next, we formally define our problem.Table 2
Summary of the notations.
NotationExplanationGV,ERoad network with node setV and edge set Eva vertex of the road networkei,jAn edge of the road networkvi,vjNetwork distance betweenvi and vjPa path on the road networkQrPath based range queryQkPath basedk NN queryBNIBackbone network index structureDefinition 1.
Path Based Continuous Range (PCR) Queries. Given a road networkG, a path based continuous range query is of the form Qr=<P,T,ψ>, where P is the query path, T is the distance threshold, and ψ is the set of query keywords. The query asks for a set of vertices Sqr=v|ψ⊆v.ψ∧v,q⩽T for each query point q on P.Definition 2.
Path Based ContinuouskNN (PCk NN) Queries. Given a road network G, a path based continuous k NN query is of the form Qk=<P,k,ψ>, where P is the query path, k is the retrieved size, and ψ is the set of query keywords. The query asks for a set of vertices Sqk for each query point q on P. Specifically, Sqk satisfies the following three conditions:(i)
Sqk=k.(ii)
∀v∈Sqk, ∀v′∉Sqk, v,q≤v′,q.(iii)
for eachv∈Sqk, it covers the query keywords set, i.e. ψ⊆v.ψ.Intuitively, there are infinite number of points on the query path, which renders issuing query at each point infeasible. We will show how to transform our queries to an equivalent problem in Section5.


## 3.2. Backbone Network

We notice that all the proposed road network index structures are built over the original road network. When the road network is large, the index construction overhead and the query evaluation overhead are expensive. To address this challenge, we propose to build the index over the backbone network based on the following observation.


### 3.2.1. Observation 1

For any vertexv with two adjacent edges, we can treat v as an internal vertex on a virtual edge.Figure2(a) depicts the instance of an original road network with 8 vertices, i.e., v1,v2,…,v8. Since v2, v3, …, v7 only have two adjacent edges, we can introduce a virtual edge e1,8 and take them as the internal vertices as shown in Figure 2(b).Figure 2
Illustration of observation 1. (a) Original edge. (b) Virtual edge.
(a)(b)


### 3.2.2. Simplifying Strategy

Observation 1 offers a simple but powerful insight for us to simplify the road network. That is, if a vertex only has two adjacent edges, we can introduce a virtual edge and take it as an internal vertex on the virtual edge. This strategy is similar to CH [33]. We observe that CH is computationally expensive and relies heavily on the weight of edges. It needs to be rebuilt when the weight of edges changes. Hereafter, we denote by backbone network the simplified network. We call the remaining vertices on the backbone network as backbone vertex (e.g.), and vertices lying on the virtual edges as internal vertex.Figure3 presents an instance of the backbone network. We denote by the black (white) circle the backbone (internal) vertex in the original network (Figure 3(a)). We present the retrieved backbone network in Figure 3(b). Furthermore, we denote by the dotted line the virtual edge. Clearly, the backbone network achieves a compact structure compared with the original road network (Experimental results in Section 7 show that the size of road network can be cut off from 50% to 95%). It is obvious that there may be more than one edge between two vertices. For instance, there are two paths, namely v1,v10 and v1,v15,v4,v10, between v1 and v10 (one is the virtual edge and the other is the original edge). In this case, we take the one with smallest distance as the edge in the backbone network, whist maintaining all edges in our index structure (to be shown later). We denote by ei,jB the edge that connects the vertices vi,vj. Note that, ei,jB is either an original edge or a virtual edge comprising of multiple original edges. For two internal vertices vi,vj, we denote by vi,vj the direct distance between them on the corresponding virtual edge.Figure 3
Backbone network. (a) Original network. (b) Backbone network
(a)(b)Theorem 1.
∀vm,vn∈V, the shortest distance between them is defined as:
ifvm,vn are on the same virtual edge ei,jB, then:(1)vm,vn=minvm,vn,vi,vj+vi,vm+vn,vj.
ifvm,vn are not on the same virtual edge ei,jB, then:(2)vm,vn=minvm,vi+vi,vn,vm,vj+vn,vj.Proof.
This theorem is self-evident, we omit the proof here due to the space consideration, the illustration of this theorem can be found in Figure4.Figure 4
Illustration of Theorem1. (a) Internal distance computation. (b) External distance computation.
(a)(b)


## 3.2.1. Observation 1

For any vertexv with two adjacent edges, we can treat v as an internal vertex on a virtual edge.Figure2(a) depicts the instance of an original road network with 8 vertices, i.e., v1,v2,…,v8. Since v2, v3, …, v7 only have two adjacent edges, we can introduce a virtual edge e1,8 and take them as the internal vertices as shown in Figure 2(b).Figure 2
Illustration of observation 1. (a) Original edge. (b) Virtual edge.
(a)(b)


## 3.2.2. Simplifying Strategy

Observation 1 offers a simple but powerful insight for us to simplify the road network. That is, if a vertex only has two adjacent edges, we can introduce a virtual edge and take it as an internal vertex on the virtual edge. This strategy is similar to CH [33]. We observe that CH is computationally expensive and relies heavily on the weight of edges. It needs to be rebuilt when the weight of edges changes. Hereafter, we denote by backbone network the simplified network. We call the remaining vertices on the backbone network as backbone vertex (e.g.), and vertices lying on the virtual edges as internal vertex.Figure3 presents an instance of the backbone network. We denote by the black (white) circle the backbone (internal) vertex in the original network (Figure 3(a)). We present the retrieved backbone network in Figure 3(b). Furthermore, we denote by the dotted line the virtual edge. Clearly, the backbone network achieves a compact structure compared with the original road network (Experimental results in Section 7 show that the size of road network can be cut off from 50% to 95%). It is obvious that there may be more than one edge between two vertices. For instance, there are two paths, namely v1,v10 and v1,v15,v4,v10, between v1 and v10 (one is the virtual edge and the other is the original edge). In this case, we take the one with smallest distance as the edge in the backbone network, whist maintaining all edges in our index structure (to be shown later). We denote by ei,jB the edge that connects the vertices vi,vj. Note that, ei,jB is either an original edge or a virtual edge comprising of multiple original edges. For two internal vertices vi,vj, we denote by vi,vj the direct distance between them on the corresponding virtual edge.Figure 3
Backbone network. (a) Original network. (b) Backbone network
(a)(b)Theorem 1.
∀vm,vn∈V, the shortest distance between them is defined as:
ifvm,vn are on the same virtual edge ei,jB, then:(1)vm,vn=minvm,vn,vi,vj+vi,vm+vn,vj.
ifvm,vn are not on the same virtual edge ei,jB, then:(2)vm,vn=minvm,vi+vi,vn,vm,vj+vn,vj.Proof.
This theorem is self-evident, we omit the proof here due to the space consideration, the illustration of this theorem can be found in Figure4.Figure 4
Illustration of Theorem1. (a) Internal distance computation. (b) External distance computation.
(a)(b)


## 4. Backbone Network Index Structure

In this section, we introduce the backbone network index (BNI) structure, which is a dual-index. Specifically, it maintains the global insights of network by G-tree (in memory) and the detailed information of network by the adjacent list (on disk).


### 4.1. G-Tree Index Structure

Though there are various partition strategies for road network, we adopts [18] in this work. This is because G-tree has the following properties: (1) enables efficient distance computations for large network; (2) offers global sight of the road network. We proceed to introduce some basic notions that lay the foundation of G-tree.Definition 3.
(Backbone Network Partition). Given a road networkG=<V,E>, we denote by GB=<VB,EB> the corresponding backbone network. The partition of GB is a set of regions, i.e., ℛ1=<V1B,E1B> ,…, ℛm=<VmB,EmB> such that:(i)
∪1≤i≤mViB=VB,(ii)
Fori≠j,ViB∩VjB=∅, and(iii)
∀u,v∈ViB, if u,v∈EB, then u,v∈EiB.In the partitions, there are some portal vertices that connect to the vertices of other regions. To illustrate this, we define the concept of borders as follows.Definition 4 (Backbone Network Border).
Given a backbone networkGB=<VB,EB>, a region ℛi of GB. We say that u∈ViB is a border if ∃eu,v∈EB and v∉ViB. Hereafter, we denote by ℬℛi all the borders of ℛi.As shown in Figure5, we present an instance of the partition of the backbone road network. Note that, all borders are marked with red. Correspondingly, we show the G-tree in Figure 6, which is built over the road network in Figure 5(b). Specifically, each node in G-tree corresponds to one subregion in Figure 5(b).Figure 5
Backbone network structure. (a) Vertex descriptions. (b) Network partition.
(a)(b)Figure 6
G-tree index structure.Each node in G-tree is of the formid,ψH,ℬℛ,ℳ, where id is the identifer of the node, ψH contains some keyword information of the corresponding node (will be discussed later). We denote by ℬℛ the borders of ℛ, and ℳ refers to the distance matrix. Specifically, for leaf node, it records the distance between borders and backbone vertices (e.g. ℳ6). For non-leaf node, it record the distance between borders (e.g. ℳ2).As with [35], we map vertices and keywords to a h bits number by a hush function H. Specifically, for each keyword ω, Hω sets exactly one of the h bits to 1. Hv is the superimposition of Hw for each w∈v.ψ, and ψH is the superimposition of Hv for each relevant vertex v. We say v is relevant to a node ℛ if v lies on an edge ei,jB such that vi∈ℛ.VB or vj∈ℛ.VB. That is, relevant vertices contain all the vertices in ℛ and the vertices on the adjacent edges to ℛ.For a vertexv and a node ℛ, we denote by minDistv,ℛ the minimum possible distance between v and the vertices in ℛ. Specifically, if v∈ℛ.VB, then we set minDistv,ℛ to 0. Otherwise, we set minDistv,ℛ as the minimum distance between v and the borders of ℛ, i.e., minDistv,ℛ=minv′∈ℬRv,v′.


### 4.2. Generalized Adjacent List File

Adjacent list has been used widely in the context of road network [19, 36] for maintaining detailed information of edges. In this work, we generalize the adjacent list by the following two aspects. First, we maintain all edges (including both the real edge and virtual edges) for two adjacent vertices v and u in the backbone network. Second, the road network is stored on disk based on locality principle rather than the vertex id. The partition strategy of G-tree suggests that the vertices in the same subregion has higher possibility to be accessed together. Inspired by this, we propose to maintain the road network sequently from left to right leaf nodes, as shown by the arrow line in Figure 6.As shown in Figure7, adjacent list is comprised of three components, namely hash table, adjacent file and point file. We proceed to introduce them. By hash table, each backbone vertex vi is mapped to a pair <ℛi,Ai>, where ℛi refers to the leaf node containing vi and Ai records the start address of the item for vi in adjacent file. For each backbone vertex vi, we maintain an item for it in adjacent file. The item first records the number of adjacent vertices, and the associated keywords for vi. Then, each adjacent vertex corresponds to an entry, and each edge is associated with a record file, the superimposition of keywords associated with the internal vertices, and the start address of internal vertices on this edge.The structure of point file is simple compared with adjacent file. In the point file, all internal vertices lying on edges between two vertices are placed in one group. More details about the generalized adjacent list file can be found in our previous work [21].Figure 7
Generalized adjacent list file.The structure of point file is simple compared with adjacent file. In the point file, all internal vertices lying on edges between two vertices are placed in one group. The group first records the corresponding backbone vertices, and the total number of internal vertices. Then, we maintain the id, the direct distance to smaller vertex, and the associated keywords for each internal vertex.


## 4.1. G-Tree Index Structure

Though there are various partition strategies for road network, we adopts [18] in this work. This is because G-tree has the following properties: (1) enables efficient distance computations for large network; (2) offers global sight of the road network. We proceed to introduce some basic notions that lay the foundation of G-tree.Definition 3.
(Backbone Network Partition). Given a road networkG=<V,E>, we denote by GB=<VB,EB> the corresponding backbone network. The partition of GB is a set of regions, i.e., ℛ1=<V1B,E1B> ,…, ℛm=<VmB,EmB> such that:(i)
∪1≤i≤mViB=VB,(ii)
Fori≠j,ViB∩VjB=∅, and(iii)
∀u,v∈ViB, if u,v∈EB, then u,v∈EiB.In the partitions, there are some portal vertices that connect to the vertices of other regions. To illustrate this, we define the concept of borders as follows.Definition 4 (Backbone Network Border).
Given a backbone networkGB=<VB,EB>, a region ℛi of GB. We say that u∈ViB is a border if ∃eu,v∈EB and v∉ViB. Hereafter, we denote by ℬℛi all the borders of ℛi.As shown in Figure5, we present an instance of the partition of the backbone road network. Note that, all borders are marked with red. Correspondingly, we show the G-tree in Figure 6, which is built over the road network in Figure 5(b). Specifically, each node in G-tree corresponds to one subregion in Figure 5(b).Figure 5
Backbone network structure. (a) Vertex descriptions. (b) Network partition.
(a)(b)Figure 6
G-tree index structure.Each node in G-tree is of the formid,ψH,ℬℛ,ℳ, where id is the identifer of the node, ψH contains some keyword information of the corresponding node (will be discussed later). We denote by ℬℛ the borders of ℛ, and ℳ refers to the distance matrix. Specifically, for leaf node, it records the distance between borders and backbone vertices (e.g. ℳ6). For non-leaf node, it record the distance between borders (e.g. ℳ2).As with [35], we map vertices and keywords to a h bits number by a hush function H. Specifically, for each keyword ω, Hω sets exactly one of the h bits to 1. Hv is the superimposition of Hw for each w∈v.ψ, and ψH is the superimposition of Hv for each relevant vertex v. We say v is relevant to a node ℛ if v lies on an edge ei,jB such that vi∈ℛ.VB or vj∈ℛ.VB. That is, relevant vertices contain all the vertices in ℛ and the vertices on the adjacent edges to ℛ.For a vertexv and a node ℛ, we denote by minDistv,ℛ the minimum possible distance between v and the vertices in ℛ. Specifically, if v∈ℛ.VB, then we set minDistv,ℛ to 0. Otherwise, we set minDistv,ℛ as the minimum distance between v and the borders of ℛ, i.e., minDistv,ℛ=minv′∈ℬRv,v′.


## 4.2. Generalized Adjacent List File

Adjacent list has been used widely in the context of road network [19, 36] for maintaining detailed information of edges. In this work, we generalize the adjacent list by the following two aspects. First, we maintain all edges (including both the real edge and virtual edges) for two adjacent vertices v and u in the backbone network. Second, the road network is stored on disk based on locality principle rather than the vertex id. The partition strategy of G-tree suggests that the vertices in the same subregion has higher possibility to be accessed together. Inspired by this, we propose to maintain the road network sequently from left to right leaf nodes, as shown by the arrow line in Figure 6.As shown in Figure7, adjacent list is comprised of three components, namely hash table, adjacent file and point file. We proceed to introduce them. By hash table, each backbone vertex vi is mapped to a pair <ℛi,Ai>, where ℛi refers to the leaf node containing vi and Ai records the start address of the item for vi in adjacent file. For each backbone vertex vi, we maintain an item for it in adjacent file. The item first records the number of adjacent vertices, and the associated keywords for vi. Then, each adjacent vertex corresponds to an entry, and each edge is associated with a record file, the superimposition of keywords associated with the internal vertices, and the start address of internal vertices on this edge.The structure of point file is simple compared with adjacent file. In the point file, all internal vertices lying on edges between two vertices are placed in one group. More details about the generalized adjacent list file can be found in our previous work [21].Figure 7
Generalized adjacent list file.The structure of point file is simple compared with adjacent file. In the point file, all internal vertices lying on edges between two vertices are placed in one group. The group first records the corresponding backbone vertices, and the total number of internal vertices. Then, we maintain the id, the direct distance to smaller vertex, and the associated keywords for each internal vertex.


## 5. Algorithms

In this section, we first explore the query framework at a high level, and then present the algorithms for PCR and PCk NN queries.


### 5.1. Overview of the Framework

Considering there are infinite number of query points on the query path, it is infeasible to issue the query at each point. We proceed to show how to transform our queries to a simple but equivalent problem.Theorem 2.
Given a path based range queryQr, and an edge ei,j on Qr.P. For any point q on ei,j, it holds that Sqr⊆Svir∪Svjr∪Ωei,j, where Ωei,j is the set of internal vertices on ei,j that cover Qr.ψ.Proof.
The proof of this theorem can be found in the conference version in [21]. And the illustration of this theorem can be found in Figure 8.Figure 8
Illustration of Theorems2 and 3.Theorem 3.
Given a path basedk NN query Qk, and an edge ei,j on Qk.P. For any point q on ei,j, it holds that Sqk⊆Svik∪Svjk∪Ωei,j, where Ωei,j is the set of internal vertices on ei,j that cover Qk.ψ.Proof.
The proof of this theorem can be derived as with Theorem2. We omit the proof here.
Inspired by the safe zone technique [4] we know that the answer set might not change when query point moves within some intervals. This intuition offers us a direction to transform our queries to a simple but equivalent problem.Definition 5.
Safe Interval. Given a query pathP, we define the safe interval as a disclose segment on P, denoted by Sℐx,y, where x and y denote the start point and end point of this interval. When q moves within Sℐx,y, the answer set is unchanged. We denote the safe interval of Qr and Qk as Sℐrx,y and Sℐkx,y respectively.In practice, there are multiple safe intervals onP, which are split by some special points, i.e., the start and end points of safe intervals. For ease of presentation, we call these points as event point hereafter.Definition 6.
Backbone Path. Given a query pathP in G=<V,E>, we define the corresponding backbone path PB as a path in GB=<VB,EB> such that:(i)
∀v∈P,∃vi,vj∈PB such that v locates on ei,j, and(ii)
PB is minimum.In the above definition, we sayPB is minimum if there does not exist another backbone path P′ that contains less number of vertices than PB and satisfies the first condition.We answer the path based queries by a two phases query framework. The task of the first phase is to compute the answer set for each vertex inPB. Note that, this can be achieved by only issuing the query once. We maintain the retrieved answer sets for the next phase. We call this phase Issuing query. In the second phase, we mainly focus on finding the event point on the PB. As discussed in Theorems 2 and 3, the answer sets for these points can be identified easily without issuing the query at these points. This phase is called Identifying event point.Clearly, by these two phases, we can answer the queries easily. Meanwhile, the computation cost can be cut off significantly. The Two-Phase Progressive (TPP) framework is described in Algorithm1. The details of the algorithm can be found in the conference version in [21].Algorithm 1: TPP Framework.
Input :Qr=<P,T,ψ>Output:S(1)
VQ←Construct the query vertices from Qr.P(2)
SQ←IssuingSpatialKeywordQueryQr(3)
Ξ←IdentifyingEventPointSQ,VQ;(4)
S←Compute answer sets for event points in Ξ progressively(5)
ReturnS.


### 5.2. PCR Query Processing

We answer the PCR query by two steps. Firstly, we get the answer sets for backbone vertices by issuing the range query at the first backbone vertex inPB. Then, we identify event points by these sets.


#### 5.2.1. Issuing Range Query

Intuitively, the answer sets for these backbone vertices are overlapped. This motivates us to compute the answer sets progressively. The following theorem offers us the insight for progressive computation.Theorem 4.
Given two query pointq,q′ on the query path, and a distance threshold T. We denote by Sq′r the range query results of q′. For any v∈Sq′r, it holds that v,q≤T+q,q′.Proof.
This theorem is obvious. We omit the proof here.
Considering the fact that the distance between backbone vertices is not large, we propose to achieve the progressive computation by a filter-and-verification model. At a high level, we expand the network from the first vertexvf in PB progressively (for filter). We know that, for each backbone vertex v, the candidates must within the range of T+v,vf. That is, we only need to verify the vertices within this range for other backbone vertices (for verification).
As presented in Algorithm2, we retrieve the answer sets for backbone vertices in PB by a filter-and-verification framework. Particularly, we utilize curtDist≤stopDist as the filter condition for the current visited vertex v (line 7). From Theorem 4, we know that the range query results for v are within the range of stopDist to vf. In the process of tree traversal, if ℛi is a non-leaf node, we need to add its child nodes that cover the query keywords into the priority queue PQ for further exploration (lines 9–13). Otherwise, that is ℛi is a leaf node. We first compute the distance between vf and the backbone vertices in ℛi (lines 15–16). Then, for each backbone vertex v′, we find the results by checking the vertices lying on the adjacent edges (lines 17–19). Note that, we also maintain the candidates, which cover the query keywords, by C for achieving quick verification. When the filter condition is broken, we proceed to build Svr by verifying candidates in C (lines 20–23).
Optimizing Strategies: To facilitate the query processing, we investigate the optimizing strategies. We observe that there are much repeated computation when computing theminDist⋅ and performing verifications, thus we can maintain the computed distances for the following distance computation.Algorithm 2:Issuing Range Query.
Input :Qr=<P,T,ψ>Output:PB, S(1)
buildPB from P(2)
PQ.pushℛ0,0;(3)
curtDist← 0; stopDist←0(4)
vf←The first vertex in PB;(5)
for each PBdo(6)
stopDist←Qr.T+v,vf(7)
whilecurtDist≤stopDistdo(8)
ℛi,curtDist←PQ.pop;(9)
ifℛi is a non-leaf node then(10)
for each child node ℛc of ℛido(11)
ifQr.ψ⊆ℛc.ψHthen(12)
compute theminDistvf,Rc;(13)
PQ.pushRc,minDistvf,Rc;(14)
else(15)
ifvf is in ℛithen(16)
InternalDistvf,ℛi ;(17)
else ExternalDist vf,ℛi ;(18)
;(19)
for each v′∈ℛido(20)
put candidates on adjacent edges intoCℛi;(21)
put qualified candidates intoSvfr;(22)
for each ℛi in Cdo(23)
ifv is in ℛithen InternalDist v,ℛi ;(24)
;(25)
else ExternalDist v,ℛi ;(26)
;(27)
put all qualified candidates ofCℛi into Svr(28)
ReturnPB and S;


#### 5.2.2. Identifying Event Point

We mainly focus on identifying event points on edges. Specifically, we distinguish event points by two types, namelyIE and OE. We denote by IE the in event point, and OE the out event point. We refer to in/out from the direction of the backbone vertex that is near to vf. As suggested in Theorem 2, the event points on ei,j are determined by Svir, Svjr and Qr.T. Specifically, there are seven cases, as follows:Algorithm 3:PCR−IdentifyingEventPoint.
Input :S,PBOutput: The sequence of event points.(1)
forl← 1 to mdo(2)
vi←PBl−1; vj←PBl;(3)
Ωei,j← the qualified vertices on ei,j;(4)
for each v∈Ωei,jdo(5)
Ξvi←event points computed by (1–4)(6)
for each v∈Svirdo(7)
ifv is not on ei,jthen(8)
ifv is not in Svjrthen(9)
Ξvi←event points computed by (5);(10)
else(11)
Ξvi←event points computed by (7);(12)
for each v∈Svjrdo(13)
ifv is not on ei,jthen(14)
ifv is not in Svirthen(15)
Ξvi←event points computed by (6)(16)
ReturnΞTheorem 5.
Given two backbone verticesvi,vj on R¯, and a vertex covering the keywords. Then, the event point in the edge has the following seven cases (we only describe the first three cases according to Figure 9, and referring our previous work [21] for more details.):(i)
Ifv on one edge between vi,vj, and vi,v>Qr.T∧v,vj>Qr.T, then there are two event point ;(ii)
Ifv on one edge between vi,vj, and vi,v>Qr.T∧v,vj>Qr.T, then there are two event point .(iii)
Ifv on one edge between vi,vj, and vi,v<Qr.T∧v,vj>Qr.T, then there are two event point.Figure 9
Illustration of range event point computation. (a) Event point 1. (b) Event point 2. (c) Event point 3. (d) Event point 4. (e) Event point 5. (f) Event point 6. (g) Event point 7.
(a)(b)(c)(d)(e)(f)(g)Algorithm3 presents the pseudo-code for identifying the event points. For each edge ei,j on PB, we denote by Svir and Svjr the answer sets for vi and vj. We first identify the event points for internal vertices on ei,j (lines 4–5). Then, for each vertex v∈Svir, if it is on the edge, we know that it has already been processed. Otherwise, we find out whether it is in Svjr. If yes, there might exist both in and out event points (lines 8–9). If no, we only need to compute the out event points for v (lines 10–11). Then, for the vertices in Svjr, we only need to process ones that are neither on ei,j nor in Svir. For these vertices, we need to compute the in event point for them (lines 12–15).


### 5.3. PCk NN Query Processing

Similarly, to answer the PCk NN queries, we first retrieve the k NN sets for backbone vertices in PB. Then, we identify the event points.


### 5.4. Issuingk NN Query

Algorithm 4:IssuingkNNQuery.
Input :Qr=<P,T,ψ>Output:PB, S(1)
buildPB from P;(2)
PQ.pushR0,0;(3)
curtDist← 0; stopDist←0;(4)
for each v in PBdo(5)
kthv←INFINITY ;(6)
stopDist←v,vf;(7)
while (curtDist<stopDist+kthvf) do(8)
Ri,curtDist←PQ.pop(9)
ifℛi is a non-leaf node then(10)
for each child node ℛc of ℛido(11)
ifQr.ψ⊆ℛc.ψHthen(12)
compute theminDistvf,Rc(13)
PQ.pushRc,minDistvf,Rc;(14)
else(15)
ifvf is in ℛithen(16)
InternalDistvf,ℛi(17)
else ExternalDist vf,ℛi(18)
;(19)
for each v′∈ℛido(20)
put candidates on adjacent edges intoCℛi;(21)
put qualified candidates intoSvfr;(22)
updatekthvf;(23)
for each ℛi in Cdo(24)
ifv is in ℛithen InternalDist v,ℛi(25)
;(26)
else ExternalDist v,ℛi(27)
;(28)
put all qualified candidates ofCℛi into Svr(29)
ReturnPB and STheorem 6.
Given two query pointq,q′ on the query path. We denote by Sq′k the k nearest neighbor query results of q′. For any v∈Sq′k, it holds that v,q≤Kq+q,q′. Here, Kq refers to the distance between q and the k th nearest neighbor.Proof.
This theorem is obvious. We omit the proof here.
Theorem6 enables to find the k nearest neighbor by only issuing the k nearest neighbor search once. Algorithm 4 shows the pseudo-code for finding k NN sets for backbone vertices. Generally, it is similar to Algorithm 1. The major difference comes from the filter condition (line 7). We denoted by kthvf the distance between vf and the k th nearest neighbor. Besides, we need to update kthvf accordingly when new result is inserted into Svfr (lines 17–20).


#### 5.4.1. Identifying Event Point

Compared with the range query, thek NN query is more complicated. Whether a vertex v is the k NN result for the query is not only determined by its distance to query point but also by other vertices. This leads to the difficulty in identifying the event points for k NN queries. To address this problem, we introduce the concept of distance curve, which captures the change of distance between query point and the candidate when query point moves along the edge.Figure10(a) illustrates the distance curve for different cases. Given the candidate vertex v, for c1,c2, we know that the shortest path from v to vj or vi must go through vi or vj. For c3,c4, it is clear that v is on ei,j. Different from c3,c4, we know that c5,c6 present cases as there are more changes. Based on the distance curve, we identify the event points as illustrated in Figure 10(b). We know that the event points always appear at the intersections and turn points. To find out the event points, we can first compute all the intersections and turn points, and then compute the k NN at each turn points. This naive method is time consuming, thus we propose the enhanced method. We maintain the k NN curves that has the lowest distance. Then, we compute the intersections between these curves and other curves. We select the first intersection, and compute the k NN. This procedure continues until this edge is explored.Figure 10
Illustration of distance function. (a) Distance curve. (b) Event point.
(a)(b)Algorithm 5:PCkNNIdentifyingEventPoint.
Input :S,PBOutput: The sequence of event point.(1)
forl← 1 to mdo(2)
vi←PBl−1; vj←PBl(3)
compute the distance curve for vertices inSvik,Svjk;(4)
k NN ←pres; curtPos←0;(5)
whilecurtPos is on this edge do(6)
curtPos← minimum intersection position between k NN and other curves(7)
k NN ← recompute the k NN at curtPos(8)
ifk NN changes then(9)
add event point intoΞvi(10)
ReturnΞWe present the details of how to compute the event points fork NN in Algorithm 5. We first compute the distance curves for vertices in Svik and Svjk (line 3). Then, we compute the event points by accessing the next explored intersection. At this point, we update the k NN by comparing the distance value of start and end points. If k NN is changed, we add the event point into Ξvi (lines 8–9).


## 5.1. Overview of the Framework

Considering there are infinite number of query points on the query path, it is infeasible to issue the query at each point. We proceed to show how to transform our queries to a simple but equivalent problem.Theorem 2.
Given a path based range queryQr, and an edge ei,j on Qr.P. For any point q on ei,j, it holds that Sqr⊆Svir∪Svjr∪Ωei,j, where Ωei,j is the set of internal vertices on ei,j that cover Qr.ψ.Proof.
The proof of this theorem can be found in the conference version in [21]. And the illustration of this theorem can be found in Figure 8.Figure 8
Illustration of Theorems2 and 3.Theorem 3.
Given a path basedk NN query Qk, and an edge ei,j on Qk.P. For any point q on ei,j, it holds that Sqk⊆Svik∪Svjk∪Ωei,j, where Ωei,j is the set of internal vertices on ei,j that cover Qk.ψ.Proof.
The proof of this theorem can be derived as with Theorem2. We omit the proof here.
Inspired by the safe zone technique [4] we know that the answer set might not change when query point moves within some intervals. This intuition offers us a direction to transform our queries to a simple but equivalent problem.Definition 5.
Safe Interval. Given a query pathP, we define the safe interval as a disclose segment on P, denoted by Sℐx,y, where x and y denote the start point and end point of this interval. When q moves within Sℐx,y, the answer set is unchanged. We denote the safe interval of Qr and Qk as Sℐrx,y and Sℐkx,y respectively.In practice, there are multiple safe intervals onP, which are split by some special points, i.e., the start and end points of safe intervals. For ease of presentation, we call these points as event point hereafter.Definition 6.
Backbone Path. Given a query pathP in G=<V,E>, we define the corresponding backbone path PB as a path in GB=<VB,EB> such that:(i)
∀v∈P,∃vi,vj∈PB such that v locates on ei,j, and(ii)
PB is minimum.In the above definition, we sayPB is minimum if there does not exist another backbone path P′ that contains less number of vertices than PB and satisfies the first condition.We answer the path based queries by a two phases query framework. The task of the first phase is to compute the answer set for each vertex inPB. Note that, this can be achieved by only issuing the query once. We maintain the retrieved answer sets for the next phase. We call this phase Issuing query. In the second phase, we mainly focus on finding the event point on the PB. As discussed in Theorems 2 and 3, the answer sets for these points can be identified easily without issuing the query at these points. This phase is called Identifying event point.Clearly, by these two phases, we can answer the queries easily. Meanwhile, the computation cost can be cut off significantly. The Two-Phase Progressive (TPP) framework is described in Algorithm1. The details of the algorithm can be found in the conference version in [21].Algorithm 1: TPP Framework.
Input :Qr=<P,T,ψ>Output:S(1)
VQ←Construct the query vertices from Qr.P(2)
SQ←IssuingSpatialKeywordQueryQr(3)
Ξ←IdentifyingEventPointSQ,VQ;(4)
S←Compute answer sets for event points in Ξ progressively(5)
ReturnS.


## 5.2. PCR Query Processing

We answer the PCR query by two steps. Firstly, we get the answer sets for backbone vertices by issuing the range query at the first backbone vertex inPB. Then, we identify event points by these sets.


### 5.2.1. Issuing Range Query

Intuitively, the answer sets for these backbone vertices are overlapped. This motivates us to compute the answer sets progressively. The following theorem offers us the insight for progressive computation.Theorem 4.
Given two query pointq,q′ on the query path, and a distance threshold T. We denote by Sq′r the range query results of q′. For any v∈Sq′r, it holds that v,q≤T+q,q′.Proof.
This theorem is obvious. We omit the proof here.
Considering the fact that the distance between backbone vertices is not large, we propose to achieve the progressive computation by a filter-and-verification model. At a high level, we expand the network from the first vertexvf in PB progressively (for filter). We know that, for each backbone vertex v, the candidates must within the range of T+v,vf. That is, we only need to verify the vertices within this range for other backbone vertices (for verification).
As presented in Algorithm2, we retrieve the answer sets for backbone vertices in PB by a filter-and-verification framework. Particularly, we utilize curtDist≤stopDist as the filter condition for the current visited vertex v (line 7). From Theorem 4, we know that the range query results for v are within the range of stopDist to vf. In the process of tree traversal, if ℛi is a non-leaf node, we need to add its child nodes that cover the query keywords into the priority queue PQ for further exploration (lines 9–13). Otherwise, that is ℛi is a leaf node. We first compute the distance between vf and the backbone vertices in ℛi (lines 15–16). Then, for each backbone vertex v′, we find the results by checking the vertices lying on the adjacent edges (lines 17–19). Note that, we also maintain the candidates, which cover the query keywords, by C for achieving quick verification. When the filter condition is broken, we proceed to build Svr by verifying candidates in C (lines 20–23).
Optimizing Strategies: To facilitate the query processing, we investigate the optimizing strategies. We observe that there are much repeated computation when computing theminDist⋅ and performing verifications, thus we can maintain the computed distances for the following distance computation.Algorithm 2:Issuing Range Query.
Input :Qr=<P,T,ψ>Output:PB, S(1)
buildPB from P(2)
PQ.pushℛ0,0;(3)
curtDist← 0; stopDist←0(4)
vf←The first vertex in PB;(5)
for each PBdo(6)
stopDist←Qr.T+v,vf(7)
whilecurtDist≤stopDistdo(8)
ℛi,curtDist←PQ.pop;(9)
ifℛi is a non-leaf node then(10)
for each child node ℛc of ℛido(11)
ifQr.ψ⊆ℛc.ψHthen(12)
compute theminDistvf,Rc;(13)
PQ.pushRc,minDistvf,Rc;(14)
else(15)
ifvf is in ℛithen(16)
InternalDistvf,ℛi ;(17)
else ExternalDist vf,ℛi ;(18)
;(19)
for each v′∈ℛido(20)
put candidates on adjacent edges intoCℛi;(21)
put qualified candidates intoSvfr;(22)
for each ℛi in Cdo(23)
ifv is in ℛithen InternalDist v,ℛi ;(24)
;(25)
else ExternalDist v,ℛi ;(26)
;(27)
put all qualified candidates ofCℛi into Svr(28)
ReturnPB and S;


### 5.2.2. Identifying Event Point

We mainly focus on identifying event points on edges. Specifically, we distinguish event points by two types, namelyIE and OE. We denote by IE the in event point, and OE the out event point. We refer to in/out from the direction of the backbone vertex that is near to vf. As suggested in Theorem 2, the event points on ei,j are determined by Svir, Svjr and Qr.T. Specifically, there are seven cases, as follows:Algorithm 3:PCR−IdentifyingEventPoint.
Input :S,PBOutput: The sequence of event points.(1)
forl← 1 to mdo(2)
vi←PBl−1; vj←PBl;(3)
Ωei,j← the qualified vertices on ei,j;(4)
for each v∈Ωei,jdo(5)
Ξvi←event points computed by (1–4)(6)
for each v∈Svirdo(7)
ifv is not on ei,jthen(8)
ifv is not in Svjrthen(9)
Ξvi←event points computed by (5);(10)
else(11)
Ξvi←event points computed by (7);(12)
for each v∈Svjrdo(13)
ifv is not on ei,jthen(14)
ifv is not in Svirthen(15)
Ξvi←event points computed by (6)(16)
ReturnΞTheorem 5.
Given two backbone verticesvi,vj on R¯, and a vertex covering the keywords. Then, the event point in the edge has the following seven cases (we only describe the first three cases according to Figure 9, and referring our previous work [21] for more details.):(i)
Ifv on one edge between vi,vj, and vi,v>Qr.T∧v,vj>Qr.T, then there are two event point ;(ii)
Ifv on one edge between vi,vj, and vi,v>Qr.T∧v,vj>Qr.T, then there are two event point .(iii)
Ifv on one edge between vi,vj, and vi,v<Qr.T∧v,vj>Qr.T, then there are two event point.Figure 9
Illustration of range event point computation. (a) Event point 1. (b) Event point 2. (c) Event point 3. (d) Event point 4. (e) Event point 5. (f) Event point 6. (g) Event point 7.
(a)(b)(c)(d)(e)(f)(g)Algorithm3 presents the pseudo-code for identifying the event points. For each edge ei,j on PB, we denote by Svir and Svjr the answer sets for vi and vj. We first identify the event points for internal vertices on ei,j (lines 4–5). Then, for each vertex v∈Svir, if it is on the edge, we know that it has already been processed. Otherwise, we find out whether it is in Svjr. If yes, there might exist both in and out event points (lines 8–9). If no, we only need to compute the out event points for v (lines 10–11). Then, for the vertices in Svjr, we only need to process ones that are neither on ei,j nor in Svir. For these vertices, we need to compute the in event point for them (lines 12–15).


## 5.2.1. Issuing Range Query

Intuitively, the answer sets for these backbone vertices are overlapped. This motivates us to compute the answer sets progressively. The following theorem offers us the insight for progressive computation.Theorem 4.
Given two query pointq,q′ on the query path, and a distance threshold T. We denote by Sq′r the range query results of q′. For any v∈Sq′r, it holds that v,q≤T+q,q′.Proof.
This theorem is obvious. We omit the proof here.
Considering the fact that the distance between backbone vertices is not large, we propose to achieve the progressive computation by a filter-and-verification model. At a high level, we expand the network from the first vertexvf in PB progressively (for filter). We know that, for each backbone vertex v, the candidates must within the range of T+v,vf. That is, we only need to verify the vertices within this range for other backbone vertices (for verification).
As presented in Algorithm2, we retrieve the answer sets for backbone vertices in PB by a filter-and-verification framework. Particularly, we utilize curtDist≤stopDist as the filter condition for the current visited vertex v (line 7). From Theorem 4, we know that the range query results for v are within the range of stopDist to vf. In the process of tree traversal, if ℛi is a non-leaf node, we need to add its child nodes that cover the query keywords into the priority queue PQ for further exploration (lines 9–13). Otherwise, that is ℛi is a leaf node. We first compute the distance between vf and the backbone vertices in ℛi (lines 15–16). Then, for each backbone vertex v′, we find the results by checking the vertices lying on the adjacent edges (lines 17–19). Note that, we also maintain the candidates, which cover the query keywords, by C for achieving quick verification. When the filter condition is broken, we proceed to build Svr by verifying candidates in C (lines 20–23).
Optimizing Strategies: To facilitate the query processing, we investigate the optimizing strategies. We observe that there are much repeated computation when computing theminDist⋅ and performing verifications, thus we can maintain the computed distances for the following distance computation.Algorithm 2:Issuing Range Query.
Input :Qr=<P,T,ψ>Output:PB, S(1)
buildPB from P(2)
PQ.pushℛ0,0;(3)
curtDist← 0; stopDist←0(4)
vf←The first vertex in PB;(5)
for each PBdo(6)
stopDist←Qr.T+v,vf(7)
whilecurtDist≤stopDistdo(8)
ℛi,curtDist←PQ.pop;(9)
ifℛi is a non-leaf node then(10)
for each child node ℛc of ℛido(11)
ifQr.ψ⊆ℛc.ψHthen(12)
compute theminDistvf,Rc;(13)
PQ.pushRc,minDistvf,Rc;(14)
else(15)
ifvf is in ℛithen(16)
InternalDistvf,ℛi ;(17)
else ExternalDist vf,ℛi ;(18)
;(19)
for each v′∈ℛido(20)
put candidates on adjacent edges intoCℛi;(21)
put qualified candidates intoSvfr;(22)
for each ℛi in Cdo(23)
ifv is in ℛithen InternalDist v,ℛi ;(24)
;(25)
else ExternalDist v,ℛi ;(26)
;(27)
put all qualified candidates ofCℛi into Svr(28)
ReturnPB and S;


## 5.2.2. Identifying Event Point

We mainly focus on identifying event points on edges. Specifically, we distinguish event points by two types, namelyIE and OE. We denote by IE the in event point, and OE the out event point. We refer to in/out from the direction of the backbone vertex that is near to vf. As suggested in Theorem 2, the event points on ei,j are determined by Svir, Svjr and Qr.T. Specifically, there are seven cases, as follows:Algorithm 3:PCR−IdentifyingEventPoint.
Input :S,PBOutput: The sequence of event points.(1)
forl← 1 to mdo(2)
vi←PBl−1; vj←PBl;(3)
Ωei,j← the qualified vertices on ei,j;(4)
for each v∈Ωei,jdo(5)
Ξvi←event points computed by (1–4)(6)
for each v∈Svirdo(7)
ifv is not on ei,jthen(8)
ifv is not in Svjrthen(9)
Ξvi←event points computed by (5);(10)
else(11)
Ξvi←event points computed by (7);(12)
for each v∈Svjrdo(13)
ifv is not on ei,jthen(14)
ifv is not in Svirthen(15)
Ξvi←event points computed by (6)(16)
ReturnΞTheorem 5.
Given two backbone verticesvi,vj on R¯, and a vertex covering the keywords. Then, the event point in the edge has the following seven cases (we only describe the first three cases according to Figure 9, and referring our previous work [21] for more details.):(i)
Ifv on one edge between vi,vj, and vi,v>Qr.T∧v,vj>Qr.T, then there are two event point ;(ii)
Ifv on one edge between vi,vj, and vi,v>Qr.T∧v,vj>Qr.T, then there are two event point .(iii)
Ifv on one edge between vi,vj, and vi,v<Qr.T∧v,vj>Qr.T, then there are two event point.Figure 9
Illustration of range event point computation. (a) Event point 1. (b) Event point 2. (c) Event point 3. (d) Event point 4. (e) Event point 5. (f) Event point 6. (g) Event point 7.
(a)(b)(c)(d)(e)(f)(g)Algorithm3 presents the pseudo-code for identifying the event points. For each edge ei,j on PB, we denote by Svir and Svjr the answer sets for vi and vj. We first identify the event points for internal vertices on ei,j (lines 4–5). Then, for each vertex v∈Svir, if it is on the edge, we know that it has already been processed. Otherwise, we find out whether it is in Svjr. If yes, there might exist both in and out event points (lines 8–9). If no, we only need to compute the out event points for v (lines 10–11). Then, for the vertices in Svjr, we only need to process ones that are neither on ei,j nor in Svir. For these vertices, we need to compute the in event point for them (lines 12–15).


## 5.3. PCk NN Query Processing

Similarly, to answer the PCk NN queries, we first retrieve the k NN sets for backbone vertices in PB. Then, we identify the event points.


## 5.4. Issuingk NN Query

Algorithm 4:IssuingkNNQuery.
Input :Qr=<P,T,ψ>Output:PB, S(1)
buildPB from P;(2)
PQ.pushR0,0;(3)
curtDist← 0; stopDist←0;(4)
for each v in PBdo(5)
kthv←INFINITY ;(6)
stopDist←v,vf;(7)
while (curtDist<stopDist+kthvf) do(8)
Ri,curtDist←PQ.pop(9)
ifℛi is a non-leaf node then(10)
for each child node ℛc of ℛido(11)
ifQr.ψ⊆ℛc.ψHthen(12)
compute theminDistvf,Rc(13)
PQ.pushRc,minDistvf,Rc;(14)
else(15)
ifvf is in ℛithen(16)
InternalDistvf,ℛi(17)
else ExternalDist vf,ℛi(18)
;(19)
for each v′∈ℛido(20)
put candidates on adjacent edges intoCℛi;(21)
put qualified candidates intoSvfr;(22)
updatekthvf;(23)
for each ℛi in Cdo(24)
ifv is in ℛithen InternalDist v,ℛi(25)
;(26)
else ExternalDist v,ℛi(27)
;(28)
put all qualified candidates ofCℛi into Svr(29)
ReturnPB and STheorem 6.
Given two query pointq,q′ on the query path. We denote by Sq′k the k nearest neighbor query results of q′. For any v∈Sq′k, it holds that v,q≤Kq+q,q′. Here, Kq refers to the distance between q and the k th nearest neighbor.Proof.
This theorem is obvious. We omit the proof here.
Theorem6 enables to find the k nearest neighbor by only issuing the k nearest neighbor search once. Algorithm 4 shows the pseudo-code for finding k NN sets for backbone vertices. Generally, it is similar to Algorithm 1. The major difference comes from the filter condition (line 7). We denoted by kthvf the distance between vf and the k th nearest neighbor. Besides, we need to update kthvf accordingly when new result is inserted into Svfr (lines 17–20).


### 5.4.1. Identifying Event Point

Compared with the range query, thek NN query is more complicated. Whether a vertex v is the k NN result for the query is not only determined by its distance to query point but also by other vertices. This leads to the difficulty in identifying the event points for k NN queries. To address this problem, we introduce the concept of distance curve, which captures the change of distance between query point and the candidate when query point moves along the edge.Figure10(a) illustrates the distance curve for different cases. Given the candidate vertex v, for c1,c2, we know that the shortest path from v to vj or vi must go through vi or vj. For c3,c4, it is clear that v is on ei,j. Different from c3,c4, we know that c5,c6 present cases as there are more changes. Based on the distance curve, we identify the event points as illustrated in Figure 10(b). We know that the event points always appear at the intersections and turn points. To find out the event points, we can first compute all the intersections and turn points, and then compute the k NN at each turn points. This naive method is time consuming, thus we propose the enhanced method. We maintain the k NN curves that has the lowest distance. Then, we compute the intersections between these curves and other curves. We select the first intersection, and compute the k NN. This procedure continues until this edge is explored.Figure 10
Illustration of distance function. (a) Distance curve. (b) Event point.
(a)(b)Algorithm 5:PCkNNIdentifyingEventPoint.
Input :S,PBOutput: The sequence of event point.(1)
forl← 1 to mdo(2)
vi←PBl−1; vj←PBl(3)
compute the distance curve for vertices inSvik,Svjk;(4)
k NN ←pres; curtPos←0;(5)
whilecurtPos is on this edge do(6)
curtPos← minimum intersection position between k NN and other curves(7)
k NN ← recompute the k NN at curtPos(8)
ifk NN changes then(9)
add event point intoΞvi(10)
ReturnΞWe present the details of how to compute the event points fork NN in Algorithm 5. We first compute the distance curves for vertices in Svik and Svjk (line 3). Then, we compute the event points by accessing the next explored intersection. At this point, we update the k NN by comparing the distance value of start and end points. If k NN is changed, we add the event point into Ξvi (lines 8–9).


## 5.4.1. Identifying Event Point

Compared with the range query, thek NN query is more complicated. Whether a vertex v is the k NN result for the query is not only determined by its distance to query point but also by other vertices. This leads to the difficulty in identifying the event points for k NN queries. To address this problem, we introduce the concept of distance curve, which captures the change of distance between query point and the candidate when query point moves along the edge.Figure10(a) illustrates the distance curve for different cases. Given the candidate vertex v, for c1,c2, we know that the shortest path from v to vj or vi must go through vi or vj. For c3,c4, it is clear that v is on ei,j. Different from c3,c4, we know that c5,c6 present cases as there are more changes. Based on the distance curve, we identify the event points as illustrated in Figure 10(b). We know that the event points always appear at the intersections and turn points. To find out the event points, we can first compute all the intersections and turn points, and then compute the k NN at each turn points. This naive method is time consuming, thus we propose the enhanced method. We maintain the k NN curves that has the lowest distance. Then, we compute the intersections between these curves and other curves. We select the first intersection, and compute the k NN. This procedure continues until this edge is explored.Figure 10
Illustration of distance function. (a) Distance curve. (b) Event point.
(a)(b)Algorithm 5:PCkNNIdentifyingEventPoint.
Input :S,PBOutput: The sequence of event point.(1)
forl← 1 to mdo(2)
vi←PBl−1; vj←PBl(3)
compute the distance curve for vertices inSvik,Svjk;(4)
k NN ←pres; curtPos←0;(5)
whilecurtPos is on this edge do(6)
curtPos← minimum intersection position between k NN and other curves(7)
k NN ← recompute the k NN at curtPos(8)
ifk NN changes then(9)
add event point intoΞvi(10)
ReturnΞWe present the details of how to compute the event points fork NN in Algorithm 5. We first compute the distance curves for vertices in Svik and Svjk (line 3). Then, we compute the event points by accessing the next explored intersection. At this point, we update the k NN by comparing the distance value of start and end points. If k NN is changed, we add the event point into Ξvi (lines 8–9).


## 6. Analysis

We proceed to offer some insights of our index structure and algorithms.


### 6.1. Analysis on Index Structure

As discussed in Section3, the key point of compact strategy is to remove some vertices from the original network, and then takes them as internal vertices on introduced virtual edges. Suppose the compression ratio is Υ (As shown by experimental studies, this value varies from 5% to 75%). That is, VB=VΥ. Since an edge will be removed from the original network when a vertex is removed. We know that, it holds that EB=EΥ.The whole space cost of BNI is comprised of three parts, namely hash table, G-tree and generalized adjacent list. By hash table, we need to maintain the corresponding leaf node and address for each backbone vertex inVB. Thus, hash table costs OVB. Motivated by the analysis about G-tree in [18], we know that the space cost of G-tree is OVB/τ+log2f/τ⋅VB+log2f⋅τVB+log22f⋅logfVB/τ⋅VB. Please refer to [18] for more details. Furthermore, we also maintain the detailed information about road network in the generalized adjacent list, which costs OVB+EB. We denote by f and τ the number of partition regions for each partition and the upper bound of the number of vertices in leaf nodes. Thus, the total cost is Olog2f⋅τVB+log22f⋅logfVB/τ⋅VB+EB.


### 6.2. Analysis on Algorithms

#### 6.2.1. Analysis on Range Queries

(1) Time Complexity. Clearly, the time complexity of path based continuous range queries comes from two components, namely issuing range queries and identifying event points. Suppose the length of query path is ℒ. That is, ℒ=P. As noted earlier, there are ℒB=Υℒ backbone vertices in PB. We need to issue the range query once and perform ℒB−1 times verification for other backbone vertices. Without loss of generality, we assume the range query needs to access Nr leaf nodes (regions) before retrieving all results. In the worst case, that is, all backbone vertices in PB belong to different regions. Thus, each backbone vertex should explore at most Nr regions. Then, ExternalDist⋅ should be invoked at most ℒBNr. Since the matrix size of each node at level i is Olog22f⋅VB/fi. The height of the G-tree is ℋ=logfVB/τ+1. Thus, the cost for ExternalDist⋅ is Olog22f⋅VB/f+Olog22f⋅VB/f2+…+Olog22f⋅VB/fℋ=Olog22f⋅VB/f. Suppose the average number of vertices maintained for each backbone vertex is Nvr. The second part of cost is OℒB⋅Nvr. The overall cost is OℒBNr⋅log22f⋅VB/f+ℒB⋅Nvr. In practice, the complexity is much smaller than the worst-case complexity.(2) Space Complexity. As discussed earlier, we need to maintain the range queries answer sets for the backbone vertices in PB. The space complexity is OℒB⋅Nvr. Compared with distance matrices of G-tree, this space cost is negligible.


#### 6.2.2. Analysis onk NN Queries

(1) Time Complexity. As presented by Algorithms 1 and 3, we know that the only difference between them is the filter condition. That is, we need to issue the k NN query once and perform ℒB−1 times verification for other backbone vertices. Without loss of generality, we assume the k NN query needs to access Nk leaf nodes (regions) before retrieving all results. Similarly, in the worst case, each backbone vertex should explore at most Nk regions. Then, ExternalDist⋅ should be invoked at most ℒBNk. Thus, the total cost for ExternalDist⋅ is OℒBNk⋅log22f⋅VB/f. Besides, the cost for computing the event points is OℒB⋅k2 in worst case. Thus, the total cost is OℒBNk⋅log22f⋅VB/f+ℒB⋅k2.(2) Space Complexity. We need to maintain the range queries answer sets and the distance curves for the backbone vertices in PB. Thus, the space complexity is OℒB⋅k.


## 6.1. Analysis on Index Structure

As discussed in Section3, the key point of compact strategy is to remove some vertices from the original network, and then takes them as internal vertices on introduced virtual edges. Suppose the compression ratio is Υ (As shown by experimental studies, this value varies from 5% to 75%). That is, VB=VΥ. Since an edge will be removed from the original network when a vertex is removed. We know that, it holds that EB=EΥ.The whole space cost of BNI is comprised of three parts, namely hash table, G-tree and generalized adjacent list. By hash table, we need to maintain the corresponding leaf node and address for each backbone vertex inVB. Thus, hash table costs OVB. Motivated by the analysis about G-tree in [18], we know that the space cost of G-tree is OVB/τ+log2f/τ⋅VB+log2f⋅τVB+log22f⋅logfVB/τ⋅VB. Please refer to [18] for more details. Furthermore, we also maintain the detailed information about road network in the generalized adjacent list, which costs OVB+EB. We denote by f and τ the number of partition regions for each partition and the upper bound of the number of vertices in leaf nodes. Thus, the total cost is Olog2f⋅τVB+log22f⋅logfVB/τ⋅VB+EB.


## 6.2. Analysis on Algorithms

### 6.2.1. Analysis on Range Queries

(1) Time Complexity. Clearly, the time complexity of path based continuous range queries comes from two components, namely issuing range queries and identifying event points. Suppose the length of query path is ℒ. That is, ℒ=P. As noted earlier, there are ℒB=Υℒ backbone vertices in PB. We need to issue the range query once and perform ℒB−1 times verification for other backbone vertices. Without loss of generality, we assume the range query needs to access Nr leaf nodes (regions) before retrieving all results. In the worst case, that is, all backbone vertices in PB belong to different regions. Thus, each backbone vertex should explore at most Nr regions. Then, ExternalDist⋅ should be invoked at most ℒBNr. Since the matrix size of each node at level i is Olog22f⋅VB/fi. The height of the G-tree is ℋ=logfVB/τ+1. Thus, the cost for ExternalDist⋅ is Olog22f⋅VB/f+Olog22f⋅VB/f2+…+Olog22f⋅VB/fℋ=Olog22f⋅VB/f. Suppose the average number of vertices maintained for each backbone vertex is Nvr. The second part of cost is OℒB⋅Nvr. The overall cost is OℒBNr⋅log22f⋅VB/f+ℒB⋅Nvr. In practice, the complexity is much smaller than the worst-case complexity.(2) Space Complexity. As discussed earlier, we need to maintain the range queries answer sets for the backbone vertices in PB. The space complexity is OℒB⋅Nvr. Compared with distance matrices of G-tree, this space cost is negligible.


### 6.2.2. Analysis onk NN Queries

(1) Time Complexity. As presented by Algorithms 1 and 3, we know that the only difference between them is the filter condition. That is, we need to issue the k NN query once and perform ℒB−1 times verification for other backbone vertices. Without loss of generality, we assume the k NN query needs to access Nk leaf nodes (regions) before retrieving all results. Similarly, in the worst case, each backbone vertex should explore at most Nk regions. Then, ExternalDist⋅ should be invoked at most ℒBNk. Thus, the total cost for ExternalDist⋅ is OℒBNk⋅log22f⋅VB/f. Besides, the cost for computing the event points is OℒB⋅k2 in worst case. Thus, the total cost is OℒBNk⋅log22f⋅VB/f+ℒB⋅k2.(2) Space Complexity. We need to maintain the range queries answer sets and the distance curves for the backbone vertices in PB. Thus, the space complexity is OℒB⋅k.


## 6.2.1. Analysis on Range Queries

(1) Time Complexity. Clearly, the time complexity of path based continuous range queries comes from two components, namely issuing range queries and identifying event points. Suppose the length of query path is ℒ. That is, ℒ=P. As noted earlier, there are ℒB=Υℒ backbone vertices in PB. We need to issue the range query once and perform ℒB−1 times verification for other backbone vertices. Without loss of generality, we assume the range query needs to access Nr leaf nodes (regions) before retrieving all results. In the worst case, that is, all backbone vertices in PB belong to different regions. Thus, each backbone vertex should explore at most Nr regions. Then, ExternalDist⋅ should be invoked at most ℒBNr. Since the matrix size of each node at level i is Olog22f⋅VB/fi. The height of the G-tree is ℋ=logfVB/τ+1. Thus, the cost for ExternalDist⋅ is Olog22f⋅VB/f+Olog22f⋅VB/f2+…+Olog22f⋅VB/fℋ=Olog22f⋅VB/f. Suppose the average number of vertices maintained for each backbone vertex is Nvr. The second part of cost is OℒB⋅Nvr. The overall cost is OℒBNr⋅log22f⋅VB/f+ℒB⋅Nvr. In practice, the complexity is much smaller than the worst-case complexity.(2) Space Complexity. As discussed earlier, we need to maintain the range queries answer sets for the backbone vertices in PB. The space complexity is OℒB⋅Nvr. Compared with distance matrices of G-tree, this space cost is negligible.


## 6.2.2. Analysis onk NN Queries

(1) Time Complexity. As presented by Algorithms 1 and 3, we know that the only difference between them is the filter condition. That is, we need to issue the k NN query once and perform ℒB−1 times verification for other backbone vertices. Without loss of generality, we assume the k NN query needs to access Nk leaf nodes (regions) before retrieving all results. Similarly, in the worst case, each backbone vertex should explore at most Nk regions. Then, ExternalDist⋅ should be invoked at most ℒBNk. Thus, the total cost for ExternalDist⋅ is OℒBNk⋅log22f⋅VB/f. Besides, the cost for computing the event points is OℒB⋅k2 in worst case. Thus, the total cost is OℒBNk⋅log22f⋅VB/f+ℒB⋅k2.(2) Space Complexity. We need to maintain the range queries answer sets and the distance curves for the backbone vertices in PB. Thus, the space complexity is OℒB⋅k.


## 7. Experiments

We evaluate the performance of our proposed algorithms on both synthetic and real life data sets. We introduce the experimental settings in Section7.1, and present the overall performance of the algorithms in Section 7.2. Section 7.3 studies the impact of different parameters on the performance of the algorithms.


### 7.1. Experimental Setup

#### 7.1.1. Comparison Algorithms

Previous studies on the continuous spatial keyword queries usually exploit the modified version of Grid index [2, 8, 22] to organize the spatial objects. It is mainly because the index structure is easy to construct and can be applied to dynamic environment. As a result, we modify the algorithms in [22] for comparison, which is developed on the top of Grid index. To be fair, we partition the generated backbone network into 2n∗2n grid cells, such that the number of grid cells is as close to the leaf nodes of G-tree as possible. Similarly, we maintain borders (connecting vertices), distance matrix (distance table) and keyword bitmap for each cell. The range query algorithm first finds all relevant cells that satisfy the given distance threshold constraint. Then, the vertices in these cells are checked by query conditions to find out the final answer set. The k NN query algorithm explores the closest unvisited cell progressively using the modified version of Dijkstra algorithm until k qualified vertices are retrieved. During the query processing, distance matrix are exploited to facilitate the distance computation. For ease of discussion, we term our algorithms and competitors as BNI-Range, BNI-k NN, Grid-Range and Grid-k NN respectively.


#### 7.1.2. Data and Queries

We test the algorithms on five real road networks, namely SF, NA, LA, NY, CA. We obtain SF and NA from [37], and LA, NY and CA are retrieved from TIGER/Line. Since the original road networks in LA, NY and CA are unconnected, we take the corresponding maximal connected subgraph as the road network. In Table 3, we reveal some statistics properties for real road networks. In particular, we denote by VB/V the compression ratio for the road network. Clearly, the road network can be reduced by 25%–95%. We generate the associated keywords for each vertex as shown in [36] based on the experimental setting. We mainly evaluate the performance on five parameters: (1) the average number of keywords associated with each vertex (AK); (2) the length of query path, i.e., the number of vertices on the path (PL); (3) the number of query keywords (QK); (4) the ratio of query scope, that is, the distance threshold for range query (RT); (5) the retrieved size for k NN query (K). To study the effect of these parameters, we conduct experiments on data set NA. Table 4 offers detailed information about the parameters. We mark their default values in bold. For each experiment, we randomly generate 20 queries based on the experimental setting in Table 4. We report the averaged performance.Table 3
The property of real life datasets.
Property#Vertex#EdgeVB/VSF174,95621,6930.0648518NA175,813179,1790.0519074LA408,161494,9530.74266NY708,520891,9900.718204CA1,595,5771,975,0260.754325Table 4
The query parameters.
ParametersInstance valueQueryAK3,4,5,6,7,8BothPL30,40,60,70,80BothQK2,3,4,5,6,7BothRT1,2,4,8,16,32RangeK50,100,150,200,250,300k NNAll algorithms are implemented in C/C++ and run in Windows 7 System on an Intel(R) Core(TM) i5-4590 CPU@3.30 GHz with 8 GB RAM. The index KHT and LIR-tree are disk-resident and the buffer size is set to 4 MB.


### 7.2. Overall Performance of Algorithms

We proceed to offer the global insights about the index structures and algorithms. We illustrate the construct time for grid index structure and backbone network index (BNI) structure over real road networks in Figure11. We observe that the construction time for two index structures does not vary much for moderate road networks, such as NA, LA and NY. As for the large network, i.e., CA, much more time is spent for building BNI than that for building grid index. The reason behind that is BNI exploits much more complicated partition strategy compared with the grid index.Figure 11
Index construction time (second).As shown in Figure12, we evaluate the overall performance of algorithms on several real road networks, namely SF, NA, LA, NY and CA. Experimental results in Figure 12 reveal that our algorithms (both the range query algorithm and k NN query algorithm) outperform competitors by several orders of magnitude in terms of number of page access and running time. The strength of our algorithms are obvious, especially on very large road network, such as CA.Figure 12
Overall performance on different data sets.
(a)(b)(c)(d)


### 7.3. Effect of Parameters

#### 7.3.1. Effect of Parameter AK

We first study the effect ofAK. In particular, we generate six synthetic data sets based on NA by varying AK from 3 to 8. Figure 13 shows experimental results as AK increases. As expected, the running time for range query algorithms increases when AK increases (see Figure 13(a)). This is because more qualified vertices are to be verified. However, AK has little effect on the number of page access(see Figure 13(b)), since it mainly affected by the search range. We notice some new findings from k NN query algorithms, as shown in Figures 13(c) and 13(d). Both the running time and the number of page access achieve the worst performance when AK = 5. Recall that, we set the number of query keywords as 5 by default. That is, the false positive rate achieves the highest value in that case. Thus, much more cost is spent for checking whether or not the current visited vertex satisfies the query condition for competitors. On the other hand, BNI-k NN performs well, which thanks to the global insights provides by our hierarchical index structure.Figure 13
Effect of parameter AK.
(a)(b)(c)(d)


#### 7.3.2. Effect of Parameter PL

In this experiment, we evaluate the effect of the length of the query path, i.e., the number of vertices onPB. Figures 14(a) and 14(b) show the results for range query algorithms. When the length of query path increases, the number of corresponding backbone vertices on PB increases accordingly. To answer the queries, much more iterations are required for building the answer sets for these backbone vertices. This leads to the increase of running time and the number of page access for Grid-Range. With the maintained answer sets, BNI-Range can retrieve answer sets for backbone vertices incrementally, rather than retrieving from scratch as Grid-Range. This explains the difference in performance. Figures 14(c) and 14(d) show the same findings, and thus can be explained with the same reason.Figure 14
Effect of parameter PL.
(a)(b)(c)(d)


#### 7.3.3. Effect of Parameter QK

In Figure15, we present the experimental results achieved by varying QK. Figures 15(a) and 15(b) reveal that the running time decreases for both Grid-Range and BNI-Range When QK increases, we know that the number of qualified vertices decreases within the query range, which incurs less verification overhead. Figure 15(b) shows that QK has little effect on the number of page access for both algorithms. In contrast, we notice the running time and the number of page access increases greatly for Grid-k NN. This is not as strange as it seems. Note that, Grid-k NN requests for k qualified vertices. When QK becomes large, it is much more difficult for Grid-k NN to obtain the answer set. That is, Grid-k NN has to explore a larger proportion of network before finding the k NN results. We omit the experimental results when QK is greater than 5, because the answer set cannot be found within one day. On the other hand, BNI-k NN is affected slightly by QK. This is because we utilize the hierarchical structure to guide the search process.Figure 15
Effect of parameter QK.
(a)(b)(c)(d)


#### 7.3.4. Effect of Parameter RT

To study the effect of distance threshold on range query algorithms, we tuneRT from 1% to 32%. To set RT, we first get the whole length of the road network, denoted by ℒW, and then RT can be set by some specific ratio. For instance, when RT is set to 8%, the corresponding real value is 0.08∗ℒW. Figures 16(a) and 16(b) show the running time and the number of page access for range query algorithms respectively. As expected, both the running time and the number of page access increase as RT increases. This is because the range query algorithms would explore a larger proportion of the networks. BNI-Range achieves much better performance than Grid-Range, which is largely due to the effective of our proposed index structure.Figure 16
Effect of parameter RT.
(a)(b)


#### 7.3.5. Effect of Parameter K

As shown in Figures17(a) and 17(b), we observe that K has much effect on k NN query algorithms. Clearly, when K increases, that is, much more vertices are required for satisfying the query. This renders the algorithms to explore much more vertices before meeting the query conditions. Figure 17(b) shows that the number of page access of Grid-k NN increases almost liner to K, whereas BNI-k NN is affected by K slightly, this demonstrates the effectiveness of our proposed index structure.Figure 17
Effect of parameterK.
(a)(b)


## 7.1. Experimental Setup

### 7.1.1. Comparison Algorithms

Previous studies on the continuous spatial keyword queries usually exploit the modified version of Grid index [2, 8, 22] to organize the spatial objects. It is mainly because the index structure is easy to construct and can be applied to dynamic environment. As a result, we modify the algorithms in [22] for comparison, which is developed on the top of Grid index. To be fair, we partition the generated backbone network into 2n∗2n grid cells, such that the number of grid cells is as close to the leaf nodes of G-tree as possible. Similarly, we maintain borders (connecting vertices), distance matrix (distance table) and keyword bitmap for each cell. The range query algorithm first finds all relevant cells that satisfy the given distance threshold constraint. Then, the vertices in these cells are checked by query conditions to find out the final answer set. The k NN query algorithm explores the closest unvisited cell progressively using the modified version of Dijkstra algorithm until k qualified vertices are retrieved. During the query processing, distance matrix are exploited to facilitate the distance computation. For ease of discussion, we term our algorithms and competitors as BNI-Range, BNI-k NN, Grid-Range and Grid-k NN respectively.


### 7.1.2. Data and Queries

We test the algorithms on five real road networks, namely SF, NA, LA, NY, CA. We obtain SF and NA from [37], and LA, NY and CA are retrieved from TIGER/Line. Since the original road networks in LA, NY and CA are unconnected, we take the corresponding maximal connected subgraph as the road network. In Table 3, we reveal some statistics properties for real road networks. In particular, we denote by VB/V the compression ratio for the road network. Clearly, the road network can be reduced by 25%–95%. We generate the associated keywords for each vertex as shown in [36] based on the experimental setting. We mainly evaluate the performance on five parameters: (1) the average number of keywords associated with each vertex (AK); (2) the length of query path, i.e., the number of vertices on the path (PL); (3) the number of query keywords (QK); (4) the ratio of query scope, that is, the distance threshold for range query (RT); (5) the retrieved size for k NN query (K). To study the effect of these parameters, we conduct experiments on data set NA. Table 4 offers detailed information about the parameters. We mark their default values in bold. For each experiment, we randomly generate 20 queries based on the experimental setting in Table 4. We report the averaged performance.Table 3
The property of real life datasets.
Property#Vertex#EdgeVB/VSF174,95621,6930.0648518NA175,813179,1790.0519074LA408,161494,9530.74266NY708,520891,9900.718204CA1,595,5771,975,0260.754325Table 4
The query parameters.
ParametersInstance valueQueryAK3,4,5,6,7,8BothPL30,40,60,70,80BothQK2,3,4,5,6,7BothRT1,2,4,8,16,32RangeK50,100,150,200,250,300k NNAll algorithms are implemented in C/C++ and run in Windows 7 System on an Intel(R) Core(TM) i5-4590 CPU@3.30 GHz with 8 GB RAM. The index KHT and LIR-tree are disk-resident and the buffer size is set to 4 MB.


## 7.1.1. Comparison Algorithms

Previous studies on the continuous spatial keyword queries usually exploit the modified version of Grid index [2, 8, 22] to organize the spatial objects. It is mainly because the index structure is easy to construct and can be applied to dynamic environment. As a result, we modify the algorithms in [22] for comparison, which is developed on the top of Grid index. To be fair, we partition the generated backbone network into 2n∗2n grid cells, such that the number of grid cells is as close to the leaf nodes of G-tree as possible. Similarly, we maintain borders (connecting vertices), distance matrix (distance table) and keyword bitmap for each cell. The range query algorithm first finds all relevant cells that satisfy the given distance threshold constraint. Then, the vertices in these cells are checked by query conditions to find out the final answer set. The k NN query algorithm explores the closest unvisited cell progressively using the modified version of Dijkstra algorithm until k qualified vertices are retrieved. During the query processing, distance matrix are exploited to facilitate the distance computation. For ease of discussion, we term our algorithms and competitors as BNI-Range, BNI-k NN, Grid-Range and Grid-k NN respectively.


## 7.1.2. Data and Queries

We test the algorithms on five real road networks, namely SF, NA, LA, NY, CA. We obtain SF and NA from [37], and LA, NY and CA are retrieved from TIGER/Line. Since the original road networks in LA, NY and CA are unconnected, we take the corresponding maximal connected subgraph as the road network. In Table 3, we reveal some statistics properties for real road networks. In particular, we denote by VB/V the compression ratio for the road network. Clearly, the road network can be reduced by 25%–95%. We generate the associated keywords for each vertex as shown in [36] based on the experimental setting. We mainly evaluate the performance on five parameters: (1) the average number of keywords associated with each vertex (AK); (2) the length of query path, i.e., the number of vertices on the path (PL); (3) the number of query keywords (QK); (4) the ratio of query scope, that is, the distance threshold for range query (RT); (5) the retrieved size for k NN query (K). To study the effect of these parameters, we conduct experiments on data set NA. Table 4 offers detailed information about the parameters. We mark their default values in bold. For each experiment, we randomly generate 20 queries based on the experimental setting in Table 4. We report the averaged performance.Table 3
The property of real life datasets.
Property#Vertex#EdgeVB/VSF174,95621,6930.0648518NA175,813179,1790.0519074LA408,161494,9530.74266NY708,520891,9900.718204CA1,595,5771,975,0260.754325Table 4
The query parameters.
ParametersInstance valueQueryAK3,4,5,6,7,8BothPL30,40,60,70,80BothQK2,3,4,5,6,7BothRT1,2,4,8,16,32RangeK50,100,150,200,250,300k NNAll algorithms are implemented in C/C++ and run in Windows 7 System on an Intel(R) Core(TM) i5-4590 CPU@3.30 GHz with 8 GB RAM. The index KHT and LIR-tree are disk-resident and the buffer size is set to 4 MB.


## 7.2. Overall Performance of Algorithms

We proceed to offer the global insights about the index structures and algorithms. We illustrate the construct time for grid index structure and backbone network index (BNI) structure over real road networks in Figure11. We observe that the construction time for two index structures does not vary much for moderate road networks, such as NA, LA and NY. As for the large network, i.e., CA, much more time is spent for building BNI than that for building grid index. The reason behind that is BNI exploits much more complicated partition strategy compared with the grid index.Figure 11
Index construction time (second).As shown in Figure12, we evaluate the overall performance of algorithms on several real road networks, namely SF, NA, LA, NY and CA. Experimental results in Figure 12 reveal that our algorithms (both the range query algorithm and k NN query algorithm) outperform competitors by several orders of magnitude in terms of number of page access and running time. The strength of our algorithms are obvious, especially on very large road network, such as CA.Figure 12
Overall performance on different data sets.
(a)(b)(c)(d)


## 7.3. Effect of Parameters

### 7.3.1. Effect of Parameter AK

We first study the effect ofAK. In particular, we generate six synthetic data sets based on NA by varying AK from 3 to 8. Figure 13 shows experimental results as AK increases. As expected, the running time for range query algorithms increases when AK increases (see Figure 13(a)). This is because more qualified vertices are to be verified. However, AK has little effect on the number of page access(see Figure 13(b)), since it mainly affected by the search range. We notice some new findings from k NN query algorithms, as shown in Figures 13(c) and 13(d). Both the running time and the number of page access achieve the worst performance when AK = 5. Recall that, we set the number of query keywords as 5 by default. That is, the false positive rate achieves the highest value in that case. Thus, much more cost is spent for checking whether or not the current visited vertex satisfies the query condition for competitors. On the other hand, BNI-k NN performs well, which thanks to the global insights provides by our hierarchical index structure.Figure 13
Effect of parameter AK.
(a)(b)(c)(d)


### 7.3.2. Effect of Parameter PL

In this experiment, we evaluate the effect of the length of the query path, i.e., the number of vertices onPB. Figures 14(a) and 14(b) show the results for range query algorithms. When the length of query path increases, the number of corresponding backbone vertices on PB increases accordingly. To answer the queries, much more iterations are required for building the answer sets for these backbone vertices. This leads to the increase of running time and the number of page access for Grid-Range. With the maintained answer sets, BNI-Range can retrieve answer sets for backbone vertices incrementally, rather than retrieving from scratch as Grid-Range. This explains the difference in performance. Figures 14(c) and 14(d) show the same findings, and thus can be explained with the same reason.Figure 14
Effect of parameter PL.
(a)(b)(c)(d)


### 7.3.3. Effect of Parameter QK

In Figure15, we present the experimental results achieved by varying QK. Figures 15(a) and 15(b) reveal that the running time decreases for both Grid-Range and BNI-Range When QK increases, we know that the number of qualified vertices decreases within the query range, which incurs less verification overhead. Figure 15(b) shows that QK has little effect on the number of page access for both algorithms. In contrast, we notice the running time and the number of page access increases greatly for Grid-k NN. This is not as strange as it seems. Note that, Grid-k NN requests for k qualified vertices. When QK becomes large, it is much more difficult for Grid-k NN to obtain the answer set. That is, Grid-k NN has to explore a larger proportion of network before finding the k NN results. We omit the experimental results when QK is greater than 5, because the answer set cannot be found within one day. On the other hand, BNI-k NN is affected slightly by QK. This is because we utilize the hierarchical structure to guide the search process.Figure 15
Effect of parameter QK.
(a)(b)(c)(d)


### 7.3.4. Effect of Parameter RT

To study the effect of distance threshold on range query algorithms, we tuneRT from 1% to 32%. To set RT, we first get the whole length of the road network, denoted by ℒW, and then RT can be set by some specific ratio. For instance, when RT is set to 8%, the corresponding real value is 0.08∗ℒW. Figures 16(a) and 16(b) show the running time and the number of page access for range query algorithms respectively. As expected, both the running time and the number of page access increase as RT increases. This is because the range query algorithms would explore a larger proportion of the networks. BNI-Range achieves much better performance than Grid-Range, which is largely due to the effective of our proposed index structure.Figure 16
Effect of parameter RT.
(a)(b)


### 7.3.5. Effect of Parameter K

As shown in Figures17(a) and 17(b), we observe that K has much effect on k NN query algorithms. Clearly, when K increases, that is, much more vertices are required for satisfying the query. This renders the algorithms to explore much more vertices before meeting the query conditions. Figure 17(b) shows that the number of page access of Grid-k NN increases almost liner to K, whereas BNI-k NN is affected by K slightly, this demonstrates the effectiveness of our proposed index structure.Figure 17
Effect of parameterK.
(a)(b)


## 7.3.1. Effect of Parameter AK

We first study the effect ofAK. In particular, we generate six synthetic data sets based on NA by varying AK from 3 to 8. Figure 13 shows experimental results as AK increases. As expected, the running time for range query algorithms increases when AK increases (see Figure 13(a)). This is because more qualified vertices are to be verified. However, AK has little effect on the number of page access(see Figure 13(b)), since it mainly affected by the search range. We notice some new findings from k NN query algorithms, as shown in Figures 13(c) and 13(d). Both the running time and the number of page access achieve the worst performance when AK = 5. Recall that, we set the number of query keywords as 5 by default. That is, the false positive rate achieves the highest value in that case. Thus, much more cost is spent for checking whether or not the current visited vertex satisfies the query condition for competitors. On the other hand, BNI-k NN performs well, which thanks to the global insights provides by our hierarchical index structure.Figure 13
Effect of parameter AK.
(a)(b)(c)(d)


## 7.3.2. Effect of Parameter PL

In this experiment, we evaluate the effect of the length of the query path, i.e., the number of vertices onPB. Figures 14(a) and 14(b) show the results for range query algorithms. When the length of query path increases, the number of corresponding backbone vertices on PB increases accordingly. To answer the queries, much more iterations are required for building the answer sets for these backbone vertices. This leads to the increase of running time and the number of page access for Grid-Range. With the maintained answer sets, BNI-Range can retrieve answer sets for backbone vertices incrementally, rather than retrieving from scratch as Grid-Range. This explains the difference in performance. Figures 14(c) and 14(d) show the same findings, and thus can be explained with the same reason.Figure 14
Effect of parameter PL.
(a)(b)(c)(d)


## 7.3.3. Effect of Parameter QK

In Figure15, we present the experimental results achieved by varying QK. Figures 15(a) and 15(b) reveal that the running time decreases for both Grid-Range and BNI-Range When QK increases, we know that the number of qualified vertices decreases within the query range, which incurs less verification overhead. Figure 15(b) shows that QK has little effect on the number of page access for both algorithms. In contrast, we notice the running time and the number of page access increases greatly for Grid-k NN. This is not as strange as it seems. Note that, Grid-k NN requests for k qualified vertices. When QK becomes large, it is much more difficult for Grid-k NN to obtain the answer set. That is, Grid-k NN has to explore a larger proportion of network before finding the k NN results. We omit the experimental results when QK is greater than 5, because the answer set cannot be found within one day. On the other hand, BNI-k NN is affected slightly by QK. This is because we utilize the hierarchical structure to guide the search process.Figure 15
Effect of parameter QK.
(a)(b)(c)(d)


## 7.3.4. Effect of Parameter RT

To study the effect of distance threshold on range query algorithms, we tuneRT from 1% to 32%. To set RT, we first get the whole length of the road network, denoted by ℒW, and then RT can be set by some specific ratio. For instance, when RT is set to 8%, the corresponding real value is 0.08∗ℒW. Figures 16(a) and 16(b) show the running time and the number of page access for range query algorithms respectively. As expected, both the running time and the number of page access increase as RT increases. This is because the range query algorithms would explore a larger proportion of the networks. BNI-Range achieves much better performance than Grid-Range, which is largely due to the effective of our proposed index structure.Figure 16
Effect of parameter RT.
(a)(b)


## 7.3.5. Effect of Parameter K

As shown in Figures17(a) and 17(b), we observe that K has much effect on k NN query algorithms. Clearly, when K increases, that is, much more vertices are required for satisfying the query. This renders the algorithms to explore much more vertices before meeting the query conditions. Figure 17(b) shows that the number of page access of Grid-k NN increases almost liner to K, whereas BNI-k NN is affected by K slightly, this demonstrates the effectiveness of our proposed index structure.Figure 17
Effect of parameterK.
(a)(b)


## 8. Conclusions and Future Work

In this paper, we introduce a novel query type, called path based continuous spatial keyword query. Different from previous studies, in this paper, we study the spatial keyword queries on a given query path. With this model, we propose to study the range queries andk NN queries. We propose a progressive framework to address these queries. Besides, to support our queries efficiently, we propose a backbone network index structure. This dual-index takes the advantage of G-tree and adjacent list. As verified by the experiments, our algorithms outperform the competitors by several orders of magnitude.There are several interesting directions to be studied in the future. First, we can study the path based continuous spatial keyword query in a dynamic environment with the moving or mobile objects. Then, it is also interesting to study the problem in the distributed environment.



---

*Source: 4091245-2022-06-10.xml*