基于MapReduce的连续概率Skyline查询

大数据对传统的Skyline研究产生了挑战,利用并行框架MapReduce计算大数据下的Skyline已成为一个研究热点。研究了不确定移动对象的Skyline查询问题,提出了一种MapReduce框架下基于事件跟踪的连续概率Skyline查询算法——MR-DTrack(domination-track algorithm based on MapReduce)。首先采用基于角度的划分方法保证负载均衡,通过预计算获取Skyline集可能变化的时刻,在Reduce阶段获取候选概率Skyline集;然后利用局部过滤点剪枝,减少计算开销;最后合并计算出全局概率Skyline集。在人工数据集和真实数据集上的实验验证了算法的有效性。     

基于MapReduce的Skyline查询处理算法

Skyline查询是一个典型的多目标优化查询,在多目标优化、数据挖掘等领域有着广泛的应用。现有的Skyline查询处理算法大都假定数据集存放在单一数据库服务器中,查询处理算法通常也被设计成针对单一服务器的串行算法。随着数据量的急剧增长,特别是在大数据背景下,传统的基于单机的串行Skyline算法已经远远不能满足用户的需求。基于流行的分布式并行编程框架MapReduce,研究了适用于大数据集的并行Skyline查询算法。针对影响MapReduce计算的因素,对现有基于角度的划分策略进行了改进,提出了Balanced Angular划分策略;同时,为了减少Reduce过程的计算量,提出了在Map端预先进行数据过滤的策略。实验结果显示所提出的Skyline查询算法能显著提升系统性能。     

海量数据上有效的top-k Skyline查询算法

在许多应用中,Skyline查询是一种十分重要的查询类型,它在潜在的巨大的数据空间中返回不被其他元组支配的用户感兴趣的元组,但是Skyline查询无法控制返回结果的数量。处理一个新的top-k Skyline查询问题,该查询返回支配分数最大的k个Skyline元组,从而控制了需要向用户返回的查询结果数量。分析发现,大多数现有算法忽略了利用支配分数作为限制Skyline查询的结果数量的度量。提出一个新的基于表扫描的RSTS(ranked Skyline with table scan)算法来有效计算海量数据上的top-k Skyline结果。RSTS算法首先对表执行预排序操作,保证预排序表的元组按照对有序列表的round-robin扫描的顺序排列。RSTS算法包括两个阶段。阶段1利用对预排序表的顺序扫描来获得候选元组。阶段2计算候选元组的支配分数并返回结果。可以证明,RSTS算法具有早结束特性,并给出其扫描深度的理论分析。提出对于候选元组的剪切操作,理论剪切效果表明,绝大多数的Skyline结果可以直接丢弃。实验结果表明,RSTS算法可以有效计算top-k Skyline结果。     

Skyline代表点的选择*

Skyline查询在多维决策和数据挖掘等方面发挥重要作用,然而随着数据属性维度的增大, Skyline集变得非常庞大.为克服该不足,提出Skyline代表点查询.文中提出新的评价函数改进Skyline点的得分计算方法以选择k个具有代表性的Skyline点.在二维空间提出动态规划算法(DPBA),利用覆盖圆的性质确定非代表点与代表点间的覆盖距离,迭代计算评价函数值,从而得到k个代表点;在高维空间针对NP-hard问题提出一个基于aR-tree结构的近似解决方法,遍历索引结构中的节点,通过与候选Skyline集比较判断是否被支配进行剪枝,降低计算开销.大量基于合成数据与真实数据的实验证明该算法的有效性.     

基于MapReduce的预处理高效Skyline算法

现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。     

无线传感器网络的ProgressiveSkyline连续查询

随着传感器技术的进步,无线传感器网络支持复杂查询在现实应用中越来越重要。Skyline查询由于可用于多种标准下的决策而受到广泛关注。对无线传感器网络中Skyline连续查询进行了研究,提出了一种增量(progressive)算法来解决静态数据集中的Skyline查询求解问题,这种增量算法能够递增返回Skyline结果,而无需事先扫描整个数据集。设计了一种新颖的算法来解决流数据集中的Skyline查询维护问题。通过实验对算法性能进行了验证,结果表明,该算法能够大大延长网络的生命周期。     

度量空间中的Top-k反向Skyline查询算法

