高效的Top-k相互Skyline查询算法

Top-k相互Skyline查询返回相互Skyline查询中的前k个对象.这种查询是数据分析者寻找有意义对象进行决策支持的一种重要直觉工具.然而,这种查询还没有引起研究社区足够的注意力.介绍了几种新颖的算法,包括Topk-TBBS,Topk-dMBBS,Topk-wMBBS.主要的思想是信息重用和高效的修剪策略.特别地,Topk-wMBBS算法由于完全重用了搜索中的节点信息,并利用了最好优先BF搜索策略.因而它获得了最好的性能.同时证明了该算法有最优的I/O访问效率.最后,使用了2个真实数据集和4个服从不同分布的合成数据集进行了集中实验.实验结果表明,提出的算法无论是变化参数k的大小、数据集的尺寸和Cache尺寸都是有效的,且具有很高的效率,尤其Topk-wMBBS具有最小的I/O访问次数.     

高效多子空间Skyline查询处理算法

随着Skyline查询应用的增多,子空间Skyline查询成为热点。针对实际应用中用户从多角度审视某一数据集的需求,充分研究了多子空间Skyline查询问题。在分析现有子空间Skyline查询算法解决该问题不足的基础上,提出了子空间立方体群(subspace skycube group,SSG)结构,并给出了基于该结构的同时计算任意多个子空间Skyline查询的MSSC(multiple subspace skycube)算法。该算法采用子空间候选集(subspace candidate sets,SCS),并充分利用了子空间立方体群结构中各子空间Skyline结果间的共享关系;在此基础上,算法采用求和过滤以及最大值过滤等方法,对数据集进行剪枝和过滤,从而进一步提高算法效率。最后,分别用人造数据和真实数据对算法进行实验,并与现有算法进行比较,结果表明MSSC算法可以高效地解决多子空间Skyline查询问题。     

多因素时间序列Skyline的快速查询算法

在给出多因素时间序列Skyline(MFTS)形式化定义的基础上,提出一种MFTS快速查询算法,获得并存储各时间点上的多因素值,计算每个最小时间区间的准MFTS,从而得到指定区间的MFTS。实验分析结果表明,在时间序列重合较少的情况下,该算法具有较好的查询效率。     

无线传感器网络中一种近似Skyline 查询处理算法

由于无线传感器网络的能源有限,且在许多应用中Skyline 查询的部分结果即可满足用户需求,提出了一 种近似Skyline 查询处理算法,在满足用户查询需求的前提下最大化地节省能量.该算法仅需无线传感器网络中的部 分传感器节点回传其感知数据即可计算出Skyline 查询的一个近似结果集.由于该算法在处理查询时,每个传感器节 点只需考察自身数据信息即可决定是否回传其感知数据,而无须与其他传感器节点的感知数据进行比较,因此可以 避免大量的网内通信开销,从而节省网络能源.模拟环境下的大量实验结果表明,该算法可以根据用户的应用需求, 节能地处理传感器网络中的近似skyline 查询.     

障碍空间中基于R+树的空间Skyline查询方法

为了解决已有研究成果无法有效解决障碍空间中的空间Skyline查询问题,提出了障碍物环境下基于R+树的空间Skyline查询方法——SOS算法。该算法采用了两个过程:过滤过程和精炼过程。过滤过程主要是利用R+树的快速定位特性有效地剪枝掉大量被支配的数据点,缩小查询范围,提高算法效率。精炼过程主要根据障碍距离以及数据点与查询点间的拓扑关系对候选集中数据点进行二次筛选,最终得到Skyline集合。进一步给出新增点的ADD_SOS算法和删除点的DEN_SOS算法。理论研究和实验结果表明,该算法在处理障碍空间中的空间Skyline查询问题时具有优势。     

道路网环境下K-支配空间Skyline查询方法

为了弥补已有的研究成果无法直接处理道路网环境下K-支配空间Skyline查询问题的不足,提出了基于网络Voronoi图的道路网环境下K-支配空间Skyline查询方法.该方法将K-支配应用到道路网Skyline查询中以处理多属性数据对象,在实际应用中可以用来解决道路网环境下多目标查询和决策问题.方法主要包括道路网中约减数据集过程和K-支配检查过程.首先基于空间数据点构建网络Voronoi图,并对查询点建立查询凸包,通过网络Voronoi图的性质与查询区域的位置关系对数据集约减,从而优化数据集并且有效地减少查询点重复搜索的现象;然后对候选集的非空间属性进行K-支配检查得到道路网精炼集合;最后对精炼集合进行支配检查得到最终的空间Skyline集合.理论研究和实验表明所提出的方法具有较高的效率,可较好地处理道路网环境下K-支配空间Skyline查询问题.     

