13 Apr 2006
On Computing Top-t Most Influential Spatial Sites
Speaker: Martin DAI Xiangyuan
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
TopInfluential-Sites, 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.
Read the Presentation
Slides...
|