Given a query location and a set of query keywords, a top-k spatial keyword query rank objects based on the distance to the query location and textual relevance to the query
With the popularization of geo-tagged data (e.g.,
geotagged 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 [
Top-k keyword queries can be used for a wide range of applications in recommendation systems and decision support systems. For example, a tourist may want to retrieve a sorted list of restaurants that serve Italian steak based on shortest distance from her location and textual relevance to the query keywords. Given a set of data objects D = d1; d2; :::; djDj, query location and set of keywords, the top-k spatial keyword query returns the best k data objects from D according to their combined textual and spatial relevance to query.
Figure 1 presents an example of a directed road network where rectangles represents the data objects with a textual description, and the triangle represent the query location. The number label on each edge indicates the distance between two adjacent objects e.g., dist(n1; d1) = 1 and dist(d1; n2) = 2. Consider a scenario where a tourist is interested in nding an \Italian restaurant". If an undirected road network is considered, the top-1 Italian restaurant is d6. However, in directed road network the shortest path from q to d6 is (q ! n3 ! n7 ! d6). Therefore, for directed road network, top-1 result is d3 because it is closer to query location than d6. Now consider tourist is looking for \Cafe bakery", the data object d7 may score better than d4 (Chinese Restaurant) d5 (Pub and Bar) n1 1
2 d1 (Grand Hotel) n2 d6 (Italian Restaurant) n6 1 n7 q 1 2 1 n5 1 3 2 d3 (Italian Restaurant)
1 n3 d2 (Cafe) 2
n4 d7 (Cafe and Bakery) the node set, edge set and edge distance matrix, respectively. Each edge is also assigned an orientation which is either undirected or directed. The undirected edge is represented by e = nsne where ns and ne are adjacent nodes, whereas directed edge represented as e = nsn!e or e = nens. Naturally, the arrow above the edge indicates associated direction. We refer ns as starting node and ne as ending node of edge. For example in Figure 1, n6 is starting node of edge n6n!2, whereas it is ending node for edge n6n5. The particular edge where query object is located is called the active edge.
Similar to previous studies [
Top-k spatial keywords in directed road networks are useful for location-based applications. However, the query processing is costly, because it requires computing several shortest paths while considering the orientation of road segments. To the best of our knowledge, this is the rst attempt to study top-k spatial keyword queries in directed road networks. In this paper, we propose a methodology to rank the data objects based on the spatial and textual relevance.
Below, we summarize our contributions: We propose an e cient indexing technique that indexes the data objects in inverted les for processing top-k spatial keyword queries in directed road networks.
We present an algorithm eSPAK that exploits the indexing framework to e ectively retrieve top-k results.
Finally, we conduct extensive experiments on a real road network and demonstrate the superiority of our proposed algorithm over baseline approach. 2.
Several approaches have been proposed for ranking
spatial data objects. Harihran et al. [
Top-k spatial keyword queries where data objects are ranked
according to their combined textual and spatial relevance to
keyword queries was rst studied by Cong et al. [
Top-k spatial keyword queries in road networks was
introduced by Rocha et al. [
Section 3.1 de nes the terms and notations that are 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
Road Network: A road network is represented by a weighted directed graph G = (N; E; W ) where N, E and W denote (1) (2) where (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 spatial relevance is considered then = 0, if more importance is given to textual relevance then > 1.
Spatial relevance ( ) is de ned as the shortest distance between data object d and q: (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 to q than data object dj . The textual relevance ( ) can be computed using any popular information retrieval model, such as cosine similarity or language model. In this study, we use the cosine similarity between d:t and q:t. The textual relevance is de ned as: (d:t; q:t) =
Pt2q:t wt(d:t):wt(q:t) qPt2p:t[wt(d:t)]2: Pt2q:t[wt(q:t)]2
Here, the weight wt(d:t) represents the frequency of term t in d:t, and the weight wt(q:t) describes the ratio of total number of data objects in D to the number of data objects that contains t in their description. Higher means, the higher textual relevance to query keywords. 4.
In this section, we present our proposed query processing system that indexes the data objects and prunes the irrelevant edges for e cient query processing. In Section 4.1, we discuss indexing framework and in Section 4.2, we present an e cient keyword query processing algorithm (eSPAK). 4.1
We implemented the inverted le for indexing data objects. The inverted le contains vocabulary and inverted lists. The vocabulary keeps general information about each term such as frequency of term which is helpful in computing the textual relevance of the data objects. The inverted list stores the data objects located on the edge nsn!e that have a term t in their description. An inverted list is identi ed by a key composed of (eid; tid), eid and tid represents edge id and term id, respectively. Each inverted le is a set of inverted lists. The separate inverted list is used for each term in the object description. Inverted list stores two attributes for each data object: rst, the distance between data object and starting node dist(ns; di); second, the signi cance factor (ti; di) of the term ti in the description of the data object. Note that the network distance between two points in directed road networks is not symmetrical (i.e, dist(ns; di) 6= dist(di; ns)). Recall that the starting node is chosen according to orientation of edge such that direction of edge is from node towards data object. In Figure 1, n3 is starting node for d7. For bi-directional edges any of the adjacent node can act as starting node.
Furthermore, we develop a pruning technique to prune the irrelevant edges. To achieve this, we introduce a highest signi cance factor ( t) of term t in the description of objects lying on the edge. The t on an edge is retrieved by a combination of eid and tid. The t is an upper-bound signi cance for an object on the edge with t. Naturally, the edges with t smaller than the score of the k-th object found so far are pruned.
The proposed indexing scheme has three main advantages. First, the object search relevant to query keywords is very e cient using the (eid; tid) pair. Second, inverted les also store the network distance between starting node and data object which helps in accessing the data object in the directed road network. Finally, the pruning technique allows faster query processing by exploring fewer edges. 4.2
eSPAK: Query Processing Algorithm
eSPAK traverses the road network incrementally in a
similar fashion to Dijkstra's algorithm [
The candsearch((eid; tid); sk) procedure nds the candidate data objects in two steps. In rst step, the upper-bound score of edges is computed using a signi cance factor ( t) of a term t 2 q:t and the shortest distance sdist(ei; q:l) between edge and the query location. In next step, the inverted lists of term t are fetched, if their upper-bound score is higher than sk. In inverted lists, the objects whose score (d) is greater than sk are returned.
In order to give a feel for our proposed algorithm, consider Algorithm 1: eSPAK: Query Processing Algorithm. 1 Input: Top-k spatial keyword query QN = (q:l; q:t; k) 2 Output: Top-k data objects with highest score 3 Dc ; /*set of candidate data objects 4 max-heap Dk ; /*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 while min-heap 6= ; or (equ) do 10 (pa; edge) min-heap.pop() 11 if (pa; edge) 2= explored then 12 explored explored [ (pa; edge) 13 Dc candsearch((eid; tid); sk) 14 update Dk and sk 15 end 16 else 17 min-heap.push(adjacent node, edge) 18 end 19 end 20 return Dk a road network presented in Figure 1. Assume, a query q generated a top-1 keyword query with q.d \Italian restaurant". For the ease of presentation, we assume = 1 and the textual relevance is the number of occurrence of query keywords in d:t divided by the number of keywords in the document. For example, the (d4) = 1+(d(4d:4t:;lq;:qt:)l) = 08:5 = 0:06. The algorithm starts the network expansion from active edge n2n!3 where q is the anchor point. Note that the direction of edge n2n!3 is from n2 to n3. Therefore, algorithm only explore qn!3. There is no data object found in qn!3. Then, n3 becomes anchor point and edges n3n!4, n3n5 and n3n!7 are inserted in min-heap. Next, candsearch function retrieves the candidate data objects on edges n3n!4, n2n3 and n3n!7 whose score is better than sk. On edge n3n5 data object d3 is retrieved with (d3) = 0:2. The data object d3 is inserted in Dk set and the value of sk is set to 0.2. For edge n3n!4 and n3n!7 there is no candidate object found because d2:t (\Cafe") and d7:t (\Cafe and Bakery") does not match with q:t. The algorithm continues expanding the edges whose upper-bound score is greater than sk. The edge n7n!2 is explored next, the upper-bound score of n7n!2 is 71 which is less than sk. Similarly, for edge n5n6 the upper-bound score is 0:5 < sk. Therefore, algorithm terminates reporting d3 as 8 top-1 result. 5.
In this section, we evaluate the performance of eSPAK through simulation experiments. We describe experiment settings in Section 5.1 and present experimental results in Section 5.2. 5.1
All of our experiments are performed using a real road
network [
Baseline eSPAK 0
Baseline eSPAK Baseline eSPAK 0 5 10 15 # of Results (K) 20 25 10K
20K 30K 40K # of Data Objects |D| 50K
The description of each data object is extracted from
twitter1 messages, we assigned one tweet per data object. As a
benchmark for eSPAK, we use a baseline method that
computes the score of every data object using the incremental
network expansion [
Figure 2 shows the query processing time for eSPAK and baseline as a function of the number k of requested data objects with the highest score. The query processing time of the baseline is nearly stable regardless of the k value because it always computes the score of each data object. However, the query processing time of eSPAK increases slightly with the k value. In Figure 3, we evaluate the performance of eSPAK and baseline by varying the cardinality of data objects. The query processing time of both the algorithms is sensitive towards an increase in jDj. However, eSPAK scales much better than baseline. Figure 4, demonstrates the impact of query parameter on query processing time. A small value of indicates more importance of textual relevance, whereas a high value of gives more preference to the spatial relevance. Experimental results reveal that does not indicate a signi cant impact on the query processing time of eSPAK and baseline. It is interesting to note that, both approaches performs better for higher values of , which indicates more importance to spatial relevance. This is mainly because, when spatial relevance is higher, fewer edges are required to explore to nd the top-k data objects.
In this paper, we investigate top-k spatial keyword queries in directed road networks. We presented an e cient indexing framework using inverted les, that indexes the data objects on edges which allows e ective searching of data objects relevant to query in term of both textual and spatial relevance. Furthermore, we present an algorithm for evaluating top-k spatial keyword queries. Finally, the experimental evaluation conducted on real road networks demonstrates that eSPAK drastically reduces the query processing time compared to baseline algorithm.
We thank anonymous reviewers for their valuable comments and suggestions. This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education(2016R1D1A1B03934129). Finally, this work was partially supported by Leaders Industry-University Cooperation Project. 8.