Math @ Duke

Publications [#235354] of Pankaj K. Agarwal
Papers Published
 Yu, A; Agarwal, PK; Yang, J, Topk preferences in high dimensions,
Proceedings International Conference on Data Engineering
(January, 2014),
pp. 748759, ISSN 10844627 [doi]
(last updated on 2018/09/22)
Abstract: Given a set of objects O, each with d numeric attributes, a topk preference scores these objects using a linear combination of their attribute values, where the weight on each attribute reflects the interest in this attribute. Given a query preference q, a topk query finds the k objects in O with highest scores with respect to q. Given a query object o and a set of preferences Q, a reverse topk query finds all preferences q ∈ Q for which o becomes one of the top k objects with respect to q. Previous solutions to these problems are effective only in low dimensions. In this paper, we develop a solution for much higher dimensions (up to high tens), if many preferences exhibit sparsity  i.e., each specifies nonzero weights for only a handful (say 57) of attributes (though the subsets of such attributes and their weights can vary greatly). Our idea is to select carefully a set of lowdimensional core subspaces to 'cover' the sparse preferences in a workload. These subspaces allow us to index them more effectively than the fulldimensional space. Being multidimensional, each subspace covers many possible preferences; furthermore, multiple subspaces can jointly cover a preference, thereby expanding the coverage beyond each subspace's dimensionality. Experimental evaluation validates our solution's effectiveness and advantages over previous solutions. © 2014 IEEE.


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

