Efficient Indexes for Diverse Top-k Range Queries
Efficient Indexes for Diverse Top-k Range Queries
复制标题
DOI：
10.1145/3375395.3387667
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
P. Agarwal;Stavros Sintos;Alex Steiger
中科院分区：
文献类型：
--
作者：
P. Agarwal;Stavros Sintos;Alex Steiger
令 P 为 Rd 中 n 个（非负）加权点的集合。我们考虑计算位于查询范围内的（至多）k 个不同且高价值的 P 点的子集的问题，该问题与搜索引擎、推荐系统和在线商店等许多领域相关。一组点的多样性和价值分别作为其成对距离和权重的函数（例如平均值或最小值）来测量。我们研究双标准和约束优化问题。在前者中，我们希望返回一组 k 个点，以最大化其价值和多样性度量的加权和，而在后者中，我们希望返回一组最多 k 个点，以最大化其价值并满足多样性约束。我们在本文中获得了三种主要类型的结果： 离线设置中双标准优化问题的近线性时间 (0.5-ε) 近似算法。双标准优化问题的近线性大小索引，对于查询矩形，在 O(k polylog(n)) 时间内返回 (0.5-ε) 近似解。索引可以在 O(n polylog(n)) 时间内构建。用于回答受限优化范围查询的近线性大小索引。对于查询矩形，可以在 O(k polylog(n)) 时间内计算出 0.5O(d) 近似解。如果我们允许一些返回点位于查询矩形之外最多 ε 处，则可以在 O(k polylog(n)) 时间内计算出 (1-ε) 近似解。索引的构建时间分别为 O(n polylog(n)) 和 nO(1/εd)。
Let P be a set of n (non-negatively) weighted points in Rd. We consider the problem of computing a subset of (at most) k diverse and high-valued points of P that lie inside a query range, a problem relevant to many areas such as search engines, recommendation systems, and online stores. The diversity and value of a set of points are measured as functions (say average or minimum) of their pairwise distances and weights, respectively. We study both bicriteria and constrained optimization problems. In the former, we wish to return a set of k points that maximize a weighted sum of their value and diversity measures, and in the latter, we wish to return a set of at most k points that maximize their value and satisfy a diversity constraint. We obtain three main types of results in this paper: Near-linear time (0.5-ε)-approximation algorithms for the bicriteria optimization problem in the offline setting. Near-linear size indexes for the bicriteria optimization problem that for a query rectangle return a (0.5-ε)-approximate solution in time O(k polylog(n)). The indexes can be constructed in O(n polylog(n)) time. Near-linear size indexes for answering constrained optimization range queries. For a query rectangle, a 0.5O(d)-approximate solution can be computed in O(k polylog(n)) time. If we allow some of the returned points to lie at most ε outside of the query rectangle then an (1-ε)-approximate solution can be computed in O(k polylog(n)) time. The indexes are constructed in O(n polylog(n)) and nO(1/εd) time, respectively.