Exact processing of uncertain top-k queries in multi-criteria settings

• Main Authors: MOURATIDIS, Kyriakos, TANG, Bo
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Databases and Information Systems; Data Storage Systems; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/4141; https://ink.library.smu.edu.sg/context/sis_research/article/5145/viewcontent/VLDB18_UTK.pdf
• Institution: Singapore Management University

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.