【摘 要】
：
从大量数据中查找用户所需信息来协助用户制定多目标决策是数据库领域中一个重要的研究方向。Top-k查询和Skyline查询被广泛用来解决此类问题,但是它们有着本质的缺陷。遗憾最小化查询也能够很好地解决此类问题,它综合了Top-k查询和Skyline查询的优点,但是现有的遗憾最小化查询算法效率不高或者缺乏理论保证。论文针对已有算法存在的缺陷,设计出具有理论保证的高效的近似算法。论文主要工作和创新点如下
论文部分内容阅读
从大量数据中查找用户所需信息来协助用户制定多目标决策是数据库领域中一个重要的研究方向。Top-k查询和Skyline查询被广泛用来解决此类问题，但是它们有着本质的缺陷。遗憾最小化查询也能够很好地解决此类问题，它综合了Top-k查询和Skyline查询的优点，但是现有的遗憾最小化查询算法效率不高或者缺乏理论保证。论文针对已有算法存在的缺陷，设计出具有理论保证的高效的近似算法。论文主要工作和创新点如下：
（1）研究基于采样技术的高效的遗憾最小化查询算法。针对已有的遗憾最小化查询算法效率较低或在某些场景下无法工作等缺陷，论文首先将遗憾率函数转化成开心度函数，并重新设计经典的贪婪算法，详述算法线性规划的计算方式，并论证改进后的算法的选点正确性。为了进一步提高算法的运行效率，利用随机采样技术设计出更高效的算法。大量实验表明基于采样的算法的运行效率较高的同时最大遗憾率也较小，并且算法在不同场景下都能够很好地运行。
（2）研究利用子模理论证明算法的近似率。论文首先介绍子模函数的定义，然后论述开心度函数和最小开心度函数的性质，以及它们与子模函数之间的联系。通过引入子模率和曲率的概念，结合基于开心度的贪婪算法，证明算法的近似率，补足经典贪婪算法没有理论保证的缺陷。此外，基于采样的算法的近似率也通过子模率和随机采样理论给出。
（3）研究基于单调性和采样的高效的k-遗憾最小化查询算法。论文首先说明了遗憾率函数在某些情况下可能不太适用，因此将研究拓展到k-遗憾率函数上，相关的查询也变为k-遗憾最小化查询。之后论述此类问题是 NP 难题，并针对已有算法的低效性，提出高效的贪婪算法，同时利用函数单调性对算法进行加速。此外，将随机采样技术加入到算法中，提出基于采样的贪婪算法，并分析与先前贪婪算法的结果集之间的联系。实验表明论文中设计的算法比已有的算法更加具有优势。
其他文献
随着互联网技术的快速发展和各种传感器的普及，人们能够非常便捷地获得海量时序数据，这些数据蕴含了丰富的内隐信息，广泛存在于安全监测、人机交互以及电子对抗等领域，如何对时序数据特征进行有效建模，有效提取内隐信息是时序数据分析需要解决的关键科学和技术问题，具有重要的理论意义和应用价值。传统时序数据分析方法主要是基于传统机器学习和模式识别等技术，存在模型特征表达能力较弱、时序数据特征建模困难等不足。深度学
现实世界中，各种各样的复杂系统，例如社交网络、计算机网络、化学分子网络、蛋白质交互网络、引文网络等都能高度抽象成图的形式。图表示学习旨在为图中的每个节点或整个图学习一个低维、稠密、实值的向量表示，从而便于后续的网络分析任务，例如节点分类、链接预测、节点可视化、图分类、社区发现、影响力最大化等。传统的图表示学习方法面临着计算效率和存储效率的问题，且图数据的复杂性给传统的机器学习算法带来了重大的挑战。
该文深入研究了异步电动机直接转矩控制方法的基本原理,在分析交流异步电动机数学模型的基础上,详细阐述了电压空间矢量、磁链加速与磁链幅值控制、转矩直接控制等直接转矩控制的基础理论,分析了直接转矩控制系统的系统结构,指明直接转矩控制方式下电机转矩性能的特点,提出一种系统的软启动方案和电流限制措施.该文对基于高速数字信号处理器TMS320F240的直接转矩数字化控制系统的软硬件设计作了初步的探讨,详细介绍
癌症是非常严重的疾病。癌细胞的快速生长侵袭是导致癌症致死率高的主要原因，因此分析癌细胞的侵袭特性非常有实用价值，能够作为指导抗癌药物研究的工具。当前称作器官芯片的细胞体外培养技术已经取得了非常大的进步，其中体外肿瘤模型可以模拟肿瘤在复杂的人体内环境的生长状态。分析体外肿瘤模型的相关的参数可以作为判断药物作用下癌细胞状态的重要指标。随着图像处理技术的发展，基于图像的癌细胞状态分析是一种简单快速的方式
随着互联网及其应用的迅猛发展，新兴应用需求层出不穷，这对网络服务能力提出了新的挑战。传统网络协议的针对性开发部署、协议之间过多的功能性冗余、协议过高的开发及部署成本等都制约着网络实现服务扩展的能力。因此，网络能否实现服务可扩展成为未来网络发展的核心，也是未来网络体系结构研究的关键问题。 目前，针对未来网络服务可扩展的相关研究基本上都侧重于解决制约传统网络实现服务扩展的某些因素，缺乏对网络服务可扩
协同过滤是目前最常用的推荐技术，其能够为用户提供个性化的推荐服务，从而有效缓解信息过载问题。然而，协同过滤需要用户上传个人历史数据，存在隐私泄露风险。即使通过传统的匿名技术对用户数据进行模糊处理，攻击者仍可通过去匿名等攻击手段推断用户的隐私。差分隐私是对于隐私的严格定义，能够对用户隐私提供保证。因此，设计面向协同过滤推荐的差分隐私机制已成为当前的研究热点。 现有研究工作从隐私保护机制的部署方式角
随着云计算、社交网络、数据挖掘等信息技术的大规模应用，信息泄露等安全问题日益突出。作为现有的保密通信方法的补充，混沌保密通信成为保密通信的一个新的发展方向，主要解决传统加密方法对视频、图像等实时性要求高的大数据量的数据加密效率低的问题，在兼顾成本和实时性的前提下，具有更高的安全性，并且可以融合现有的加密机制建立跨层的联合安全保障体系。分数阶时滞混沌系统具有多个正的Lyapunov指数，时滞参数引入
物联网(IoT)利用传感器感知技术、特征识别技术、和云计算等技术,将控制器、执行器、传感器、等智能部件和人连接在一起,实现物物互联,是智能网络的终极形态。其中,大量设备催生了大量的数据共享与数据融合的需求,可靠的数据共享能够促进不同设备之间的相互协作,对于物联网的智能化、帮助节点克服不确定性、提高对风险的感知具有十分重要的意义。本文以车联网(IoV)与无人机(UAVs)网络为例,分别提出了基于区块
近年来中国民用飞机及系统的研制进展非常迅速,随着飞机功能及系统复杂度的快速增长,与飞机系统安全性紧密相关的航电系统及软件的设计与分析方法已经成为领域中的热点问题。在ARP4754以及DO-178C等民机研制标准中所定义的系统工程/软件工程过程中非常强调在软件产品生命周期开始时构造完整、一致且组织良好的系统/软件需求,并开始引入了基于模型的系统工程(Model Based System Engine
由于信息技术的进步,人们越来越频繁地在社交网络中分享各种照片。其中,以人为主体的照片占据了极大比重,特别是那些围绕人脸的照片。人脸属性识别的任务是分析人脸的生物描述,在人脸搜索等众多领域有广泛应用,因此具有重要的研究意义。随着机器学习的发展,学界涌现出许多人脸属性识别相关研究。然而,目前很多研究割裂了人脸属性之间的关系,并采用单任务学习方式。虽然一些研究开始使用多任务学习,但大部分仅针对个别属性。