Skyline查询处理算法研究

来源 :哈尔滨工业大学 | 被引量 : 0次 | 上传用户:caikesbad
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着信息技术的飞速发展,各行各业都迎来了大数据时代。面对如此庞大的数据量,数据管理系统显得尤其重要。数据查询处理技术作为数据管理系统中最重要的组成部分之一,可以快速地、直观地反映数据的各种特性,为用户的决策提供参考和帮助。目前为止,数据管理系统中最常见的查询有Skyline查询、最近邻查询、Top-k查询、聚集查询、Join查询、相似性查询等。其中,Skyline查询是一种重要的多维度偏好查询,在多维度决策、个性化推荐、数据挖掘等领域有着广泛的应用。Skyline查询处理问题已经得到了国内外学者的广泛关注,并将其扩展到许多不同的环境中。然而,现有的研究工作在基于空间划分的Skyline查询处理、不完整数据上的Skyline查询处理、不确定数据上的Skyline查询处理和G-Skyline查询处理等方面仍有许多不足。因此,本文主要在这四个方面进行研究,成果如下:
  首先,本文研究了基于空间划分的Skyline查询处理问题。Skyline查询处理算法大致分成两类:一类是基于索引的,另一类则不需要索引结构。尽管基于索引的Skyline查询处理算法效率很高,但是索引结构的构建面临维度灾难问题,所需时间和空间代价巨大。目前最优的非索引Skyline查询处理算法是基于空间划分框架。然而,现有的基于空间划分的Skyline查询处理算法忽略了均匀划分对空间划分框架的重要性,降低了算法性能。为此,本文提出了基于空间划分的Skyline查询处理算法VMPSP。VMPSP算法通过构造虚拟中点作为划分点对集合进行递归划分,使得划分更加均匀,降低划分次数和检验点与空间划分树中Skyline点的比较次数,提高了计算Skyline的效率。本文分析了算法的时间复杂度并通过实验验证了算法的高效性。
  其次,本文研究了不完整数据上的Skyline查询处理问题。数据的不完整性是实际应用中非常普遍的现象。然而,现有不完整数据上Skyline查询的定义存在严重缺陷,只关注数据点之间相同有效维度上的比较,忽略了缺失属性的问题,使得查询结果集可能为空或存在异常点,无法为用户的决策提供参考。为了克服此问题,本文利用概率模型提出了不完整数据上的概率Skyline查询处理的问题定义。通过返回k个成为Skyline的概率最大的点保证结果集大小和有效性。计算出数据点成为Skyline的概率的必要因素是确定所有不完整数据点的概率密度函数。为此,本文分别在独立的、正相关的和负相关的数据分布上构建了不完整数据模型,并利用有效属性值估计出不完整数据点的概率密度函数。为了高效地进行概率Skyline计算,本文针对三种数据分布分别提出了高效的概率Skyline查询算法SPISkyline,SPCSkyline和SPASkyline。这些算法利用裁剪策略、概率计算的优化策略和排序技术加速了概率Skyline计算。本文分析了算法时间复杂度并用实验验证了算法的高效性和可行性。
  再次,本文研究了不确定数据上的Skyline查询处理问题。数据的不确定性在实际应用中普遍存在,不确定数据上的Skyline查询处理问题也得到了广泛的研究。然而,列分布式环境下不确定数据上的Skyline查询处理问题却仍未引起研究人员的关注。基于此,本文提出了三个通讯高效的列分布环境下不确定数据上的Skyline查询处理算法ASR,IASR和FSLR。在预处理阶段,服务器上的记录在每个维度上都被组织成排序的数据列并支持顺序访问和随机访问。ASR算法交替利用顺序访问和随机访问循环地检索所有排序的数据列,不断更新不确定对象的概率上界和下界,直到所有的不确定对象都已检测出是否存在Skyline结果中为止。IASR算法是在ASR基础上,通过提前终止循环访问来提高算法效率。FSLR算法先利用代价小的顺序访问获得宽松的概率上界和下界,然后再利用代价大的随机访问进一步缩紧概率上界和下界。通过此访问顺序,FSLR能够减少代价大的随机访问的次数,从而提高算法效率。本文分析了算法的通讯复杂度并用实验验证了算法的高效性。
  最后,本文研究了G-Skyline查询处理问题。G-Skyline是一种基于点集的Skyline查询处理,旨在检索出所有优化点集为用户的决策提供参考。然而,随着数据维度的增高,G-Skyline结果集所包含的点集会越来越多,导致用户很难从如此庞大的结果集中选择满意的点集。因此,本文提出了k-支配G-Skyline查询,是传统的G-Skyline查询结果的一个更具有代表性的子集。由于k-支配不具有传统支配关系的传递性,导致现有的G-Skyline查询处理方法无法直接应用于计算k-支配G-Skyline查询问题。基于此,本文提出了一个两阶段k-支配G-Skyline算法。第一阶段尽可能多地裁减掉永远都不会出现在k-支配G-Skyline查询结果集中的点并用剩余的点构造lk-支配图。第二阶段利用已经构造好的lk-支配图搜索出所有的k-支配G-Skyline点集。本文提出两种搜索算法SM-P和SM-G,SM-P算法通过单个点来生成新的候选点集,而SM-G则通过祖先点集来生成新的候选点集。本文分析了算法时间复杂度并用实验验证了算法的高效性。
