# AGN feedback duty cycle in Planck SZ selected clusters using Chandra
observations

V. Olivares1,Y. Su1, P. Nulsen2,3, R. Kraft2, T. Somboonpanyakul4, F. Andrade-
Santos2, C. Jones2, W. Forman2
1 Department of Physics and Astronomy, University of Kentucky, 505 Rose
Street, Lexington, KY 40506, USA
2 Harvard-Smithsonian Center for Astrophysics, 60 Garden St., Cambridge, MA
02138, USA
3 ICRAR, University of Western Australia, 35 Stirling Hwy, Crawley, WA 6009,
Australia
3 Kavli Institute for Particle Astrophysics & Cosmology, P.O. Box 2450,
Stanford University, Stanford, CA 94305, USA

(Accepted XXX. Received YYY; in original form ZZZ)

###### Abstract

We present a systematic study of X-ray cavities using archival Chandra
observations of nearby galaxy clusters selected by their Sunyaev-Zel’dovich
(SZ) signature in the Planck survey, which provides a nearly unbiased mass-
selected sample to explore the entire AGN feedback duty cycle. Based on X-ray
image analysis, we report that 30 of the 164 clusters show X-ray cavities,
which corresponds to a detection fraction of 18%. After correcting for spatial
resolution to match the high-$z$ SPT–SZ sample, the detection fraction
decreases to 9%, consistent with the high-z sample, hinting that the AGN
feedback has not evolved across almost 8 Gyrs. Our finding agrees with the
lack of evolution of cool-core clusters fraction. We calculate the cavity
power, $P_{\rm cav}$, and find that most systems of our sample have enough AGN
heating to offset the radiative losses of the intracluster medium.

###### keywords:

galaxies: clusters: general – intergalactic medium – X-rays: galaxies

††pubyear: 2022

##  1 Introduction

Feedback from active galactic nuclei (AGN) jets has been proposed to solve the
cooling flow problem (see Fabian 1994; McNamara et al. 2005, for a review).
Although the details of how AGN feedback counteracts the radiative losses of
the intracluster medium (ICM) in clusters are still not fully understood.
Early observations with the X-ray satellite ROSAT revealed surface brightness
deficits that appear to be spatially aligned with regions of radio emission in
the ICM of a few galaxy clusters (Boehringer et al., 1993; Carilli et al.,
1994). Nowadays, with the superb resolution of the X-ray Chandra observatory,
it has become clear that central AGN located in the Brightest Cluster Galaxy
(hereafter BCG) continuously interacts with the surrounding ICM, producing,
not solely, the X-ray surface brightness depressions known as X-ray cavities
(or bubbles), but also shocks and ripples (e.g., Fabian et al., 2006). In
addition, high-resolution radio observations by the Jansky Very Large Array
(JVLA) have shown that extended radio lobes inflated by the central AGN may
excavate these X-ray cavities by pushing aside the surrounding hot gas.
Accordingly, they are expected to be filled with radio emission (e.g., Bîrzan
et al., 2020). There have also been detections of the so-called “ghost
cavities” at low radio frequency, which are believed to trace a past AGN
outburst, for which the radio emission has faded away. More importantly, the
X-ray cavities and bubbles may provide a direct measurement of the work done
by the radio-mode feedback on the ICM (e.g., Gitti et al., 2010). The X-ray
cavities are not only supposed to carry enough energy to balance the cooling
losses of the X-ray emitting plasma (Bîrzan et al., 2008), but also play a key
role in the formation of extended multiphase filaments observed in cooling
flow clusters (e.g., Olivares et al., 2019, 2022; Russell et al., 2019).
Therefore, investigating the physical properties of X-ray cavities can improve
our understanding of AGN feedback and its impact on galaxy formation and
evolution.

Currently, most X-ray cavity studies of clusters, groups and elliptical
galaxies are based on Chandra X-ray observations for both individual systems
and dedicated surveys (see Bîrzan et al. 2004, 2008; Rafferty et al. 2006;
Nulsen et al. 2009; Dong et al. 2010; O’Sullivan et al. 2011; Hlavacek-
Larrondo et al. 2013; Shin et al. 2016; Panagoulia et al. 2014; Bîrzan et al.
2017). One of the main limitations of existing studies based on X-ray
selection methods is that they are often biased towards bright cool-core
systems and, consequently, against X-ray faint clusters. A complete unbiased
sample of galaxy clusters is desirable to obtain heating and cooling balance
constraints (Gitti et al., 2010), and to understand the duty cycle of AGN
feedback, which is estimated as the fraction of systems displaying bubbles
inflated by the central AGN.

Millimeter-wave surveys utilizing the SZ effect have the advantage of
providing nearly mass-limited samples, as the impact of SZ effect on the CMB
(cosmic microwave background) brightness temperature is independent of
redshift. This allows us to explore the entire AGN feedback duty cycle.
Examples of instruments used to undertake SZ surveys include the Planck
satellite (Planck Collaboration et al., 2011), the South Pole Telescope (SPT)
(Bleem et al., 2015, 2020), and the Atacama Cosmology Telescope (Hincks et
al., 2010; Hilton et al., 2018). For the high-$z$ Universe, Hlavacek-Larrondo
et al. (2015, hereafter HL15) performed a Chandra study of 83 clusters
selected from the SPT-SZ survey, and found X-ray surface brightness depression
in 6 clusters consistent with radio jets inflating X-ray cavities in their
ICM. Here, we present a study of X-ray cavities in the Planck SZ survey, which
provides a unique and unbiased view of AGN feedback in the nearby ($z<0.35$)
Universe and anchors the evolution of AGN feedback over the past 8 Gyrs.

This paper examines Chandra observations of 164 Planck SZ clusters with the
aim of identifying X-ray bubbles. In section 2 we describe the Planck SZ
sample. Section 3 presents the X-ray Chandra observations and describes the
methods used to identify X-ray surface brightness depressions. Section 4 is
devoted to the results and their implications. Section 5 presents the
limitations of the present study. Finally, section 6 summarizes our findings.

Throughout this paper, we adopted a standard cosmology with H0=70 km s-1 Mpc-1
and $\Omega_{\rm m}$=0.3.

##  2 Sample

The Chandra-Planck Legacy Program for Massive Clusters of Galaxies (Jones,
2012) is a deep X-ray survey of massive Planck clusters with redshift $\leq
0.35$ detected over almost the full sky (and $|$b$|>15\deg$) through the
Sunyaev-Zel’dovich effect by the first Planck mission released in early 2011
(Planck Collaboration et al., 2011). The observations are constructed by
combining the Chandra XVP (PI: Jones) and HRC Guaranteed Time Observations
(PI: Murray). At least 10,000 source counts have been collected for each
cluster to derive its gas properties out to $R_{\rm 500}$ (Andrade-Santos et
al., 2017, hereafter AS17). The Chandra Planck sample is nearly an unbiased,
mass-selected sample, covering the mass range $7\times 10^{13}{\rm
M}_{\odot}\leq M_{500}\leq 2\times 10^{15}{\rm M}_{\odot}$. The sample
consists of 164 clusters, of which a small fraction contain pronounced
substructures (35, subclusters), visually identified in the X-ray images
(AS17). Central density is the best known proxy for the central cooling time
(e.g., Su et al., 2020), and has been widely used to classify CC and NCC
clusters (e.g., Ruppin et al., 2021; Andrade-Santos et al., 2017). Based on
the central density classification of $n_{\rm core}=1.5\times$10-2 cm-3, as
presented in AS17, 63 clusters are classified as CC and 101 as NCC clusters.
Deprojected temperature and density profiles of clusters in this sample are
taken from AS17, to which we refer the reader for a detailed description.

##  3 Observation and Analysis

For each cluster, we used all available Chandra observations, including both
CCDs ACIS-I and ACIS-S. The data reduction and calibration of Chandra
observations were carried out using Chandra Interactive Analysis of
Observations software (CIAO) 4.12, and Chandra Calibration Database (CALDB)
4.9.2.1. The observations were reprocessed using the chandra_repro tool of
CIAO. Standard blank sky background files and readout artifacts were
subtracted. Point sources were detected in the 0.5-8.0 keV energy band, then
masked before performing the spectral and imagining analysis of the clusters.
Exposure corrected images were produced in the 0.5–2.0 keV band energy, and
used for the X-ray cavity analysis.

Unsharp masked images were produced to help identify X-ray cavities using CIAO
tool aconvolve. The original image was smoothed twice using a small- and
large-scale Gaussian kernel. The highly smoothed image was then subtracted
from the less smoothed image, enhancing the inhomogeneities in the residual
image. We tried different smoothing lengths for the more heavily smoothed
images based on the large scale of the cluster emission, starting on 10 up to
60 kpc. For the less smoothed images, we tried smoothing lengths comparable to
the physical size of a cavity, from 1 up to 20 kpc (e.g. Rafferty et al.,
2006). We also examined the residual image after subtracting an elliptical
double beta model, which was obtained by fitting a slightly smoothed 0.5–2.0
keV image. The second beta model is to account for excess emission from the
cool core.

We classified each cavity identified as Certain (C) or Potential (P). The
first two co-author independently looked for X-ray cavities and then
classified them based on the significance of each cavity.

Cavities were classified as certain if they appear as a clear visible
depression in the original image, but also the unsharp-masked image or double
$\beta$-subtracted image. In figure 1 we present an example of the methods
employed to identify cavities for a clusters with certain (C), potential (P),
and without cavities. A cavity was classified as potential if there was only a
hint of an X-ray depression in the original X-ray image, but visible in the
unsharp-masked or double $\beta$-model subtracted image. The number of counts
of the central region ($<$20 kpc) of the clusters with potential cavities is
too low for the cavities to be certain (see also Section 5). Clusters without
depressions were classified as lacking cavities. We also consider clusters
with dark annuli or rings created by bright excesses and asymmetries of the
cluster distribution as lacking cavities, as such surface brightness
depressions are not consistent with bubbles inflated by radio jets.

