Math @ Duke

Publications [#350111] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sintos, S; Steiger, A, Efficient Indexes for Diverse Topk Range Queries,
Proceedings of the Acm Sigact Sigmod Sigart Symposium on Principles of Database Systems
(June, 2020),
pp. 213227, ISBN 9781450371087 [doi]
(last updated on 2021/05/17)
Abstract: Let P be a set of n (nonnegatively) weighted points in Rd. We consider the problem of computing a subset of (at most) k diverse and highvalued 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: Nearlinear time (0.5ϵ)approximation algorithms for the bicriteria optimization problem in the offline setting. Nearlinear 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. Nearlinear 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

