遗憾最小化查询研究综述  

Survey on Regret Minimization Queries

作　　者：郑吉平[1,2] 马源 马炜 郝志扬 王美静 ZHENG Ji-ping;MA Yuan;MA Wei;HAO Zhi-yang;WANG Mei-jing(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China;Collaborative Innovation Center of Novel Software Technology and Industrialization,Nanjing 210093,China)

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京211106 [2]软件新技术与产业化协同创新中心,南京210093

出　　处：《小型微型计算机系统》2022年第2期236-246,共11页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(U1733112,61702260)资助;中央高校基本科研业务费专项资金项目(NS2020068)资助。

摘　　要：面临大量数据时,如何从中摘取一部分感兴趣的数据帮助用户进行决策是数据库系统的一项重要功能.在过去几十年里,top-k和skyline查询是两种最常用的技术手段,但他们分别存在不能控制输出结果大小与需要用户提供效用函数的缺陷.为克服两者的缺陷,k代表点查询技术应运而生;其中性质较好、受到较多关注的是k-遗憾查询.本文首先回顾了skyline、top-k查询和几种典型的代表点查询.随后,详细地介绍了k-遗憾查询的概念与方法,从多个角度分析了提升查询质量的途径,并对k-遗憾查询的变体进行了研究.最后对未来遗憾最小化查询的可能研究方向与应用前景进行了展望.Extracting interesting points from a large database is an important functionality of database systems to help users make decisions when facing massive data.Skyline and top-k queries are two important tools in the past decades;however,skyline queries cannot control the output size and top-k queries require users to provide utility functions.To overcome these deficiencies,k-representative queries have been proposed,among which the k-regret query has attracted much attention due to its nice properties.In this survey,we first review skyline and top-k queries,and several typical k-representative queries.Then,the concepts and methods of k-regret queries are introduced.Further,we analyze several approaches to improve the query quality from different aspects.We also investigate the variants of regret queries.At length,we provide possible research directions and applications for regret minimization queries.

关 键 词：k-遗憾查询 SKYLINE查询 TOP-K查询 多准则决策 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]