ML p(r)ior | Reverse Nearest Neighbor Heat Maps: A Tool for Influence Exploration

Reverse Nearest Neighbor Heat Maps: A Tool for Influence Exploration

2016-02-01
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-05-13

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-05-17

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

Highlights - Most important sentences from the article

2018-09-28

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-02-07

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

Highlights - Most important sentences from the article

2019-02-19

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-10-30

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
PDF

Highlights - Most important sentences from the article

2018-12-29

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

Highlights - Most important sentences from the article

2019-03-12
1903.05255 | cs.CG

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

Highlights - Most important sentences from the article

2019-04-24

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

Highlights - Most important sentences from the article

2018-10-22

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

Highlights - Most important sentences from the article

2018-12-04

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

Highlights - Most important sentences from the article

2018-10-27

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

Highlights - Most important sentences from the article

2018-10-30
1810.12826 | cs.CG

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