Figure 1: Example of the methods employed to look for X-ray cavities for a
cluster with Certain (top), Potential (middle) detected cavities, and without
(bottom) cavities. From left to right: 0.5-2.0 keV original image, double
$\beta$-subtracted image, and unsharp image. Detected cavities are displayed
with green ellipses.

Figure 2:  Left panel: Detection fraction of cavities as a function of
redshift. The detection fraction for the entire sample is shown with a green
square. The detection fraction corrected by resolution to match the SPT-SZ
sample is shown with a green circle. The SPT-SZ detection fraction is
displayed with an orange circle (HL15). The grey arrows correspond to the
detection fraction when only “certain” cavities are taken into account. Right
panel: Cavity size versus redshift color-coded by the number of counts within
the central 20 kpc. We have also included cavity measurements from the
high-$z$ SPT–SZ sample (HL15), shown with black symbols. Certain (C) cavities
are displayed with circles, whereas potential (P) cavities with square
symbols. The dashed black line corresponds to two times the size of the
Chandra PSF as a function of redshift. In both panels, the upper axis gives
the lookback times in Gyr.

##  4 Results and Discussion

###  4.1 Detection fraction of cavities and evolution

Overall, we detected 67 X-ray cavities in 30 clusters, of which 32 are
classified as certain (C) and 35 as potential (P) cavities. From the CC
cluster sub-sample, we find 29 clusters with cavities, of which 12 clusters
reveal mostly certain cavities and 17 potential cavities. The remaining 34 CC
clusters lack X-ray depressions. We also find in one NCC cluster,
G269.51+26.42, two potential cavities located in opposite sides of the cluster
center. The rest of the NCC clusters show no hint of X-ray depressions. We
find that most of the detected cavities come in pairs, and they are usually
located on opposite sides of the cluster core, as expected, considering that
X-ray cavities are believed to be inflated by radio jets. It is worth
mentioning that 29/30 of clusters with cavities also have radio emission
associated with the central source (Olivares et al. in prep). Some clusters
show multiple X-ray cavities, likely due to either multiple AGN outbursts or
the disintegration of large cavities, while five clusters have single cavities
(e.g., Morsony et al., 2010; Canning et al., 2013).

In total, 18% of all clusters in our sample, including both CC and NCC
clusters contain X-ray cavities (see Fig 2, left panel), a few times smaller
than the fractions found by previous studies of nearby clusters and about
twice as high as that of the high-$z$ SPT–SZ sample (7%–9%; HL15). We have
included uncertainties associated with the fraction of clusters with cavities
using the Wilson interval method (Brown et al., 2001). We note that previous
studies of nearby clusters tend to be biased towards X-ray bright clusters.
Furthermore, our findings suggest a slightly lower duty cycle of $\sim$46%, as
28 of the 63 CC clusters ($n_{\rm core}$>1.5$\times$10-2 cm-3) have detected
cavities (see Fig. 2, left panel), compared to previous studies which predict
AGN feedback duty cycle to be high (60–90%, Bîrzan et al. 2012; Fabian 2012;
Panagoulia et al. 2014). We stress, however, that different definitions have
been used to classify cool core clusters. At high-$z$, HL15 found a lower
limit of $\sim$11% on the duty cycle for the SPT-SZ sample, as only 6 of the
52 clusters with signs of cooling reveal cavities.

To explore the evolution of the detection fraction of cavities, we compare our
results with those found in the high-$z$ SPT-SZ sample (HL15). Bear in mind
that the SPT–SZ sample is limited by resolution (see Fig 2, right panel), with
the smaller cavities detected in this sample having sizes of $\lesssim$10 kpc.
The latter is due to a combination of larger Chandra PSF at high $z$ and lower
number of counts compared to low-$z$ clusters. To account for that limitation,
we compute the detection fraction taking only clusters with cavities sizes
larger than $\gtrsim$10 kpc to match the observing bias of the SPT–SZ sample.
That yields a detection fraction of 9%, which is in good agreement with the
SPT–SZ sample (HL15). In the same vein, if we consider only clusters with
“certain” (C) cavities and sizes $\gtrsim$10 kpc, the detection fraction of
the Planck sample drops to 3%, close to the 2% obtained in the high-$z$ SPT–SZ
sample when only clearly detected cavities are taken into account. These
findings suggest that the AGN feedback duty cycle has remained constant over
almost 8 Gyrs. This trend strongly agrees with the lack of evolution in the
fraction of cool-cores clusters (of $\sim$40–60% across the same redshift
range Ruppin et al. 2021), which is linked to the ICM cooling. An absence of
evolution on the detection fraction of cavities could imply that the
mechanical feedback in CC clusters has been in place and maintained across
almost 8 Gyrs.

All the above is quite intriguing given that the AGN-hosting BCG fraction in
the SPT-SZ cluster sample, selected from infrared WISE observations, appears
to be strongly evolving with redshift (see Somboonpanyakul et al. 2022; Bîrzan
et al. 2017; Hlavacek-Larrondo et al. 2013; also Silverman et al. 2009;
Haggard et al. 2010 for related studies). The authors argue that nearby
clusters may grow by dry mergers without increasing the AGN activity. Whereas,
high-$z$ clusters may accrete cold gas from gas-rich mergers and satellite
interactions, which could drive a massive inflow of cold gas towards the
central region, increasing the AGN activity. With more fuel available at
high-$z$, the accretion rate is more likely to reach the Eddington limit,
leading to a transition from a mechanical feedback state to a radiative
feedback mode (e.g., Churazov et al., 2005; Dubois et al., 2012; Russell et
al., 2013). Therefore, the lack of evolution on the cavity fraction at
high-$z$ may be due to the dominance of BCGs with radiatively efficient AGNs
(see also Hlavacek-Larrondo et al. 2013).

###  4.2 Cooling luminosity versus Cavity power

Figure 3: Comparison between the mechanical power being injected by the AGN in
the BCG ($P_{\rm cav}$) and the cooling luminosity ($L_{\rm cool}$) of the
cluster at 7.7 Gyrs. The dotted lines are from bottom to top are pV, 4pV,
16pV, per cavity, respectively. Certain (C) cavities are shown with filled
green circles, whereas Potential (P) cavities with open green circles for
Planck selected clusters. We included X-ray cavities from the high-$z$ SPT–SZ
sample (HL15) with filled and open orange circles for the certain and
potential cavities, respectively. We have also added nearby clusters with
X-ray cavities from Rafferty et al. (2006) sample shown with purple circles.

One goal of this work is to test whether the AGN is able to compensate for the
cooling losses of the ICM by heating caused from radio jets. We used the
cavity power ($P_{\rm cav}$) as a proxy for the mechanical power released by
the AGN. The $P_{\rm cav}$ was estimated by dividing the total enthalpy of
each cavity ($E_{\rm cav}=4pV$) by its age. Here $p$ is the thermal pressure
of the ICM at the projected location of the cavity, defined as the center of
each ellipse, and $V$ is the cavity volume. We assumed that the cavities have
a prolate shape. The age of the cavity can be given by the buoyant rise time,
the refill time, or the sound crossing time (McNamara et al., 2000; Bîrzan et
al., 2004; McNamara et al., 2005). For the purpose of this work, we used the
buoyant rise time ($t_{\rm buoy}$) as the age of the cavity, as done in
previous studies. The $t_{\rm buoy}$ corresponds to time for the cavity to
rise buoyantly at its terminal velocity, and is defined as $t_{\rm
buoy}=R/v_{\rm t}=R\sqrt{SC/2gV}$, where $S$ is the cross-section of the
bubble ($S=\pi r_{\rm b}^{2}$), $C$ (= 0.75) is the drag coefficient (Churazov
et al., 2001). Lastly, the local gravitational potential, $g$, was derived
assuming hydrostatic equilibrium.

We drew on top of each identified X-ray cavity an ellipse model, as done in
previous works (e.g., Dong et al., 2010; Shin et al., 2016). Accordingly, the
volume of the cavities is $V=4\pi r_{\rm b}^{2}r_{\rm a}/3$, where $r_{\rm a}$
is the semi-major axis, $r_{\rm b}$ is the semi-minor axis of each X-ray
cavity (see Table 1). We also include in Table 1 the significance of the
detection for each cavity. The significance was calculate as the surface
brightness ratio of the surrounding “blackground”, measured within the same
aperture size as the cavity , and the cavity. Certain cavities have average
significance of 2.2, while potential cavities have average significance of
1.5.

Table 1: Cavity properties

Cluster name | Class | $r_{\rm a}$ | $r_{\rm b}$ | R | PA | $t_{\rm bouy}$ | $P_{\rm cav}$ | $L_{\rm cool}$ | cav.
---|---|---|---|---|---|---|---|---|---
|  | (kpc) | (kpc) | (kpc) | (deg.) | ( 107 yr) | ( 1044 erg s-1) | (1044 erg s-1) | significance
G021.09+33.25 | C | 4.1 | 2.6 | 6 | 140 | 0.9${}^{+0.6}_{-3.3}$ | 0.9${}^{+1.6}_{-0.2}$ | 10.1 | 2.2
G021.09+33.25 | C | 5.4 | 3.6 | 7 | 70 | 1.6${}^{+2.2}_{-1.3}$ | 1.2${}^{+1.1}_{-1.0}$ | 10.1 | 2.7

(This table is available in its entirety in machine-readable form.)

