The goal of collective spatial keyword queries is to retrieve, from a spatial database, a group of spatial items such that the description of the items included in that set (typically based on the use of
• Retrieval tasks and goals → Recommender systems.
Recommender systems (RS) have been studied for several decades,
aiming to facilitate item selection as part of the user’s
decisionmaking processes [
The idea of Collective Spatial Keyword Querying (CoSKQ)
emerged some years ago as a promising technique to query spatial
databases containing information about items and their location [
We believe that exploiting spatial keyword querying as a basis to build recommender systems is an interesting research avenue to explore. Therefore, combining both fields of research, in this position paper we present the idea of Re-CoSKQ, a recommender system that uses CoSKQ to provide a set of items that semantically covers the keywords of a query (even if they do not match perfectly) and minimizes the cost, in terms of the distance to get to them and the similarity between query keywords and item descriptions.
As a problem statement, let us consider a set U = {u1, ..., un } of users spending their time in a city as tourists. Let O = {o1, ..., om } be a set of POIs, i.e., spots with some kind of relevant attraction for visitors. Examples of POIs could be museums, monuments, parks, or buildings with some historical flavour, just to mention a few. Now, let oi .κ = {k1, ..., kj } be a set of keywords with which a POI oi ∈ O is described. These keywords can usually be retrieved in an automated way by using semantically-annotated resources. Moreover, every POI oi ∈ O is placed in a location denoted by oi .λ.
Re-CoSKQ uses collective spatial keyword querying in order to cope with the location of POIs and users and also with the similarity between the keywords in the user’s query and the description of the POIs. Let q = ⟨λ, κ⟩ be a user’s query, where q.λ represents the user’s location and q.κ stands for the query split in keywords (only relevant words for the search are taken into account). The main goal is to provide a method to return a set of items O′ ⊆ O which semantically covers the keywords in q.κ and also ensures that their cost, in terms of distance –between the POIs and the user who issued the query– and the similarity of terms, is minimal.
The next sections intend to shed some light into the problem and present the approach we have envisioned to deal with it. Specifically, the rest of the paper is structured as follows. First, Section 2 we revise the concept of CoSKQ. Then, in Section 3, we present the Re-CoSKQ approach. In Section 4, we sketch an evaluation proposal. Finally, in Section 5, we conclude with a summary and some future work. 2
As we have previously stated, CoSKQ attempts to find the solution
to the problem of retrieving a group of spatial objects that
collectively match the user preferences given specific locations (of the
user and also of the objects) and a set of keywords. The method is
designed to work with spatial databases, so it does much efort on
providing an eficient computation, in terms of the data structure
used and how data are accessed [
It uses the concept of IR-tree data structures [
CoSKQ presents diferent algorithmic solutions based on
minimizing a cost function. The chosen cost function may vary
depending on the authors of each specific proposal and the scenario
where it is applied. Diferent cost functions, taking into account
the distances between items and query locations, can be found in
[
We present Re-CoSKQ as an instantiation of the CoSKQ problem,
especially designed for recommendations in the tourism domain
(i.e., the user is a tourist and the items are points of interest that the
user may want to visit). The most common instantiation of CoSKQ
assumes that the set of keywords describing the POIs in the query
result must contain, at least, all the keywords contained in the
query [
Moreover, in this paper, we do not assume that q.κ can be fully covered. Actually, we claim that this assumption may derive in empty sets in many recommendation scenarios where queries are expressed, for instance, with diferent vocabularies, or where they cannot be easily solved with the given descriptions of POIs. Thus, we believe that it is important to provide query outcomes even when full keyword coverage is not possible. In order to do that, we propose to use a similarity function to calculate how similar the keywords in q.κ are compared to those in ∪o ∈O′ . For example, given q.κ = {outdoors, animals, kids }, if located nearby, one of the POIs included in the outcome could be a zoo, which could be described by a set of keywords {open-air, birds, snakes, mammals, f amily}. This object would never be returned using a classic CoSKQ approach, but considering the semantic similarity between keywords one can easily observe that the terms are related, since birds, snakes and mammals are types of animals, outdoors and open-air are synonyms and kids are part of families. We will present how to cope with this when presenting diferent cost functions.
Re-CoSKQ attempts to minimize the cost of finding an appropriate
set of POIs for a given query q. This cost is modelled as a function
that depends on distances between the query and the locations of
POIs as well as between the keywords. Diferent equations have
been proposed to model cost in the CoSKQ problem [
TYPE 1. A linear combination of the maximum distance between the query location and any POI in O′, the maximum pairwise distance between any two POIs in O′, and the maximum of the semantic distance between the query keywords (q.κ) and the set of (1) (2) (3) (4) cost (q, O′) = α · om∈aOx′ [dist (q .λ, o .λ)] + β · o1m,oa2∈xO′ [dist (o1, o2)] + ω · k1∈q .κ,km2a∈x∪o∈O′ o.κ [dist (k1, k2)] where α + β + ω = 1 are weights to denote the relevance of each of the three types of distances involved, which allow adding up distances which may have diferent ranges of values.
TYPE 2. This type of function defines cost as the maximum of the three factors in the TYPE 1 function; i.e., the highest value between the maximum distance among the query location and any POI in O′, the maximum pairwise distance between any two POIs in O′, and the maximum of the semantic distance between query keywords (q.κ) and the set of keywords in ∪o ∈O′o.κ. This is formally defined by Eq. 2, where again weights α , β and ω are used. cost (q, O′) = max α · om∈aOx′ [dist (q .λ, o .λ)] , β · o1m,oa2∈xO′ [dist (o1, o2)] , ω · k1∈q .κ,km2a∈x∪o∈O′ o.κ [dist (k1, k2)]
TYPE 3. This function uses a min-max approach, linearly combining the minimum distance between the query location and any POI with the maximum values for pairwise distance between any two POIs in O′ and the semantic distance between query keywords (q.κ) and the set of keywords in O′, i.e., ∪o ∈O′o.κ (see Eq. 3). cost (q, O′) = α · om∈iOn′ [dist (q .λ, o .λ)] + β · o1m,oa2∈xO′ [dist (o1, o2)] + ω · k1∈q .κ,km2a∈x∪o∈O′ o.κ [dist (k1, k2)] again with α + β + ω = 1.
TYPE 4. This is a unified cost function, adapted from [
ϕ2 + β · o1m,oa2∈xO′ dist (o1, o2) + ω ·
max k1∈q .κ,k2∈∪o∈O′ o.κ dist (k1, k2) ϕ2 # ϕ12 with α + β + ω = 1, ϕ1 ∈ {−∞, 1, ∞} and ϕ2 ∈ {1, ∞} . The ϕ1 and ϕ2 values stand for tuning parameters, allowing to describe the previous cost functions (types 1-3) by varying their values. For example, an instantiation with α, β, ω = 13 , ϕ1 = ∞ and ϕ2 = 1 results in a Type 1 cost function with the weights α , β , and ω indicated: cost (q, O′) = 13 max Õ (dist (q .λ, o .λ))+
o∈O′ +
max o1,o2∈O′ dist (o1, o2) +
max k1∈q .κ,k2∈∪o∈O′ o.κ dist (k1, k2)
As we have pointed out, there exist diferent distance functions needed to calculate the cost in Re-CoSKQ. Analyzing any of the proposed cost functions, we can observe that there are three diferent distance instantiations, as we explain in the following.
Location distance. (dist (q.λ, o.λ)) refers to the physical distance between the query location and a POI’s location. It can be calculated with diferent geometrical approaches. In the following, we point out some possible functions.
Euclidean distance. It is probably the most common distance function used in the literature for many diferent types of problems and domains. It is formally defined by Eq. 5: (5) We assume that the position of queries and POIs are given by a pair of coordinates ⟨lat, lonд⟩. This distance may work well when the routes between POIs are roughly calculated or the users can walk straight from any location to another.
L1-Norm. It is another well-known distance function, also known as Manhattan distance. It calculates the sum of the magnitudes of the vectors in a space, i.e., the sum of absolute diference of the components of the vectors (see Eq. 6).
n dist (q .λ, o .λ) = Õ |q .λi − o .λi | (6) i=1 We use 2-dimension spaces, denoted by location coordinates. This distance may be suitable for grid-based scenarios, e.g., POIs in a city connected by roads/paths, or halls in a museum linked by corridors.
Geodesic distance. It is the type of function we need if we use a graph to model how POIs and users are connected. The geodesic distance is defined as the shortest path between two vertices in a graph. This is useful when modeling a scenario with weighted edges, since some extra information can be added (e.g., about congested routes or crowded halls). Many algorithms can be used to calculate shortest paths in graphs (e.g., the Dijkstra’s algorithm).
POI-to-POI distance. (dist (o1, o2)) could also be called intraPOI distance, since it calculates the distance between two POIs. Note again that the location of o ∈ O′ is denoted by o.λ. As we assume a 2-dimension space in Re-CoSKQ, we can reduce the calculation of this distance to the problem of calculating the location distance. Thus, the same functions described above may apply to this case.
Term distance. (dist (k1, k2)) is the distance we use to calculate how similar two diferent keywords are. In this case, we compare the query keywords (q.κ) and the keywords in ∪o ∈O′ o.κ. In the cost function, we try to minimize the maximum distance between the q.κ set and o.κ in a pairwise basis. In order to calculate the similarity between keywords, we adhere to ontology-based measures, typically used in semantic web approaches. This type of measures usually calculates the similarity according to structured knowledge defined by an ontology. In the following, we propose some functions that we consider to be suitable for the Re-CoSKQ problem; once the similarity has been estimated, we should provide a way to calculate the distance associated to it, such as dist (k1, k2) = 1 − sim(k1, k2).
Similarity based on concept closeness. This measure takes into
account the closeness of the concepts in the hierarchical tree
representing the ontology. It is based on the relatedness property
presented in [
Similarity based on closeness and concept depth. This measure,
proposed in [
k1 , k2 ot her wise (7) where l is the shortest path between k1 and k2 and h is the depth of the least common subsumer of both concepts. Parameters α, β > 0 are weights to modulate the contribution of these factors.
Several algorithms address the problem of implementing CoSKQ.
CoSKQ is an NP-complete problem, so exact algorithms (e.g., the
linear programming approaches presented in [
Most works on CoSKQ focus their evaluation on measuring the
performance (in terms of running time) and approximation ratio.
Nevertheless, when applying this approach to recommender
systems we are not only interested in these issues, as the quality of
the recommendation is also key. An interesting problem is that
full coverage is assumed in classic CoSKQ; that is, ∪o ∈O′ o.κ is
assumed to contain, at least, all keywords in q.κ. This is not the
case of Re-CoSKQ, where the coverage is estimated by keyword
similarity. Moreover, the evaluation usually needs a ground truth to
compare with, in order to be able to calculate accuracy metrics such
as precision and recall. As far as we know, there is no dataset
annotated with this type of information. Thus, we propose to first define
a set of interesting and representative keyword queries and then
manually annotate a dataset containing POIs descriptions with the
keywords by assigning each POI to a set of predefined categories
(much smaller than the number of keywords) defined based on the
queries that have been selected for evaluation, in order to define a
dataset with information that can represent a suitable ground truth
to compare with. Precision and recall may be calculated by
comparing the retrieved POIs according to the categories specified by
the user in the query. Regarding the items, there are many datasets
that contain information about geographic locations and keyword
descriptions; a tailored synthetic dataset could also be generated
by using DataGenCARS [
The main idea in the empirical evaluation is to show the benefits of the proposal and test how diferent cost functions behave, tuning diferent parameters. We are also interested in the scalability of the proposal, so tests with diferent numbers of query keywords and POIs (as well as simultaneous queries/users) should be carried out. Moreover, in order to check the feasibility concerning the use of resources, we will use exact and approximate algorithms to test their performance (running time and approximation ratio).
In this position paper, we have presented the idea of Re-CoSKQ, a collective spatial keyword query approach for recommender systems, where keyword coverage is not assumed, by considering keyword similarity. We have tackled the problem as a minimization problem, for which we have defined some cost functions.
We are currently working on an empirical evaluation to test the approach and its benefits over other POI recommendation approaches. Furthermore, we would like to extend the approach to group recommendation; that is, diferent users in diferent locations will issue their queries and the opportunity of group visits (groups of people visiting the same items together) will be explored, so the problem becomes more complex, since O′ must contain suitable POIs that satisfy all users (or at least a set of them). We are also interested in dynamic environments where both the POIs and users could potentially be on the move and context conditions can change quickly over time. Finally, we also intend to consider other spatial distance calculation approaches, such as heuristic searches (e.g., by using A⋆ algorithms), as well as other approaches to compute term distances (e.g., a word embedding approach such as word2vec).
Work supported by the project TIN2016-78011-C4-3-R (AEI/FEDER, UE) and the Government of Aragon (Group Reference T35_17D, COSMOS group) and co-funded with Feder 2014-2020 “Construyendo Europa desde Aragon”.