从大型数据库中查找出用户最感兴趣的k个数据来支持用户多标准决策的制定是数据库领域一个重要的研究课题。k遗憾查询使用最大遗憾率的衡量标准,返回k个使得用户的最大遗憾率最小的数据。但是,目前已有的关于k遗憾查询的研究存在效率较低和结果集会偏向于最不满意的用户的问题。论文针对k遗憾查询存在的问题,研究了基于用户开心度的k代表点选取技术,结合目标函数函数的特性,给出了高效的解决方案。主要工作和创新点如下:(1)研究了k代表点代表性的衡量标准。针对现有的k代表点代表性的衡量标准,论文详细地分析了它们的优缺点,并提出通过最小开心度和平均开心度的衡量标准来更好地对返回的k个代表点的质量进行衡量。(2)研究了基于用户最小开心度的k代表点查询处理技术。论文首先提出了最小开心度的衡量标准,并证明了最小开心度函数是单调非减的。基于这一特性,提出了延迟评估的加速策略来减少k遗憾查询所需要的函数评估次数。此外,引入随机采样技术来缩小k遗憾率查询候选集的大小。最后,基于延迟评估的加速策略和随机采样技术,论文提出了两个高效的算法。实验表明通过减少k遗憾查询所需要的函数评估次数,论文提出的算法可以有效提高k遗憾查询的效率。(3)研究了基于用户平均开心度的k代表点查询处理技术。为了解决k遗憾查询会偏向最不满意的用户的问题,论文提出利用平均开心度的标准来更好地衡量用户在只看到k个返回的数据点而不是整个数据库中所有数据点时的满意程度,给出了平均开心度最大化的问题定义并证明了该问题是一个NP-hard问题。此外,论文发现平均开心度函数满足子模的特性,基于该特性并结合延迟评估的加速策略和随机采样技术,论文提出了高效的具有理论保证的近似算法并给出了详细的理论分析。实验表明论文提出的算法在查询效率和结果集的质量方面都优于已有的查询。