Top-$k$ Preferences in High Dimensions
Albert Yu, Pankaj K. Agarwal, Jun Yang · IEEE Transactions on Knowledge and Data Engineering · 2015
Given a set of objects$\mathcal {O}$, each with$d$numeric attributes, atop-$k$preferencescores 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$, atop-$k$queryfinds the$k$objects in$\mathcal {O}$with highest scores with respect to$q$. Given a query object$o$and a set of preferences$\mathcal {Q}$, areverse top-$k$queryfinds all preferences$q\in \mathcal {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 exhibitsparsity—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-dimensionalcore subspacesto “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.