Processing a large number of continuous preference top-k queries


Journal Article

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 preference. When objects or user preferences 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 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. © 2012 ACM.

Full Text

Duke Authors

Cited Authors

  • Yu, A; Agarwal, PK; Yang, J

Published Date

  • June 28, 2012

Published In

Start / End Page

  • 397 - 408

International Standard Serial Number (ISSN)

  • 0730-8078

Digital Object Identifier (DOI)

  • 10.1145/2213836.2213882

Citation Source

  • Scopus