Nowadays, spatial data are ubiquitous in various fields of science, such as transportation and smart city management. A recent research direction in analyzing spatial data is to provide means for “exploratory analysis” of such data where users are guided towards interesting options in consecutive analysis iterations. Typically, the guidance component learns user's preferences using his/her explicit feedback, e.g., picking a spatial point of interest (POI) or selecting a region of interest. However, it is often the case that users forget or don't feel necessary to explicitly express their feedback in what they find interesting. Our approach captures implicit feedback on spatial data. The approach consists of observing mouse moves (as a means of user's interaction) to discover interesting spatial regions with dense mouse hovers. In this paper, we define, formalize, and explore Interesting Dense Regions (IDRs) which capture preferences of users, in order to automatically find interesting spatial highlights. Our approach involves a polygon-based abstraction layer for capturing preferences. Using these IDRs, we highlight POIs to guide users in the analysis process. We discuss the eficiency and efectiveness of our approach through realistic examples and experiments on Airbnb and Yelp datasets.
Nowadays, there has been a meteoric rise in the generation of
spatial datasets in various fields of science, such as
transportation, lodging services, and smart city management [
Spatial data are often voluminous. Hence the focus in the
literature of spatial data analysis is on “eficiency”, i.e., enabling fluid
means of navigation in spatial data to facilitate the exploratory
analysis. The common approach is to design pre-computed
indexes which enable eficient retrieval of spatial data (e.g., [
Feedback is often expressed explicitly, i.e., the user clicks on
a POI and mentions if he/she likes or dislikes the POI [
He decides to rent a home-stay from Airbnb website4. He likes to discover the city, hence he is open to any type of lodging in any region with an interest to stay in the center of Paris. The website returns 1500 diferent locations. As he has no other preferences, an exhaustive investigation needs scanning each location independently, which is nearly infeasible. While he is scanning the very first options, he shows interest in the region of Trocadero by hovering his mouse around the Eifel tower and checking the amenities within that region. However, he forgets or doesn’t feel necessary to click a POI (i.e., a home-stay) in that region. An ideal system should capture this implicit feedback in order to short-list a small subset of locations that Benício should consider as high priority.
The above example shows in practice that implicit feedback capturing is crucial in the context of spatial data analysis, as a POI can easily remain out of sight and be missed. It is particularly the case in small-screen devices such as smart watches, smartphones, and tablets.
In this paper, we present a simple yet efective approach whose
aim is to capture and analyze implicit feedback of users in spatial
data analysis. Without loss of generality, we focus on “mouse
moves” as the implicit feedback received from the user. Mouse
moves are the most common way that users interact with
geographical maps to collect information within a region of
interest [
Contributions. In this paper, we make the following contributions: • We define and explore the notion of “implicit user feedback” which enables a seamless navigation in spatial data. • We define the notion of “information highlighting”, a mechanism to highlight out-of-sight important information for users. A clear distinction of our proposal with the literature is that it doesn’t aim for pruning (such as top-k recommendation), but leveraging the actual data with potential interesting results (i.e., highlights). • We define and formalize the concept of Interesting Dense Regions (IDRs), a polygon-based approach to explore and highlight spatial data. • We propose an eficient greedy approach to compute highlights on-the-fly. • We show the efectiveness of our approach through a set of qualitative experiments.
The outline of the paper is the following. Section 2 describes our data model. In Section 3, we formally define our problem. Then in Section 4, we present our solution and its algorithmic details. Section 5 reports our experiments on the framework. We review the related work in Section 6. We present some limitations of our work in Section 7. Last, we conclude in Section 8.
We consider two diferent layers on a geographical map: “spatial layer” and “interaction layer”. The spatial layer contains POIs from a spatial database P. The interaction layer contains mouse move points M.
Spatial layer. Each POI p ∈ P is described using its coordinates, latitude and longitude, i.e., p = ⟨lat, lon⟩. Note that in this work, we don’t consider “time” for POIs, as our contribution focuses on their location. POIs are also associated to a set of domain-specific attributes A. For instance, for a dataset of a real estate agency, POIs are properties (houses and apartments) and A contains attributes such as “surface”, “number of rooms” and “price”. The set of all possible values for an attribute a ∈ A is denoted as dom(a). We also define user’s feedback F as a vector over all attribute values (i.e., facets), i.e., F = −∪−a−−∈−A−−d−o−m−−(→a). The vector F is initialized by zeros and will be updated to express user’s preferences. Interaction layer. Whenever the user moves his/her mouse, a new point m is appended to the set M. Each mouse move point is described using the pixel position that it touches and the clock time of the move. Hence each mouse move point is a tuple m = ⟨x, y, t ⟩, where x and y specifies the pixel location and t is a Unix Epoch time. To conform with geographical standards, we assume m = ⟨0, 0⟩ sits at the middle of the interaction layer, both horizontally and vertically.
The user is in contact with the interaction layer. To update the feedback vector F , we need to translate pixel locations in the interaction layer to latitudes and longitudes in the spatial layer. We employ equirectangular projection to obtain the best possible approximation of a point m = ⟨x, y, t ⟩ ∈ M in the spatial layer, denoted as p(m). x p(m = ⟨x, y, t ⟩) = ⟨lat = y + γ , lon = + θ ⟩ (1) cosγ
The inverse operation, i.e., transforming a point p = ⟨lat, lon⟩ from the spatial layer to the interaction is done using Equation 2. m(p = ⟨lat, lon⟩) = ⟨x = (lon − θ ) × cosγ , y = lat − γ ⟩ (2)
The reference point for the transformation is the center of both layers. In Equations 1 and 2, we assume that γ is the latitude and θ is the longitude of a point in the spatial layer corresponding to the center of the interaction layer, i.e., m = ⟨0, 0⟩. 3
When analyzing spatial data, users require to obtain only a few options (so-called “highlights”) to focus on. These options should be in-line with what they have already appreciated. In this paper, we formulate the problem of “information highlighting using implicit feedback”, i.e., highlight a few POIs based on implicit interests of the user in order to guide him/her towards what he/she should concentrate on in consecutive iterations of the analysis process. We formally define our problem as follows.
feedback vector F using points m ∈ M where m.t ≤ tc , and choose k POIs Pk ⊆ P as “highlights” where Pk satisfies two following constraints. (i) ∀p ∈ Pk , similarity(p, F ) is maximized. (ii) diversity(Pk ) is maximized.
The first constraint guarantees that returned highlights are highly similar with user’s interests captured in F . The second Algorithm 1: Spatial Highlighting Algorithm
Input: Current time tc , mouse move points M
Output: Highlights Pk 1 S ← find _interesting_dense_regions(tc , M) // Section 4.1 2 Ps ← match_points(S, P) // Section 4.2 3 F ← update_feedback_vector(F , Ps ) // Section 4.3 4 Pk ← get_highlights(P, F ) // Section 4.4
constraint ensures that k POIs cover diferent regions and they don’t repeat themselves. While our approach is independent from the way that similarity and diversity functions are formulated, we provide a formal definition of these functions in Section 4.
The aforementioned problem is hard to solve due to the following challenges.
Challenge 1. First, it is not clear how mouse move points influence the feedback vector. Mouse moves occur on a separate layer and there should be some meaningful transformations to interpret mouse moves as potential changes in the feedback vector. Challenge 2. Analyzing all generated mouse moves is challenging and may introduce false positives. A typical mouse with 1600 DPI (Dots Per Inch) touches 630 pixels for one centimeter of move. Hence a mouse move from the bottom to the top of a typical 13-inch screen would yield 14,427 points which may not be necessarily meaningful.
Challenge 3. Beyond the two first challenges, finding the most
similar and diverse POIs with F needs an exhaustive scan of
all POIs in P which is prohibitively expensive: in most spatial
datasets, there exist millions of POIs. Moreover, we need to follow
bi-objective optimization considerations as we aim to optimize
both similarity and diversity at the same time [
We recognize the complexity of our problem using the aforementioned challenges. In Section 4, we discuss a solution for the discussed problem and its associated challenges. 4
Our approach exploits user’s implicit feedback (i.e., mouse moves) to highlight a few interesting POIs as future analysis directions. Algorithm 1 summarizes the principled steps of our approach.
The algorithm begins by mining the set of mouse move points M in the interaction layer to discover one or several Interesting Dense Regions, abbr., IDRs, in which most user’s interactions occur (line 1). Then it matches the POIs P with IDRs using Equation 2 in order to find POIs inside each region (line 2). The attributes of resulting POIs will be exploited to update the user’s feedback vector F (line 3). The updated vector F will then be used to find k highlights (line 4). These steps ensure that the final highlights reflect user’s implicit interests. We detail each step as follows (Sections 4.1 to 4.4). 4.1
The objective of this step is to obtain one or several regions in which the user has expressed his/her implicit feedback. There are two observations for such regions.
Observation 1. We conjecture that a region is more interesting for the user if it is denser, i.e., the user moves his/her mouse in that region several times, to collect information from the background map.
Algorithm 2: Find Interesting Dense Regions (IDRs) Input: Current time tc , mouse move points M
Output: IDRs S 1 S ← ∅ 2 д ←number of time segments 3 for i ∈ [1, д] do 4 Mi ← {m = ⟨x, y, t ⟩|( tдc × i) ≤ t ≤ ( tдc × (i + 1))} 5 6 7 end
Ci ← mine_clusters(Mi )
Oi ← find _ploygons(Ci ) 8 for Oi , Oj where i, j ∈ [0, д] and i ̸= j do
S.append(intersect(Oi , Oj ))
Observation 2. It is possible that the user moves his/her mouse everywhere in the map. This should not signify that all those locations have the same significance.
Following our observations, we propose Algorithm 2 for
mining IDRs. We add points to M only every 200ms to prevent adding
redundant points (i.e., Challenge 2). Following Observation 1 and
in order to mine the recurring behavior of the user, the algorithm
begins by partitioning the set M into д fixed-length consecutive
segments M1 to Mд . The first segment starts at time zero (where
the system started), and the last segment ends at tc , i.e., the
current time. Following Observation 2, we then find dense clusters
in each segment of M using a variant of DB-SCAN approach [
For clustering points in each time segment (i.e., line 5 of
Algorithm 2), we use ST-DBSCAN [
Once clusters are obtained for all subsets of M, we find their
intersections to locate recurring regions (line 6). To obtain
intersections, we need to clearly define the spatial boundaries of each
cluster. Hence for each cluster, we discover its corresponding
polygon that covers the points inside. For this aim, we employ
Quickhull algorithm, a quicksort-style method which computes
the convex hull for a given set of points in a 2D plane [
We describe the process of finding IDRs in an example. Figure 1 shows the steps that Benício follows in our running example to explore home-stays in Paris. Figure 1.A shows mouse moves of Benício in diferent time stages. In this example, we consider д = 3 and capture Benício’s feedback in three diferent time segments (progressing from Figures 1.B to 1.D). It shows that Benício started his search around Eifel Tower and Arc de Triomphe (Figure 1.B) and gradually showed interest in south (Figure 1.C) and north (Figure 1.D) as well. All intersections between those clusters are discovered (hatching regions in Figure 1.E) which will constitute the set of IDRs (Figure 1.F), i.e., IDR1 to IDR4.
A D 1 2
Being a function of mouse move points, IDRs are discovered in the interaction layer. We then need to find out which POIs in P fall into IDRs, hence forming the subset Ps . We employ Equation 2 to transform those POIs from the spatial layer to the interaction layer. Then a simple “spatial containment” function can verify which POIs fit into the IDRs. Given a POI p and an IDR r , a function contains(p, r ) returns “true” if p is inside r , otherwise “false”. In our case, we simply use the implementation of ST _Within(p, r ) module in PostGIS5, i.e., our underlying spatial DBMS which hosts the data.
In the vanilla version of our spatial containment function, all
POIs should be checked against all IDRs. Obviously, this depletes
the execution time. To prevent the exhaustive scan, we employ
Quadtrees [
We follow our running example and illustrate the matching process in Figure 2. In the Airbnb dataset, POIs are home-stays which are shown with their nightly price on the map. We observe that there exist many matching POIs with IDR3 and absolutely no matching POI for IDR2. For IDR4, although there exist many home-stays below the region, we never check their containment, as they belong to a Quadtree cell which doesn’t intersect with the IDR. 4.3
The set of matching POIs Ps (line 2 of Algorithm 1) depicts the implicit preference of the user. We keep track of this preference
in a feedback vector F . The vector is initialized by zero, i.e., the
user has no preference at the beginning. We update F using the
attributes of the POIs in Ps . We enable transparency by choosing
F ’s schema to be defined on the POI attributes. In exploratory
analysis scenarios, it is often the case that users do not trust in
what they get from the system (i.e., algorithmic anxiety [
We consider an increment value δ to update F . If p ∈ Ps gets v1 for attribute a1, we augment the value in the F ’s cell of ⟨a1, v1⟩ by δ . Note that we only consider incremental feedback, i.e., we never decrease a value in F .
We explain the process of updating the feedback vector using a toy example. Given the four matched POIs in IDR1 (Figure 2) with prices 130e, 58e, 92e and 67e, we want to update the vector F given those POIs. A few attributes of these POIs are mentioned in Table 1. In practice, there are often more than 50 attributes for POIs. The cells of F are illustrated in the first column of Table 2. As three POIs get the value “1” for the attribute “#Beds”, then the value in cell ⟨#Beds,1⟩ is augmented three times by δ . The same process is repeated for all attribute-values of POIs in Ps . Note that all cells of F are not necessarily touched in the feedback update process. For instance, in the above example, 5 cells out of 12 remain unchanged.
By specifying an increment value, we can materialize the updates and normalize the vector using a Softmax function. Given δ = 1.0, the normalized values of the F vector is illustrated in the third column of Table 2. Higher values of δ increase the influence of feedbacks.
The normalized content of the vector F captures the implicit preferences of the user. For instance, the content of F after applying POIs in IDR1 shows that the user has a high interest in having a balcony in his/her home-stay, as his/her score for the cell ⟨Balcony,Yes⟩ is 0.25, i.e., the highest among other cells. This reflects the fact that all POIs in IDR1 has balcony. It is important to note that although we only consider positive feedback, the Softmax function lowers the values of untouched cells once other cells get rewarded. The updated feedback vector is fully transparent and the user can easily comprehend what has been learned from his/her previous actions. 4.4
The ultimate goal is to highlight k POIs to guide users in analyzing their spatial data. The updated feedback vector F is the input to the highlighting phase. We assume that POIs in IDRs are already investigated by the user. Hence our search space for highlighting is P \ Ps . We seek two properties in k highlights: similarity and diversity. First, the highlights should be in the same direction of the user’s implicit feedback, hence similar to the vector F . The similarity between a POI p ∈ P and the vector F is defined as follows.
similarity(p, F ) = avga ∈A (sim(p, F, a)) (3)
The sim() function can be any function such as Jaccard or Cosine. Each attribute can have its own similarity function (as string and integer attributes are compared diferently.) Then sim() works as an overriding-function which provides encapsulated similarity computations for any type of attribute.
Second, highlighted POIs should also represent distinct directions so that the user can observe diferent aspects of data and decide based on the big picture. Given a set of POIs Pk = {p1, p2 . . . pk } ⊆ P, we consider a pair-wise definition of diversity as follows.
diversity(Pk ) = avg {p,p′ } ⊂ Pk |p̸=p′ distance(p, p′) (4)
The function distance(p, p′) operates on geographical coordinates of p and p′ and can be considered as any distance function of Minkowski distance family. However, as distance computations are done in the spherical space, a natural choice is to employ Haversine distance.
To solve our bi-objective problem (i.e., maximizing
similarity and diversity), we employ the ϵ-constraint method [
In order to speed up the similarity computation in the online execution, we pre-compute an inverted index for each single POI p ∈ P in the ofline step (as is commonly done in the Web search). Each index Lp for the POI p keeps all other POIs in P in decreasing order of their similarity with p. While index computation may be extremely time-consuming, we stop generating those lists if the similarity value is lower than the ϵ threshold.
The first step of Algorithm 3 is to find the most similar POI to F , so-called p∗. The POI p∗ is the closest possible approximation of F in order to exploit pre-computed similarities. The algorithm makes sequential accesses to Lp∗ (i.e., the inverted index of the POI p∗) to greedily maximize diversity. Algorithm 3 does not sacrifice eficiency in price of value. We consider a time limit parameter which determines when the algorithm should stop seeking maximized diversity. Scanning inverted indexes guarantees the similarity maximization even if time limit is chosen to be very restrictive. Our observations with several spatial datasets show that we achieve the diversity of more than 0.9 with time limit set to 200ms.
In line 2 of Algorithm 3, Pk is initialized with the k highest ranking POIs in Lp∗ . Function get_next(Lp∗ ) (line 3) returns the next POI pnext in Lp∗ in sequential order. Lines 4 to 12 iterate over the inverted indexes to determine if other POIs should be considered to increase diversity while staying within the time limit.
The algorithm looks for a candidate POI pcurrent ∈ Pk to replace in order to increase diversity. The boolean function diversity_improved() (line 6) checks if by replacing pcurrent by Algorithm 3: Get k similar and diverse highlights get_highlights() Input: POIs P, Feedback vector F , k, time_limit
Output: Pk 1 p∗ ← max_sim_to(P, F ) 2 Pk ← top_k(Lp∗, k) 3 pnex t ← дet _next (Lp∗ ) 4 while time_limit not exceeded ∨ pnex t = ∅ do 5 6 7 for pcur r ent ∈ Pk do if diversity_improved(Pk , pnex t , pcur r ent ) then
Pk ← replace(Pk , pnex t , pcur r ent ) break 8 9 10 11 12 end 13 return Pk
end end pnex t ← дet _next (Lp∗ ) pnext in Pk , the overall diversity of the new Pk increases. It is important to highlight that for each run of the algorithm, we only focus on one specific inverted list associated to the input POI. Algorithm 3 verifies the similarity and diversity of each POI with all other POIs, and then processes the normalization. 5
We discuss two sets of experiments. The first set is on the usefulness of our approach. Then we focus more on IDR discovery and present some statistics and insights on the functionality of our approach. The experiments are done on a 2.8 GHz Intel Core i5 machine running a Mac OS operating system. 5.1
First of, we validate the usefulness of our approach. For this aim, we design a user study with 30 participants who are all students of Computer Science. Given an exploratory task to fulfill, we hypothesize that there are three prominent factors which influence the usefulness of our system: user expertise, type of the task, and starting point. To examine the user expertise, we recruited 15 “novice” participants who don’t know the location under investigation, and also 15 “experts.” We also define two diferent types of tasks on the Airbnb dataset of Paris with 1,000 POIs: T1: “finding a POI in a requested location” (e.g., find a home-stay in the “Champ de Mars” area), and T2: “finding a POI with a requested profile” (e.g., find a cheap home-stay.) Last, the participants may have diferent starting points, i.e., they may begin their navigation from a POI which is either I1: “geographically close to the goal” or I2: “far from the goal”. For each participant, we report a variant of time-to-insight measure, i.e., how long (in seconds) the participants interact with the tool before fulfilling the task. Evidently, less number of interactions are preferred as it means that the participant can reach insights faster.
The participants perform the tasks T 1 and T 2 on two diferent tools: Airbnb website (without information highlighting and without incorporation of implicit feedbacks, as our baseline) and our highlighting tool. Table 3 shows the results. Our initial observation is that the highlights enable users to fulfill tasks one order of magnitude faster than the baseline without the highlights. This shows that the highlighting approach with implicit feedback capturing is an efective mechanism which helps users to reach their goals in a reasonable time. Also expert participants need on average 6.25 seconds less time than the novice participants when using the highlights. Interestingly, starting POIs, i.e., I1 and I2, do not have a huge impact on the number of steps. It is potentially due to the diversity component which provides distinct options and can quickly steer users towards their region of interest. We also observe that the task T1 is an easier task than T2, as on average it took less time to be accomplished. This is potentially due to where the user can request options similar to what he/she has already observed and greedily move to his/her preferred regions. In the second part of our experiments, we analyze the efectiveness of our approach in generating IDRs for information highlighting. We employ two diferent datasets, i.e., Airbnb and Yelp6. We pick a similar subset from both datasets, i.e., home-stays and restaurants in Paris, respectively. We consider four diferent sizes of those datasets, i.e., 100, 1000, 2000 and 4000 POIs, respectively. For each size of the datasets, we manually perform 20 sessions, and then present some statistics as the average of the sessions. We limit each session to 2 minutes where we seek for interesting POIs in the datasets. We capture the following information in each session: • The number of regions created from the mouse moves during the session; • The number of generated IDRs (intersection of regions); • The number of POIs from the dataset presented in each IDR; • The coverage of POIs (in the dataset) with IDRs collectively.
Tables 4 and 5 show the results for Airbnb and Yelp, respectively. In Table 4, we observe that the number of regions decreases when the number of POIs increases. On average, 7.7 regions are constructed per session. The average number of POIs presented in IDRs is 25.97, which shows that our approach highlights at least 8.05% of POIs from the dataset, on average. We notice an outlier in the experiment with 2000 POIs in Table 4. This happened due the fact that the user concentrated in a very small area generating a smaller number of IDRs, and consequently a smaller number of POIs.
More uniform results are observed in Table 5, i.e., for Yelp dataset vis-à-vis Airbnb. The average number of generated regions reaches 12.75 per session. Also, the number of regions decreases by increasing the number of POIs. The number of POIs presented in IDRs is on average 108.65 and it represents on average 13.11% of POIs highlighted from the dataset. 6
To the best of our knowledge, the problem of spatial information highlighting using implicit feedback has not been addressed before in the literature. However, our work relates to a few others in their semantics.
Information Highlighting. The literature contains a few
instances of information highlighting approaches [
Online recommendation approaches can also be considered as
an information highlighting approach where recommended items
count as highlights. Most recommendation algorithms are
spaceagnostic and do not take into account the spatial information.
While a few approaches focus on the spatial dimension [
Feedback Capturing. Several approaches are proposed in the
state of the art for capturing diferent forms of feedback [
Few works formulate fusing approaches of explicit and
implicit feedbacks to better capture user preferences [
Region Discovery. Our approach finds interesting dense
regions (IDRs) in order to derive user’s implicit preferences. There
exist several approaches to infer a spatial region for a given set
of POIs [
In this paper, we presented a solution for highlighting out-ofsight information using a polygon-based approach for capturing implicit feedbacks. To the best of our knowledge, our work is the ifrst efort towards formalizing and implementing information highlighting using implicit feedback. However, we consider our work as an on-going efort where we envision to address some limitations in the future, such as “customizability”, “performance”, “cold start”, and “quantitative experiments”.
Custom maps and feedbacks. One limitation is about the “customizable” use of geographical maps as an interaction means. As we only consider static maps, we plan to work on translations and rotations as a future work. We also consider adapting other types of feedback enablers such as gaze tracking and touch gestures as a direction of future work. Our research will investigate potential challenges which may arise when employing those feedback enablers.
Mobility. Our current focus is only on POIs, and hence trajectories and areas of mobility are not incorporated directly. While trajectories and areas can be broken into a subset of POIs (and hence be easily fed to our approach), we envision to enrich our model in a way that those mobility elements are considered as ifrst-class citizens.
Cold start. Our problem bears similarities with recommendation
algorithms where the quality of the output may be influenced
by scarce availability of input. This problem is referred to as the
cold start problem [
Performance. Another limitation is the medium-size datasets
to be processed. Our algorithm processes similarity and diversity
in an O(n2) complexity. Also Quickhull [
In this paper, we present an approach to explore Interesting Dense Regions (IDRs) using implicit feedback in order to detect user latent preferences. The implicit feedbacks are captured from mouse moves of users over the geographical map while analyzing spatial data. We formalize a novel polygon-based mining algorithm which returns a few highlights in-line with user’s implicit preferences. The highlights enable users to focus on what matters the most and prevent information overload.
We consider various future directions for this work, including
the limitations of our current approach which we listed in
Section 7. First, we are interested to incorporate an “explainability”
component which can describe causalities behind preferences.
For instance, we are interested to find seasonal patterns to see
why the preferences of users change from place to place during
various seasons of the year. Another direction is to incorporate
“Query by Visualization” approaches, where users can specify
their intents alongside their implicit preferences, directly on the
map [