# Efficient Processing of Moving Top-k Spatial Keyword Queries in Directed and Dynamic Road Networks

Authors: Muhammad Attique; Hyung-Ju Cho; Tae-Sun Chung
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

A top-k spatial keyword (TkSk) query ranks objects based on the distance to the query location and textual relevance to the query keywords. Several solutions have been proposed for top-k spatial keyword queries. However, most of the studies focus on Euclidean space or only investigate the snapshot queries where both the query and data object are static. A few algorithms study TkSk queries in undirected road networks where each edge is undirected and the distance between two points is the length of the shortest path connecting them. However, TkSk queries have not been thoroughly investigated in directed and dynamic spatial networks where each edge has a particular orientation and its weight changes according to the traffic conditions. Therefore, in this study, we address this problem by presenting a new method, called COSK, for processing continuous top-k spatial keyword queries for moving queries in directed and dynamic road networks. We first propose an efficient framework to process snapshot TkSK queries. Furthermore, we propose a safe-exit-based approach to monitor the validity of the results for moving TkSK queries. Our experimental results demonstrate that COSK significantly outperforms existing techniques in terms of query processing time and communication cost.


---

## Body

## 1. Introduction

With the popularization of geo-tagged data (e.g., geo-tagged photos, videos, check-ins, and text messages), many online location-based services such as Google Maps, Yahoo Maps, and Bing Maps have started providing useful information via location-based queries [1–4]. Moreover, textual descriptions of points of interest, e.g., hotels, shopping malls, and tourist attractions, are easily accessible on the Web. These developments demand techniques that efficiently process top-k spatial keyword queries that return a ranked list of thek best facilities based on their proximity to the query location and relevance to the query keywords. Several algorithms have been proposed for processing top-k spatial keyword queries in Euclidean space [5, 6]. Although few algorithms exist that study keyword queries in a road network, they all focus on undirected road networks. However, in real scenarios the urban road networks are directed and dynamic where each edge has a particular orientation and its weight changes according to traffic conditions such as traffic congestion and reversible lanes. Therefore, in this study, we investigate moving top-k spatial keyword queries in directed and dynamic road networks.Top-k keyword queries can be used for a wide range of applications in recommendation and decision support systems. For example, tourists may want to retrieve a sorted list of restaurants that serve Italian steak based on the shortest distance from their location and textual relevance to the query keywords. Tourists can issue a top-k spatial keyword query to the location-based services (LBS) to collect information about qualifying restaurants in their vicinity. However, through moving top-k spatial keyword queries if they does not like the results, they can simply keep moving, and the updated results will be provided until a desired restaurant is found. Typically, the query issuer follows the underlying road network to reach at the desired location. Therefore, TkSK algorithms based on Euclidean space does not work in road networks. A road network is generally modeled as a weighted directed graph, where each edge has some direction and its weight can vary according to the traffic conditions.Given a set of data objectsD={d1,d2,…,d|D|}, query location, and set of keywords, the TkSK query returns the bestk data objects fromD according to their combined textual and spatial relevance to the query. We use distance function dist(q,d) to represent the shortest network distance fromq to data objectd. Figure 1 presents an example of a directed road network, where rectangles represent the data objects with a textual description, and the triangle represents the query location. The number label on each edge indicates the weight of that edge such as the amount of time required to travel along it, e.g., dist(d1,n1)=1 and dist(d1,n2)=2. Consider a scenario where a tourist is interested in finding an “Italian Restaurant." If an undirected road network is considered, the top-1 “Italian Restaurant" is d6. However, in a directed road network, the shortest path fromq to d6 is (q→n3→n7→d6). Therefore, for a directed road network, the top-1 result is d3 because it is closer to the query location than d6. Now, consider that the tourist is looking for “Cafe Bakery". The data object d7 could score higher than data object d1 because d7 (“Cafe and bakery") is more textually relevant to query keywords than d2 (“Cafe"), and dist(q,d7) is only marginally greater than dist(q,d2).Figure 1
Illustration of directed road network.Moving Top-k spatial keywords in directed and dynamic road networks are useful for many location-based applications. However, query processing is costly because movement of query objectq may invalidate the query results. Therefore, the main challenge in moving TkSk is to maintain the freshness of the query results when the query objects are moving freely. A straightforward approach is to increase the update frequency of the query. However, this approach not only compromises the up-to-date query results but also increases the computation and communication overhead. Because whenever query object changes its location the query object has to report its location to server which increases the communication cost and server has to recompute the results again which increases the computation cost.To address the aforementioned challenges, we first present an efficient processing technique of snapshot TkSK queries in directed road networks. Then, we present a safe-exit-based approach for processing and monitoring moving TkSk queries where query objectq is freely moving in a directed spatial network. The safe exit point of query objectq represents a boundary point between the safe region and nonsafe region ofq. A safe region of query points indicates that the query result remains valid if the query object lies within its respective safe region. Therefore, the query results will only be recomputed whenq leaves its respective safe region which significantly reduces the computation and communication costs. To the best of our knowledge, this is the first attempt to study moving top-k spatial keyword queries in directed and dynamic road networks.Below, we summarize our contributions:(i)
We study the problem of continuous monitoring of moving top-k spatial keyword queries in a directed and dynamic road networks.(ii)
We present an algorithm to monitor the moving TkSK queries which efficiently computes the safe exit points for query objectq in a directed road network. The algorithm significantly minimizes the computation and communication costs for moving queries.(iii)
We also propose a method that monitors the validity of query results and safe region when weight of road segments is updated due to traffic conditions.(iv)
Finally, we conduct extensive experiments on real road network datasets and demonstrate the superiority of the proposed algorithm over the existing approach.The remainder of this paper is structured as follows. Section2 reviews the existing work on the processing of TkSk queries on Euclidean and road networks. Section 3 provides terminology definitions and describes the problem. Section 4 elaborates on the proposed query processing technique for TkSK queries in directed road networks. In Section 5, we present our safe-exit-based technique to process moving TkSK queries. Section 7 presents a performance analysis of the proposed technique. Section 8 concludes this paper.


## 2. Related Work

In this section, we discuss some of the promising related studies of top-k spatial keyword queries. Our related work is divided into two sections: Section 2.1 reviews snapshot TkSK queries, and Section 2.2 presents the studies proposed to address moving TkSK queries.


### 2.1. Snapshot Top-k Spatial Keyword Queries

In recent years, spatial keyword queries have drawn the attention of many researchers. Several approaches have been proposed for ranking spatial data objects. Initially, Zhouet al. [7] worked on combining inverted indexes [8] and R-trees [9]. They proposed three different hybrid indexing structures. Their study demonstrated that building an inverted index on top of an R-tree provides superior performance. Hariharanet al. [10] proposed the indexing structure KR∗-tree by capturing the joint distribution of keywords in space. Ian de Felipeet al. [11] proposed a data structure that combines an R-tree with text signatures. Each node of the R-tree exploits a signature to indicate the presence of keywords in the subtree of the node. However, both these approaches address only Boolean keyword queries in Euclidean space.Top-k spatial keyword queries where data objects are ranked according to their combined textual and spatial relevance to keyword queries were first studied by Conget al. [5] and Liet al. [6]. Both studies [6] integrate location indexing and text indexing to generate IR-trees. These studies process top-k spatial keyword queries only in Euclidean space and are not suitable for processing top-k spatial preference queries in road networks, where the distance between objects is determined by the shortest path connecting them. Later, Rocha et al. [12] proposed the indexing technique S2I, which maps each term in the vocabulary into a separate block or aR tree for efficient processing of top-k spatial keyword queries. Zhanget al. [13] proposed an m-closest keyword query that returns the closest object based on distance and which matchesm query keywords.Top-k spatial keyword queries in road networks were introduced by Rochaet al. [14]. In particular, they proposed three different indexing techniques (Basic Indexing, Enhanced Indexing, and Overlay Indexing) for processing spatial keyword queries in road networks.


### 2.2. Moving Top-k Spatial Keyword Queries

Recently, research focus has shifted to the continuous processing of spatial queries where query or data objects are arbitrarily moving in road networks, which is the most realistic scenario. Considerable research effort has been undertaken to process moving range,k nearest neighbor (kNN), and reversek nearest neighbor queries (RkNN) [15–18]. However, there is a lack of efficient algorithms for moving top-k spatial keyword queries. Initially, Wuet al. [19] and Huang et al. [20] proposed different methods for monitoring top-k spatial keyword queries in Euclidean space. Guoet al. [21] studied moving top-k spatial keyword queries on road networks. They presented two methods for monitoring moving queries in an continuous manner that reduces the traversing of network edges. Later, Liet al. [22] proposed TPR-tree-based indexing to monitor moving top-k spatial keyword queries. In contrast to [21, 22], in this study we consider moving top-k spatial keyword queries in directed and dynamic road networks where each road segment has a particular orientation and its weight changes due to according to traffic conditions.Table1 compares our problem scenario with related work in terms of query type, space domain, and orientation of road networks.Table 1
Comparisons with existing solutions.
Algorithm Type Space Domain Orientation Conget al. [5] Snapshot Euclidean No orientation Rochaet al. [14] Snapshot Static Road Undirected Wuet al. [19] moving Euclidean No orientation Huanget al. [20] moving Euclidean No orientation Guoet al. [21] moving Static Road Undirected Liet al. [22] moving Static Road Undirected COSK moving Dynamic Road Directed


## 2.1. Snapshot Top-k Spatial Keyword Queries

In recent years, spatial keyword queries have drawn the attention of many researchers. Several approaches have been proposed for ranking spatial data objects. Initially, Zhouet al. [7] worked on combining inverted indexes [8] and R-trees [9]. They proposed three different hybrid indexing structures. Their study demonstrated that building an inverted index on top of an R-tree provides superior performance. Hariharanet al. [10] proposed the indexing structure KR∗-tree by capturing the joint distribution of keywords in space. Ian de Felipeet al. [11] proposed a data structure that combines an R-tree with text signatures. Each node of the R-tree exploits a signature to indicate the presence of keywords in the subtree of the node. However, both these approaches address only Boolean keyword queries in Euclidean space.Top-k spatial keyword queries where data objects are ranked according to their combined textual and spatial relevance to keyword queries were first studied by Conget al. [5] and Liet al. [6]. Both studies [6] integrate location indexing and text indexing to generate IR-trees. These studies process top-k spatial keyword queries only in Euclidean space and are not suitable for processing top-k spatial preference queries in road networks, where the distance between objects is determined by the shortest path connecting them. Later, Rocha et al. [12] proposed the indexing technique S2I, which maps each term in the vocabulary into a separate block or aR tree for efficient processing of top-k spatial keyword queries. Zhanget al. [13] proposed an m-closest keyword query that returns the closest object based on distance and which matchesm query keywords.Top-k spatial keyword queries in road networks were introduced by Rochaet al. [14]. In particular, they proposed three different indexing techniques (Basic Indexing, Enhanced Indexing, and Overlay Indexing) for processing spatial keyword queries in road networks.


## 2.2. Moving Top-k Spatial Keyword Queries

Recently, research focus has shifted to the continuous processing of spatial queries where query or data objects are arbitrarily moving in road networks, which is the most realistic scenario. Considerable research effort has been undertaken to process moving range,k nearest neighbor (kNN), and reversek nearest neighbor queries (RkNN) [15–18]. However, there is a lack of efficient algorithms for moving top-k spatial keyword queries. Initially, Wuet al. [19] and Huang et al. [20] proposed different methods for monitoring top-k spatial keyword queries in Euclidean space. Guoet al. [21] studied moving top-k spatial keyword queries on road networks. They presented two methods for monitoring moving queries in an continuous manner that reduces the traversing of network edges. Later, Liet al. [22] proposed TPR-tree-based indexing to monitor moving top-k spatial keyword queries. In contrast to [21, 22], in this study we consider moving top-k spatial keyword queries in directed and dynamic road networks where each road segment has a particular orientation and its weight changes due to according to traffic conditions.Table1 compares our problem scenario with related work in terms of query type, space domain, and orientation of road networks.Table 1
Comparisons with existing solutions.
Algorithm Type Space Domain Orientation Conget al. [5] Snapshot Euclidean No orientation Rochaet al. [14] Snapshot Static Road Undirected Wuet al. [19] moving Euclidean No orientation Huanget al. [20] moving Euclidean No orientation Guoet al. [21] moving Static Road Undirected Liet al. [22] moving Static Road Undirected COSK moving Dynamic Road Directed


## 3. Preliminaries

Section3.1 defines the terms and notations used in this paper. Section 3.2 formulates the problem using an example that illustrates the general results of top-k spatial keyword queries.


### 3.1. Definition of Terms and Notations

#### 3.1.1. Road Network

A road network is represented by a weighted directed graphG=(N,E,W) where N, E, and W denote the node set, edge set, and edge distance matrix, respectively. The network distance of an edge changes depending on the traffic conditions. Each edge is also assigned an orientation that is either undirected or directed. The undirected edge is represented by e=(ns,ne)¯ where ns and ne are the boundary nodes nβ of an edge, whereas the directed edge is represented by e=(ns,ne)→ or e=(ne,ns)←. Naturally, the arrow above the edge indicates the associated direction. We refer to ns as the starting node and ne as the ending node of an edge. For example, in Figure 1, n6 is the starting node of edge (n6,n2)→, whereas it is the ending node for edge (n6,n5)←. The particular edge where a query object is located is called an active edge. It is important to note that, the distance between two points, p1 and p2, is not symmetrical in directed road networks (i.e., dist(p1,p2)≠dist(p2,p1)). For example in Figure 1, the dist(d3,d4)=3, whereas the dist(d4,d3)=11 because shortest path from d4 to d3 is (d4→n6→n2→n3→d3).


#### 3.1.2. Segment

Segments=(p1,p2) is the part of an edge between two points, p1 and p2, on the edge. An edge consists of one or more segments. An edge is also considered a segment where the nodes are the end points of the edge. The weight of a segment (p1,p2) is denoted by W(s).


### 3.2. Problem Formulation

Similar to previous studies [5, 14, 23], we assume each data object d∈D has a point location d.l in the road network and a text description d.t. Given a query location q.l, a set of keywords q.t, andk number of data objects to return, the top-k spatial keyword query Qk is defined as Qk=(q.l,q.t,k), which takes three arguments and returns the bestk data objects fromD according to a score that considers spatial proximity and text relevance. The score ψ(d) of a data objectd is defined by the following equation:(1)ψd=μd.t,q.t1+α·λd.l,q.lwhereλ(d.l,q.l) is the spatial relevance between d.l and q.l, μ(d.t,q.t) is the textual relevance between d.t and q.t, and α is a positive real number that determines the importance of one measure over the other. For example, if only textual relevance is considered, then α=0. If more importance is given to spatial relevance, then α>1.Spatial relevance(λ) is defined as the shortest distance between data objectsd andq: λ(d.l,q.l)=dist(d.l,q.l). Thus, dist(di.l,q.l)<dist(dj.l,q.l) indicates that data object di is more spatially relevant toq than data object dj. The textual relevance (μ) can be computed using any popular information retrieval model, such as cosine similarity or the language model. In this study, we use the cosine similarity between d.t and q.t. The textual relevance is defined as follows:(2)μd.t,q.t=∑t∈q.twtd.t.wtq.t∑t∈d.twtd.t2.∑t∈q.twtq.t2The weightwt(d.t)=1+ln⁡(ft(d,t)), where ft(d,t) represents the frequency of termt in d.t. The weight wt(q.t)=ln⁡(1+|D|/dft), where |D| is the number of objects inD, and dft is the document frequency. A higher μ means a higher textual relevance to the query keywords. We used the variation of cosine similarity based on the significance factor θt(n) of termt in a documentn, wheren represents the description of data object d.t or query keywords q.t. The significance θt(n)=wt(n)/∑t∈n‍(wt(n))2 is the normalized weight of the term in the document by taking into account the length of the document [24, 25]. Hence, the textual relevance μ(d.t,q.t) can be rewritten as(3)μd.t,q.t=∑t∈q.tθtd.t.θtq.t


## 3.1. Definition of Terms and Notations

### 3.1.1. Road Network

A road network is represented by a weighted directed graphG=(N,E,W) where N, E, and W denote the node set, edge set, and edge distance matrix, respectively. The network distance of an edge changes depending on the traffic conditions. Each edge is also assigned an orientation that is either undirected or directed. The undirected edge is represented by e=(ns,ne)¯ where ns and ne are the boundary nodes nβ of an edge, whereas the directed edge is represented by e=(ns,ne)→ or e=(ne,ns)←. Naturally, the arrow above the edge indicates the associated direction. We refer to ns as the starting node and ne as the ending node of an edge. For example, in Figure 1, n6 is the starting node of edge (n6,n2)→, whereas it is the ending node for edge (n6,n5)←. The particular edge where a query object is located is called an active edge. It is important to note that, the distance between two points, p1 and p2, is not symmetrical in directed road networks (i.e., dist(p1,p2)≠dist(p2,p1)). For example in Figure 1, the dist(d3,d4)=3, whereas the dist(d4,d3)=11 because shortest path from d4 to d3 is (d4→n6→n2→n3→d3).


### 3.1.2. Segment

Segments=(p1,p2) is the part of an edge between two points, p1 and p2, on the edge. An edge consists of one or more segments. An edge is also considered a segment where the nodes are the end points of the edge. The weight of a segment (p1,p2) is denoted by W(s).


## 3.1.1. Road Network

A road network is represented by a weighted directed graphG=(N,E,W) where N, E, and W denote the node set, edge set, and edge distance matrix, respectively. The network distance of an edge changes depending on the traffic conditions. Each edge is also assigned an orientation that is either undirected or directed. The undirected edge is represented by e=(ns,ne)¯ where ns and ne are the boundary nodes nβ of an edge, whereas the directed edge is represented by e=(ns,ne)→ or e=(ne,ns)←. Naturally, the arrow above the edge indicates the associated direction. We refer to ns as the starting node and ne as the ending node of an edge. For example, in Figure 1, n6 is the starting node of edge (n6,n2)→, whereas it is the ending node for edge (n6,n5)←. The particular edge where a query object is located is called an active edge. It is important to note that, the distance between two points, p1 and p2, is not symmetrical in directed road networks (i.e., dist(p1,p2)≠dist(p2,p1)). For example in Figure 1, the dist(d3,d4)=3, whereas the dist(d4,d3)=11 because shortest path from d4 to d3 is (d4→n6→n2→n3→d3).


## 3.1.2. Segment

Segments=(p1,p2) is the part of an edge between two points, p1 and p2, on the edge. An edge consists of one or more segments. An edge is also considered a segment where the nodes are the end points of the edge. The weight of a segment (p1,p2) is denoted by W(s).


## 3.2. Problem Formulation

Similar to previous studies [5, 14, 23], we assume each data object d∈D has a point location d.l in the road network and a text description d.t. Given a query location q.l, a set of keywords q.t, andk number of data objects to return, the top-k spatial keyword query Qk is defined as Qk=(q.l,q.t,k), which takes three arguments and returns the bestk data objects fromD according to a score that considers spatial proximity and text relevance. The score ψ(d) of a data objectd is defined by the following equation:(1)ψd=μd.t,q.t1+α·λd.l,q.lwhereλ(d.l,q.l) is the spatial relevance between d.l and q.l, μ(d.t,q.t) is the textual relevance between d.t and q.t, and α is a positive real number that determines the importance of one measure over the other. For example, if only textual relevance is considered, then α=0. If more importance is given to spatial relevance, then α>1.Spatial relevance(λ) is defined as the shortest distance between data objectsd andq: λ(d.l,q.l)=dist(d.l,q.l). Thus, dist(di.l,q.l)<dist(dj.l,q.l) indicates that data object di is more spatially relevant toq than data object dj. The textual relevance (μ) can be computed using any popular information retrieval model, such as cosine similarity or the language model. In this study, we use the cosine similarity between d.t and q.t. The textual relevance is defined as follows:(2)μd.t,q.t=∑t∈q.twtd.t.wtq.t∑t∈d.twtd.t2.∑t∈q.twtq.t2The weightwt(d.t)=1+ln⁡(ft(d,t)), where ft(d,t) represents the frequency of termt in d.t. The weight wt(q.t)=ln⁡(1+|D|/dft), where |D| is the number of objects inD, and dft is the document frequency. A higher μ means a higher textual relevance to the query keywords. We used the variation of cosine similarity based on the significance factor θt(n) of termt in a documentn, wheren represents the description of data object d.t or query keywords q.t. The significance θt(n)=wt(n)/∑t∈n‍(wt(n))2 is the normalized weight of the term in the document by taking into account the length of the document [24, 25]. Hence, the textual relevance μ(d.t,q.t) can be rewritten as(3)μd.t,q.t=∑t∈q.tθtd.t.θtq.t


## 4. Query Processing System

In this section, we present the proposed query processing system that indexes the data objects and prunes the irrelevant edges for efficient query processing. In Section4.1, we discuss the indexing framework, and in Section 4.2, we present an efficient keyword query processing algorithm for snapshot queries.


### 4.1. Indexing Framework

In this study, our main work focuses on moving queries in a directed and dynamic road networks. We use a method similar to the enhanced technique presented in [12] as our basic framework for processing snapshot queries in directed and dynamic road networks. The indexing framework combines a road network framework [1] for storing spatial information and an inverted file for indexing data objects. For easy traversing of the network, we store the adjacent nodes of each given node by storing node id (nid), edge id (eid), the direction of the edge, and the weight of the edge. The indexing framework consists of two main components: a pruning component and an inverted file component. Figure 2 illustrates the main components of an indexing framework. The pruning component first prunes the edges that contain data objects irrelevant to the query keyword. To achieve this, we introduced the highest significance θt+ of a given termt in the description of objects lying on the edge. The θt+ on an edge is retrieved by a key composed of a pair of edge id and term id (eid,tid). The θt+ represents an upper-bound significance of any object lying on an edge with termt in its description. The inverted list of a termt on an edge is accessed only if the upper-bound score composed by θt+ and the minimum network distance between the starting node of the edge and queryq may return a candidate data object. Naturally, the edges with upper-bound scores smaller than the score of thek-th object found so far are pruned.Figure 2
Indexing framework.We implement an inverted file for indexing data objects. The inverted file contains a vocabulary and inverted lists. The vocabulary keeps general information about each term (such as the frequency of the term), which is helpful in computing the textual relevance of the data objects. The inverted list stores the data objects located on the edge(ns,ne)→ that have a termt in their description. An inverted list is identified by a key composed of (eid,tid). Each inverted file is a set of inverted lists. A separate inverted list is used for each term in the object description. An inverted list stores two attributes for each data object: first, the distance between the data object and the starting node dist(ns,di); second, the significance factor θ(ti,di) of the term ti in the description of the data object. Note that the network distance between two points in a directed road network is not symmetrical (i.e., dist(ns,di)≠dist(di,ns)). Recall that the starting node is chosen according to the orientation of the edge such that the direction of the edge is from the node toward the data object. In Figure 1, n3 is the starting node for d7. For bidirectional edges, any of the adjacent nodes can act as a starting node.The proposed indexing scheme has three main advantages. First, the object search relevant to query keywords is very efficient using the(eid,tid) pair. Second, inverted files also store the network distance between the starting node and the data object, which helps in accessing the data object in the directed road network. Finally, the pruning technique allows for faster query processing by exploring fewer edges.Table2 presents the notations used in this study.Table 2
Summary of notations used in this paper.
Notation Definition G = (N, E,W) Graph model of road network dist(ps,pe) Length of shortest path fromps to pe, where ps and pe represent start and end points, respectively l e n ( p 1 , p 2 ) Length of segment connecting two pointsp1 and p2 ni Node in road network e=(ns,ne) Edge in edge set E, wherens and ne are start and end points of the edge nβ Boundary node corresponding to start (ns) or end (ne) point of an edge W(e) Weight of edge(ns,ne) q Query point in road network k A number that representsq can be among k number of closest facilities to a data object d D Set of data objectsD=d1,d2,…,d|D| D ( n s , n e ) Set of data objects in an edge p a Anchor point that corresponds to start point of expansion P S E Safe exit point where safe and non-safe regions ofq intersect α query parameter ψ ( d ) Score of data objectd μ ( d . t , q . t ) textual relevance of data objectd with query keywords λ ( d . l , q . l ) Spatial relevance of data objectd with query location D + Set of answer objects D - Set of non-answer objects d l + Lowest answer object d h - Highest non-answer object


### 4.2. Query Processing Algorithm

Our algorithm traverses the road network incrementally in a similar fashion to Dijkstra’s algorithm [26]. Algorithm 1 returns the top-k data objects with the highest scores according to their joint textual and spatial relevance to the query. The algorithm begins by exploring the active edge where query objectq is located, and expands the network in an increasing order of distance fromq. Each entry in the min-heap has the form (pa,edge), where pa indicates the anchor point in the edge. For an active edge,q becomes the anchor point. Otherwise, for directed edges, ending node ne becomes the anchor point. For bidirectional edges, either of the adjacent boundary nodes, i.e., ns or ne, becomes the anchor point. Let Dk be the current set of top-k data objects and sk be the score of thek-th data object in Dk. The candsearch((eid,tid),sk) function retrieves the candidate data objects Dc located in an edge with a better score ψ(d) than sk. Next, the Dk set is updated with the data objects in Dc, and so does sk. The algorithm continues its expansion and inserts the adjacent edges of the boundary node until the heap is exhausted or the upper-bound score of the remaining data objects cannot have a better score than sk. The upper-bound score ψ(n) of noden is computed using dist(n,q) and the maximum textual relevance (μ=1). Therefore, if ψ(n)≤sk, it means that even if there is unexplored data objectd matching all query keywords, its score can be better than the k-th object in Dk because dist(d,q.l)≥dist(n,q.l). This is certain owing to the fact that the algorithm strictly expands the node with a minimum distance to the query location.Algorithm 1:EvaluateSnapshotQuery(Node ni, Edge ei).
( 1 )  Input: Top-k spatial keyword query QN=(q.l,q.t,k) ( 2 )  Output: Top-k data objects with highest score ( 3 )  D c ← ∅ /∗set of candidate data objects (4)max-heapDk←∅ /∗current Top-k set (5)sk←0 /∗k-th score in Dk (6)min-heap←∅ (7)explored←∅ (8)min-heap.insert(q.l,edgeactive) (9)Dc←candsearch((eid,tid),sk) (10)update Dk and sk with d∈Dc (11)whilemin-heap≠∅and(1/1+α.λ(d.l,q.l)<sk)do (12)for  each unexplored adjacent edge of (pa,edge)  do (13)explored←explored∪(pa,edge) (14)Dc←candsearch((eid,tid),sk) (15)update Dk and sk with d∈Dc (16)end (17)min-heap.insert(adjacent node, edge) (18)end (19)return DkAlgorithm2 presents the candsearch((eid,tid),sk) procedure, which finds the candidate data objects. This procedure has two main steps. In the first step, the upper-bound score of the edges is computed using a significance factor (θt) of a term t∈q.t and the shortest distance sdist(ei,q.l) between the edge and the query location. In the next step, the inverted lists of termt are fetched if their upper-bound score is greater than sk. In the inverted lists, the objects with score ψ(d) greater than sk are returned.Algorithm 2:CandidateSearch((eid,tid),sk).
( 1 )  Input: Edge ID: eid, Term ID: tid, score of k-th object sk ( 2 )  Output: candidate list Dc ( 3 ) compute θt(ei) (4)ifθt(ei)>0then (5)max.score(ei)←computemax.score(θt,dist(ei,q.l)) (6)end (7)ifmax.score(ei)>skthen (8)for  each data object ineido (9)compute d.score (10)end (11)ifd.score>skthen (12)Dc←Dc∪d (13)end (14)end (15)return DcTo understand the proposed algorithm, consider the road network presented in Figure1. Assume that a queryq generated a top-1 keyword query with q.d “Italian Restaurant.” For ease of presentation, we assume α=1 and the textual relevance μ is the number of occurrences of query keywords in d.t divided by the number of keywords in the document (description of data object). For example, ψ(d4)=μ(d4.t,q.t)/1+λ(d4.l,q.l)=0.5/8=0.06. The algorithm starts the network expansion from an active edge (n2,n3)→ whereq is the anchor point. Note that the direction of the edge (n2,n3)→ is from n2 to n3. Therefore, the algorithm explores only (q,n3)→. There is no data object found in (q,n3)→. Then, n3 becomes the anchor point and edges (n3,n4)¯, (n3,n5)¯, and (n3,n7)¯ are inserted in min-heap. Next, the candsearch function retrieves the candidate data objects on edges (n3,n4)¯, (n2,n3)¯, and (n3,n7)¯, whose score is better than sk. On edge (n3,n5)¯, data object d3 is retrieved with ψ(d3)=0.2. Data object d3 is inserted in the Dk set, and the value of sk is set to 0.2. For edges (n3,n4)¯ and (n3,n7)¯, there is no candidate object found because d2.t (“Cafe”) and d7.t (“Cafe and Bakery”) do not match with q.t. The algorithm continues expanding the edges whose upper-bound score is greater than sk. The edge (n7,n2)→ is explored next. The upper-bound score of (n7,n2)→ is 1/7, which is less than sk. Similarly, for edge (n6,n5)←, the upper-bound score is 0.5/8<sk. Therefore, the algorithm terminates and reports d3 as the top-1 result.


## 4.1. Indexing Framework

In this study, our main work focuses on moving queries in a directed and dynamic road networks. We use a method similar to the enhanced technique presented in [12] as our basic framework for processing snapshot queries in directed and dynamic road networks. The indexing framework combines a road network framework [1] for storing spatial information and an inverted file for indexing data objects. For easy traversing of the network, we store the adjacent nodes of each given node by storing node id (nid), edge id (eid), the direction of the edge, and the weight of the edge. The indexing framework consists of two main components: a pruning component and an inverted file component. Figure 2 illustrates the main components of an indexing framework. The pruning component first prunes the edges that contain data objects irrelevant to the query keyword. To achieve this, we introduced the highest significance θt+ of a given termt in the description of objects lying on the edge. The θt+ on an edge is retrieved by a key composed of a pair of edge id and term id (eid,tid). The θt+ represents an upper-bound significance of any object lying on an edge with termt in its description. The inverted list of a termt on an edge is accessed only if the upper-bound score composed by θt+ and the minimum network distance between the starting node of the edge and queryq may return a candidate data object. Naturally, the edges with upper-bound scores smaller than the score of thek-th object found so far are pruned.Figure 2
Indexing framework.We implement an inverted file for indexing data objects. The inverted file contains a vocabulary and inverted lists. The vocabulary keeps general information about each term (such as the frequency of the term), which is helpful in computing the textual relevance of the data objects. The inverted list stores the data objects located on the edge(ns,ne)→ that have a termt in their description. An inverted list is identified by a key composed of (eid,tid). Each inverted file is a set of inverted lists. A separate inverted list is used for each term in the object description. An inverted list stores two attributes for each data object: first, the distance between the data object and the starting node dist(ns,di); second, the significance factor θ(ti,di) of the term ti in the description of the data object. Note that the network distance between two points in a directed road network is not symmetrical (i.e., dist(ns,di)≠dist(di,ns)). Recall that the starting node is chosen according to the orientation of the edge such that the direction of the edge is from the node toward the data object. In Figure 1, n3 is the starting node for d7. For bidirectional edges, any of the adjacent nodes can act as a starting node.The proposed indexing scheme has three main advantages. First, the object search relevant to query keywords is very efficient using the(eid,tid) pair. Second, inverted files also store the network distance between the starting node and the data object, which helps in accessing the data object in the directed road network. Finally, the pruning technique allows for faster query processing by exploring fewer edges.Table2 presents the notations used in this study.Table 2
Summary of notations used in this paper.
Notation Definition G = (N, E,W) Graph model of road network dist(ps,pe) Length of shortest path fromps to pe, where ps and pe represent start and end points, respectively l e n ( p 1 , p 2 ) Length of segment connecting two pointsp1 and p2 ni Node in road network e=(ns,ne) Edge in edge set E, wherens and ne are start and end points of the edge nβ Boundary node corresponding to start (ns) or end (ne) point of an edge W(e) Weight of edge(ns,ne) q Query point in road network k A number that representsq can be among k number of closest facilities to a data object d D Set of data objectsD=d1,d2,…,d|D| D ( n s , n e ) Set of data objects in an edge p a Anchor point that corresponds to start point of expansion P S E Safe exit point where safe and non-safe regions ofq intersect α query parameter ψ ( d ) Score of data objectd μ ( d . t , q . t ) textual relevance of data objectd with query keywords λ ( d . l , q . l ) Spatial relevance of data objectd with query location D + Set of answer objects D - Set of non-answer objects d l + Lowest answer object d h - Highest non-answer object


## 4.2. Query Processing Algorithm

Our algorithm traverses the road network incrementally in a similar fashion to Dijkstra’s algorithm [26]. Algorithm 1 returns the top-k data objects with the highest scores according to their joint textual and spatial relevance to the query. The algorithm begins by exploring the active edge where query objectq is located, and expands the network in an increasing order of distance fromq. Each entry in the min-heap has the form (pa,edge), where pa indicates the anchor point in the edge. For an active edge,q becomes the anchor point. Otherwise, for directed edges, ending node ne becomes the anchor point. For bidirectional edges, either of the adjacent boundary nodes, i.e., ns or ne, becomes the anchor point. Let Dk be the current set of top-k data objects and sk be the score of thek-th data object in Dk. The candsearch((eid,tid),sk) function retrieves the candidate data objects Dc located in an edge with a better score ψ(d) than sk. Next, the Dk set is updated with the data objects in Dc, and so does sk. The algorithm continues its expansion and inserts the adjacent edges of the boundary node until the heap is exhausted or the upper-bound score of the remaining data objects cannot have a better score than sk. The upper-bound score ψ(n) of noden is computed using dist(n,q) and the maximum textual relevance (μ=1). Therefore, if ψ(n)≤sk, it means that even if there is unexplored data objectd matching all query keywords, its score can be better than the k-th object in Dk because dist(d,q.l)≥dist(n,q.l). This is certain owing to the fact that the algorithm strictly expands the node with a minimum distance to the query location.Algorithm 1:EvaluateSnapshotQuery(Node ni, Edge ei).
( 1 )  Input: Top-k spatial keyword query QN=(q.l,q.t,k) ( 2 )  Output: Top-k data objects with highest score ( 3 )  D c ← ∅ /∗set of candidate data objects (4)max-heapDk←∅ /∗current Top-k set (5)sk←0 /∗k-th score in Dk (6)min-heap←∅ (7)explored←∅ (8)min-heap.insert(q.l,edgeactive) (9)Dc←candsearch((eid,tid),sk) (10)update Dk and sk with d∈Dc (11)whilemin-heap≠∅and(1/1+α.λ(d.l,q.l)<sk)do (12)for  each unexplored adjacent edge of (pa,edge)  do (13)explored←explored∪(pa,edge) (14)Dc←candsearch((eid,tid),sk) (15)update Dk and sk with d∈Dc (16)end (17)min-heap.insert(adjacent node, edge) (18)end (19)return DkAlgorithm2 presents the candsearch((eid,tid),sk) procedure, which finds the candidate data objects. This procedure has two main steps. In the first step, the upper-bound score of the edges is computed using a significance factor (θt) of a term t∈q.t and the shortest distance sdist(ei,q.l) between the edge and the query location. In the next step, the inverted lists of termt are fetched if their upper-bound score is greater than sk. In the inverted lists, the objects with score ψ(d) greater than sk are returned.Algorithm 2:CandidateSearch((eid,tid),sk).
( 1 )  Input: Edge ID: eid, Term ID: tid, score of k-th object sk ( 2 )  Output: candidate list Dc ( 3 ) compute θt(ei) (4)ifθt(ei)>0then (5)max.score(ei)←computemax.score(θt,dist(ei,q.l)) (6)end (7)ifmax.score(ei)>skthen (8)for  each data object ineido (9)compute d.score (10)end (11)ifd.score>skthen (12)Dc←Dc∪d (13)end (14)end (15)return DcTo understand the proposed algorithm, consider the road network presented in Figure1. Assume that a queryq generated a top-1 keyword query with q.d “Italian Restaurant.” For ease of presentation, we assume α=1 and the textual relevance μ is the number of occurrences of query keywords in d.t divided by the number of keywords in the document (description of data object). For example, ψ(d4)=μ(d4.t,q.t)/1+λ(d4.l,q.l)=0.5/8=0.06. The algorithm starts the network expansion from an active edge (n2,n3)→ whereq is the anchor point. Note that the direction of the edge (n2,n3)→ is from n2 to n3. Therefore, the algorithm explores only (q,n3)→. There is no data object found in (q,n3)→. Then, n3 becomes the anchor point and edges (n3,n4)¯, (n3,n5)¯, and (n3,n7)¯ are inserted in min-heap. Next, the candsearch function retrieves the candidate data objects on edges (n3,n4)¯, (n2,n3)¯, and (n3,n7)¯, whose score is better than sk. On edge (n3,n5)¯, data object d3 is retrieved with ψ(d3)=0.2. Data object d3 is inserted in the Dk set, and the value of sk is set to 0.2. For edges (n3,n4)¯ and (n3,n7)¯, there is no candidate object found because d2.t (“Cafe”) and d7.t (“Cafe and Bakery”) do not match with q.t. The algorithm continues expanding the edges whose upper-bound score is greater than sk. The edge (n7,n2)→ is explored next. The upper-bound score of (n7,n2)→ is 1/7, which is less than sk. Similarly, for edge (n6,n5)←, the upper-bound score is 0.5/8<sk. Therefore, the algorithm terminates and reports d3 as the top-1 result.


## 5. Moving Top-k Spatial Keyword Queries

In this section, we present our method to monitor the moving top-k spatial keyword queries where query objects are moving in a directed road network. Figure3 provides an example of TkSK in road networks, where query pointq issues a TkSK query at point p1. Note that the numbers on the arrows in the figure indicate the order of the steps. To obtain top-k results at p1, the server executes Algorithm 1 as mentioned in Section 4.2. Now, consider that the query object is moved to p2 as shown in Figure 4 to retrieve the top-k results at point p2. The simple method is to repeat the procedure executed at p1. However, the use of recomputation whenever queryq changes its location significantly increases the computation cost. Furthermore, it also increases the communication overhead because the query object must report its location whenever it moves, and the server must send the results set. To address these issues, we introduce the safe exit approach.Figure 3
Illustration of directed road network.Figure 4
Illustration of directed road network.In the proposed framework, the server computes safe exit points for a query object. The server maintains a set of moving queries, and the query result remains valid until the query objects remain inside their respective safe exit points. Whenever a query object leaves its safe exit points, the server recomputes the TkSK and safe exit points for the query object.Next, we present our method to compute the safe exit points for a query object. The safe exit point represents a point in the segment where a safe region and nonsafe region meet. We compute the safe exit point using the divide-and-conquer technique. Before presenting the detailed methodology, we define the terminologies used in this section.Definition 1 (safe region).
A portion of a road segment that can guarantee that, as long as the query point lies in it, its top-k results remain valid.Definition 2 (answer objectsD+).
A data objectd is called an answer object of queryq if the score of data objectd (ψ(d)>ψ(da)), where da represents any other data object in the directed road network. Similarly, we can generalize this definition for TkSK: a data objectd is called an answer object of queryq if the score of a data objectd (ψ(d)>ψ(dk+1)), where dk+1 represents the (k+1)th data object in the directed road network. In other words, we can state that all answer objects are top-k results of queryq.Definition 3 (nonanswer objectsD-).
A data objectd is called a nonanswer object of queryq if the score of data objectd (ψ(d)<ψ(da)), where da represents any other data object in the directed road network. Similarly, we can generalize this definition for TkSK: a data objectd is called a nonanswer object of queryq if the score of data objectd (ψ(d)<ψ(dk)), where dk represents thekth data object in the directed road network. That is, we can say that all answer objects are top-k results of queryq. Therefore, we can state that none of the nonanswer objects are in the top-k results of queryq.Definition 4 (lowest answer objectDl+).
An answer objectd+∈D+ is called a lowest answer object to a point p∈G such that ψ(dl+)p=min(ψ(d1+)p,ψ(d2+)p,…,ψ(d|d+|+)p), where ψ(dl+)p represents the score of the lowest answer object at pointp. In other words, ψ(dl+)p<ψ(da+)p at pointp, where da+ is any other answer object in the D+ set.Definition 5 (highest nonanswer objectDh-).
A nonanswer objectd-∈D- is called a highest nonanswer object to a point p∈G such that ψ(dh-)p=max(ψ(d1-)p,ψ(d2-)p,…,ψ(d|d-|+)p), where ψ(dh+)p represents the score of the highest nonanswer object at pointp. In other words, the ψ(dl-)p<ψ(da-)p at pointp, where da- is any other nonanswer object in the D- set.As discussed earlier, the main challenge in the continuous processing of moving TkSK is to maintain the validity of the result set because the movement of query objects can nullify the result set. To monitor the validity of the result set, we propose a safe-region-based approach.


### 5.1. Computation of Safe Exit Points

In this section, we present our technique to compute the safe exit points. The main goal is to find a point in the road network where the query result set will change. The result set will change when the score of highest nonanswerDh- surpasses the score of Dl+. Generally, the textual relevance score does not change. Therefore, the score of data objects only changes because of the spatial relevance score, which can only change by the movement of query objects. The computation of the safe exit point is based on two key observations:Observation 1.
IfDnβ+=Dpa+, there is no safe exit point in the segment
Explanation. Dpa+ represents the set of answer objects at anchor point pa, whereas Dnβ+ represents the set of answer objects at boundary node nβ. As discussed earlier, the safe exit point is the particular point where the query results changed. If the query results at the starting node are the same as the ending node of any segment/edge, there does not exist any point where the query result is changing. Hence, we do not search the safe exit point in that segment.Observation 2.
IfDpa+≠Dnβ+, there is a safe exit point in the segment
Explanation. In contrast to Observation 1, if the query results are different at the starting and ending points, then there exists a point where the query results are changing. Hence, there is a safe exit point in the segment.To find the safe region, we observe the following cases:Case 1 (whenα=1 and the textual relevance of the highest nonanswer object and lowest answer object is the same).
In this case, both the textual and spatial relevance have the same importance (i.e.,α=1). In addition, the top-k result depends only on the spatial relevance because the textual relevance of both objects is the same. The data object that is closer to query pointq becomes the answer object. For an undirected edge, the safe exit point pse is the center point, i.e., max(dist(pse,d1+),dist(pse,d2+),…,dist(pse,d|d+|+))=min(dist(pse,d1-),dist(pse,d2-),…,dist(pse,d|d-|-)), between the lowest answer object and the highest nonanswer object. However, in case of a directed edge where dist(pa,nβ)≠dist(nβ,pa), the safe exit point is either dl+ or pa. If dl+∈(pa,nβ), then the safe exit point is dl+; otherwise, the safe exit point is pa.Case 2 (whenα≠1 and the textual relevance of the highest nonanswer object and lowest answer object is different).
In this case, the top-k result depends on all functions that are the α, spatial, and textual relevance. Clearly, for the undirected edges, the midpoint between the lowest answer object and the highest nonanswer object does not provide a valid safe exit point. Therefore, we introduce the divide-and-conquer technique. This will keep dividing the search space until we get the point where the score of the nonanswer is greater than that of the answer object. Typically, the safe exit point should be closer to the data object whose score is lower. Based on this observation, first we compute the midpoint in a similar fashion to Case 1, and then we continue dividing the search space until we find the point. For undirected edges, the safe exit point can be computed in a similar fashion to Case 1.Case2 also works for other cases when the safe exit point is not the mid point between the lowest answer object and the highest nonanswer object. In these cases the safe exit point depends on two or more functions. Therefore, the safe exit point can be easily computed using the aforementioned divide-and-conquer technique. Following are the scenarios where the safe exit point can be computed using Case 2.(a)
Whenα=1 and textual relevance of the nearest nonanswer object and farthest answer object is different.(b)
Whenα≠1 and textual relevance of the nearest nonanswer object and farthest answer object is same.Case 3 (whenα=0).
This means the spatial relevance has no effect on the score of data objects. Hence, no monitoring is required for this scenario.Algorithm3 retrieves the safe exit points using the observations we discussed earlier. The core function in this algorithm is ComputeSafeExit(pa,nβ), which finds the safe exit point in a segment between pa and nβ. The detailed ComputeSafeExit(pa,nβ) is described in Algorithm 4. First, Algorithm 4 determines dl+ and dh- at point p∈[pa,nβ]. Recall that dl+ is the lowest answer object top, where dh- is the highest nonanswer object top. Algorithm 4 computes the safe exit point based on the cases we discussed earlier. There are a further two scenarios for Cases 1 and 2. For Case 1, if dist(pa,nβ)=dist(nβ,pa), then the safe exit point is the midpoint between dl+ and dh-. If dist(pa,nβ)≠dist(nβ,pa), then the edge is directed, and therefore the safe exit point is either pa or dl+. If dl+ lies on the edge [pa,nβ], then dl+ is the safe exit point. Otherwise, pa is the safe exit point.Algorithm 3:COSK: monitoring algorithm.
( 1 )  Input: Same as Algorithm 1 ( 2 )  Output: P S E: a set of safe exit points ( 3 )  P S E ← ∅/∗set of safe exit points (4)Dpa+←EvaluateSnapshotQuery(pa,(pa,nβ)) (5)/∗Results calculated using Algorithm 1 (6)Dnβ+←EvaluateSnapshotQuery((nβ,(pa,nβ))) (7)/∗Results calculated using Algorithm 1 (8)ifDpa+=Dnβ+then (9)no safe exit point /∗refer to Observation 1 (10)end (11)ifDpa+≠Dnβ+then (12)PSE←PSE∪ComputeSafeExit(pa,nβ)/∗safe exit point exist - refer to Observation 2 (13)end (14)return PSEAlgorithm 4:ComputeSafeExit(pa,nβ).
( 1 )  Input: same as Algorithm 1 ( 2 )  Output: se: safe exit point in (pa,nβ) ( 3 )  D l + ←   < p , D l + > | for each point p∈[pa,nβ], dl+ such that ψ ( d l + ) p = m i n ( ψ ( d 1 + ) p , ψ ( d 2 + ) p , … , ψ ( d | d + | + ) p (4)Dh-←<p,Dh->| for each point p∈[pa,nβ], dh- such that ψ ( d h - ) p = m a x ( ψ ( d 1 - ) p , ψ ( d 2 - ) p , … , ψ ( d | d - | - ) p (5)if  Case1  then (6)ifdist(pa,nβ)=dist(nβ,pa)then (7)pse= m a x ( d i s t ( s e , d 1 + ) , d i s t ( s e , d 2 + ) , … , d i s t ( s e , d | d + | + ) ) = m i n ( d i s t ( s e , d 1 - ) , d i s t ( s e , d 2 - ) , … , d i s t ( s e , d | d - | - ) ) (8)end (9)ifdist(pa,nβ)≠dist(nβ,pa)then (10)pse=pa or pse=dl+ where dl+∈(pa,nβ) (11)end (12)end (13)if  Case2  then (14)ifdist(pa,nβ)=dist(nβ,pa)then (15)pse=closest point to pa such that ψ(dh-)>ψ(dl+) (16)end (17)ifdist(pa,nβ)≠dist(nβ,pa)then (18)Same as Line (10) (19)end (20)end (21)return pseSimilarly, for Case2, if dist(pa,nβ)=dist(nβ,pa), then the safe exit point is computed by dividing the search space by half until we find the closest point such that ψ(dh-)>ψ(dl+). The safe exit point is computed in the same way as in Case 2 if dist(pa,nβ)≠dist(nβ,pa).


### 5.2. Computation of Safe Exit Points for Example

Consider the same example in Figure1, where the query pointq issues a top-1 keyword query withq.t “Italian restaurant.” For this example, let us consider α=1. The monitoring algorithm starts exploring from the active edge containing the query objectq. Therefore, (q,n3)→ is explored first. As shown in Table 3, for (q,n3)→, Dq+=d3 and Dn3+=d3. According to Observation 1, no safe exit point exists in this segment. Therefore, edges adjacent to n3 are explored, and n3 becomes the new pa. The edge (n3,n4)¯ is explored next. Similarly, the answer object at n3 and n4 is the same: Dn3+=Dn4+=d3. Therefore, a safe exit point does not exist in (n3,n4)¯. The edge (n3,n7)¯ is explored next. As shown in Table 3, Dn3+=d3 and Dn7+=d6. By Observation 2, there is a safe exit point in (n3,n7)¯. As shown in Figure 1, d3.t=d6.t=“ItalianRestaurant” and dist(n3,n7)=dist(n7,n3). Therefore, according to Case 1, the safe exit point s1 is the midpoint between d3 and d6. That is, dist(pse1,d3)=dist(pse1,d6), where dist(pse1,d3)=x+3 and dist(pse1,d6)=-x+5 for 0<x<3. Consequently, x=1, which means that the distance from n3 to pse1 is 1.Table 3
Computation of safe exit points for example scenario.
Edge/Segment pa Dpa+ Dnβ+ pse (q,n3)→ q D q + = d 3 D n 3 + = d 3 none (n3,n4)¯ q D n 3 + = d 3 D n 4 + = d 3 none (n3,n7)¯ n 3 D n 3 + = d 3 D n 7 + = d 6 p s e 1 (n3,n5)→ n 3 D n 3 + = d 3 D n 5 + = d 3 none (n6,n5)← n 5 D n 5 + = d 3 D n 6 + = d 4 pse2Next, we determine a safe exit point in(n3,n5)¯. As shown in Table 3, the answer object at n5 is also the same as n3. Hence, no safe exit point exists in this edge. Next, (n6,n5)← is explored with pa=n5. According to Table 3, Dn7+=d4 and Dn5+=d3. Therefore, a safe exit point exists in this edge. This edge is directed, and for each point p∈(n6,n5)←, the shortest distance fromp to d3 is from p→n6→n2→n3→d3. Therefore, n5 is the safe exit point.The bold lines in Figure5 indicate the safe region ofq. The top-1 result remains d3 until the queryq lies in the safe region.Figure 5
Illustration of safe region ofq.Next, we analyze the time complexity for determining a set of safe exit points using a set of qualifying objectsd∈Dpa+∪Dnβ+∪D(pa,nβ¯). Note that Dpa+(Dnβ+) indicates the set ofk data objects that satisfies the query condition at pa(nβ). According to Dijkstras algorithm [26], the time complexity O(Dq+) for computing a set of answer objects at a query pointq is O(Dq+)=O(E+Nlog⁡N). This means that O(Dpa+)=O(Dnβ+)=O(E+Nlog⁡N) holds for endpoints pa and nβ. Thus, time complexity O(Ωkth) when determining the skyline Ωkth with the k-th highest score is O(Ωkth)=Ckth.O(|Dpa+∪Dnβ+∪D(pa,nβ¯)|) where Ckth is the number of qualifying objects that participate in the constitution of the skyline with the k-th highest score. Therefore, the time complexity of determining a safe exit point coincides with the time complexity of determining the two skylines, i.e., the skyline Dl+ with the k-th highest (or lowest) score for answer objects and the skyline Dh- with the highest score for nonanswer objects. This is because the safe exit point is found at the cross point between these skylines.Figure6, represents the skyline graph for k=1 in an edge (n7,n3)¯. Let us draw the score function for d3 and d6 for the road segment (n7,n3)¯ where a safe exit point exists. This is because D(n3)+=d3 and D(n7)+=d6 for k=1. For each point p∈(n7,n3)¯, the distance between d3 and pointp can be represented as dist(d3,p)=dist(d3,n3)+len(n3,p)=6-len(n7,p). Similarly, for each point p∈(n7,n3)¯, the distance between d6 and pointp can be represented as dist(d6,p)=dist(d6,n7)+len(n7,p)=2+len(n7,p). Let, len(n7,p) be a variablex(0≤x≤3). We can write λ(d3,p)=dist(d3,p)=6-x and λ(d6,p)=dist(d6,p)=2+x. Then, we can represent score function ψ(d3) and ψ(d6) as follows:ψ(d3)=μ(d3.t,q.t)/1+α·λ(d3,p)=1/(7-x) for (0≤x≤3)ψ(d6)=μ(d6.t,q.t)/1+α·λ(d6,p)=1/(3+x) for (0≤x≤3)Figure 6
Skyline graph fork=1 on the road segment (n7,n3)¯.Finally, we present the lemma to prove that safe exit points computed by COSK are correct.Lemma 8.
The COSK algorithm correctly computes a set of safe exit points.Proof.
We will prove the correctness of the COSK algorithm by contradiction. We assume that ifDpa+≠Dnβ+, there is no safe exit point in a road segment (panβ¯). This means that, for each pointp in the road segment (panβ¯), the query result atp equals Dpa+, i.e., Dp+=Dpa+∀p∈(panβ¯). However, it leads to a contradiction that Dnβ+=Dpa+ when p=nβ. Therefore, if Dpa+≠Dnβ+, a safe exit point exists in (panβ¯). In addition, a safe exit point is determined using the skyline Dl+ for answer objects and the skyline Dh- with the highest score for nonanswer objects when Dpa+≠Dnβ+. The first skyline is a composite polyline drawn from answer objects in Dpa+. The second skyline is a composite polyline drawn from nonanswer objects in Dnβ+∪D(pa,nβ¯)-Dpa+.


## 5.1. Computation of Safe Exit Points

In this section, we present our technique to compute the safe exit points. The main goal is to find a point in the road network where the query result set will change. The result set will change when the score of highest nonanswerDh- surpasses the score of Dl+. Generally, the textual relevance score does not change. Therefore, the score of data objects only changes because of the spatial relevance score, which can only change by the movement of query objects. The computation of the safe exit point is based on two key observations:Observation 1.
IfDnβ+=Dpa+, there is no safe exit point in the segment
Explanation. Dpa+ represents the set of answer objects at anchor point pa, whereas Dnβ+ represents the set of answer objects at boundary node nβ. As discussed earlier, the safe exit point is the particular point where the query results changed. If the query results at the starting node are the same as the ending node of any segment/edge, there does not exist any point where the query result is changing. Hence, we do not search the safe exit point in that segment.Observation 2.
IfDpa+≠Dnβ+, there is a safe exit point in the segment
Explanation. In contrast to Observation 1, if the query results are different at the starting and ending points, then there exists a point where the query results are changing. Hence, there is a safe exit point in the segment.To find the safe region, we observe the following cases:Case 1 (whenα=1 and the textual relevance of the highest nonanswer object and lowest answer object is the same).
In this case, both the textual and spatial relevance have the same importance (i.e.,α=1). In addition, the top-k result depends only on the spatial relevance because the textual relevance of both objects is the same. The data object that is closer to query pointq becomes the answer object. For an undirected edge, the safe exit point pse is the center point, i.e., max(dist(pse,d1+),dist(pse,d2+),…,dist(pse,d|d+|+))=min(dist(pse,d1-),dist(pse,d2-),…,dist(pse,d|d-|-)), between the lowest answer object and the highest nonanswer object. However, in case of a directed edge where dist(pa,nβ)≠dist(nβ,pa), the safe exit point is either dl+ or pa. If dl+∈(pa,nβ), then the safe exit point is dl+; otherwise, the safe exit point is pa.Case 2 (whenα≠1 and the textual relevance of the highest nonanswer object and lowest answer object is different).
In this case, the top-k result depends on all functions that are the α, spatial, and textual relevance. Clearly, for the undirected edges, the midpoint between the lowest answer object and the highest nonanswer object does not provide a valid safe exit point. Therefore, we introduce the divide-and-conquer technique. This will keep dividing the search space until we get the point where the score of the nonanswer is greater than that of the answer object. Typically, the safe exit point should be closer to the data object whose score is lower. Based on this observation, first we compute the midpoint in a similar fashion to Case 1, and then we continue dividing the search space until we find the point. For undirected edges, the safe exit point can be computed in a similar fashion to Case 1.Case2 also works for other cases when the safe exit point is not the mid point between the lowest answer object and the highest nonanswer object. In these cases the safe exit point depends on two or more functions. Therefore, the safe exit point can be easily computed using the aforementioned divide-and-conquer technique. Following are the scenarios where the safe exit point can be computed using Case 2.(a)
Whenα=1 and textual relevance of the nearest nonanswer object and farthest answer object is different.(b)
Whenα≠1 and textual relevance of the nearest nonanswer object and farthest answer object is same.Case 3 (whenα=0).
This means the spatial relevance has no effect on the score of data objects. Hence, no monitoring is required for this scenario.Algorithm3 retrieves the safe exit points using the observations we discussed earlier. The core function in this algorithm is ComputeSafeExit(pa,nβ), which finds the safe exit point in a segment between pa and nβ. The detailed ComputeSafeExit(pa,nβ) is described in Algorithm 4. First, Algorithm 4 determines dl+ and dh- at point p∈[pa,nβ]. Recall that dl+ is the lowest answer object top, where dh- is the highest nonanswer object top. Algorithm 4 computes the safe exit point based on the cases we discussed earlier. There are a further two scenarios for Cases 1 and 2. For Case 1, if dist(pa,nβ)=dist(nβ,pa), then the safe exit point is the midpoint between dl+ and dh-. If dist(pa,nβ)≠dist(nβ,pa), then the edge is directed, and therefore the safe exit point is either pa or dl+. If dl+ lies on the edge [pa,nβ], then dl+ is the safe exit point. Otherwise, pa is the safe exit point.Algorithm 3:COSK: monitoring algorithm.
( 1 )  Input: Same as Algorithm 1 ( 2 )  Output: P S E: a set of safe exit points ( 3 )  P S E ← ∅/∗set of safe exit points (4)Dpa+←EvaluateSnapshotQuery(pa,(pa,nβ)) (5)/∗Results calculated using Algorithm 1 (6)Dnβ+←EvaluateSnapshotQuery((nβ,(pa,nβ))) (7)/∗Results calculated using Algorithm 1 (8)ifDpa+=Dnβ+then (9)no safe exit point /∗refer to Observation 1 (10)end (11)ifDpa+≠Dnβ+then (12)PSE←PSE∪ComputeSafeExit(pa,nβ)/∗safe exit point exist - refer to Observation 2 (13)end (14)return PSEAlgorithm 4:ComputeSafeExit(pa,nβ).
( 1 )  Input: same as Algorithm 1 ( 2 )  Output: se: safe exit point in (pa,nβ) ( 3 )  D l + ←   < p , D l + > | for each point p∈[pa,nβ], dl+ such that ψ ( d l + ) p = m i n ( ψ ( d 1 + ) p , ψ ( d 2 + ) p , … , ψ ( d | d + | + ) p (4)Dh-←<p,Dh->| for each point p∈[pa,nβ], dh- such that ψ ( d h - ) p = m a x ( ψ ( d 1 - ) p , ψ ( d 2 - ) p , … , ψ ( d | d - | - ) p (5)if  Case1  then (6)ifdist(pa,nβ)=dist(nβ,pa)then (7)pse= m a x ( d i s t ( s e , d 1 + ) , d i s t ( s e , d 2 + ) , … , d i s t ( s e , d | d + | + ) ) = m i n ( d i s t ( s e , d 1 - ) , d i s t ( s e , d 2 - ) , … , d i s t ( s e , d | d - | - ) ) (8)end (9)ifdist(pa,nβ)≠dist(nβ,pa)then (10)pse=pa or pse=dl+ where dl+∈(pa,nβ) (11)end (12)end (13)if  Case2  then (14)ifdist(pa,nβ)=dist(nβ,pa)then (15)pse=closest point to pa such that ψ(dh-)>ψ(dl+) (16)end (17)ifdist(pa,nβ)≠dist(nβ,pa)then (18)Same as Line (10) (19)end (20)end (21)return pseSimilarly, for Case2, if dist(pa,nβ)=dist(nβ,pa), then the safe exit point is computed by dividing the search space by half until we find the closest point such that ψ(dh-)>ψ(dl+). The safe exit point is computed in the same way as in Case 2 if dist(pa,nβ)≠dist(nβ,pa).


## 5.2. Computation of Safe Exit Points for Example

Consider the same example in Figure1, where the query pointq issues a top-1 keyword query withq.t “Italian restaurant.” For this example, let us consider α=1. The monitoring algorithm starts exploring from the active edge containing the query objectq. Therefore, (q,n3)→ is explored first. As shown in Table 3, for (q,n3)→, Dq+=d3 and Dn3+=d3. According to Observation 1, no safe exit point exists in this segment. Therefore, edges adjacent to n3 are explored, and n3 becomes the new pa. The edge (n3,n4)¯ is explored next. Similarly, the answer object at n3 and n4 is the same: Dn3+=Dn4+=d3. Therefore, a safe exit point does not exist in (n3,n4)¯. The edge (n3,n7)¯ is explored next. As shown in Table 3, Dn3+=d3 and Dn7+=d6. By Observation 2, there is a safe exit point in (n3,n7)¯. As shown in Figure 1, d3.t=d6.t=“ItalianRestaurant” and dist(n3,n7)=dist(n7,n3). Therefore, according to Case 1, the safe exit point s1 is the midpoint between d3 and d6. That is, dist(pse1,d3)=dist(pse1,d6), where dist(pse1,d3)=x+3 and dist(pse1,d6)=-x+5 for 0<x<3. Consequently, x=1, which means that the distance from n3 to pse1 is 1.Table 3
Computation of safe exit points for example scenario.
Edge/Segment pa Dpa+ Dnβ+ pse (q,n3)→ q D q + = d 3 D n 3 + = d 3 none (n3,n4)¯ q D n 3 + = d 3 D n 4 + = d 3 none (n3,n7)¯ n 3 D n 3 + = d 3 D n 7 + = d 6 p s e 1 (n3,n5)→ n 3 D n 3 + = d 3 D n 5 + = d 3 none (n6,n5)← n 5 D n 5 + = d 3 D n 6 + = d 4 pse2Next, we determine a safe exit point in(n3,n5)¯. As shown in Table 3, the answer object at n5 is also the same as n3. Hence, no safe exit point exists in this edge. Next, (n6,n5)← is explored with pa=n5. According to Table 3, Dn7+=d4 and Dn5+=d3. Therefore, a safe exit point exists in this edge. This edge is directed, and for each point p∈(n6,n5)←, the shortest distance fromp to d3 is from p→n6→n2→n3→d3. Therefore, n5 is the safe exit point.The bold lines in Figure5 indicate the safe region ofq. The top-1 result remains d3 until the queryq lies in the safe region.Figure 5
Illustration of safe region ofq.Next, we analyze the time complexity for determining a set of safe exit points using a set of qualifying objectsd∈Dpa+∪Dnβ+∪D(pa,nβ¯). Note that Dpa+(Dnβ+) indicates the set ofk data objects that satisfies the query condition at pa(nβ). According to Dijkstras algorithm [26], the time complexity O(Dq+) for computing a set of answer objects at a query pointq is O(Dq+)=O(E+Nlog⁡N). This means that O(Dpa+)=O(Dnβ+)=O(E+Nlog⁡N) holds for endpoints pa and nβ. Thus, time complexity O(Ωkth) when determining the skyline Ωkth with the k-th highest score is O(Ωkth)=Ckth.O(|Dpa+∪Dnβ+∪D(pa,nβ¯)|) where Ckth is the number of qualifying objects that participate in the constitution of the skyline with the k-th highest score. Therefore, the time complexity of determining a safe exit point coincides with the time complexity of determining the two skylines, i.e., the skyline Dl+ with the k-th highest (or lowest) score for answer objects and the skyline Dh- with the highest score for nonanswer objects. This is because the safe exit point is found at the cross point between these skylines.Figure6, represents the skyline graph for k=1 in an edge (n7,n3)¯. Let us draw the score function for d3 and d6 for the road segment (n7,n3)¯ where a safe exit point exists. This is because D(n3)+=d3 and D(n7)+=d6 for k=1. For each point p∈(n7,n3)¯, the distance between d3 and pointp can be represented as dist(d3,p)=dist(d3,n3)+len(n3,p)=6-len(n7,p). Similarly, for each point p∈(n7,n3)¯, the distance between d6 and pointp can be represented as dist(d6,p)=dist(d6,n7)+len(n7,p)=2+len(n7,p). Let, len(n7,p) be a variablex(0≤x≤3). We can write λ(d3,p)=dist(d3,p)=6-x and λ(d6,p)=dist(d6,p)=2+x. Then, we can represent score function ψ(d3) and ψ(d6) as follows:ψ(d3)=μ(d3.t,q.t)/1+α·λ(d3,p)=1/(7-x) for (0≤x≤3)ψ(d6)=μ(d6.t,q.t)/1+α·λ(d6,p)=1/(3+x) for (0≤x≤3)Figure 6
Skyline graph fork=1 on the road segment (n7,n3)¯.Finally, we present the lemma to prove that safe exit points computed by COSK are correct.Lemma 8.
The COSK algorithm correctly computes a set of safe exit points.Proof.
We will prove the correctness of the COSK algorithm by contradiction. We assume that ifDpa+≠Dnβ+, there is no safe exit point in a road segment (panβ¯). This means that, for each pointp in the road segment (panβ¯), the query result atp equals Dpa+, i.e., Dp+=Dpa+∀p∈(panβ¯). However, it leads to a contradiction that Dnβ+=Dpa+ when p=nβ. Therefore, if Dpa+≠Dnβ+, a safe exit point exists in (panβ¯). In addition, a safe exit point is determined using the skyline Dl+ for answer objects and the skyline Dh- with the highest score for nonanswer objects when Dpa+≠Dnβ+. The first skyline is a composite polyline drawn from answer objects in Dpa+. The second skyline is a composite polyline drawn from nonanswer objects in Dnβ+∪D(pa,nβ¯)-Dpa+.


## 6. Monitoring Query Results and Safe Regions in Dynamic Directed Road Networks

In this section, we discuss the monitoring of spatial keyword queries in dynamic road networks where the network distance changes depending on the traffic conditions. The updates on weight of some edges may invalidate the query results or safe region ofq, even though the query objectq remains within their respective safe region. Figure 7 illustrates an example of changing the weights edges (n1,n2)← and (n1,n6)←. For convenience we consider α=1 andq.t = “Italian restaurant.” In Figure 7(a), the top-1 result is d1 and bold lines show the safe region of queryq. Now consider at time tj the weights of two edges (n1,n2)← and (n1,n6)← changed due to heavy traffic condition as shown in Figure 7(b). The update in weight of edges may invalidate the query result or safe region ofq. Therefore, it is necessary to monitor the validity of results and safe region when the changes occur.Figure 7
Updating the weight of edges in a dynamic road network, whereti<tj.
(a)
Safe region at timeti (b)
Updating weight of(n1,n2)← and (n1,n6)← at time tjNext, we introduce a monitoring region to monitor the validity of the safe region effectively when the weight of an edge is changed. Monitoring regionMR contains all the points between query pointq and lowest answer object and highest nonanswer object. Formally, it is defined as MR=dist(q,Dl+)∪dist(q,Dh-), where dist(q,Dl+) is the distance betweenq and lowest answer object and dist(q,Dh-) is highest nonanswer object. In given example, the Dl+=d1 and Dh-={d2,d3}. Therefore, the dotted lines in Figure 8(a) shows the monitoring region of query objectq.Figure 8
Monitoring region and updated safe region at timetj.
(a)
Monitoring region at timeti (b)
New safe region at timetjNow at timetj, the update to edges (n1,n6)← and (n1,d1)← which is not part of monitoring region can safely be ignored. However, the updated on segment (n2,d1)→ which is associated with monitoring region may nullify the results. As shown in Figure 8(b), after update the top-1 result becomes d2 and bold lines represents the new safe region ofq.Algorithm5 monitors the validity of result set and safe region of query objectq when the weight of any edge changes. Let us consider weight of edge (ni,nj)¯ changes at time tj. First, algorithm checks whether edge (ni,nj)¯ is associated with monitoring region or not. If it is not part of monitoring region then algorithm simply ignores the update in edge (ni,nj)¯ and query results and safe region remains valid. In contrast, if edge is associated with monitoring region (i.e., MR∩(ni,nj)¯≠∅) then algorithm evaluates the query results. Consequently, the top-k results and safe region of queryq needs to be updated. Finally, the algorithm updates the monitoring region ofq.Algorithm 5:MonitoringSafeRegion(MR,(ni,nj)¯).
( 1 )  Input: Monitoring region: MR, updated edge: (ni,nj)¯ ( 2 )  Output: none ( 3 )  if M R ∩ ( n i , n j ) ¯ = ∅ then (4)/∗edge (ni,nj)¯ is not part of monitoring region (5)ignore the change in the weight of edge (ni,nj)¯ (6)end (7)PSE←∅ /∗set of safe exit points (8)else (9)Dkupd←EvaluateSnapshotQuery(ni,ei) /∗update set of top-k results (10)PSEupd←ComputeSafeExit(Pa,nβ) /∗update safe exit points (11)MRupd←ComputeMonitoringRegion(Dl+,Dh-) /∗update monitoring region (12)end


## 7. Performance Evaluation

In this section, we evaluate the performance of COSK through simulation experiments. We describe our experimental settings in Section7.1, and we present our experimental results for static and dynamic road networks in Sections 7.2 and 7.3, respectively.


### 7.1. Experimental Settings

All of our experiments were performed using real road networks, namely, Oldenburg, San Francisco, and San Joaquin. All three road networks were obtained from [27]. The original road network of San Francisco had 21,047 nodes and 21,692 edges. We reformatted the network, pruned approximately 30% of the nodes, and adjusted the edges and their weights accordingly. This resulted in a network with 14,732 nodes and 14,316 edges. Both the direction of edges and data objects on the edges were generated randomly. The description of each data object was extracted from Twitter messages [28], and we assigned one tweet per data object. Table 4 presents the characteristics of the data sets used in the experimental evaluation. We simulated moving query objects by using a spatiotemporal data generator [29]. The input to generator was the road network of the data set used, and the output was the set of query objects moving on the road network. Each experiment had 100 moving queries which were continuously monitored for 100 timestamps (1 timestamp = 1 second), and the average result was reported in the experiments.Table 4
Summary of datasets.
Attribute Oldenburg San Francisco San Joaquin Total no. of nodes 6104 14732 18262 Total no. of edges 7034 14316 23876 Percentage of directed edges 30% 30% 30% Total no. of objects 5627 11453 19098 Average no. of objects per edge 0.8 0.8 0.8 Total no. of words 49517 103649 166153As a benchmark for COSK in static road network, we implemented a CMTkSK+ algorithm [22] which also continuously monitored the moving top-k spatial keyword queries in the road networks. However, this algorithm was originally designed for undirected road networks. To make a fair comparison, we modified CMTkSK+ to process top-k spatial keyword queries in directed road networks and called it CMTkSK+. Specifically, we modified the distance computation method between two points such that in directed road networks, dist(p1,p2)≠dist(p2,p1). Since CMTkSK+ does not handle top-k spatial queries in dynamic road roads, we compared the performance of COSK with basic algorithm which recomputes the results whenever query object changes its location. All algorithms were implemented in Java and were executed on a desktop PC 2.80-GHz Intel Core i5 with 8 GB of memory. In the experiments, we compared (1) query processing times; (2) edges processed, i.e., the number of edges processed for retrieving query results; and (3) index sizes. Table 5 summarizes the parameters used in the experiments. In each experiment, we varied a single parameter within the range that is shown in Table 5 while maintaining the other parameters at the bolded default values.Table 5
Experimental parameter settings.
Parameter Range Number of results (k) 5, 10,15, 20, 25 Number of keywords (n) 1, 2,3, 4, 5 Query parameter (α) 0.01, 0.1,1, 10, 100 Dataset Oldenburg,San Francisco, San Joaquin Number of data objects (ND) 10, 20,30, 40, 50 (x1000) Speed of query objects (Vqry) 25, 50,75, 100, 125 (km/h) Mobility (Mqry) 20,40, 60, 80, 100 Ratio of directed edges (Edir) 10,20, 30, 40, 50 Ratio of updated edges (Eupd) 15, 30, 60, 80, 100We evaluated the performance of the algorithms by using the following measures:(1) total amount of server CPU time, which indicates the query processing time, and (2) total communication cost as the total number of points (i.e., the location updates sent by query objects, and the query results and safe exit points returned by the server) transferred between clients and the server. The battery power and wireless bandwidth consumption typically increase with the amount of data transferred between objects (clients) and servers. Thus, we used the amount of transferred data as a metric to evaluate the communication cost.


### 7.2. Experimental Results of Top-k Spatial Keyword Queries in Static Road Networks

#### 7.2.1. Effect of k

Figure9 indicates the effect of the number of results on the query processing time and communication cost for both algorithms. Figure 9(a) indicates that the query processing time increases for both algorithms as the value ofk increases. This is expected because with an increase ink, more data objects are required to be explored and verified. Nevertheless, COSK significantly outperforms CMTkSK+ for two main reasons. First, a relevant object search is very efficient when using the highest significant factor; and second, COSK does not need to verify the set of answer objects as long as the query object lies in a safe region. On the other hand, the CMTkSK+ query processing time increases significantly because it has to monitor and verify the set of candidate objects periodically. In Figure 9(b), the communication costs for both algorithms increase as the number of objects increases. However, the proposed algorithm demonstrates superior performance compared to CMTkSK+ because client-server communication is not required when the query object lies within the safe exit points, whereas in CMTkSK+, the query object is required to report its location to the server whenever it moves.Figure 9
Effect ofk on query processing time and number of edges processed.
(a)
Query  processing time (b)
Communication cost


#### 7.2.2. Effect ofND

This experiment was conducted on dataset San Joaquin. This dataset included 19,098 data objects; therefore, we randomly generated approximately 30,000 additional data objects on different edges. In Figure10, we evaluate the performance of COSK and CMTkSK+ by varying the cardinality of the data objects. Note that ND=10K corresponds to a low density of data points, while ND=50K corresponds to a high density. In Figure 10(a), it is interesting to notice that the query processing times of both algorithms decrease as the cardinality of the data objects increases. For CMTkSK+, this is because with high density, the monitoring range of a query decreases. However, for COSK, it is mainly because when the data density is high, fewer edges are required to be expanded, which decreases the query processing time. In Figure 10(b), we study the influence of the cardinality of the data objects on the communication costs. The experimental results indicate that the communication costs of CMTkSK+ incur almost constant communication costs regardless of data object cardinality. However, the communication costs of COSK increase in proportion to the ND value. This is expected because the safe region becomes smaller as the density of the data objects increases, which increases the communication costs.Figure 10
Effect ofND on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


#### 7.2.3. Effect of Query Keywords (n)

Figure11 shows the query processing time and communication for COSK and CMTkSK+ as a function of the number of query keywords. Figures 11(a) and 11(b) show the trend that the performance of both algorithms degrades when the number of keywords increases. This is mainly because by increasing the number of query keywords, the number of relevant objects may also increase, resulting in a higher query processing time and communication cost. However, the safe-region-based algorithm COSK scales better than CMTkSk+ because of its less expensive monitoring technique.Figure 11
Effect of number of keywords on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


#### 7.2.4. Effect ofα

Figure12 demonstrates the impact of query parameter α on the query processing time and on the communication cost. A small value of α indicates a greater importance of textual relevance, whereas a high value of α gives more preference to the spatial relevance. It is interesting to note that the query processing time is lower for higher values of α, which indicates more importance to the spatial relevance. This is mainly because when the spatial relevance is higher, fewer edges and objects are required to be explored and processed to determine the top-k data objects. Observe that in Figure 12(b), the number of messages sent by COSK decreases sharply with an increase in α.Figure 12
Effect ofα on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


#### 7.2.5. Effect of Speed

Figure13(a) demonstrates the influence of the speed of the query objects on the query processing time of the COSK and CMTkSK+ algorithms. The experimental results indicate that the performance of CMTkSK+ is not significantly influenced by the speed of the query objects because the candidate objects must be continuously monitored after a regular interval of time, regardless of the speed. On the other hand, for COSK, the performance gradually decreases as the speed of the query objects increases because the objects leave their respective safe regions more frequently. Figure 13(b) shows the communication costs of COSK and CMTkSK+ with respect to the speed of the query objects. CMTkSK+ incurs almost constant communication costs because a server-initiated request to verify the candidate objects does not depend on the speed. For COSK, the query objects cross safe regions more frequently when the speed is high, which increases the communication costs.Figure 13
Effect of speed on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


#### 7.2.6. Effect of Mobility

Figure14 shows the effect of mobility Mqry (mobility refers to the percentage of query objects that are moving at any timestamp) on the performance of COSK and CMTkSK+ algorithms. As expected, the query processing time and communication costs for both algorithms increase with Mqry. Nevertheless, COSK performs better than CMTkSK+ in terms of query processing time and communication costs.Figure 14
Effect of mobility on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


#### 7.2.7. Effect of Directed Edges

Figure15 shows the impact of percentage of directed edges Edir on the performance of COSK and CMTkSK+ algorithms. The query processing time increases with Edir because algorithm needs to explore more edges to retrieve the top-k keyword queries. However, the communication cost is not significantly affected by the value of Edir for both the algorithms.Figure 15
Effect ofEdir on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


#### 7.2.8. Effect of Datasets

Figure16 demonstrates the index sizes of the COSK and CMTkSK+ approaches for different datasets. As shown in Figure 16, both algorithms have similar index sizes. However, COSK has minor space overhead because it stores additional information of the highest significance factor θt of edges. More important, this space overhead is minimal as compared to the gain achieved by COSK in query processing time and communication costs.Figure 16
Effect of dataset on index size.


### 7.3. Experimental Results of Top-k Spatial Keyword Queries in Dynamic Road Networks

In this section, we evaluate the performance of COSK and basic algorithm for dynamic road networks. TheEupd indicates the percentage of all edges that change their weight at each timestamp. The length of an updated edge is randomly selected between 0.1 to 10 times the original length. Figure 17(a) depicts the query processing time of COSK and basic algorithm. It is evident from the figure that query processing time of basic algorithm is not significantly affected by Eupd. This is mainly because the query objects issue top-k spatial queries at each timestamp. However, query processing time of COSK increases with the value of Eupd because the probability that the updated edge may associated with the monitoring region of queryq increases with Eupd. Therefore, when Eupd becomes large the results need to be frequently updated which increases the query processing time. Figure 17(b) shows the communication costs of COSK and basic algorithm with respect to Eupd. Basic algorithm incurs almost constant communication costs regardless of the value of Eupd. In contrast, the communication cost of COSK increases with Eupd because the query result and safe regions needs to be frequently updated.Figure 17
Effect ofEupd on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.1. Experimental Settings

All of our experiments were performed using real road networks, namely, Oldenburg, San Francisco, and San Joaquin. All three road networks were obtained from [27]. The original road network of San Francisco had 21,047 nodes and 21,692 edges. We reformatted the network, pruned approximately 30% of the nodes, and adjusted the edges and their weights accordingly. This resulted in a network with 14,732 nodes and 14,316 edges. Both the direction of edges and data objects on the edges were generated randomly. The description of each data object was extracted from Twitter messages [28], and we assigned one tweet per data object. Table 4 presents the characteristics of the data sets used in the experimental evaluation. We simulated moving query objects by using a spatiotemporal data generator [29]. The input to generator was the road network of the data set used, and the output was the set of query objects moving on the road network. Each experiment had 100 moving queries which were continuously monitored for 100 timestamps (1 timestamp = 1 second), and the average result was reported in the experiments.Table 4
Summary of datasets.
Attribute Oldenburg San Francisco San Joaquin Total no. of nodes 6104 14732 18262 Total no. of edges 7034 14316 23876 Percentage of directed edges 30% 30% 30% Total no. of objects 5627 11453 19098 Average no. of objects per edge 0.8 0.8 0.8 Total no. of words 49517 103649 166153As a benchmark for COSK in static road network, we implemented a CMTkSK+ algorithm [22] which also continuously monitored the moving top-k spatial keyword queries in the road networks. However, this algorithm was originally designed for undirected road networks. To make a fair comparison, we modified CMTkSK+ to process top-k spatial keyword queries in directed road networks and called it CMTkSK+. Specifically, we modified the distance computation method between two points such that in directed road networks, dist(p1,p2)≠dist(p2,p1). Since CMTkSK+ does not handle top-k spatial queries in dynamic road roads, we compared the performance of COSK with basic algorithm which recomputes the results whenever query object changes its location. All algorithms were implemented in Java and were executed on a desktop PC 2.80-GHz Intel Core i5 with 8 GB of memory. In the experiments, we compared (1) query processing times; (2) edges processed, i.e., the number of edges processed for retrieving query results; and (3) index sizes. Table 5 summarizes the parameters used in the experiments. In each experiment, we varied a single parameter within the range that is shown in Table 5 while maintaining the other parameters at the bolded default values.Table 5
Experimental parameter settings.
Parameter Range Number of results (k) 5, 10,15, 20, 25 Number of keywords (n) 1, 2,3, 4, 5 Query parameter (α) 0.01, 0.1,1, 10, 100 Dataset Oldenburg,San Francisco, San Joaquin Number of data objects (ND) 10, 20,30, 40, 50 (x1000) Speed of query objects (Vqry) 25, 50,75, 100, 125 (km/h) Mobility (Mqry) 20,40, 60, 80, 100 Ratio of directed edges (Edir) 10,20, 30, 40, 50 Ratio of updated edges (Eupd) 15, 30, 60, 80, 100We evaluated the performance of the algorithms by using the following measures:(1) total amount of server CPU time, which indicates the query processing time, and (2) total communication cost as the total number of points (i.e., the location updates sent by query objects, and the query results and safe exit points returned by the server) transferred between clients and the server. The battery power and wireless bandwidth consumption typically increase with the amount of data transferred between objects (clients) and servers. Thus, we used the amount of transferred data as a metric to evaluate the communication cost.


## 7.2. Experimental Results of Top-k Spatial Keyword Queries in Static Road Networks

### 7.2.1. Effect of k

Figure9 indicates the effect of the number of results on the query processing time and communication cost for both algorithms. Figure 9(a) indicates that the query processing time increases for both algorithms as the value ofk increases. This is expected because with an increase ink, more data objects are required to be explored and verified. Nevertheless, COSK significantly outperforms CMTkSK+ for two main reasons. First, a relevant object search is very efficient when using the highest significant factor; and second, COSK does not need to verify the set of answer objects as long as the query object lies in a safe region. On the other hand, the CMTkSK+ query processing time increases significantly because it has to monitor and verify the set of candidate objects periodically. In Figure 9(b), the communication costs for both algorithms increase as the number of objects increases. However, the proposed algorithm demonstrates superior performance compared to CMTkSK+ because client-server communication is not required when the query object lies within the safe exit points, whereas in CMTkSK+, the query object is required to report its location to the server whenever it moves.Figure 9
Effect ofk on query processing time and number of edges processed.
(a)
Query  processing time (b)
Communication cost


### 7.2.2. Effect ofND

This experiment was conducted on dataset San Joaquin. This dataset included 19,098 data objects; therefore, we randomly generated approximately 30,000 additional data objects on different edges. In Figure10, we evaluate the performance of COSK and CMTkSK+ by varying the cardinality of the data objects. Note that ND=10K corresponds to a low density of data points, while ND=50K corresponds to a high density. In Figure 10(a), it is interesting to notice that the query processing times of both algorithms decrease as the cardinality of the data objects increases. For CMTkSK+, this is because with high density, the monitoring range of a query decreases. However, for COSK, it is mainly because when the data density is high, fewer edges are required to be expanded, which decreases the query processing time. In Figure 10(b), we study the influence of the cardinality of the data objects on the communication costs. The experimental results indicate that the communication costs of CMTkSK+ incur almost constant communication costs regardless of data object cardinality. However, the communication costs of COSK increase in proportion to the ND value. This is expected because the safe region becomes smaller as the density of the data objects increases, which increases the communication costs.Figure 10
Effect ofND on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


### 7.2.3. Effect of Query Keywords (n)

Figure11 shows the query processing time and communication for COSK and CMTkSK+ as a function of the number of query keywords. Figures 11(a) and 11(b) show the trend that the performance of both algorithms degrades when the number of keywords increases. This is mainly because by increasing the number of query keywords, the number of relevant objects may also increase, resulting in a higher query processing time and communication cost. However, the safe-region-based algorithm COSK scales better than CMTkSk+ because of its less expensive monitoring technique.Figure 11
Effect of number of keywords on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


### 7.2.4. Effect ofα

Figure12 demonstrates the impact of query parameter α on the query processing time and on the communication cost. A small value of α indicates a greater importance of textual relevance, whereas a high value of α gives more preference to the spatial relevance. It is interesting to note that the query processing time is lower for higher values of α, which indicates more importance to the spatial relevance. This is mainly because when the spatial relevance is higher, fewer edges and objects are required to be explored and processed to determine the top-k data objects. Observe that in Figure 12(b), the number of messages sent by COSK decreases sharply with an increase in α.Figure 12
Effect ofα on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


### 7.2.5. Effect of Speed

Figure13(a) demonstrates the influence of the speed of the query objects on the query processing time of the COSK and CMTkSK+ algorithms. The experimental results indicate that the performance of CMTkSK+ is not significantly influenced by the speed of the query objects because the candidate objects must be continuously monitored after a regular interval of time, regardless of the speed. On the other hand, for COSK, the performance gradually decreases as the speed of the query objects increases because the objects leave their respective safe regions more frequently. Figure 13(b) shows the communication costs of COSK and CMTkSK+ with respect to the speed of the query objects. CMTkSK+ incurs almost constant communication costs because a server-initiated request to verify the candidate objects does not depend on the speed. For COSK, the query objects cross safe regions more frequently when the speed is high, which increases the communication costs.Figure 13
Effect of speed on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


### 7.2.6. Effect of Mobility

Figure14 shows the effect of mobility Mqry (mobility refers to the percentage of query objects that are moving at any timestamp) on the performance of COSK and CMTkSK+ algorithms. As expected, the query processing time and communication costs for both algorithms increase with Mqry. Nevertheless, COSK performs better than CMTkSK+ in terms of query processing time and communication costs.Figure 14
Effect of mobility on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


### 7.2.7. Effect of Directed Edges

Figure15 shows the impact of percentage of directed edges Edir on the performance of COSK and CMTkSK+ algorithms. The query processing time increases with Edir because algorithm needs to explore more edges to retrieve the top-k keyword queries. However, the communication cost is not significantly affected by the value of Edir for both the algorithms.Figure 15
Effect ofEdir on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


### 7.2.8. Effect of Datasets

Figure16 demonstrates the index sizes of the COSK and CMTkSK+ approaches for different datasets. As shown in Figure 16, both algorithms have similar index sizes. However, COSK has minor space overhead because it stores additional information of the highest significance factor θt of edges. More important, this space overhead is minimal as compared to the gain achieved by COSK in query processing time and communication costs.Figure 16
Effect of dataset on index size.


## 7.2.1. Effect of k

Figure9 indicates the effect of the number of results on the query processing time and communication cost for both algorithms. Figure 9(a) indicates that the query processing time increases for both algorithms as the value ofk increases. This is expected because with an increase ink, more data objects are required to be explored and verified. Nevertheless, COSK significantly outperforms CMTkSK+ for two main reasons. First, a relevant object search is very efficient when using the highest significant factor; and second, COSK does not need to verify the set of answer objects as long as the query object lies in a safe region. On the other hand, the CMTkSK+ query processing time increases significantly because it has to monitor and verify the set of candidate objects periodically. In Figure 9(b), the communication costs for both algorithms increase as the number of objects increases. However, the proposed algorithm demonstrates superior performance compared to CMTkSK+ because client-server communication is not required when the query object lies within the safe exit points, whereas in CMTkSK+, the query object is required to report its location to the server whenever it moves.Figure 9
Effect ofk on query processing time and number of edges processed.
(a)
Query  processing time (b)
Communication cost


## 7.2.2. Effect ofND

This experiment was conducted on dataset San Joaquin. This dataset included 19,098 data objects; therefore, we randomly generated approximately 30,000 additional data objects on different edges. In Figure10, we evaluate the performance of COSK and CMTkSK+ by varying the cardinality of the data objects. Note that ND=10K corresponds to a low density of data points, while ND=50K corresponds to a high density. In Figure 10(a), it is interesting to notice that the query processing times of both algorithms decrease as the cardinality of the data objects increases. For CMTkSK+, this is because with high density, the monitoring range of a query decreases. However, for COSK, it is mainly because when the data density is high, fewer edges are required to be expanded, which decreases the query processing time. In Figure 10(b), we study the influence of the cardinality of the data objects on the communication costs. The experimental results indicate that the communication costs of CMTkSK+ incur almost constant communication costs regardless of data object cardinality. However, the communication costs of COSK increase in proportion to the ND value. This is expected because the safe region becomes smaller as the density of the data objects increases, which increases the communication costs.Figure 10
Effect ofND on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.2.3. Effect of Query Keywords (n)

Figure11 shows the query processing time and communication for COSK and CMTkSK+ as a function of the number of query keywords. Figures 11(a) and 11(b) show the trend that the performance of both algorithms degrades when the number of keywords increases. This is mainly because by increasing the number of query keywords, the number of relevant objects may also increase, resulting in a higher query processing time and communication cost. However, the safe-region-based algorithm COSK scales better than CMTkSk+ because of its less expensive monitoring technique.Figure 11
Effect of number of keywords on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.2.4. Effect ofα

Figure12 demonstrates the impact of query parameter α on the query processing time and on the communication cost. A small value of α indicates a greater importance of textual relevance, whereas a high value of α gives more preference to the spatial relevance. It is interesting to note that the query processing time is lower for higher values of α, which indicates more importance to the spatial relevance. This is mainly because when the spatial relevance is higher, fewer edges and objects are required to be explored and processed to determine the top-k data objects. Observe that in Figure 12(b), the number of messages sent by COSK decreases sharply with an increase in α.Figure 12
Effect ofα on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.2.5. Effect of Speed

Figure13(a) demonstrates the influence of the speed of the query objects on the query processing time of the COSK and CMTkSK+ algorithms. The experimental results indicate that the performance of CMTkSK+ is not significantly influenced by the speed of the query objects because the candidate objects must be continuously monitored after a regular interval of time, regardless of the speed. On the other hand, for COSK, the performance gradually decreases as the speed of the query objects increases because the objects leave their respective safe regions more frequently. Figure 13(b) shows the communication costs of COSK and CMTkSK+ with respect to the speed of the query objects. CMTkSK+ incurs almost constant communication costs because a server-initiated request to verify the candidate objects does not depend on the speed. For COSK, the query objects cross safe regions more frequently when the speed is high, which increases the communication costs.Figure 13
Effect of speed on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.2.6. Effect of Mobility

Figure14 shows the effect of mobility Mqry (mobility refers to the percentage of query objects that are moving at any timestamp) on the performance of COSK and CMTkSK+ algorithms. As expected, the query processing time and communication costs for both algorithms increase with Mqry. Nevertheless, COSK performs better than CMTkSK+ in terms of query processing time and communication costs.Figure 14
Effect of mobility on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.2.7. Effect of Directed Edges

Figure15 shows the impact of percentage of directed edges Edir on the performance of COSK and CMTkSK+ algorithms. The query processing time increases with Edir because algorithm needs to explore more edges to retrieve the top-k keyword queries. However, the communication cost is not significantly affected by the value of Edir for both the algorithms.Figure 15
Effect ofEdir on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 7.2.8. Effect of Datasets

Figure16 demonstrates the index sizes of the COSK and CMTkSK+ approaches for different datasets. As shown in Figure 16, both algorithms have similar index sizes. However, COSK has minor space overhead because it stores additional information of the highest significance factor θt of edges. More important, this space overhead is minimal as compared to the gain achieved by COSK in query processing time and communication costs.Figure 16
Effect of dataset on index size.


## 7.3. Experimental Results of Top-k Spatial Keyword Queries in Dynamic Road Networks

In this section, we evaluate the performance of COSK and basic algorithm for dynamic road networks. TheEupd indicates the percentage of all edges that change their weight at each timestamp. The length of an updated edge is randomly selected between 0.1 to 10 times the original length. Figure 17(a) depicts the query processing time of COSK and basic algorithm. It is evident from the figure that query processing time of basic algorithm is not significantly affected by Eupd. This is mainly because the query objects issue top-k spatial queries at each timestamp. However, query processing time of COSK increases with the value of Eupd because the probability that the updated edge may associated with the monitoring region of queryq increases with Eupd. Therefore, when Eupd becomes large the results need to be frequently updated which increases the query processing time. Figure 17(b) shows the communication costs of COSK and basic algorithm with respect to Eupd. Basic algorithm incurs almost constant communication costs regardless of the value of Eupd. In contrast, the communication cost of COSK increases with Eupd because the query result and safe regions needs to be frequently updated.Figure 17
Effect ofEupd on query processing time and communication cost.
(a)
Query  processing time (b)
Communication cost


## 8. Conclusion

In this paper, we investigated moving top-k spatial keyword queries in directed and dynamic road networks. We presented an efficient indexing framework using inverted files that indexes the data objects on edges, allowing for the effective searching of data objects relevant to queries in terms of both textual and spatial relevance. We also presented a safe-exit-based algorithm called COSK to monitor moving top-k spatial keyword queries. We demonstrated that the query results remain valid as long as the query object resides within a safe region. Furthermore, COSK can effectively monitor the validity of query results and safe regions in dynamic road networks. Finally, an experimental evaluation conducted on real road networks demonstrated that COSK significantly reduced the query processing time and communication costs compared to the CMTkSK+ algorithm.



---

*Source: 7373286-2018-11-01.xml*