Skip to main content

Top-k Preferences in High Dimensions

Publication ,  Journal Article
Yu, A; Agarwal, PK; Yang, J
Published in: IEEE Transactions on Knowledge and Data Engineering
February 1, 2016

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.

Duke Scholars

Published In

IEEE Transactions on Knowledge and Data Engineering

DOI

ISSN

1041-4347

Publication Date

February 1, 2016

Volume

28

Issue

2

Start / End Page

311 / 325

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Yu, A., Agarwal, P. K., & Yang, J. (2016). Top-k Preferences in High Dimensions. IEEE Transactions on Knowledge and Data Engineering, 28(2), 311–325. https://doi.org/10.1109/TKDE.2015.2451630
Yu, A., P. K. Agarwal, and J. Yang. “Top-k Preferences in High Dimensions.” IEEE Transactions on Knowledge and Data Engineering 28, no. 2 (February 1, 2016): 311–25. https://doi.org/10.1109/TKDE.2015.2451630.
Yu A, Agarwal PK, Yang J. Top-k Preferences in High Dimensions. IEEE Transactions on Knowledge and Data Engineering. 2016 Feb 1;28(2):311–25.
Yu, A., et al. “Top-k Preferences in High Dimensions.” IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 2, Feb. 2016, pp. 311–25. Scopus, doi:10.1109/TKDE.2015.2451630.
Yu A, Agarwal PK, Yang J. Top-k Preferences in High Dimensions. IEEE Transactions on Knowledge and Data Engineering. 2016 Feb 1;28(2):311–325.

Published In

IEEE Transactions on Knowledge and Data Engineering

DOI

ISSN

1041-4347

Publication Date

February 1, 2016

Volume

28

Issue

2

Start / End Page

311 / 325

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences