On top-k weighted sum aggregate nearest and farthest neighbors in the L₁ plane

Abstract: In this paper, we study top-

k

aggregate (or group) nearest neighbor queries using the weighted SUM operator under the

L_{1}

metric in the plane. Given a set

P

of

n

points, for any query consisting of a set

Q

of

m

weighted points and an integer

k

,

1 l e k l e n

, the top-

k

aggregate nearest neighbor query asks for the

k

points of

P

whose aggregate distances to

Q

are the smallest, where the aggregate distance of each point

p

of

P

to

Q

is the sum of the weighted distances from

p

to all points of

Q

. We build an

O (n l o g n l o g l o g n)

-size data structure in

O (n l o g n l o g l o g n)

time, such that each top-

k

query can be answered in

O (m l o g m + (k + m) l o g^{2} n)

time. We also obtain other results with trade-off between preprocessing and query. Even for the special case where

k = 1

, our results are better than the previously best method (in PODS 2012), which requires

O (n l o g^{2} n)

preprocessing time,

O (n l o g^{2} n)

space, and

O (m^{2} l o g^{3} n)

query time. In addition, for the one-dimensional version of this problem, our approach can build an

O (n)

-size data structure in

O (n l o g n)

time that can support

O (m i n k, l o g m c d o t m + k + l o g n)

time queries. Further, we extend our techniques to the top-

k

aggregate farthest neighbor queries, with the same bounds.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: On top-\(k\) weighted sum aggregate nearest and farthest neighbors in the \(L_1\) plane