道路网环境下K-支配空间Skyline查询方法

已有的天际线（Skyline）查询主要聚焦于单用户场景,并基于单用户模型进行Skyline计算,而较少考虑道路网环境下多用户情况. 为了弥补已有方法无法解决道路网络环境下多用户偏好和权重Top-k Skyline查询问题的不足,提出了一种基于道路网环境下多用户偏好Top-k Skyline（multi-user preference Top-k Skyline,MUP-TKS）查询方法. 在道路网环境下考虑多用户的不同偏好和权重进行Skyline查询,可以快速得到符合查询用户群偏好和权重的结果集,提供用户群更好的决策支持.MUP-TKS首先通过所提的G_DBC算法,利用道路网中数据点与查询点之间的位置关系和新的索引结构Vor-R^*-DHash剪枝、过滤数据点,从而得到距离较优集;再利用静态Skyline集不变的性质,预先计算、保存该集合;然后通过所提的新支配关系对距离较优集与静态Skyline集取并集后的集合S进行放松支配;最后利用所提TK_DC算法对经过放松支配后的候选结果集打分,依据数据点得分情况,排序输出Top-k个结果集返回用户群. 理论研究与实验表明,所提方法具有较好的效率与可靠性.

     

空间Skyline查询处理:应用、研究与挑战

引入动态属性的空间Skyline查询处理技术正在多个领域得到应用。首先引出传统Skyline和空间Skyline的定义,进而回顾了15年来Skyline的发展历程。重点介绍了当前空间Skyline在各个领域的主要应用,并根据这些应用总结了主要的研究方法和技术。最后,给出了空间Skyline查询处理面临的诸多挑战,指出了今后的大体研究方向。     

结合非空间属性的通用Skyline查询处理技术

Skyline查询作为多目标决策的重要手段之一,近年来在各个领域得到广泛的应用。提出了结合非空间属性的通用Skyline查询处理技术,采用R树对设施集及数据集建立索引,并提出了两种方法来计算Skyline。第一种是基于全最近邻算法的扩展,通过计算静态Skyline结果来裁剪部分数据集。另一种是基于渐进最近邻的算法,采用查询点导向的搜索方法,利用静态Skyline结果计算与每一类设施最远的距离,将其作为边界阈值对数据点集进行裁剪,采用数据点导向的搜索方法,为裁剪后的每一个数据点计算距其最近的设施,并将数据点与设施的距离映射到多维距离空间中,结合非空间属性进行Skyline计算。实验结果表明,第二种方法减少了I/O次数,降低了CPU执行时间,提高了计算效率。     

Skyline查询处理

对目前的Skyline查询方法进行分类和综述.首先介绍Skyline查询处理问题产生的背景,然后介绍Skyline查询处理的内存算法,并从带索引和不带索引两个方面对现有的外存Skyline查询处理方法进行分类介绍,在每组算法后,都对该组算法进行了性能评价,然后介绍不同子空间上的多SKyline查询处理模型——SKYCUBE的概念和相关研究.另外,还介绍了不同应用环境下解决Skyline查询处理的策略以及Skyline查询处理问题的扩展,最后归结出Skyline查询处理后续研究的几个方向.     

3FO:基于过滤的一种Skyline查询算法

Skyline查询是从一个给定的数据集上返回所有不被其它点支配的点的集合.本文主要针对二维和三维空间上Skyline查询结果的单调性特点提出了一种新的3FO算法,它通过NN过滤、最小值覆盖过滤和单调性过滤三次过滤操作,删除非skyline点数据.可以快速地返回全部的Skyline点.实验结果表明,该算法比传统算法在相同数据集上平均性能提高2-3倍,是一种高效的算法.     

面向大规模数据集的并行化Top-k Skyline查询算法

随着数据规模的日益庞大,在大规模数据集中帮助用户定位出数据量可控的代表性信息显得越发重要。虽然Top-k Skyline查询能够找到数据集中前k个最具代表性的信息,在获取代表性信息的同时又控制了结果规模,满足了上述要求,但是现有的Top-k Skyline查询在面对大规模数据集时效率较低,并不适用于大规模数据集。为了解决这个问题,将Top-k Skyline查询与并行化处理相结合,提出了一种面向大规模数据集的并行化Top-k Skyline查询算法PTKS（parallel Top-k Skyline）,通过充分利用分布式资源,将原有查询进行有效的并行化处理,同时设计了基于用户偏好的用于缩减结果数据量的筛选规则,满足用户需求。在真实数据集上进行了相关实验,并与现有方法进行了对比,结果表明PTKS在大规模数据集上的查询效率更具有优势,能很好地适用于大规模数据集。     

分布式环境下的Skyline代表点查询

