Skip to main content

Top-k preferences in high dimensions

Publication ,  Journal Article
Yu, A; Agarwal, PK; Yang, J
Published in: Proceedings - International Conference on Data Engineering
January 1, 2014

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 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 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. © 2014 IEEE.

Duke Scholars

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

January 1, 2014

Start / End Page

748 / 759
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Yu, A., Agarwal, P. K., & Yang, J. (2014). Top-k preferences in high dimensions. Proceedings - International Conference on Data Engineering, 748–759. https://doi.org/10.1109/ICDE.2014.6816697
Yu, A., P. K. Agarwal, and J. Yang. “Top-k preferences in high dimensions.” Proceedings - International Conference on Data Engineering, January 1, 2014, 748–59. https://doi.org/10.1109/ICDE.2014.6816697.
Yu A, Agarwal PK, Yang J. Top-k preferences in high dimensions. Proceedings - International Conference on Data Engineering. 2014 Jan 1;748–59.
Yu, A., et al. “Top-k preferences in high dimensions.” Proceedings - International Conference on Data Engineering, Jan. 2014, pp. 748–59. Scopus, doi:10.1109/ICDE.2014.6816697.
Yu A, Agarwal PK, Yang J. Top-k preferences in high dimensions. Proceedings - International Conference on Data Engineering. 2014 Jan 1;748–759.

Published In

Proceedings - International Conference on Data Engineering

DOI

ISSN

1084-4627

Publication Date

January 1, 2014

Start / End Page

748 / 759