Motivated from the previous studies (e.g., Rafferty et al., 2006), we
calculate the X-ray cooling luminosity, $L_{cool}$, within a volume where the
deprojected (isobaric) cooling time, $t_{\rm cool}$, is 7.7 Gyrs (see Table
1). It is representative of the epoch of the last major. Since then, clusters
have been relaxed and a cooling flow could develop (Rafferty et al., 2006).
For the cooling luminosity, we used $L_{\rm cool}=\int n_{\rm e}n_{\rm
H}\Lambda(T,Z)dV$, where $\Lambda(Z,T)$ is the cooling function which depends
on the temperature, $T$, and metallicity, $Z$, of the hot gas. We use the
cooling functions from Gnat & Sternberg (2007), assuming metallicity of
$Z=1~{}Z\odot$, since typical CC clusters have solar or nearly solar
metallicity within their cores (e.g., Molendi & Pizzolato, 2001; Mernier et
al., 2016).

In Figure 3 we compare the mechanical power released by the AGN located in the
central BCG and the cooling luminosity ($L_{\rm cool}$) of each cluster. As a
matter of comparison, we included galaxy groups and elliptical galaxies from
(Rafferty et al., 2006), as well as high-$z$ clusters from the SPT–SZ (HL15).
Notably, our Planck sample has systematically lower mechanical powers than the
high-$z$ SPT–SZ sample, indicating our ability to detect smaller cavities. The
smallest X-ray cavities detected in the SPT–SZ sample have sizes on the order
of $\sim$10 kpc, whereas the resolution for the Planck clusters, as they are
at lower $z$ clusters, is on the order of $\sim$2.5 kpc. The scatter on the
$L_{\rm cool}$ versus $P_{\rm cav}$ relation is slightly smaller in our sample
than in the high-$z$ SPT–SZ sample by $\sim$20%. To make a fair comparison
with the high-$z$ SPT-SZ sample taking only cavities with sizes $\gtrsim$10
kpcs, we find that the scatter is 65% smaller compared to the SPT-SZ sample.
The higher scatter on this relation for high-$z$ clusters is consistent with
being fueled mainly through wet mergers (Somboonpanyakul et al., 2022).

As shown in Fig 3 the $L_{\rm cool}$ and $P_{\rm cav}$ realized from the jets
are positively correlated, indicating that the energy realized by the AGN is
sufficient to balance the radiative losses of the ICM within the cooling
radius for most of the sources in the sample. Some of those objects may
require additional heating from another mechanism, such as thermal conduction
and shocks (e.g., Pope et al., 2005). However, we expect that some of these
clusters may be in a cooling phase discarding the need for an additional
heating source. The nature of the AGN feedback is cyclic and does not always
require a balance between the cooling luminosity and the AGN heating (McNamara
& Nulsen, 2007). This is likely displayed on the scatter of the $L_{\rm cool}$
versus $P_{\rm cav}$ relation. In that sense, the AGN power is variable, and
the objects change their $P_{\rm cav}$ depending on what phase of the AGN
feedback cycle they are observed in. Another source of scatter comes from
dynamically disturbed clusters due to either sloshing motions or mergers.
These mechanisms move the hot gas out of the central BCG to large distances
producing lower $L_{\rm cool}$ for a given $P_{\rm cav}$ value, as found for
clusters with higher centroid shifts indicative of dynamically disturbed
atmospheres (Olivares et al. in prep).

##  5 Limitations

One of this work’s limitations is the fact that we are probably missing
cavities due to shallow X-ray observations, in particular in high-$z$ clusters
(e.g., Diehl et al., 2008; Bîrzan et al., 2012). As pointed out by several
studies, X-ray cavities are more easily detected in clusters with stronger
cool cores, as the contrast between the depression and surroundings is
sharper, and it is more difficult to find bubbles in high-redshift clusters
due to the lack of counts. The detectability of cavities also decreases with
their radius (Enßlin & Heinz, 2002).

More importantly, cavities that have sizes below the resolution (e.g., cavity
size $\leq 2$ kpc for clusters at $z$=0.1) will be undetectable in such an
analysis. As shown in Figure 2, this effect will increase at high-$z$. For
example, cluster at $z$>0.5 only cavities with sizes $\geq 6$ kpc can be
detected. We also note that sources with more than 2000 counts, in the central
region, tend to have “certain” detected X-ray cavities (circle symbols).
Therefore, we stress that deeper Chandra follow-up observations are required
to confirm the presence of any potential X-ray cavity, especially in high-$z$
clusters. Aside from the data quality, other effects may be also interfering
with the cavity detectability, such as orientation, location, and angular size
(see Enßlin & Heinz 2002; Diehl et al. 2008; Brüggen et al. 2009 for more
details). As pointed out by Enßlin & Heinz (2002), the detectability of
cavities decreases with distance to the center, and for a cavity moving in the
plane of the cavities, the contrast decreases slowly. Cavities that lie off
the plane of the sky have reduced contrast and therefore are harder to detect.
To quantify this projection effect, we assume a random distribution of the
angle of the cavity relative to the plane of the sky, a typical cavity size of
10 kpc, and a typical beta profile for the ICM distribution (rc=20, beta=3/4).
At an average projected distance of 30 kpc, 20%–30% of the cavities would have
a contrast below our detection limit and would have been missed in our study.

It should be noted that the $P_{\rm cav}-L_{\rm cool}$ relation is also
affected by projection effects, likely introducing scatter. As pointed out by
Diehl et al. (2008), all the physical quantities involving the cavity power,
$P_{\rm cav}$, such as density, temperature, and pressure, are measured at the
projected distance from the cavity to the center rather than the true
distance. The former corresponds to a lower limit. The pressure increases
towards the center, leading to an overestimation of the ambient pressure at
the cavity position. On the other hand, the cavity ages will be underestimated
as they are proportional to the cavity distance. Both mentioned effects will
bias the cavity power upwards.

##  6 Conclusions

We have investigated the mechanical AGN feedback mechanism in central cluster
galaxies using archival X-ray Chandra observations of 164 Planck selected
clusters to search for X-ray cavities.

(i) Using several techniques to look for X-ray cavities, including inspection
of the original image, a model subtracted image and an unsharp masked image,
we find 65 X-ray cavities in 29 systems out of 63 CC clusters. Among them, 12
systems have clearly detected cavities, whereas 17 have only potential
depressions. Two potential cavities were also found in one NCC cluster.

(ii) We measured a total detection fraction of X-ray cavities of $\sim$18%,
twice the detection rate of the high-$z$ SPT–SZ sample, indicating that
clusters have radio-mode feedback only 18% of the time. Nevertheless, our
detection fraction of 9% is close to the high-$z$ SPT–SZ sample when taking
only cavities with sizes $\gtrsim$10 kpc to match the resolution of the SPT-SZ
sample. We interpreted this as an lack of evolution of the AGN feedback cycle
across cosmic time.

(iii) We find that the AGN heating traced by the power of the X-ray cavities
alone is able to balance the radiative losses of the ICM in our sample. Our
sources have slightly lower cavity power per cavity than high-$z$ massive
clusters from the SPT-SZ sample due to smaller cavities being detected in our
sample.

Future high-resolution X-ray observations from Chandra satellite and the
upcoming Advanced X-ray Imaging Satellite (AXIS) telescope will be needed to
find more cavities in the faintest clusters and confirm the discussed findings
in high-$z$ clusters.

## Acknowledgments

This research has made use of software provided by the Chandra X-ray Center
(CXC) in the application packages CIAO. V.O. and Y.S. were supported by NSF
grant 2107711, Chandra X-ray Observatory grant GO1-22126X, and NASA grant
80NSSC21K0714.

## Data Availability

The Chandra raw data used in this paper are available to download at the
HEASARC Data Archive website111https://heasarc.gsfc.nasa.gov/docs/archive.htm.

