Top-k Preferences in High Dimensions
Published
Journal Article
© 1989-2012 IEEE. Given a set of objects O, each with d numeric attributes, a top-k 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 top- k 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 top- k query finds all preferences in 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 non-zero weights for only a handful (say 5 - 7) of attributes (though the subsets of such attributes and their weights can vary greatly). Our idea is to select carefully a set of low-dimensional core subspaces to 'cover' the sparse preferences in a workload. These subspaces allow us to index them more effectively than the full-dimensional space. Being multi-dimensional, 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.
Full Text
Duke Authors
Cited Authors
- Yu, A; Agarwal, PK; Yang, J
Published Date
- February 1, 2016
Published In
Volume / Issue
- 28 / 2
Start / End Page
- 311 - 325
International Standard Serial Number (ISSN)
- 1041-4347
Digital Object Identifier (DOI)
- 10.1109/TKDE.2015.2451630
Citation Source
- Scopus