高效的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查询问题,提出了KSkySenor算法,有效地从传感器网络中获取更有意义的skyline结果;KSkySenor算法对感知数据进行预处理计算每个元组的支配能力,按照支配能力与各维度值之和对其进行排序,设计了一个基于聚簇的结构用于收集所有传感器读数,提出了一个剪枝方法用于渐进的从传感器网中获取skyline结果集;实验中分别改变传感器网络规模大小、数据维度、支配属性个数k,对KSkySensor算法进行测试,实验结果表明KSkySenor算法与先前的skyline查询处理算法相比具有很高效率,减少了无线传感器网络中的数据传输量,延长了网络生命周期。

跨信任域的联邦k-支配Skyline查询算法

k-支配Skyline查询是一种主流的Skyline查询变种,其在多目标决策与推荐领域有着广泛的应用。随着这些应用规模不断扩大,在由多个参与方组成的数据联邦中进行跨域k-支配Skyline查询的需求日益旺盛。然而,由于数据联邦中的参与方之间彼此不互信,进行跨信任域的查询计算需引入大量安全操作,效率较低。为此提出了一种基于跨域隐私向量聚合的算法,从而实现高效的联邦k-支配Skyline查询,并运用一种密文压缩技术进一步优化查询效率,最后通过充分的实验验证了所提方案的优越性。

一种基于路网的多源聚合距离Skyline查询算法

基于路网距离的多源Skyline查询在地图服务中广泛使用,但现有的Skyline查询方法对于复杂的路网距离计算效率低下,并且随着查询点数量的增加查询结果集变得过于庞大,无法为用户提供精简有效的查询结果。为了提高查询结果的有效性和查询效率,提出一种基于最小聚合距离的倒排索引Skyline查询算法,该算法对道路网建立QG-tree索引,提高聚合距离的计算效率;同时对兴趣点集建立倒排索引,结合剪枝策略对兴趣点进行检索,减少聚合距离计算和支配判定的开销,有效地提高查询效率。在真实道路网上的实验表明,所提出的算法效率比现有算法DSR和N3S快1~3个数量级,可以有效地处理道路网环境下多源Skyline查询问题。

一种网格化高并发Skyline查询处理方法

为减少冗余支配测试对Skyline查询性能的影响并提高Skyline查询处理的效率,本文将测试单位扩大为网格,并设计了一种基于网格分层划分的Skyline查询方法.通过不断缩小Skyline点集所在网格的方式,使网格之间的支配关系与点支配关系重合,从而避免了点与点之间大量无效的支配测试,提升了Skyline查询处理的效率.方法中同一层的网格可并行计算,且层次计算过程可达到任意精度,适用于计算能力有限但对结果精度要求不高的场合.实验结果表明,方法与现有Skyline查询处理方式相比具有数据吞吐量大、响应速度快等特点,在拥有高性能GPU或多核CPU等高并发环境下其优势更为明显.

面向高维数据的Skyline查询处理技术研究

Skyline查询是一种基本的数据库操作,在推荐系统等多标准决策场景中有许多应用.随着数据量的迅速增长和信息技术的不断发展,原有的高纬数据Skyline查询算法存在着成本高、速度慢的问题.本文提出了新的基于网格划分的Skyline查询算法,该算法有效利用了新型CPU结构多线程能力增强的特点,提高了对硬件的利用效率.在基于网格划分的思想下,数据空间被划分为多个网格,以网格为单位检查支配关系,这样可以按网格进行修剪,而无需检查每个网格中的点.实验结果表明,本文提出的算法在多个方面都优于最先进的Skyline算法,尤其在计算时间上的优势最为明显.

基于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点,人们提出了k-支配skyline的定义.但现有的用于k-支配skyline的算法在时间效率、空间复杂度和渐进输出性上都有待提高.该文提出了一种基于索引的高效k-支配skyline算法,通过为数据集建立两个索引,算法可以高效地进行计算,在时间、空间和渐进性上均优于现有的算法.

数据流上高效计算子空间Skyline的算法

流数据处理和多维空间中子空间上Skyline的计算是近年来数据管理与数据挖掘领域的研究热点.此前相关工作只专注于滑动窗口上Skyline的维护问题,未涉及到滑动窗口中子空间Skyline的计算.文中提出了一个基于网格索引的高效维护滑动窗口上Skyline的算法,以此为基础采用自顶向下的方式通过两个阶段增量式地返回目标子空间上的结果;开发的多个剪枝策略和启发式优化方法显著地提高了全空间Skyline的维护以及子空间Skyline的计算效率.理论分析和实验结果表明:与同类算法相比,文中提出的StreamSubsky算法以极少的时间开销就能输出第一个结果,并且算法具有良好的可扩展性.

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

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

云环境下基于超球面投影分区的Skyline计算

