Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1109/TKDE.2015.2451630 | IEEE Transactions on Knowledge and Data Engineering |
Keywords | Field | DocType |
High Dimension,Personalization,Query Processing,Reverse Top-k,Top-k | Data mining,Linear combination,Subspace topology,Computer science,Workload,Curse of dimensionality,Linear subspace | Conference |
Volume | Issue | ISSN |
PP | 99 | 1041-4347 |
Citations | PageRank | References |
3 | 0.37 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Albert Yu | 1 | 59 | 4.09 |
Pankaj K. Agarwal | 2 | 5257 | 593.81 |
Jun Yang | 3 | 2762 | 241.66 |