On Computing Top-t Most Influential Spatial Sites
Tian Xia, Donghui Zhang, Evangelos Kanoulas and Yang Du
Abstract
Given a set O of weighted objects, a set S of sites, and
a query site s, the bichromatic RNN query computes the
influence set of s, or the set of objects in O
that consider s as the nearest site among all sites in
S. The influence of a site s can be defined as
the total weight of its RNNs. This paper addresses the new and
interesting problem of finding the top-t most influential sites
from S, inside a given spatial region Q. A
straightforward approach is to find the sites in Q, and compute
the RNNs of every such site. This approach is not efficient for two
reasons. First, all sites in Q need to be identified
whatsoever, and the number may be large. Second, both the site R-tree
and the object R-tree need to be browsed a large number of times. For
each site in Q, the R-tree of sites is browsed to identify the
influence region - a polygonal region that may contain RNNs,
and then the R-tree of objects is browsed to find the RNN set. This
paper proposes an algorithm called TopInfluentialSites, which
finds the top-t most influential sites by browsing both trees
once systematically. Novel pruning techniques are provided, based on
a new metric called minExistDNN. There is no need to compute
the influence for all sites in Q, or even to visit all sites in
Q. Experimental results verify that our proposed method
outperforms the straightforward approach.