## References

  * Andrade-Santos et al. (2017) Andrade-Santos F., et al., 2017, ApJ, 843, 76
  * Bîrzan et al. (2004) Bîrzan L., Rafferty D. A., McNamara B. R., Wise M. W., Nulsen P. E. J., 2004, ApJ, 607, 800
  * Bîrzan et al. (2008) Bîrzan L., McNamara B. R., Nulsen P. E. J., Carilli C. L., Wise M. W., 2008, ApJ, 686, 859
  * Bîrzan et al. (2012) Bîrzan L., Rafferty D. A., Nulsen P. E. J., McNamara B. R., Röttgering H. J. A., Wise M. W., Mittal R., 2012, MNRAS, 427, 3468
  * Bîrzan et al. (2017) Bîrzan L., Rafferty D. A., Brüggen M., Intema H. T., 2017, MNRAS, 471, 1766
  * Bîrzan et al. (2020) Bîrzan L., et al., 2020, MNRAS, 496, 2613
  * Bleem et al. (2015) Bleem L. E., et al., 2015, ApJS, 216, 27
  * Bleem et al. (2020) Bleem L. E., et al., 2020, ApJS, 247, 25
  * Boehringer et al. (1993) Boehringer H., Voges W., Fabian A. C., Edge A. C., Neumann D. M., 1993, MNRAS, 264, L25
  * Brown et al. (2001) Brown L. D., Cai T., DasGupta A., 2001, Statistical Stadistical science, 16, 101
  * Brüggen et al. (2009) Brüggen M., Scannapieco E., Heinz S., 2009, MNRAS, 395, 2210
  * Canning et al. (2013) Canning R. E. A., et al., 2013, MNRAS, 435, 1108
  * Carilli et al. (1994) Carilli C. L., Perley R. A., Harris D. E., 1994, MNRAS, 270, 173
  * Churazov et al. (2001) Churazov E., Brüggen M., Kaiser C. R., Böhringer H., Forman W., 2001, ApJ, 554, 261
  * Churazov et al. (2005) Churazov E., Sazonov S., Sunyaev R., Forman W., Jones C., Bohringer H., 2005, MNRAS: Letters, 363, L91
  * Diehl et al. (2008) Diehl S., Li H., Fryer C. L., Rafferty D., 2008, ApJ, 687, 173
  * Dong et al. (2010) Dong R., Rasmussen J., Mulchaey J. S., 2010, The Astrophysical Journal, 712, 883
  * Dubois et al. (2012) Dubois Y., Devriendt J., Slyz A., Teyssier R., 2012, MNRAS, 420, 2662
  * Enßlin & Heinz (2002) Enßlin T. A., Heinz S., 2002, A&A, 384, L27
  * Fabian (1994) Fabian A. C., 1994, ARA&A, 32, 277
  * Fabian (2012) Fabian A., 2012, ARA&A, 50, 455
  * Fabian et al. (2006) Fabian A. C., Sanders J. S., Taylor G. B., Allen S. W., Crawford C. S., Johnstone R. M., Iwasawa K., 2006, MNRAS, 366, 417
  * Gitti et al. (2010) Gitti M., O’Sullivan E., Giacintucci S., David L. P., Vrtilek J., Raychaudhury S., Nulsen P. E. J., 2010, ApJ, 714, 758
  * Gnat & Sternberg (2007) Gnat O., Sternberg A., 2007, ApJS, 168, 213
  * Haggard et al. (2010) Haggard D., Green P. J., Anderson S. F., Constantin A., Aldcroft T. L., Kim D.-W., Barkhouse W. A., 2010, ApJ, 723, 1447
  * Hilton et al. (2018) Hilton M., et al., 2018, ApJS, 235, 20
  * Hincks et al. (2010) Hincks A. D., et al., 2010, ApJS, 191, 423
  * Hlavacek-Larrondo et al. (2013) Hlavacek-Larrondo J., Fabian A. C., Edge A. C., Ebeling H., Allen S. W., Sanders J. S., Taylor G. B., 2013, MNRAS, 431, 1638
  * Hlavacek-Larrondo et al. (2015) Hlavacek-Larrondo J., et al., 2015, ApJ, 805, 35
  * Jones (2012) Jones C., 2012, A Chandra-Planck Legacy Program for Massive Clusters of Galaxies, Chandra Proposal
  * McNamara & Nulsen (2007) McNamara B., Nulsen P., 2007, ARA&A, 45, 117
  * McNamara et al. (2000) McNamara B. R., et al., 2000, ApJ, 534, L135
  * McNamara et al. (2005) McNamara B. R., Nulsen P. E. J., Wise M. W., Rafferty D. A., Carilli C., Sarazin C. L., Blanton E. L., 2005, Nature, 433, 45
  * Mernier et al. (2016) Mernier F., de Plaa J., Pinto C., Kaastra J. S., Kosec P., Zhang Y. Y., Mao J., Werner N., 2016, A&A, 592, A157
  * Molendi & Pizzolato (2001) Molendi S., Pizzolato F., 2001, ApJ, 560, 194
  * Morsony et al. (2010) Morsony B. J., Heinz S., Brüggen M., Ruszkowski M., 2010, MNRAS, 407, 1277
  * Nulsen et al. (2009) Nulsen P., Jones C., Forman W., Churazov E., McNamara B., David L., Murray S., 2009, in Heinz S., Wilcots E., eds, American Institute of Physics Conference Series Vol. 1201, The Monster’s Fiery Breath: Feedback in Galaxies, Groups, and Clusters. pp 198–201 (arXiv:0909.1809), doi:10.1063/1.3293033
  * O’Sullivan et al. (2011) O’Sullivan E., Giacintucci S., David L. P., Gitti M., Vrtilek J. M., Raychaudhury S., Ponman T. J., 2011, ApJ, 735, 11
  * Olivares et al. (2019) Olivares V., et al., 2019, A&A, 631, A22
  * Olivares et al. (2022) Olivares V., et al., 2022, arXiv e-prints, p. arXiv:2201.07838
  * Panagoulia et al. (2014) Panagoulia E. K., Fabian A. C., Sanders J. S., Hlavacek-Larrondo J., 2014, MNRAS, 444, 1236
  * Planck Collaboration et al. (2011) Planck Collaboration et al., 2011, A&A, 536, A1
  * Pope et al. (2005) Pope E. C. D., Pavlovski G., Kaiser C. R., Fangohr H., 2005, MNRAS, 364, 13
  * Rafferty et al. (2006) Rafferty D. A., McNamara B. R., Nulsen P. E. J., Wise M. W., 2006, ApJ, 652, 216
  * Ruppin et al. (2021) Ruppin F., McDonald M., Bleem L. E., Allen S. W., Benson B. A., Calzadilla M., Khullar G., Floyd B., 2021, ApJ, 918, 43
  * Russell et al. (2013) Russell H. R., McNamara B. R., Edge A. C., Hogan M. T., Main R. A., Vantyghem A. N., 2013, MNRAS, 432, 530
  * Russell et al. (2019) Russell H. R., et al., 2019, MNRAS, 490, 3025
  * Shin et al. (2016) Shin J., Woo J.-H., Mulchaey J. S., 2016, ApJS, 227, 31
  * Silverman et al. (2009) Silverman J. D., et al., 2009, ApJ, 695, 171
  * Somboonpanyakul et al. (2022) Somboonpanyakul T., et al., 2022, arXiv e-prints, p. arXiv:2201.08398
  * Su et al. (2020) Su Y., et al., 2020, MNRAS, 498, 5620


# Interactive Region-of-Interest Discovery using Exploratory Feedback

Behrooz Omidvar-Tehrani
Grenoble AI Institute

###### Abstract

In this paper, we propose a geospatial data management framework called IRIDEF
which captures and analyzes user’s exploratory feedback for an enriched
guidance mechanism in the context of interactive analysis. We discuss that
exploratory feedback can be a proxy for decision-making feedback when the
latter is scarce or unavailable. IRIDEF identifies regions of interest (ROIs)
via exploratory feedback, and highlights a few interesting and out-of-sight
POIs in each ROI. These highlights enable the user to shape up his/her future
interactions with the system. We detail the components of our proposed
framework in the form of a data analysis pipeline, and present the aspects of
efficiency and effectiveness for each component. We also discuss evaluation
plans and future directions for IRIDEF.

##  1 Introduction

Background. Nowadays, geospatial data are ubiquitous in various fields of
science, such as transportation, smart city management [1, 2], travel planning
[3], bike sharing [4], localized advertising [5], and regional health-care
[6]. A recent solution for an improved geospatial data management is to
provide means for interactive analysis, where users in the loop are guided
towards interesting subsets of data in an exploratory iterative manner [7, 8].
Typically, the guidance is performed through learning user’s preferences using
a decision-making feedback received from the user in each iteration, e.g.,
picking (clicking on) a favorite point of interest (POI). However, it is often
the case in geospatial scenarios that users forget or don’t feel necessary to
explicitly express their feedback in what they find interesting. As a result,
the interactive dialog will be broken and no guidance can be delivered. In
this paper, we focus on the following question: Is it possible to perform
interactive analysis on geospatial data without having access to decision-
making interactions?

Proposal. In the absence of decision-making interactions, we propose to focus
on exploratory feedback, i.e., patterns in signals captured from the user in
the background which provide hints on user’s interests. For instance, users
often hover their mouse (or make frequent touch actions on a touch screen,
such as scroll, pinch and zoom) over a region of interest to collect
information on the map (e.g., touristic places and hidden gems presented in
the form of map layers and tooltips) before landing on a decision about
picking a POI in that region, such as a home-stay. Hence it is possible to
infer the interest towards that region even without decision-making
interactions. This inferred knowledge should be leveraged in the guidance
mechanism. An instance of such guidance is to highlight a few interesting POIs
in the region of interest. We advocate a geospatial data management framework
(called IRIDEF) which captures and analyzes user’s exploratory feedback for an
enriched guidance mechanism in the context of interactive analysis.

Scenario. Lindsey is a visiting researcher from the US. She wants to rent a
home-stay in Paris via the Airbnb website. She likes to discover the city,
hence she is open to any type of lodging in any region with an interest to
stay in the center of Paris. Her exploration starts with a query which
expresses the preliminary set of her interests. The website returns 1500
different home-stays for her query. While scanning the very first items, she
shows (an exploratory) interest towards the region of Trocadero by hovering
her mouse around the Eiffel tower and checking the amenities within that
region. However, she forgets or doesn’t feel the necessity to click a POI
(i.e., a home-stay) in that region. While typical recommendation and
exploration systems do not necessarily focus on this implicit interest in the
future iterations, our framework ensures that Lindsey receives home-stay
recommendations related to the Trocadero region even if she didn’t provide any
decision-making feedback.

Challenges. Analyzing exploratory feedback is challenging. First, it is not
clear how this feedback should be interpreted in terms of the user
preferences. Exploratory feedback on geospatial data can be enabled via
different signals, such as mouse hovering [9], touch actions [10], voice [11],
and gaze [12]. Translating such enablers into geospatial semantics is
challenging. Second, all exploratory signals are not necessarily useful and
some may introduce false positives. For instance, a small mouse move on a
typical screen would yield more than 14,000 points (assuming 1600 DPI) which
may turn out to be just a random futile move. Beyond the first two challenges,
guiding users towards interesting POIs is also challenging, as it requires an
exhaustive scan over the geospatial data against the evolving user
preferences.

Contributions. We propose a guidance approach for interactive exploration of
geospatial data. Our approach identifies regions of interest (ROIs) without
the need for any decision-making feedback. Our proposed guidance mechanism is
to highlight a few interesting and out-of-sight POIs in each ROI, and let the
user investigate those POIs in his/her future interactions with the system.
The following list summarizes the contributions and claims discussed in this
paper:

  * •

We define the notion of “exploratory user feedback” which enables a seamless
navigation in the geospatial data.

  * •

We define the notion of “information highlighting”, a mechanism to highlight
important spatial information that is out-of-sight.

  * •

We employ an efficient polygon-based approach to discover ROIs.

  * •

We propose an approach to compute highlights on-the-fly in an efficient
manner.

