On Top-kk Weighted SUM Aggregate Nearest and Farthest Neighbors in the L1L_1 Plane

preprint2014arXivOpen access

Abstract

In this paper, we study top-kk aggregate (or group) nearest neighbor queries using the weighted SUM operator under the L1L_1 metric in the plane. Given a set PP of nn points, for any query consisting of a set QQ of mm weighted points and an integer kk, 1≤k≤n 1 \le k \le n, the top-kk aggregate nearest neighbor query asks for the kk points of PP whose aggregate distances to QQ are the smallest, where the aggregate distance of each point pp of PP to QQ is the sum of the weighted distances from pp to all points of QQ. We build an O(nlog⁡nlog⁡log⁡n)O(n\log n\log\log n)-size data structure in O(nlog⁡nlog⁡log⁡n)O(n\log n \log\log n) time, such that each top-kk query can be answered in O(mlog⁡m+(k+m)log⁡2n)O(m\log m+(k+m)\log^2 n) time. We also obtain other results with trade-off between preprocessing and query. Even for the special case where k=1k=1, our results are better than the previously best method (in PODS 2012), which requires O(nlog⁡2n)O(n\log^2 n) preprocessing time, O(nlog⁡2n)O(n\log^2 n) space, and O(m2log⁡3n)O(m^2\log^3 n) query time. In addition, for the one-dimensional version of this problem, our approach can build an O(n)O(n)-size data structure in O(nlog⁡n)O(n\log n) time that can support O(min⁡{k,log⁡m}⋅m+k+log⁡n)O(\min\{k,\log m\}\cdot m+k+\log n) time queries. Further, we extend our techniques to the top-kk aggregate farthest neighbor queries, with the same bounds.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.