### Reverse Nearest Neighbor Heat Maps: A Tool for Influence Exploration

**2016-02-01**

1602.00389 | cs.DB

We study the problem of constructing a reverse nearest neighbor (RNN) heat
map by finding the RNN set of every point in a two-dimensional space. Based on
the RNN set of a point, we obtain a quantitative influence (i.e., heat) for the
point. The heat map provides a global view on the influence distribution in the
space, and hence supports exploratory analyses in many applications such as
marketing and resource management. To construct such a heat map, we first
reduce it to a problem called Region Coloring (RC), which divides the space
into disjoint regions within which all the points have the same RNN set. We
then propose a novel algorithm named CREST that efficiently solves the RC
problem by labeling each region with the heat value of its containing points.
In CREST, we propose innovative techniques to avoid processing expensive RNN
queries and greatly reduce the number of region labeling operations. We perform
detailed analyses on the complexity of CREST and lower bounds of the RC
problem, and prove that CREST is asymptotically optimal in the worst case.
Extensive experiments with both real and synthetic data sets demonstrate that
CREST outperforms alternative algorithms by several orders of magnitude.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-05-13**

1905.05066 | cs.CG

Let P be a set of n points and each of the points is colored with one of the
k possible colors. We p… show more

**2018-09-27**

1809.10531 | cs.CG

In the range closest pair problem, we want to construct a data structure
storing a set $S$ of $n$ po… show more

**2019-05-17**

1905.07124 | cs.CG

Classical separability problem involving multi-color point sets is an
important area of study in com… show more

**2018-09-28**

1809.11147 | cs.CG

For any constant $d$ and parameter $\varepsilon > 0$, we show the existence
of (roughly) $1/\varepsi… show more

**2019-03-15**

1903.06785 | cs.CG

Given a set of $n$ points in the plane, and a parameter $k$, we consider the
problem of computing th… show more

**2019-02-07**

1902.02660 | cs.LG

In Statistical Learning, the Vapnik-Chervonenkis (VC) dimension is an
important combinatorial proper… show more

**2019-02-19**

1902.06875 | cs.CG

We show new applications of the nearest-neighbor chain algorithm, a technique
that originated in agg… show more

**2019-03-16**

1903.06904 | cs.CG

The k-means for lines is a set of k centers (points) that minimizes the sum
of squared distances to … show more

**2017-10-30**

1710.10888 | cs.CG

Let $P$ be a set of $n$ points in the plane. We compute the value of
$\theta\in [0,2\pi)$ for which … show more

**2018-12-29**

1812.11332 | cs.CG

We study several problems concerning convex polygons whose vertices lie in a
Cartesian product (for … show more

**2019-03-12**

1903.05255 | cs.CG

We revisit a classical graph-theoretic problem, the \textit{single-source
shortest-path} (SSSP) prob… show more

**2019-04-24**

1904.11026 | cs.CG

We study two fundamental problems dealing with curves in the plane, namely,
the nearest-neighbor pro… show more

**2018-10-22**

1810.09232 | cs.CG

Let $P$ be a set of $n$ colored points in the plane. Introduced by Hart
(1968), a consistent subset … show more

**2018-12-04**

1812.01663 | cs.DB

Skyline queries are important in many application domains. In this paper, we
propose a novel structu… show more

**2018-10-27**

1810.11628 | cs.CG

We propose a new $(1+O(\varepsilon))$-approximation algorithm with $O(n+
1/\varepsilon^{\frac{(d-1)}… show more

**2018-10-30**

1810.12826 | cs.CG

$\renewcommand{\Re}{{\rm I\!\hspace{-0.025em} R}}
\newcommand{\eps}{{\varepsilon}} \newcommand{\Core… show more