为了克服Skyline查询的不足即结果集大小无法控制,提出了Skyline代表点查询,返回k个可描述全局Skyline轮廓的Skyline代表点。研究了分布式环境下的Skyline代表点查询,提出了Naive算法和FDRA。Naive算法首先转移每个子节点上满足条件的两个局部代表点,再通过比较传来的局部代表点间的评价函数值大小决定子节点是否需要传送余下的局部点,以实现剪枝非代表点;与之相比,FDRA的改进在于过滤元组的选择,运用反馈方法,将每次动态更新最大评价函数值的点作为过滤元组,大大降低了计算代价,中心服务器每次只发送过滤元组到分布节点,这样可以尽早且最大限度地剪枝不可能成为代表的Skyline点。提出的算法降低了服务器间的通信开销,返回了正确的结果集,实验论证了算法的有效性与高效性。     

不确定数据流上的并行反Skyline查询

作为Skyline查询的一种重要变体,不确定数据流上的反Skyline查询已经成为研究的热点。已有的单机算法无法应对诸如高速数据流、高数据维度、大滑动窗口等情况,相应提出并行查询处理算法PRSUDS。算法采用基于角度划分的分发策略将处理任务分发至各并行节点,给出该分发策略的正确性证明,进而设计、实现算法的并行处理框架。实验结果表明PRSUDS算法较单机算法具有更好的综合性能,更能满足数据流查询的实时性要求。     

面向匹配结果不可排序的Top-k查询算法研究与实现

随着互联网技术发展,同构发布/订阅系统的应用也越来越广泛.怎么能快速高效的为用户推荐k个最优的候选环匹配是同构对称发布/订阅系统中研究的关键问题之一.就匹配结果不能通过调用打分函数打分的问题,文章提出基于k-支配Skyline查询的面向匹配结果不可排序的Top-k查询算法.先扩展了同构对称发布/订阅的模型;再对算法得基本思想及基本操作做详细的描述.通过实验表明文章提出的算法查全率和查准率都在94%以上.     

无线传感器网络中Skyline节点连续查询算法

作为多目标决策的重要手段之一,Skyline节点查询在传感器网络应用中发挥着非常重要的作用.文中深入地分析了Skyline节点查询的性质,提出了基于过滤的Skyline节点连续查询算法(FIlter based Skyline moniToringalgorithm,FIST).FIST算法共包括自底向上、自顶向下和混合3种过滤方式,均通过在传感器节点设置本地或全局过滤器来避免不必要的数据传输,进而节约传感器节点的能量.自底向上过滤方式通过缓存先前Skyline结果作为本地过滤器来避免数据重复传输,而自顶向下过滤则通过设置超立方体作为全局过滤器来避免数据反复更新.由于两者各有利弊,因而提出了混合过滤方式,通过为节点选择合适的过滤器来扬长避短.大量仿真实验的结果表明,FIST算法能有效地减少Skyline节点连续查询过程中传感器节点的通信代价,进而降低传感器网络的能量消耗.     

Vague数据库Skyline查询技术研究

Skyline查询处理是近年来数据库领域的一个热门研究方向。由于现实世界中普遍存在着大量不精确、不确定的信息,Skyline查询也随之成为模糊数据处理中的一个重要内容。在已有研究的基础上,讨论了基于Vague关系数据模型的Skyline查询,其用于查询给定Vague关系中的任意元组确定不被该关系中的任意其它元组所支配的程度,并给出了相关的计算公式和查询算法,该算法可直接作用于Vague关系数据库,而无需对Vague关系数据库对应的所有可能性状态逐一进行扫描,具有较高的执行效率。在此基础上,还进一步讨论了带有预选择条件的Skyline查询的计算方法。     

云计算环境下的容错并行Skyline查询算法研究

云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时,其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能,不能保证故障情况下查询继续正确执行。为此,提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline,FTPS)。该算法通过故障监测和任务迁移,使得能够在查询过程中及时发现故障,并将故障节点的计算任务迁移到副本节点,保证查询的正确执行。理论分析和实验证明,FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。     

垂直分布数据集上的安全Skyline查询算法

Skyline查询是指从多维数据集中筛选出不被其他任何数据点支配的数据点,是一种重要的数据分析方法。近年来,随着隐私保护需求的不断增长,分布式数据集上保护隐私的Skyline查询算法也受到越来越多关注。然而,现有的垂直分布数据集上的Skyline查询方案数据以明文存储,不能实现数据的隐私保护。为此,深入研究了垂直分布式数据集上保护隐私的Skyline查询问题,提出了一种抗合谋攻击的多方垂直分布数据集上的Skyline查询协议。理论分析证明了提出协议的正确性和安全性。此外,通过理论分析和模拟实验对协议运行效率进行了评估,结果显示新方案具有较高的运行效率。