Top k Preferences in High Dimensions
Given a set of objects \mathcal {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 \mathcal {O} with highest scores with respect to $q$ Given a query object $o$ and a set of preferences \mathcal {Q} a reverse top $k$ query finds 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 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.
IEEE Trans. Knowl. Data Eng.