Given a set of objects, each with multiple numeric attributes, a (preference) top-k query retrieves the k objects with the highest scores according to a user preference, defined as a linear combination of attribute values. We consider the problem of processing a large number of continuous top-k queries, each with its own weights on attributes. When objects change, the query results must be updated. We present a dynamic index that supports the reverse top-k query, which is of independent interest. Combining this index with another one for top-k queries, we develop a scalable solution for processing many continuous top-k queries that naturally exploits the clusteredness in user preferences. We also define an approximate version of the problem and present a solution significantly more efficient than the exact one with little loss in accuracy.
Next, we develop a solution for supporting preference and reverse top-k queries in high dimensions 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 carefully select 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.