所属单位：计算机科学与技术学院/人工智能学院/软件学院
发表刊物：Lect. Notes Comput. Sci.
摘要：Extracting interesting points from a large dataset is an important problem for multi-criteria decision making. Recently, k-regret query was proposed and received attentions from the database community because it does not require any utility function from users and the output size is controllable. In this paper, we consider k-regret queries with binary constraints which doesn’t be addressed before. Given a collection of binary constraints, we study the problem of extracting the k representative points with small regret ratio while satisfying the binary constraints. To express the satisfaction of data points by the binary constraints, we propose two models named NBC and LBC in quantitative and qualitative ways respectively. In quantitative way, the satisfaction is expressed by a real number between 0 and 1 which quaNtifies the satisfaction of a point by the Binary Constraints. While in qualitative way, the satisfaction is modeled quaLitatively by a set of Binary Constraints which are satisfied by the point. Further, two efficient approximate algorithms called -Greedy and -Greedy are developed based on NBC while -Greedy algorithm is proposed based on LBC. Extensive experiments on synthetic and real datasets confirm the efficiency and effectiveness of our proposed algorithms. © 2018, Springer Nature Switzerland AG.
ISSN号：0302-9743
是否译文：否
发表时间：2018-01-01
合写作者：郑吉平,Qiu, Xianhong,Huang, Xingnan
通讯作者：蒋冬青
发表时间：2018-01-01