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

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

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

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

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

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

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

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

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

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

数据流上连续动态skyline查询研究

skyline查询能够从大规模数据集上计算满足多个标准的最优点.数据流上的skyline计算是数据流上最基本的查询操作之一,对于很多在线应用具有非常重要的意义,尤其在移动计算环境、网络监控、通信网络以及传感器网络等领域.不同于大部分传统的skyline研究,主要研究数据流上约束skvline和动态skyline计算问题.采用网格索引存储元组,提出了GBDS算法用于计算和维护动态skvline.通过为每个查询定义影响区域,使得在元组到达和失效时需要处理的元组个数最小化.理论分析和实验结果证明了提出方法的有效性.     

一种基于索引的高效k-支配Skyline算法

由于在多标准决策支持等应用上具有重要的意义,skyline查询成为近年来数据库和数据挖掘领域的一个研究热点.然而随着数据集维数的增加,数据点之间形成支配关系的可能性越来越小,导致了skyline点数目过多而无法提供任何有效信息.为了在高维数据集中找到更重要和更有意义的skyline点,人们提出了k-支配skyline的定义.但现有的用于k-支配skyline的算法在时间效率、空间复杂度和渐进输出性上都有待提高.该文提出了一种基于索引的高效k-支配skyline算法,通过为数据集建立两个索引,算法可以高效地进行计算,在时间、空间和渐进性上均优于现有的算法.     

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

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

无线传感器网络不确定数据PT-Top k查询处理技术

在无线传感器网络现实应用中,感知数据普遍存在不确定性。由于不确定数据引入了概率维度,使得不确定数据查询种类更加丰富,同时也给查询处理带来困难。不确定数据Top-k查询是一个典型的不确定数据查询任务。考虑到无线传感器网络查询处理技术对查询响应时间和网络通信消耗的高要求,研究了面向层次聚簇结构的无线传感器网络不确定数据Top-k查询处理技术。通过分析不确定数据特点,基于x-tuple规则元组模型,采用簇内与簇间的两阶段数据查询处理机制,提出了基于Poisson分布的分布式不确定数据PT-Top k查询处理近似算法TPQP。通过实验,从总体通信消耗、与概率阈值p相关分析、与排序数k相关分析以及数据敏感度分析等方面,说明了TPQP算法在通信消耗、查询响应时间上的优越性。     

基于网格的数据流连续约束Skyline处理技术研究

作为数据流上的一种重要查询,skyline对于很多在线应用都非常重要,包括移动运算环境、网络监控、传感器网络、股票交易等。与大多数数据流skyline处理技术不同,本文着重于约束skyline的处理。约束skyline支持用户定义在某些属性上的偏好,系统中存在多个约束skyline查询,为skyline查询处理技术带来了新的挑战。为了在高速数据流上对约束skyline进行高效处理,本文使用了一种网格索引存储元组,并提出两个算法用于计算和维护skyline集合,我们还为每个查询定义了影响区域,以减少在新元组到达和旧元组失效时需要处理的网格数目。理论分析和实验证明了该方法的有效性。