To the best of our knowledge, our contributions have not been investigated
before in the literature. Popular map-based applications such as Google Maps
and Bing Maps do not offer interactive functionalities for feedback capturing.
In the literature, information highlighting [13, 14, 15] and spatial
recommendation approaches [16, 17] often assume that the user’s preferences
are static and will never change in time. This limits their functionality for
serving the scenarios of an interactive analysis. The process of feedback
capturing is mostly formulated for decision-making interactions [18, 19, 20,
21, 22, 23]. While a few fuse decision-making and exploratory feedbacks [24,
25, 26], our approach is not dependent on decision-making feedback and is able
to operate purely on exploratory feedback. It is to state the obvious that a
straightforward extension of our system is to incorporate decision-making
feedback (if available) to improve the effectiveness of the system.

Paper outline. The rest of this paper is organized as follows. In Section 2,
we elaborate on different instances of decision-making and exploratory
feedbacks in the literature. We discuss the data model and introduce in the
problem in Section 3. We present our proposed approach in Section 4, and
discuss evaluation plans in Section 5. Last, we conclude and present future
directions in Section 6.

Figure 1: Examples of decision-making and exploratory feedbacks in realistic
geospatial scenarios [6, 27, 3]

##  2 Decision-making Feedback versus and Exploratory Feedback

We briefly discuss a few examples in the literature to clarify the distinction
between decision-making and exploratory feedback types in realistic geospatial
applications. These examples are illustrated in Figure 1. In summary, we argue
that different types of decision-making feedback have been already employed,
but the exploratory feedback is often missing.

Medical domain. COVIZ [6] is an interactive web-based application which
enables medical experts to form and compare medical cohorts. In Figure 1-A,
the expert clicks on the Auvergne-Rhône-Alpes region (as a decision-making
feedback) to compare the patient cohort in this particular region with the
whole France. In Figure 1-B, the expert adds the air pollution layer to the
analysis to examine any potential correlation between the patients’ health
status and the abundance of the air pollution. While the expert explores the
cohort comparisons and pollution correlations, the tool does not collect any
exploratory feedback, such as mouse hover and gaze.

Aviation domain. DV8 [27] is an interactive aviation data analysis tool. When
several flight trajectories are visualized (Figure 1-C), the expert can click
on one trajectory to retrieve its information (departure, destination, etc.),
and double-click to solely focus on that single trajectory and analyze it
further (Figure 1-D). The interaction is always through the decision-making
feedback (single-click and double-click) and the exploratory feedback is not
supported. DV8 also supports touch gestures, such as pinch and zoom (Figure
1-E) and brush (Figure 1-F). However the touch actions are all considered as
decision-making feedback with an immediate resulting action. Hence there is no
support for exploratory feedback. The virtual reality (VR) version of DV8
(Figures 1-G and 1-H) enhances the exploration experience of the aviation
expert, particularly for analyzing flights in different altitudes. While the
gaze signal is an exploratory feedback which can be captured through VR, DV8
employs the signal only for navigating the geospatial data, and not for
guidance.

Travel domain. Simurgh [3] is an interactive travel package generation tool.
The user can ask for a new day plan using a drag-and-drop action over a region
of interest (the drag-and-drop in Figure 1-I and the resulting day plan in
Figure 1-J). She can also replace a point of interest by clicking on the point
(the selection in Figure 1-K and the replacement in Figure 1-L). All the
interactions are defined as the decision-making feedback. In other words,
Simurgh does not detect the regions of interest by following the exploratory
feedback.

##  3 Data Model and Problem Definition

To enable feedback capturing, we consider two different layers on a
geographical map: spatial layer and interaction layer. The spatial layer
contains POIs from a spatial database $\mathcal{P}$. The interaction layer
contains exploratory feedback points $\mathcal{M}$. These layers are explained
below.