目前,Skyline查询在集中式数据库、分布式数据库、数据流及分类属性数据集上的良好应用前景,使其成为当前数据库界研究的重点和热点之一,受到了学术界和工业界的广泛关注,它作为一种重要的数据挖掘技术广泛应用于多目标优化、城市导航系统、用户偏好查询及约束决策、智能防御系统以及地理信息系统等领域。随着人类可以采集和利用的数据信息的急剧增长,如何处理大数据的Skyline查询成为急需解决的问题。针对云计算环境,在Map-Reduce框架下设计并实现了基于超球面投影分区的分布式Skyline算法HSPD-Skyline,其主要思想是通过对高维数据点的超平面投影映射,即由空间坐标转换为超球面坐标,可以有效提高分区内数据点的平均减枝力度,降低Skyline的计算代价。同时,使用基于空间分区树的启发式策略HA-SPT,进一步提高了HSPD-Skyline算法的处理效率。通过详细的理论分析和实验验证表明,在不考虑数据分布和进一步优化算法的条件下,提出的HSPD-Skyline算法的总体性能(可扩展性、Skyline查询时间等)优于同类算法。

基于社交的空间文本skyline查询

将社交信息应用到空间文本skyline查询中,提出了基于社交的空间文本skyline(SSTS)查询。SSTS查询中skyline对象的选择依赖于三个方面:与查询用户之间的距离、与查询关键字的文本相关性和在用户中的流行性。该查询引入了新型的函数计算它的社交相关性。为了提高查询者的满意度,扩展了SSTS查询,提出了受限的基于社交的空间文本skyline(constrained SSTS,CSSTS)查询,同时引入了一个新颖的概念受限skyline。针对每一种查询,应用了裁剪策略和终止条件,提高了查询速度。最后,通过实验验证了所提方法的有效性。

基于时间的空间文本关键词skyline查询

在移动互联网环境下,空间文本skyline查询可以有效支持用户在空间和关键词方面的查询。随着需求的多样性,基于用户经常会同时考虑空间距离、数值型信息、关键词和时间等因素对查询结果的影响,提出了基于时间的空间文本关键词skyline查询(Time based Spatial Text Keyword Skyline Query,TSTKSQ),用来查找在空间、数值、关键词和时间都满足条件的优秀对象,设计了基于时间的空间文本关键词skyline查询的索引结构STTR-Tree,提出了关键词、时间和时空关键词相关性的评价函数,在裁剪策略的基础上提出了skyline查询算法。通过实验结果分析,验证了算法的准确性和有效性。

基于约束分析的Skyline属性相对重要性发现算法

skyline查询广泛应用于多目标决策等应用领域.优先skyline关系通过引入属性相对重要性扩展了传统的skyline关系;并且应用优先skyline关系能够减小skyline查询的结果集.提出了基于约束分析的skyline属性相对重要性发现算法CABDA.CABDA算法直接分析构造优先skyline关系所必需满足的约束集合的特征,从而确定每个属性与其他属性之间的相对重要性,最终得到满足约束的优先skyline关系.实验表明,与已有方法相比,CABDA算法能够以更少的时间开销计算出能够有效减小skyline查询结果集的优先skyline关系.

Chord网络中的Skyline计算

针对Skyline计算中,需要处理的数据量大,处理时间较长的问题,引入P2P网络,将数据计算的压力分摊至各网络节点.预处理中,合理采用数据映射方式,增加同一节点数据间的决定能力,减少本地计算量.在全局Skyline计算时,通过网络点对点传输,将各节点需计算数据量减少至最小.实验结果和理论分析表明,新算法可将Chord网络中,本地节点需要计算的数据量减至10%左右,当数据量较大,数据各维度间没有相关性,且网络传输较为正常时,算法具有明显优势.

改进的不确定性数据概率Skyline查询算法

针对基于不确定性数据概率Skyline查询的bottom-up算法提出改进算法。bottom-up算法的核心是对象和实例的定界、裁剪和提纯三个过程的迭代。主要将原算法中逐个对象实例的分层迭代处理改为所有对象的实例由优到劣的迭代处理;将裁剪的条件和顺序也作了调整,使其更有效。理论分析和实验都证明,改进后算法运行效率可明显提高约20%。

数据流上约束的子空间Skyline计算

在数据流环境下,此前有关Skyline计算的研究涉及到滑动窗口上全空间Skyline的维护或子空间Skyline的计算,未考虑到满足约束条件的子空间Skyline计算。在首次研究数据流上约束的子空间Skyline渐进计算问题中,给出了具有良好渐进性的约束的子空间Skyline计算算法—CSSC,该算法首先通过增量维护滑动窗口中元组之间的非多余支配关系来计算约束的Skyline,然后在此基础上,将文献[8]中介绍的子空间Skyline计算方案引入到约束条件下,从而实现约束的子空间Skyline的计算。

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

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

基于云模型的不确定性QoS感知的Skyline服务选择

由于传统QoS感知的Web服务选择方法无法保证服务选择的可靠性和实时性,提出了一种基于云模型的不确定性QoS感知的Skyline服务选择方法.该方法首先通过云模型计算QoS的不确定性,然后采用Skyline计算提取Web服务中的Skyline服务,剔除冗余服务,最后采用混合整数规划在Skyline服务中进行服务选择.在公共有效数据集和合成数据集上的实验结果表明,所提出的方法能够为用户提供可靠、快速的服务选择.

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

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