2011 | OriginalPaper | Buchkapitel
Aggregate Farthest-Neighbor Queries over Spatial Data
verfasst von : Yuan Gao, Lidan Shou, Ke Chen, Gang Chen
Erschienen in: Database Systems for Advanced Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study a new type of spatial query, namely
aggregate k farthest neighbor
(AkFN) search. Given a data point set
P
, a query point set
Q
, an AkFN query returns
k
points in
P
with the largest aggregate distances to all points in
Q
. For instance, it is reasonable to build a new hotel where the aggregate distances to all existing hotels are maximized to reduce competition. Our investigation of AkFN queries focuses on three aggregate functions, namely
Sum
,
Max
and
Min
. Assuming that the data set is indexed by R-tree, we propose two algorithms, namely
minimum bounding
(MB) and
best first
(BF), for efficiently solving AkFN queries with all three aggregate functions. The BF algorithm is incremental and IO optimal. Extensive experiments on both synthetic and real data sets confirm the efficiency and effectiveness of our proposed algorithms.