其他文献
组织蛋白酶cathepsinD(cathD)是普遍存在于真核细胞溶酶体中的天冬氨酸蛋白水解酶,在溶酶体的酸性环境下发挥剪切底物降解蛋白的功能。但在本研究中,我们发现cathD还具有非传统蛋白酶活性的新功能。与其经典的在酸性环境中降解蛋白的蛋白水解酶活性不同,在中性环境中,cathD可以作为一种新型的磷酸酶,通过去磷酸化丝切蛋白cofilin参与调控细胞微丝骨架的重组。通过免疫蛋白印迹和免疫荧光化学
脊椎动物脊髓内的神经网络是中枢神经系统控制身体动作和行为的重要组成部分。V2居间神经元是脊椎动物脊髓腹侧运动神经网络内的一类将脑部信号转换为协调的身体动作和控制运动速率至关重要的神经元。V2居间神经元发生部位,发育过程和分化类型在脊椎动物中是保守的。在所有脊椎动物中,V2居间神经元都包含激活型V2a和抑制型V2b居间神经元两个亚类。V2a和V2b在分子特征和功能上都不同,但都是由神经管腹侧的P2前
学位
当前,癌症依旧严重威胁着人类健康。据2015年世界卫生组织对全球172个国家人口死因的数据统计,癌症是其中91个国家人口过早死亡(70岁前)的首要或次要原因,是另外22个国家人口过早死亡的第三或第四原因。2018年,结肠癌成为全球发病率排行第四,致死率排行第五的癌症。  许多肿瘤细胞,即使是在氧气充足的条件下,也会优先通过糖酵解途径,而不是经线粒体三羧酸(Tricarboxylic acid,TC
学位
背景:  肺癌是对人类健康和生命威胁最大的恶性肿瘤之一,其每年的发病率和死亡率在所有类型的癌症中是增长最快,且呈逐年上升趋势。人类基因组中98%以上的基因属于非编码RNA(non-codingRNA,ncRNA)。LncRNA是一种至少拥有200个核苷酸的一种不编码蛋白质的RNA。大量研究表明,肿瘤的形成和演进和lncRNA的异常表达有密切的关系。LncRNA的表达在肿瘤组织和细胞中相对于正常的组
学位
植物叶片衰老是一个受到严格遗传调控的程序性细胞死亡过程,受到各种內源信号和环境刺激的影响。丝裂原活化蛋白激酶(Mitogen Activated Protein Kinase, MAPK)级联是真核生物中高度保守的信号通路。在拟南芥中,两个功能高度冗余的MAPKs(MPK3和MPK6)及其上游两个功能也高度冗余的MAPKKs(MKK4和MKK5)组成一条信号级联,在植物生长发育以及免疫反应等生物学
学位
自噬是真核细胞中高度保守的依赖于溶酶体的一种降解途径,能够降解细胞内异常聚集的蛋白以及细胞内受损的细胞器。自噬的异常和人类许多疾病的发生密切相关,如:神经退行性疾病,代谢类疾病及肿瘤等。自噬的发生过程主要分为四个阶段:自噬的起始,自噬体的延伸与闭合,自噬体和溶酶体的融合,自噬底物的降解。这些过程由一系列自噬相关蛋白参与,并受到细胞内自噬诱导信号的调控。近年来研究发现,自噬相关蛋白受到乙酰化修饰的调
目的:本次研究主要利用CRISPR/Cas9基因编辑技术在体外建立SCN1A基因稳定敲除的细胞系并采用RNA-seq分析细胞的基因表达谱的变化。通过检测mRNA水平的变化分析SCN1A与DS发病之间的关联,并希望为Dravet综合症的治疗提供一些线索。  方法:①根据SCN1A启动子区序列设计sgRNA,并构建CRISPR/Cas9敲除质粒(pX459-SCN1A)。②将pX459-SCN1A质粒
学位
随着互联网的普及,人们之间的交流可以通过语音视频等更为直观和更具表现力的方式实现。未来随着5G技术的推进,网络、车载视频、安防和体育录像都将出现井喷式增长,这使得视频内容理解和处理工作面临着巨大挑战。  本文便是在这一研究背景下,期望对复杂视频的内容进行缩减,实现紧凑表达,以促进相关工作的进展。视频内部存在没有效力的视频帧或者片段,而传统方法对视频进行全局描述并未考虑到这种差异。视频紧凑表达的目标
视觉目标追踪是计算机视觉领域的一项基础性研究,其应用场景包括自动驾驶、人机交互、智能视频处理等。尽管对于视觉目标追踪的研究已经取得了很大的进展,但它仍是一个颇具挑战性的问题。其挑战性在于如何依据目标的一个初始状态,来估计后续视频帧中会发生各种变化的目标的状态。本文结合追踪任务的特性,按照先在线信息挖掘和应用后离线先验信息应用的研究路线,从追踪框架的表观模型和决策模型着手,对以下四个问题进行了研究。
学位
自然语言处理是人工智能的重要子学科。作为自动处理文本的第一步,将词转换为数值化表示很大程度地影响了自然语言处理的性能。词向量为自然语言的最小语义单元—词提供了包含句法语义信息的稠密向量表示。作为基于神经网络的自然语言处理的基础,依据词义分布假设构造的词向量给诸多自然语言处理模型带来了性能的提升。为了提高词向量的学习效率,前人工作进一步对词向量进行静态假设,即一个词有唯一的向量表示。这一假设使得在大