Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2018

Abstract

Traditional rank-aware processing assumes a dataset that contains available options to cover a specific need (e.g., restaurants, hotels, etc) and users who browse that dataset via top-k queries with linear scoring functions, i.e., by ranking the options according to the weighted sum of their attributes, for a set of given weights. In practice, however, user preferences (weights) may only be estimated with bounded accuracy, or may be inherently uncertain due to the inability of a human user to specify exact weight values with absolute accuracy. Motivated by this, we introduce the uncertain top-k query (UTK). Given uncertain preferences, that is, an approximate description of the weight values, the UTK query reports all options that may belong to the top-k set. A second version of the problem additionally reports the exact top-k set for each of the possible weight settings. We develop a scalable processing framework for both UTK versions, and demonstrate its efficiency using standard benchmark datasets.

Discipline

Databases and Information Systems | Data Storage Systems | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

Proceedings of the VLDB Endowment: 44th VLDB 2018, August 27-31, Rio de Janeiro, Brazil

First Page

866

Last Page

879

Identifier

10.14778/3204028.3204031

Publisher

VLDB Endowment

City or Country

Stanford, CA

Copyright Owner and License

Publisher

Additional URL

https://doi.org/10.14778/3204028.3204031

Download

Share

COinS