Spatial layer. Each POI
$p=\langle\mathit{lat},\mathit{lon}\rangle\in\mathcal{P}$ is described using
its geographical coordinates. POIs are also associated to a set of domain-
specific attributes $\mathcal{A}$. For instance, in the dataset of a real
estate agency, POIs are properties (houses and apartments) and $\mathcal{A}$
contains attributes such as surface, number of rooms and price. The set of all
possible values for an attribute $a\in\mathcal{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\in\prod_{a\in\mathcal{A}}dom(a)$. The vector $F$ is
initialized by zeros and will be updated to express the user’s preferences.
The facet-based schema of $F$ ensures that learned feedback is always
transparent and interpretable by the user using the facets, and hence reduces
algorithmic anxiety [28].

Interaction layer. We assume that an exploratory signal addresses one specific
point $m$ on the screen, e.g., hovering at, gazing at, or providing a voice
command about $m$. When an exploratory signal is received, the point $m$ is
appended to the set $\mathcal{M}$. Each point is a tuple $m=\langle
x,y,t\rangle$, where $x$ and $y$ specify the affected pixel location and $t$
is a timestamp. To conform with geographical standards, we assume $m=\langle
0,0,t\rangle$ sits at the middle of the interaction layer, both horizontally
and vertically, for any $t$.

Transitioning between the layers. 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=\langle x,y,t\rangle\in\mathcal{M}$ in the spatial layer, denoted
as $p(m)$.

$p(m=\langle
x,y,t\rangle)=\langle\mathit{lat}=y+\gamma,\mathit{lon}=\frac{x}{\mathit{cos}\gamma}+\theta\rangle$
(1)

The inverse operation, i.e., transforming a point
$p=\langle\mathit{lat},\mathit{lon}\rangle$ from the spatial layer to the
interaction is done using Equation 2.

$m(p=\langle\mathit{lat},\mathit{lon}\rangle)=\langle
x=(\mathit{lon}-\theta)\times\mathit{cos}\gamma,y=\mathit{lat}-\gamma\rangle$
(2)

The reference point for the transformation is the center of both layers. In
Equations 1 and 2, we assume that $\gamma$ is the latitude and $\theta$ is the
longitude of a point in the spatial layer corresponding to the center of the
interaction layer, i.e., $m=\langle 0,0\rangle$.

Problem definition. Given the user’s feedback $F$, we are interested in
solving two consecutive problems: $(i)$ discover regions of interest in the
form of geospatial clusters whose centroids correlate with $F$ (with respect
to the POI attributes in which the user is interested in), and $(ii)$ for each
discovered region, find at most $k$ POIs ($k$ is an input parameter) which are
relevant to $F$ and have high exploration quality. We define relevance and
exploration quality in Section 4.

Figure 2: IRIDEF framework.

##  4 Proposed Approach

We propose IRIDEF (Interactive Region-of-Interest Discovery using Exploratory
Feedback), a framework for exploiting exploratory feedback to highlight
interesting POIs as future analysis directions. As depicted in Figure 2, our
approach consists of a pipeline with three main components: CAPTURE, DISCOVER,
and HIGHLIGHT. After the user has explored the map for a while, IRIDEF
captures exploratory feedback from the exploration (i.e., the CAPTURE
component detailed in Section 4.2). Then a set of regions of interest (ROIs)
will be discovered using the captured feedback (i.e., the DISCOVER component
detailed in Section 4.3). Finally some out-of-sight interesting POIs will be
highlighted for each discovered ROI (i.e., HIGHLIGHTcomponent detailed in
Section 4.4). In the following, we first discuss the desiderata behind our
approach, and then detail each component of the pipeline.

###  4.1 Principles

In order to maximize the usability of IRIDEF, we believe that the framework
should be generic and fluid, as discussed below.

Genericness. IRIDEF’s pipeline is applicable to different datasets and
different types of exploratory feedback. This enables IRIDEF to cover
different exploration scenarios. The minimal requirement is that the input
dataset and the feedback signal match with our data model (Section 3).

Fluidity. A fluid interactive system does not break the user’s train of
thought. The fluidity is ensured by rendering results in an efficient and
effective manner. In the CAPTURE component, effectiveness is satisfied by
disregarding irrelevant signals. In the DISCOVER and HIGHLIGHT components,
effectiveness is interpreted as delivering meaningful and useful regions
(ROIs) and highlights (POIs), respectively. In all of the components,
efficiency is to return results instantaneously, often considered to be $\leq
500ms$ [29].

###  4.2 CAPTURE Component

Exploratory feedback can be captured using different latent signals, e.g.,
time dedicated to item details, touch actions, gaze, mouse moves, scrolling
speed, etc. Without loss of generality, we focus on mouse moves as an instance
of exploratory feedback signal. A particular challenge in capturing mouse
moves as the exploratory feedback is that the user may mindlessly move the
mouse everywhere on the map. Obviously, this should not signify that all the
locations are equally important to the user. An effective approach should only
capture a subset of this feedback which is then useful for discovering ROIs.
Also an efficient approach should capture this feedback without any
interruption in the fluidity of the user experience. For an effective and
efficient feedback capturing, IRIDEF performs the two following actions:

  1. 1.

First, it records the exploratory signals (by adding the coordinates of the
screen points they were applied on to $\mathcal{M}$) only every $\varepsilon$
milliseconds to prevent adding redundant points.

  2. 2.

After a given period of feedback capturing time, it groups the recorded
signals into $g$ different segments, $\mathcal{M}_{1}$ to $\mathcal{M}_{g}$.
The first segment starts at time zero (where the system started to operate),
and the last segment ends at the current time.

The choice of $\varepsilon$ depends on various parameters such as the
application (e.g., tourism, delivery, transportation) and the user’s
expertise. For instance, a larger $\varepsilon$ seems more appropriate for
novice users, as they might perform many random moves to get acquainted with
the data. In conformance with progressive data analytics [29], we set
$\varepsilon=100ms$ as the default value to ensure continuity preserving
latency.

Input: Mouse move points $\mathcal{M}$, time gap $\varepsilon$, segmentation
strategy $\psi$

Output: Segments $\mathcal{M}_{i}$, $i\in[1,g]$

1 $\mathit{segment\\_count}\leftarrow 0$

2 for  _$m\in\mathcal{M}$ captured every $\varepsilon$ milliseconds_ do

3
$\mathcal{M}[\mathit{segment\\_count}]\leftarrow\mathcal{M}[\mathit{segment\\_count}]\cup\\{m\\}$

4
$\mathit{segment\\_change}\leftarrow\mathit{check\\_strategy}(\psi,m,\mathcal{M})$

5 if  _$\mathit{segment\\_change}=\mathit{true}$_ then

6 $\mathit{segment\\_count}\leftarrow\mathit{segment\\_count}+1$

7 $\mathcal{M}[\mathit{segment\\_count}]\leftarrow\emptyset$

8

9 end if

10

11 end for

12return _$\mathcal{M}_{i}$ , $i\in[1,g]$ where $g=\mathit{segment\\_count}$_

Algorithm 1 CAPTURE algorithm

Moreover, the end of a segment is determined by one of the following
approaches:

  * •

$\psi_{1}$: End the current segment after a fixed amount of time (i.e., fixed-
length segments). In this case, the value of $g$ is selected based on the
spatial density of the dataset under investigation.

  * •

$\psi_{2}$: End the current segment if the mouse location is unchanged for a
certain amount of time.

  * •

$\psi_{3}$: End the current segment after a drastic change in the signal,
where the drift is captured using signal segmentation approaches. We employ
the Wedding Cake technique for the dynamic segmentation of our signals [30,
31].

Algorithm 1 summarizes the CAPTURE process.

###  4.3 DISCOVER Component

The objective of this step in the IRIDEF pipeline is to obtain one or several
ROIs in which the user has expressed his/her exploratory feedback. We
conjecture that a region is more interesting for the user if it is denser,
i.e., the user moves the mouse in that region frequently, to collect
information from the background map. Hence ROIs can be simply discovered as
dense clusters of mouse move points. We denote the set of all ROIs as
$\mathcal{R}$ and we refer to the $i$-th ROI as $R_{i}\in\mathcal{R}$.
Algorithm 2 summarizes the DISCOVER process.

We employ ST-DBSCAN [32], a space-aware variant of DB-SCAN, to cluster points
in each segment (line 2 in Algorithm 2). For each subset of mouse move points
$\mathcal{M}_{i}$, $i\in[1,g]$, ST-DBSCAN begins with a random point
$m_{0}\in\mathcal{M}_{i}$ and collects all density-reachable points from
$m_{0}$ using a distance metric. As mouse move points are in the 2-dimensional
pixel space (i.e., the screen), we choose euclidean distance as the distance
metric. A density-reachable point $m_{i}$ is either directly reachable from
$m_{0}$, i.e., the distance between $m_{i}$ and $m_{0}$ is lower than a
distance threshold (an input parameter for the ST-DBSCAN algorithm), or
reachable via a path $m_{0}\dots m_{j-1},m_{j}\dots m_{i}$ where each point
$m_{j}$ in the path is directly reachable from its immediately prior point in
the path $m_{j-1}$. If $m_{0}$ turns out to be a core point, a cluster will be
generated. A point is core if there exist a certain amount of points in its
vicinity, i.e., with a distance lower than the distance threshold. The minimum
number of points for a core point is yet another input parameter for ST-
DBSCAN. If $m_{0}$ is not a core point, the algorithm picks another random
point in $\mathcal{M}_{i}$. The process is repeated until all points have been
processed. We denote the set of all resulting clusters for $\mathcal{M}_{i}$
as $\mathcal{C}_{i}=\\{C_{1},C_{2},\dots\\}$.

Input: Segments $\mathcal{M}_{1}$ to $\mathcal{M}_{g}$, user feedback vector
$F$, number of interactions performed so far $T$

Output: Set of discovered ROIs $\mathcal{R}$

$O\leftarrow\emptyset$

// the set of all polygons initialized as empty

$\mathcal{R}\leftarrow\emptyset$

// the set of all ROIs initialized as empty

1 for  _each segment $\mathcal{M}_{i}$_ do

$\mathcal{C}_{i}\leftarrow\mathit{ST\\_DBSCAN}(\mathcal{M}_{i})$

// all clusters inside $\mathcal{M}_{i}$

2 $\mathcal{C}_{i}\leftarrow\mathit{AklToussaint}(\mathcal{C}_{i})$

$O_{i}\leftarrow\mathit{Graham\\_scan}(\mathcal{C}_{i})$

// all polygons inside $\mathcal{M}_{i}$

$O_{i}.\mathit{expand}(\mathit{confidence}(F,T))$

// Equation 3

3 $O\leftarrow O\cup O_{i}$

4 end for

5for  _each pair of polygons $O_{x}\in O$ and $O_{y}\in O$_ do

6 $S\leftarrow\mathit{intersect}(O_{x},O_{y})$

7 if  _$S.\mathit{size} >0$_ then
$\mathcal{R}\leftarrow\mathcal{R}\cup\\{S\\}$

8

9 end for

10 return _$\mathcal{R}$_

Algorithm 2 DISCOVER algorithm

Once the clusters are obtained for all the subsets of $\mathcal{M}$, we find
their intersections to locate recurring regions. Note that we don’t aim to
directly consider the clusters $\mathcal{C}$ as the ROIs, as they may contain
noisy signals. Their intersection counts as a confirmation of user
preferences. To obtain intersections, we need to clearly define the spatial
boundaries of each cluster. For this aim, we discover the polygons which cover
the points inside each cluster. We employ Graham scan algorithm (line 2 in
Algorithm 2) which is an efficient method to compute the convex hull for a
given set of points in a 2D plane [33]. We reduce the typical complexity of
Graham scan (i.e., $\mathcal{O}(|C_{i}|\times\mathit{log}|C_{i}|)$, $|C_{i}|$
being the number of points in the $i$-th cluster) to $\mathcal{O}(|C_{i}|)$ by
ordering the cluster members by their spatial coordinates. For more
efficiency, we perform Akl-Toussaint heuristics [34] before the polygon
computation to prune the points which are unnecessary for shaping the polygons
(line 2 in Algorithm 2). The intersections between the polygons constitute the
ROIs (lines 2 to 2 in Algorithm 2).

Personalizing discovered ROIs. By default, our ROI discovery approach creates
strictly tight ROIs, i.e., the area of the polygons is exactly inferred by the
points it covers. However in exploratory scenarios, the feedback points do not
necessarily reflect the exact interests of the user. The user exposes his/her
interests in a gradual manner using exploratory feedback captured in several
iterations. We believe that the user’s confidence (interpreted as the richness
of the user feedback vector $F$) should impact the way ROIs are computed,
hence personalized ROIs. In case the user is less confident (e.g., the user is
in early stages of his/her exploration), ROIs should be expanded in their area
(up to twice their original size) to let more opportunities arise (line 2 in
Algorithm 2). The user confidence is computed as follows.

$\mathit{confidence}(F,T)=\mathit{min}(1.0,\frac{||F||_{0}}{\xi\times T})$ (3)

In Equation 3, $\xi$ is a feedback frequency, and $T$ is the number of
interactions performed so far. For instance, given $|F|=50$, $T=10$, and
assuming that a typical user provides $7$ exploratory signals per iteration,
the confidence will be equal to $0.71$. The confidence is a coefficient for
stretching the ROI area. Let $A_{1}$ denote the area of the ROI $R_{1}$, the
confidence-aware area $A^{\prime}_{1}$ is computed as follows:
$A^{\prime}_{1}=(A_{1}+A_{1}\times\mathit{confidence})$. This process is shown
in line 2 of Algorithm 2.

Example. Figure 3 shows the steps that Lindsey follows to explore home-stays
in Paris. For the sake of simplicity, we assume Lindsey’s confidence is $1.0$.
Figure 3.A shows the mouse moves of Lindsey in different time stages. In this
example, we consider $g=3$ and capture Lindsey’s feedback in three different
time segments with fixed-length, i.e., $\psi_{1}$ (progressing from Figures
3.B to 3.D). It shows that Lindsey started her search around Eiffel Tower and
Arc de Triomphe (Figure 3.B) and gradually showed interest in areas located
south (Figure 3.C) and north (Figure 3.D) as well. All intersections between
those clusters are discovered (hatched regions in Figure 3.E) which will
contribute to the set of interesting regions (Figure 3.F), i.e., ROI1 to ROI4.

Figure 3: An example of discovering ROIs [9].

###  4.4 HIGHLIGHT Component

We define highlights as a subset of POIs in the form of suggestions for
directions of future analysis of the user. The highlights are generated by
performing the three following steps: matching points, updating feedback, and
highlighting POIs. First, we find POIs which fit into the polygons obtained in
the DISCOVER component. Then we update the user feedback $F$ according to
those POIs. Finally we highlight a set of POIs based on the updated content of
$F$.

Matching points. Being a function of mouse move points, ROIs are discovered in
the interaction layer. We then need to find out which POIs in $\mathcal{P}$
fall into ROIs. We employ Equation 2 to transform those POIs from the spatial
layer to the interaction layer. Then a simple spatial containment function can
verify whether a given POI fits into a given ROI.111Typically, we use the
implementation of $\mathit{ST\\_Within}()$ module in PostGIS for the
containment verification. To improve efficiency, we employ Quadtrees [35] in a
two-step approach: $(i)$ In an offline process, we build a Quadtree index for
all POIs in $\mathcal{P}$. We record the membership relations between POIs and
Quadtree grid cells in the index. $(ii)$ Once ROIs are discovered, we record
which cells in the Quadtree index intersect with the ROIs. For matching POIs,
we only check a subset which is inside the cells associated to ROIs and ignore
the ones outside, hence a drastic pruning of POIs in $\mathcal{P}$. Given an
ROI $R_{i}$, we denote the set of its matching points as $\mathcal{P}_{i}$. We
also define the binary vector $\overrightarrow{\mathcal{P}_{i}}$ whose cell of
$\langle a_{j},v_{w}\rangle$ is $1$ if at least one point in $\mathcal{P}_{i}$
gets the value $v_{w}\in\mathit{dom}(a_{j})$ for the attribute
$a_{j}\in\mathcal{A}$, otherwise $0$.

Updating feedback. The matching points depict the exploratory preferences of
the user. To memorize these preferences, we update the feedback vector $F$
using the attributes of the matching points. We consider an increment value
$\delta$ to update $F$. If $p$ is a matching point and gets
$v_{w}\in\mathit{dom}(a_{j})$ for attribute $a_{j}\in\mathcal{A}$, we augment
the value in the $F$’s cell of $\langle a_{j},v_{w}\rangle$ by the factor
$\delta$. Note that we only consider incremental feedback, i.e., we never
decrease a value in $F$. The vector $F$ will become normalized after each
update using a softmax function. The updated feedback vector is fully
transparent and the user can easily apprehend what has been learned from
his/her previous actions. Our current update model considers the feedback
vector to be recency-agnostic. We leave the integration of recency as future
work.

Highlighting POIs. The updated feedback vector $F$ is the input to the
highlighting phase. The objective is to select $k$ POIs out of all POIs inside
ROIs whose relevance and exploration quality are maximal. We denote the set of
highlights as $\mathcal{H}$. We propose two approaches to achieve our
objective, depending on how we define relevance and quality:

Input: Discovered ROIs $\mathcal{R}$, user feedback vector $F$, $k$,
$\mathit{time\\_limit}$, $\mathit{similarity\\_threshold}$

Output: Highlights $\mathcal{H}$

$\mathcal{H}\leftarrow\emptyset$

// highlights

1 for  _each discovered ROI $R_{i}\in\mathcal{R}$_ do

2 $\mathcal{P}_{i}\leftarrow\mathit{match\\_points}(R_{i})$

3 $F.\mathit{update}(\mathcal{P}_{i})$

4 $\mathcal{L}_{i}\leftarrow$ sort the POIs in $\mathcal{P}_{i}$ in decreasing
order of their similarity with $F$

5 $p^{*}\leftarrow\mathit{most\\_similar\\_point}(\mathcal{P}_{i},F)$

6 $k^{\prime}\leftarrow k\times\mathit{peculiarity}(R_{i})$

7 $\mathcal{H}[R_{i}]\leftarrow\mathit{top}(\mathcal{L}_{i},k^{\prime})$

8 $p_{\mathit{next}}\leftarrow\mathit{get\\_next}(\mathcal{L}_{i})$

9 while  _$\mathit{time\\_limit}$ not exceeded and
$\mathit{similarity}(p_{\mathit{next}},p^{*})\leq\mathit{similarity\\_threshold}$_
do

10 for  _$p_{\mathit{current}}\in\mathcal{H}[R_{i}]$_ do

11 if
_$\mathit{diversity\\_improved}(\mathcal{H}[R_{i}],p_{\mathit{next}},p_{\mathit{current}})$_
then
$\mathcal{H}[R_{i}]\leftarrow\mathcal{H}[R_{i}]\cup\\{p_{\mathit{next}}\\}\setminus\\{p_{\mathit{current}}\\}$

12

13 end for

14 $p_{\mathit{next}}\leftarrow\mathit{get\\_next}(\mathcal{L}_{i})$

15

16 end while

17

18 end for

return _$\mathcal{H}$_

Algorithm 3 Greedy HIGHLIGHT algorithm

Greedy approach. Inspired from [9, 36, 37], we define the relevance as the
Cosine similarity between $F$ and the POIs (note that the feedback vector $F$
and the POIs are defined over the same schema), and the quality as the
diversity between the POIs. The diversity is computed using Cosine distance
between the POI attribute values. We then follow a greedy approach for each
ROI to maximize diversity while respecting a lower bound on similarity.
Algorithm 3 summarizes this approach. The similarity values are preprocessed
and organized in $\mathcal{L}_{i}$ for all POIs in $\mathcal{P}_{i}$ (line 3
in the algorithm). The algorithm starts the greedy process by initializing a
list $\mathcal{H}[R_{i}]$ with $k^{\prime}$ POIs at the top of
$\mathcal{L}_{i}$, i.e., the most similar POIs in $\mathcal{P}_{i}$ to $F$
(line 3 in the algorithm). While a time limit is not exceeded (time limit is
an input parameter which is often set to values $\leq 500ms$ [29]), the
algorithm scans $\mathcal{L}_{i}$ sequentially to find appropriate POI
replacements in $\mathcal{H}[R_{i}]$ to improve diversity (line 3 of the
algorithm). Once the greedy loop is done, the set $\mathcal{H}$ will be
returned by the algorithm, containing the highlights for all the discovered
ROIs.

Fuzzy approach. Inspired from [38, 39, 40, 3], we employ fuzzy clustering to
process all ROIs simultaneously. Algorithm 4 summarizes this approach. The
relevance is defined in the same way as the greedy approach, and the
exploration quality is defined using two factors: cohesiveness between POIs of
the same ROI (opposite of diversity, hence measured using Cosine similarity),
and representativeness, i.e., the sum of euclidean distances between ROI
centroids. We use a weighted sum over relevance and quality where the weights
are user-defined parameters ($w_{1}$ to $w_{3}$ in line 4 of Algorithm 4).
Through several trial-and-error tests and user studies in previous works [40,
39], we found that the most ideal set of weights are $w_{1}=0.5$, $w_{2}=0.25$
and $w_{3}=0.25$. The algorithm refines the centroids of ROIs iteratively
until convergence (lines 4 to 4 in Algorithm 4). Then $k^{\prime}$ most
probable points (in fuzzy clustering semantics) will be returned as highlights
for each centroid (line 4 in Algorithm 4).

Which approach to choose? We conjecture that the greedy approach is more
appropriate for the bird’s-eye view exploration, which mainly refers to early
stages of the exploration where the user is trying to get acquainted with the
geospatial data by random explorations. In this case, ROIs do not necessarily
need to be related and may represent independent future directions. However,
in the case of more focused exploration scenarios, the fuzzy approach would be
able to deliver highlights with more coverage over the whole regions of
interest. We plan to validate these hypotheses via extensive qualitative
evaluations.

Peculiar highlighting. Recall the main objective of the highlighting component
is to return out-of-sight POIs as future analysis directions. This simply
means that the neighborhoods that have been already investigated by the user
are less peculiar, and the POIs within those regions may not be as interesting
as the ones in unexplored regions. Given an ROI $R_{i}$, we define its
peculiarity score as follows.

$\mathit{peculiarity}(R_{i})=\mathit{Cosine\\_similarity}(F,\overrightarrow{\mathcal{P}_{i}})$
(4)

Input: Discovered ROIs $\mathcal{R}$, user feedback vector $F$, $k$

Output: Highlights $\mathcal{H}$

1 $\mathcal{P}_{\mathit{all}}\leftarrow\emptyset$

2 for  _each discovered ROI $R_{i}\in\mathcal{R}$_ do

3
$\mathcal{P}_{\mathit{all}}\leftarrow\mathcal{P}_{\mathit{all}}\cup\mathit{match\\_points}(R_{i})$

4 $\mathit{centroid}_{\mathit{old}}\leftarrow\emptyset$

5
$\mathit{centroid}_{\mathit{current}}\leftarrow\mathit{get\\_centroid}(R_{i})$

6

7 end for

8$k^{\prime}\leftarrow k\times\mathit{peculiarity}(R_{i})$

9 while
_$\delta(\mathit{centroid}_{\mathit{old}},\mathit{centroid}_{\mathit{current}})$
is significant_ do

10
$\mathit{centroid}_{\mathit{old}}\leftarrow\mathit{centroid}_{\mathit{current}}$

11
$\mathit{centroid}_{\mathit{current}}\leftarrow\mathit{argmax}_{k^{\prime}}(w_{1}\times\mathit{relevance}(\mathcal{P}_{\mathit{all}}),$
$w_{2}\times\mathit{cohesiveness}(\mathcal{P}_{\mathit{all}}),$
$w_{3}\times\mathit{representativeness}(\mathcal{P}_{\mathit{all}}))$

12

13 end while

14
$\mathcal{H}\leftarrow\mathit{fuzzy\\_clusters}(\mathit{centroid}_{\mathit{current}})$

return _$\mathcal{H}$_

Algorithm 4 Fuzzy HIGHLIGHT algorithm

We then enrich the traditional $k$ parameter with the peculiarity semantics as
follows: $k^{\prime}=\lfloor k\times\mathit{peculiarity}(R_{i})\rfloor$ (line
3 in Algorithm 3 and line 4 in Algorithm 4). Note that $k^{\prime}$ is the
peculiarity-aware version of the $k$. This simply means that $k^{\prime}$ is
lower for less peculiar ROIs, and hence less POIs will be highlighted in them.
For instance, in case $F$ has already captured feedback about two-bedroom
home-stays and an ROI has only amenities with two bedrooms, that ROI will
receive a low peculiarity score, and hence very few POIs will be highlighted
in it.

##  5 Discussion on Evaluation

We plan to perform the following evaluation strategies to validate the
usefulness of IRIDEF:

Single-shot quantitative analysis. Although our approach is multi-shot, we can
consider only one iteration of our approach (CAPTURE $\rightarrow$ DISCOVER
$\rightarrow$ HIGHLIGHT) and see how the components behave in this single
iteration. The behavior can be captured through execution time and memory
consumption, as well as precision. We average over several single-shot runs.
The feedback will be captured through crowdsourcing campaigns.

Simulation study. We simulate interactive scenarios using virtual agents and
measure accumulated quality such as precision, hit ratio, and diversity.

User study. We also perform an in-depth lab study and an in-breadth
crowdsourcing study to survey real users about their perception on the
resulting regions (ROIs) and the highlights (POIs).

##  6 Conclusion and Future Work

In this paper, we present IRIDEF, an approach to interactively discover
regions of interest (ROIs) using exploratory feedback. The exploratory
feedback is captured from mouse moves over the geographical map while
analyzing spatial data. We propose a novel polygon-based mining algorithm
which returns a few highlights (POIs) in conformance with user’s exploratory
preferences. The highlights enable users to have a better understanding of
what to focus on in the followup steps in their analysis scenarios. We plan to
extend IRIDEF in several directions, such as the incorporation of multi-modal
exploratory feedback and the generation of sequential highlights as a
mobility-aware guidance.

## Acknowledgment

The author thanks Thibaut Thonet, Sruthi Viswanathan, Fabien Guillot, Jean-
Michel Renders, and Placido Neto for their constructive comments in the
process of writing this paper.

## References

  * [1] John F. Roddick, Max J. Egenhofer, Erik G. Hoel, Dimitris Papadias, and Betty Salzberg.  Spatial, temporal and spatio-temporal databases - hot issues and directions for phd research.  SIGMOD Record, 33(2):126–131, 2004.
  * [2] Zheng Xu, Yunhuai Liu, Neil Yen, Lin Mei, Xiangfeng Luo, Xiao Wei, and Chuanping Hu.  Crowdsourcing based description of urban emergency events using social media big data.  TCC, 2016.
  * [3] Sihem Amer-Yahia, Ria M Borromeo, Shady Elbassuoni, Behrooz Omidvar-Tehrani, and Sruthi Viswanathan.  Interactive generation and customization of travel packages for individuals and groups.  In IUI, 2020.
  * [4] Hangil Chung, Daniel Freund, and David B Shmoys.  Bike angels: An analysis of citi bike’s incentive program.  In SIGCAS. ACM, 2018.
  * [5] Kaiyu Feng, Gao Cong, Sourav S Bhowmick, Wen-Chih Peng, and Chunyan Miao.  Towards best region search for data exploration.  In SIGMOD, 2016.
  * [6] Cicero A. L. Pahin, Behrooz Omidvar-Tehrani, Sihem Amer-Yahia, Valerie Siroux, Jean-Louis Pepin, Jean-Christian Botel, and Comba Joao.  COVIZ: A system for visual formation and exploration of patient cohorts.  In VLDB, 2019.
  * [7] Ori Bar El, Tova Milo, and Amit Somech.  Towards autonomous, hands-free data exploration.  In CIDR, 2020.
  * [8] Arnab Nandi and H. V. Jagadish.  Guided interaction: Rethinking the query-result paradigm.  Proc. VLDB Endow., 4(12):1466–1469, 2011.
  * [9] Behrooz Omidvar-Tehrani, Plácido A. Souza Neto, Francisco B. Silva Júnior, and Felipe M. Freire Pontes.  Exploration of interesting dense regions on spatial data.  In Proceedings of the Workshops of the EDBT/ICDT 2020 Joint Conference. CEUR-WS.org, 2020.
  * [10] Lilong Jiang, Michael Mandel, and Arnab Nandi.  Gesturequery: A multitouch database query interface.  Proc. VLDB Endow., 6(12):1342–1345, 2013.
  * [11] Sruthi Viswanathan, Fabien Guillot, and Maria Antonietta Grasso.  What is natural?: Challenges and opportunities for conversational recommender systems.  In María Inés Torres, Stephan Schlögl, Leigh Clark, and Martin Porcheron, editors, Proceedings of the 2nd Conference on Conversational User Interfaces, CUI 2020, Bilbao, Spain, July 22-24, 2020, pages 40:1–40:4. ACM, 2020.
  * [12] Georg Buscher, Andreas Dengel, Ralf Biedert, and Ludger V Elst.  Attentive documents: Eye tracking as implicit feedback for information retrieval and beyond.  ACM Transactions on Interactive Intelligent Systems (TiiS), 1(2):1–30, 2012.
  * [13] J. Liang and M. L. Huang.  Highlighting in information visualization: A survey.  In 2010 14th International Conference Information Visualisation, July 2010.
  * [14] Anthony C. Robinson.  Highlighting in geovisualization.  Cartography and Geographic Information Science, 38(4):373–383, 2011\.
  * [15] Kanit Wongsuphasawat, Dominik Moritz, Anushka Anand, Jock Mackinlay, Bill Howe, and Jeffrey Heer.  Voyager: Exploratory analysis via faceted browsing of visualization recommendations.  TVCG, 22(1), 2016.
  * [16] Jie Bao, Yu Zheng, David Wilkie, and Mohamed Mokbel.  Recommendations in location-based social networks: a survey.  GeoInformatica, 19(3):525–565, 2015.
  * [17] Justin J. Levandoski, Mohamed Sarwat, Ahmed Eldawy, and Mohamed F. Mokbel.  Lars: A location-aware recommender system.  In ICDE, pages 450–461, 2012.
  * [18] Mansurul Bhuiyan, Snehasis Mukhopadhyay, and Mohammad Al Hasan.  Interactive pattern mining on hidden data: a sampling-based solution.  In Proceedings of the 21st ACM international conference on Information and knowledge management, pages 95–104. ACM, 2012.
  * [19] Dong Xin, Xuehua Shen, Qiaozhu Mei, and Jiawei Han.  Discovering interesting patterns through user’s interactive feedback.  In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 773–778. ACM, 2006.
  * [20] Kyriaki Dimitriadou, Olga Papaemmanouil, and Yanlei Diao.  Aide: an active learning-based approach for interactive data exploration.  IEEE Transactions on Knowledge and Data Engineering, 28(11):2842–2856, 2016.
  * [21] Niranjan Kamat, Prasanth Jayachandran, Karthik Tunga, and Arnab Nandi.  Distributed and interactive cube exploration.  In ICDE, 2014.
  * [22] Behrooz Omidvar-Tehrani, Sihem Amer-Yahia, and Alexandre Termier.  Interactive user group analysis.  In CIKM, pages 403–412. ACM, 2015.
  * [23] Mario Boley, Michael Mampaey, Bo Kang, Pavel Tokmakov, and Stefan Wrobel.  One click mining: Interactive local pattern discovery through implicit preference and performance learning.  In Proceedings of the ACM SIGKDD Workshop on Interactive Data Exploration and Analytics, pages 27–35. ACM, 2013.
  * [24] Eoin Mac Aoidh, Michela Bertolotto, and David C. Wilson.  Analysis of implicit interest indicators for spatial data.  In 15th ACM International Symposium on Geographic Information Systems, ACM-GIS 2007, November 7-9, 2007, Seattle, Washington, USA, Proceedings, page 47, 2007.
  * [25] Andrea Ballatore and Michela Bertolotto.  Semantically enriching vgi in support of implicit feedback analysis.  In Katsumi Tanaka, Peter Fröhlich, and Kyoung-Sook Kim, editors, Web and Wireless Geographical Information Systems, pages 78–93, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [26] Nathan N. Liu, Evan W. Xiang, Min Zhao, and Qiang Yang.  Unifying explicit and implicit feedback for collaborative filtering.  In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10, pages 1445–1448, New York, NY, USA, 2010. ACM.
  * [27] Behrooz Omidvar-Tehrani, Arnab Nandi, Nicholas Meyer, Dalton Flanagan, and Seth Young.  DV8: interactive analysis of aviation data.  In 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, CA, USA, April 19-22, 2017, pages 1411–1412. IEEE Computer Society, 2017.
  * [28] Shagun Jhaver, Yoni Karpfen, and Judd Antin.  Algorithmic anxiety and coping strategies of airbnb hosts.  In Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems, page 421. ACM, 2018.
  * [29] Jean-Daniel Fekete and Romain Primet.  Progressive analytics: A computation paradigm for exploratory data analysis.  arXiv preprint arXiv:1607.05162, 2016.
  * [30] John Krumm and Eric Horvitz.  Predestination: Inferring destinations from partial trajectories.  In UbiComp, 2006.
  * [31] Sobhan Moosavi, Behrooz Omidvar-Tehrani, R Bruce Craig, Arnab Nandi, and Rajiv Ramnath.  Characterizing driving context from driver behavior.  In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 1–4, 2017.
  * [32] Derya Birant and Alp Kut.  ST-DBSCAN: An algorithm for clustering spatial-temporal data.  Data Knowl. Eng., 60(1):208–221, January 2007.
  * [33] Ronald L. Graham.  An efficient algorithm for determining the convex hull of a finite planar set.  Info. Pro. Lett., 1:132–133, 1972.
  * [34] Luc Devroye and Godfried T Toussaint.  A note on linear expected time algorithms for finding convex hulls.  Computing, 26(4):361–366, 1981.
  * [35] Raphael A. Finkel and Jon Louis Bentley.  Quad trees a data structure for retrieval on composite keys.  Acta informatica, 4(1):1–9, 1974.
  * [36] Behrooz Omidvar-Tehrani, Plácido A. Souza Neto, Felipe M. Freire Pontes, and Francisco Bento da Silva Júnior.  Geoguide: An interactive guidance approach for spatial data.  In IEEE Smart Data, pages 1112–1117, 2017.
  * [37] Behrooz Omidvar-Tehrani, Sruthi Viswanathan, and Jean-Michel Renders.  Interactive and explainable point-of-interestrecommendation using look-alike groups.  In SIGSPATIAL, 2020.
  * [38] Vincent Leroy, Sihem Amer-Yahia, Eric Gaussier, and Hamid Mirisaee.  Building representative composite items.  In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 1421–1430, 2015.
  * [39] Manish Singh, Ria Mae Borromeo, Anas Hosami, Sihem Amer-Yahia, and Shady Elbassuoni.  Customizing travel packages with interactive composite items.  In DSAA, pages 137–145. IEEE, 2017.
  * [40] Sihem Amer-Yahia, Shady Elbassuoni, Behrooz Omidvar-Tehrani, Ria Borromeo, and Mehrdad Farokhnejad.  Grouptravel: Customizing travel packages for groups.  In EDBT, 2019.