k-Pleased Querying

• Published in: IEEE transactions on knowledge and data engineering 2023-04, Vol.35 (4), p.4003-4017
• Main Authors: Chen, Zitong, Fu, Ada Wai-Chee, Long, Cheng, Wu, Yang
• Format: Article
• Language: English
• Subjects: Automobiles; Datasets; Furnaces; Greedy algorithms; k-pleased querying; k-regret; Measurement; Random sampling; Sampling methods; Stability analysis; Temperature distribution; top-k querying; Utility functions
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2021.3132992

k-Regret Querying is a well studied problem to query a dataset D D for a small subset S S of size k k with the minimal regret ratio for unknown utility functions. In this paper, we point out some issues in k k -Regret Querying, including the assumption of non-negative dataset and the lack of shift invariance. Known algorithms for k k -Regret Querying are limited in scope and result quality, and are based on the assumption of non-negative data. We introduce a new problem definition called k k -pleased querying for dealing with the shift variance issue, and propose a strategy of random sampling of the utility functions. This strategy is based on a study of the theoretical guarantee of the sampling approach. We also introduce a dimensionality reduction strategy, an improved greedy algorithm, and a study of other utility function sampling methods. All of our solutions can handle negative data. Theoretically, we derive a guarantee on the approximation attained by our sampling algorithm. Experimental results on numerous real datasets show that our proposed method is effective even with a small number of samples and small values of k k .