基于Flink的k-支配skyline体并行求解算法

k-支配skyline算法弱化了数据点之间的支配关系,更适合高维数据。k-支配skyline体适应于多名用户使用k-支配skyline算法查询,而现有的求解算法在时间效率和代码扩展性方面都有待提高。因此,提出了面向多用户的k-支配skyline体求解优化算法MKSSOA,该算法对每名用户的候选集和中间集分别进行存储,同时在k-支配检查过程中利用2集合中数据点出现的先后次序将候选集中的非k-支配skyline点存储到对应用户的中间集中,以便下一名用户筛选使用,这样可以减少数据点之间的比较次数,避免重复计算,从而提升查询效率。同时,提出了面向多用户的k-支配skyline体并行求解算法MKSPSA,通过Apache Flink并行处理框架有效减少了数据点的比较时间。理论研究和实验结果显示,提出的算法具有较高的效率,能很好地处理多用户k-支配skyline问题。     

一种使用简化预排序的k-支配Skyline查询算法

近年来,Skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛应用.然而在高维空间环境下,skyline查询因为返回的结果集过大而不能提供有用的信息.因此,学术界提出了七-支配skyline查询的概念.它通过弱化数据点之间的支配关系,使数据点间更容易产生支配关系,从而使结果集的大小保持在一个合适的范围内.现有七-支配skyline查询算法分为建立索引和不建立索引两种类型.其中不建立索引的算法在高维空间,反相关数据和渐近输出等方面表现比较差,而基于索引的算法花费大量时间去建立索引,整体性能都不高.本文提出一种基于简化预排序的七-支配skyline查询算法(SPA),实现用O(n)的时间复杂度对数据进行简化预排序.理论论证和实验数据都显示了SPA算法远比国内外现有的最好算法更加高效.     

一种面向不完整数据流上的k-支配skyline查询算法

skyline查询是数据挖掘一个重要的研究方向,在基于数据的决策支持等应用中有着重要的作用.由于现实应用中存在着大量的不完整数据流,但大多数现有的skyline查询算法都依赖于如下的假设:1)任意数据点的所有维度值都是已知的;2)数据集是稳定、有界的并且可以随意访问.此外,随着数据维度的增加,skyline数据点的个数会变得过多,因此引入了k-支配skyline的概念,但是不完整数据的k-支配关系并不具有传递性,现有的skyline查询算法都无法适用.基于这些问题,考虑到数据流高维、无界、顺序性的特点,并且在某些维度上可能具有缺失值的特性,提出了一种新的基于滑动窗口的不完整数据流的k-支配skyline查询算法,实验结果表明,算法不仅可以支持不完整数据流上的k-支配skyline计算,并能够保证效率和性能.     

一种基于逆支配点集的数据流Top-k计算方法

网格索引构造简单,常用于数据流系统计算top-k和skyline。但是,网格索引结构粗略,查询过程可能访问大量非top-k结点。为了提高网格索引计算top-k查询的精确度,本文提出基于数据点逆支配点集性质的网格索引方法,将查询访问集缩小到网格索引的"k-最大运算区域区域k-MCA"中,有效地减少了网格索引存储量和查询计算开销。同时,给出了k-MCA索引结构及适应于数据流计算的k-MCA维护更新算法。理论分析和实验结果均验证了上述方法的有效性。     

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

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

已知时间的空间文本skyline查询

现有的空间文本skyline查询忽略了地理空间对象的时间信息,考虑到时间信息对应用的重要性,将时间信息应用到空间文本skyline查询中,提出了一种新的查询,即已知时间的空间文本skyline查询（Time-aware Spatial-Textual Skyline Query,TSTSQ）。TSTSQ中skyline对象的筛选依赖于三个条件：文本相关性、空间邻近和有效时间。分别设计了对象的空间文本相关性和时间文本相关性的计算函数,构建时空信息和文本信息的对象索引结构TKR-Tree,通过构造高效的裁剪策略实现了TSTSQ的查询算法。通过实验数据的分析和对比,验证了TSTSQ查询的有效性。     

基于结构化对等网络的skyline计算

一个多维数据库的skyline,是此数据库上不被其它任何数据支配的点所组成的集合.集中式skyline作为早前的关注焦点得到了较深入成熟的研究,现在已经有了大量针对集中式数据库的skyline算法.而迄今为止,对等网络上的skyline研究却仍然很匮乏,仅有三篇文章对此作出了初步的探索.其中一篇文章是专门为子空间上的skyline计算设计的,另两篇则是分别针对某种特殊的对等网络协议而不能适用于其他协议.提出了一种新的skyline算法.它基于一种重要的对等网络Chord,着力于减小网络带宽的占用量和节点访问数,并提供了保持负载均衡的方法,具有良好的扩展性和渐进性.理论分析与实验结果均证明这种算法是一个符合对等网络特点的准确高效的skyline算法.     

GDG:一种基于逆支配点集的top-k高效查询索引方法

考虑偏好top-k计算问题,提出一种整合网格索引和DG索引的Gridded Dominant Graph(GDG)混合索引结构.首先,提出基于数据点逆支配点集性质的剪枝自由点方法,该方法大大减少了构建索引中的数据点及查询时可能访问的数据点.通过网格索引高效地计算逆支配点集,并得出网格中"k-最大运算区域"和"k-最大查找区域",分别在建立索引和top-k查询阶段近似地剪枝自由点.然后,分析了查询索引阶段层次式索引(如dominant graph(DG))在同一层次中无序访问数据点的不足,通过增加网格索引而使访问有序.计算网格概要信息并将网格单元按函数分值排序,使层次内数据点依据网格单元顺序而访问有序.由于附加的网格索引增加计算和存储开销较少,同时性能有较大提升,所以GDG适用性强.理论分析和实验结果均验证了上述方法的有效性.     

无线传感器网络延迟约束的MDC分布式轨道规划算法

针对引入移动元素后无线传感器网络数据面临的收集延时问题,提出了一种分布式的移动数据收集器(MDC)轨道规划算法.首先给出基于k跳支配集的MDC最小时延规划问题定义,并证明它是NP-hard.在基于集结的数据收集模式汇总,k跳支配节点作为集结点缓存传感节点收集的数据并在MDC到达时上传.然后,提出了一种高效的基于k跳支配集的MDC轨迹构建算法.算法通过分布式的k-跳支配集算法找出网络中的支配节点,进而通过Prim算法和Christofides近似算法对MDC的移动轨道进行规划.算法的正确性、k-跳支配集的界、时间复杂性和消息交换复杂性通过理论进行分析.最后,通过仿真实验验证了算法的有效性.仿真结论表明,与同类算法相比,所提出算法能够显著缩短MDC的移动轨迹,因而可以降低网络延迟.     

基于小波概要的区间差分skyline研究

在很多应用中需要分析大量的时序数据,而相对于其它数据具有支配优势的时序数据片段往往会引起特别的关注。基于量值度量,现有的区间skyline查询可以返回给定时间区间内所有没有被其他数据支配的时序数据,这种查询有时不能满足应用的需求,且可能存在“淹没”现象。为此提出了区间差分skyline的概念,针对数据增长率属性进行分析,以解决现有区间量值skyline的不足。目前很多时序数据呈现为数据流的形式,由于资源的限制往往只会维护一个反映数据概况的概要结构,在此背景下提出了基于常用的小波概要支持不同粒度区间差分sk沙nc查询的基本算法,继而在保证准确性的基础上提出了改进后的快速算法。在真实股票价格数据集上的实验验证了所提方法的有效性。