Answering Why-not Questions on Reverse Top-k Queries

• Main Authors: GAO, Yunjun, LIU, Qing, CHEN, Gang, ZHENG, Baihua, ZHOU, Linlin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Ranked queries; algorithms; products; Computer Sciences; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/2895; https://ink.library.smu.edu.sg/context/sis_research/article/3895/viewcontent/ZhengBH_2015_vldb_AnsweringWhyNot.pdf
• Institution: Singapore Management University

Why-not questions, which aim to seek clarifications on the missing tuples for query results, have recently received considerable attention from the database community. In this paper, we systematically explore why-not questions on reverse top-k queries, owing to its importance in multi-criteria decision making. Given an initial reverse top-k query and a missing/why-not weighting vector set Wm that is absent from the query result, why-not questions on reverse top-k queries explain why Wm does not appear in the query result and provide suggestions on how to refine the initial query with minimum penalty to include Wm in the refined query result. We first formalize why-not questions on reverse top-k queries and reveal their semantics, and then propose a unified framework called WQRTQ to answer why-not questions on both monochromatic and bichromatic reverse top-k queries. Our framework offers three solutions, namely, (i) modifying a query point q, (ii) modifying a why-not weighting vector set Wm and a parameter k, and (iii) modifying q, Wm, and k simultaneously, to cater for different application scenarios. Extensive experimental evaluation using both real and synthetic data sets verifies the effectiveness and efficiency of the presented algorithms.