不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS(metric top-kreverse skyline).MkRS从反向角度执行度量空间中的Skyline.给定查询对象q和单调参考函数f,MkRS返回k个包含m个数据对象的子集,以至于每个子集G的度量Skyline包含q.评估这种查询,需要执行从输入数据集P中n个数据对象里选择m个对象的穷举搜索以及每个排列子集的度量Skyline.这些计算由于巨大的搜索空间而需要极高成本.提出了基于排序机理的算法STS(sort and threshold skyline),它可以提前终止计算,仅需要检查很少部分的子集.然后,利用信息重用技术给出了基于重用的STS算法rSTS(reuse STS),进一步减少了STS中80%以上的I?O访问.大量的实验表明提出的算法有效、快速.     

基于事件的位置不确定移动对象连续概率Skyline查询

Skyline查询是基于位置服务(Location based service, LBS)的一项重要操作,其目的是发现数据集中不被其他点支配的点的集合.移动对象在运动过 程中,其位置信息具有不确定性,导致各数据点间的支配关系不稳定,从而影响Skyline操作.本文针对以位置不确定移动对象为查 询点的Skyline查询进行研究,首先,定义了查询点移动时各对象间支配概率,提出了支配概率和Skyline概率的微元计算方法.在此基 础上,提出一种面向不确定移动对象进行连续概率Skyline查询的有效算法U_CPSC.该算法首先快速计算初始时刻的p-Skyline集合; 然后,定义了两类可能引起p-Skyline变动的事件,通过对这些事件的跟踪计算快速更新p-Skyline集合,无需在移动对象的每一运动 时刻去遍历整个数据集,实现了对p-Skyline的连续更新操作,大大减少了算法的查找和计算开销,提高了运算效率;最后,提出一 种静态算法U_SPSC,与U_CPSC进行了对比试验,实验结果证明了算法的有效性.     

基于数据垂直划分的高效并行Skyline查询

基于数据垂直划分的分布并行Skyline查询算法大多并行性较低,无法适应海量分布式数据的快速响应要求。为此,在BDS算法的基础上提出一种更高效的分布并行Skyline查询算法PDS-VP。其中,节点被分为协调者与参与者,原本由协调者节点完成的随机访问和本地Skyline计算分发给各参与者节点进行处理,以提高算法的执行效率。实验结果证明,该算法提高了原算法的并行性和运行效率。     

无线传感器网络中基于聚簇结构的Skyline查询方法

现有的基于单服务器的Skyline查询算法已经不能很好地应用于无线传感器网络这类分布式多跳自组织网络中。基于聚簇结构的Skyline查询算法就是针对 这类特定的网络结构而提出的。该算法采用基于聚簇的路由结构,为了减少Skyline查询处理过程中传感器节点的通信开销,挑选具有最大支配力的数据元组作为全局过滤元组来过滤不满足Skyline条件的数据。同时,在Skyline查询处理过程中引入滑动窗口机制,该机制也能有效地降低通信开销。大量的仿真实验结果显示,所提Skyline查询算法在确保能耗的基础上仍然具有很好的性能。     

不确定移动对象概率Skyline集的查询更新

Skyline查询的研究已从传统的静态Skyline操作延伸到动态的、不确定数据集上的Skyline查询和计算上。研究了移动环境下,查询点位置固定、目标点处于运动状态并且位置不确定情况下的连续概率Skyline计算问题。这个过程中,移动对象与查询对象之间的距离随时间不断变化。移动对象由于其运动状态导致位置无法精确定位,因此移动对象之间的支配关系只能采用概率形式表示,且随时间不断变化。给出了移动对象间的支配概率的定义,以及移动对象Skyline概率的定义,并定义了触发事件来记录对象支配概率发生变化的时刻,实现概率Skyline计算的连续跟踪和动态更新。提出了基于事件触发的连续概率Skyline查询算法(event triggered continuous probabilistic Skyline query for uncertain moving object,U-ECPS),对移动环境下的Skyline集进行连续查询和更新。大量的实验结果验证了U-ECPS算法的有效性。     

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

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

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

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

基于高斯模型的不确定数据流Skyline查询方法

由于数据的动态性及不确定性等特征,使得不确定数据流上Skyline查询研究面临挑战.不确定对象一般采用多元概率密度函数(PDF)表示,现有的不确定数据流Skyline查询方法均采用离散型随机变量建模.然而不确定数据流中的对象可能是连续变化的,离散模型对连续性随机变量难以适用.针对连续PDF建模的不确定数据流Skyline查询进行了研究,提出了基于高斯模型的不确定数据流Skyline查询方法(SGMU),该方法包含2个过程:1)动态高斯建模算法(DGM):对滑动窗口采样并建立高斯模型,将原始的数据流转化为不确定对象PDF的参数流;2)提出了基于高斯树的查询算法(GTS)以建立空间索引结构和执行Skyline查询.实验结果表明,SGMU算法不仅能够对连续型不确定对象进行有效建模以辅助Skyline查询,而且能够有效地减少查询对象个数,提高Skyline查询效率.     

不确定Skyline查询技术研究

当前不确定数据广泛存在于诸如传感器网络、RFID网络、基于位置服务、移动对象管理网上购物和市场监控等各种实际应用中.不确定Skyline查询作为不确定数据管理的一个重要方面,由于其在决策制定、市场分析、环境监控和数据挖掘等方面的重要作用,近年来在数据库和网络计算领域受到广泛关注.首先,概述了各种不确定数据类型上的Skyline查询定义,包括离散、连续概率分布模型以及不完全数据上的Skyline查询定义;其次,分析了不确定Skyline查询的特点,并在此基础上综述了现有的各种不确定数据集上的集中式和分布式Skyline查询方法,重点分析了各种算法的原理和优缺点;再次,介绍了不确定数据流上的Skyline查询定义并综述了各种不确定数据流上的Skyline查询方法;最后,基于最新研究动态指出了未来不确定Skyline查询研究的趋势.     

基于属性优先关系的多用户Skyline查询处理算法#br#

Skyline查询为多目标决策等问题提供了解决方案。每个用户对数据属性的优先关系的需求不同,传统算法无法有效解决多用户场景下的偏好Skyline查询。针对该问题,提出一种基于属性优先关系的多用户偏好Skyline查询算法--MUPS算法。该算法基于属性权重对原始Skyline结果集通过新的σ-支配方式进行剪枝;同时,通过交互动态修正属性的权重大小,使最终结果更符合用户群的真实偏好需求。最后,在模拟和真实数据上验证MUPS算法的有效性和良好的交互性能。     

分布式环境下连续概率Skyline查询

Skyline计算是多准则决策,数据挖掘和数据库可视化的重要操作。移动对象在运动过程中,由于位置信息的不确定,导致局部各数据点间的支配关系不稳定,从而影响全局概率Skyline集合。针对分布式环境下不确定移动对象的连续概率Skyline查询更新进行研究,提出了一种降低通信开销的连续概率Skyline查询的有效算法CDPS-UMO,该算法在局部节点中对局部概率Skyline点的变化进行跟踪;提出了有效的排序方法和反馈机制,大大降低了通信开销和计算代价;提出一种基本算法naive,与CDPS-UMO进行了对比实验,实验结果证明了算法的有效性。     

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

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

非完整数据库Skyline-join查询*

传统的Skyline-join查询仅适用于完整数据库,随着新的应用需要的出现,实际应用中考虑到非完整数据库中的Skyline-join查询。概率Skyline利用概率值表示非完整数据项之间的支配关系,有效地避免了传统非完整数据库Skyline查询存在的支配性丢失问题。在分析概率Skyline无法有效处理多关系查询的基础上,对概率Skyline定义进行了扩充,使其适用于多关系查询,并提出了基于多层次分组的PSkyline-join算法。该算法首先基于连接键值及缺失位图对各个关系进行多层次分组,再计算各组数据项的局部Skyline概率上界,然后连接数据项并更新数据项的全局Skyline概率上界,最后利用全局Skyline概率上界与全局Skyline概率下界设计了两种剪枝策略,高效地计算全局概率Skyline结果集。在模拟数据集上验证了PSkyline-join算法效率相较传统算法有着几十倍的提升。     

MapReduce框架下的Skyline计算

由于Skyline查询广泛应用于多目标决策、数据可视化等领域,近年来成为数据库领域的一个研究热点。针对云计算环境,在MapReduce框架下设计并实现了Skyline算法。MapReduce是一个运行在大型集群上处理海量数据的并行计算框架,其主要思想是任务的分解与结果的汇总。基于不同的数据划分思想,实施了三种Skyline并行算法,分别是基于MapReduce的块嵌套循环算法(MapReduce based block-nested-loops,MR-BNL)、基于MapReduce的排序过滤算法(MapReduce based sort-filter-skyline,MR-SFS)以及基于MapReduce的位图算法(MapReduce based bitmap,MR-Bitmap),并针对这三种算法进行了系统的实验比较,得出了不同数据分布、维数、缓存等因素对算法性能的影响结果。