高速流环境下近似连续k代表轮廓查询算法

k代表轮廓查询是从传统轮廓查询中衍生出来的一类查询.给定多维数据集合D,轮廓查询从D中找到所有不被其他对象支配的对象,将其返回给用户,便于用户结合自身偏好选择高质量对象.然而,轮廓对象规模通常较大,用户需要从大量数据中进行选择,导致选择速度和质量无法得到保证.与传统轮廓查询相比,k代表轮廓查询从所有轮廓对象中选择“代表性”最强的k个对象返回给用户,有效地解决了传统轮廓查询存在的这一问题.给定滑动窗口W和连续查询q,q监听窗口中的数据.当窗口滑动时,查询q返回窗口中,组合支配面积最大的k个对象.现有算法的核心思想是:实时监测当前窗口中的轮廓对象集合,当轮廓对象集合更新时,算法更新k代表轮廓.然而,实时监测窗口中,轮廓集合的计算代价通常较大.此外,当轮廓集合规模较大时,从中选择k代表轮廓的计算代价是同样巨大的,导致已有算法无法在高速流环境下使用.针对上述问题,提出了ρ-近似k代表轮廓查询.为了支持该查询,提出了查询处理框架PAKRS(predict-based approximate k representative skyline).首先,PAKRS利用高速流的特性对当前窗口进行划分,根据划分结果构建未来窗口预测结果集,用其预测新流入窗口数据成为轮廓对象的最早时间.其次,提出了索引ρ-GRID.它帮助PAKRS在2维和d维(d>2)环境下,分别以O(k/s+k/m)和O(2Ld/m+2Ld/s)的增量维护代价下筛选近似k代表轮廓,L是一个小于k的正整数.由理论分析证明可知,PAKRS的计算复杂度小于前人所提的算法计算复杂度.最后,通过大量实验对所提算法性能进行评估.结果表明,PAKRS的运行时间是PBA(prefix-based algorithm)算法的1/4、GA(greedy algorithm)算法的1/6、ε-GA(ε-constraint greedy algorithm)算法的1/3.

一种ρ-支配轮廓查询的高效处理算法

近年来,作为重要的多目标决策手段的轮廓查询逐渐得到学术界的重视,相继提出了基于不同支配关系的多种轮廓变体查询.首先,通过对实际应用需求进行分析,提出了基于元组对应数值间比例值大小的ρ-支配关系的定义,进而提出了ρ-支配轮廓查询的概念.其次,对ρ-支配轮廓的基本性质进行了细致而深入的分析,在此基础上,提出了基于分支定界的ρ-支配轮廓查询算法(Branch and Boundρ-Dominant Skyline Algorithm,BBDS),避免了对R-树索引的多次访问,从而提高了ρ-支配轮廓查询的执行效率.最后,通过大量的仿真实验对ρ-支配轮廓查询的语义进行分析,并对BBDS算法的性能进行验证.实验结果表明,ρ-支配轮廓查询是轮廓查询语义的扩展和补充,而提出的BBDS算法则是求解ρ-支配轮廓查询的高效算法.

不确定数据流上的概率反轮廓查询处理

反轮廓查询在制定有效的市场决策方面具有重要的作用,随着数据流特征和不确定性的表现日益明显,不确定数据流上概率反轮廓查询已经成为一个新的研究课题.为了高效解决不确定数据流上概率反轮廓查询问题,首先,通过对实际应用需求进行分析,提出了不确定数据流上概率反轮廓查询的定义,并根据相关概念,提出了不确定数据流上概率反轮廓查询的索引模型;其次,通过对不确定数据流上概率反轮廓的性质进行深入分析,提出了一种新颖高效的基于R-tree的不确定数据流上概率反轮廓查询算法RT2RS,该算法运用了高效的剪枝策略,避免了大量的无效运算;最后,通过大量的仿真实验对RT2RS性能进行了验证.实验结果表明,RT2RS是解决不确定数据流上概率反轮廓查询的有效方法,大大减少了不确定数据流上概率反轮廓查询的运行时间,能够满足实际应用需求.

超对等网络中的轮廓查询优化

轮廓查询是近年来信息服务领域的一个研究重点和热点.现有的三阶段算法TPAOSS(Three-PhaseAlgo-rithm for Optimizing Skyline Scalar)至少存在如下两个缺陷:(1)在TPAOSS算法的第3阶段中,当网络节点上的对象个数较多时,Bloom filter的长度将呈指数级增长,从而严重影响获取子空间重复值的效率以及占用内存空间的大小;(2)TPAOSS算法只考虑预处理阶段的时间代价,而没有考虑各网络节点进行局部或全局子空间轮廓查询计算的效率.为此,提出一种适合超对等网络(Super-Peer Architecture,SPA)的子空间轮廓查询方法EPSSQDN(Efficient Processing of Sub-space Skyline Queries in Distributed Networks).EPSSQDN算法有效解决了TPAOSS算法的的两个主要性能问题,并且显著提高了SPA网络中的子空间轮廓查询处理的效率.此外,为了能够进一步降低子空间上轮廓查询的时间开销以及网络节点间的数据传输量,我们给出新颖且有效的优化策略.实验结果表明,EPSSQDN算法比TPAOSS算法更能够缩短SPA网络中子空间轮廓查询的时间开销.

无线传感器网络中的近似轮廓查询算法

近年来,无线传感器网络被广泛地应用到国民经济的各个领域.在传感应用中,轮廓查询作为多目标决策和数据挖掘的重要手段发挥着重要的作用.然而,由于轮廓查询需要消耗大量能量,因此在传感器网络中计算真实轮廓是非常不经济的.事实上,在大多数的应用中,近似轮廓已经可以反映数据的大致状态.通过对近似轮廓的语义研究,本文提出基于选择的基本近似轮廓算法(BAS)和基于映射的误差保证的近似轮廓算法(GAS)来高效地计算传感器网络中的近似轮廓.实验结果表明,这两种算法能有效地减少传感器网络中的通信代价,进而延长传感器网络的使用寿命.

无线传感器网络中滑动窗口轮廓查询算法

提出了一种基于过滤的算法(filter based algorithm,FBA)来连续地维护传感器网络中的滑动窗口轮廓查询。首先,研究了利用元组过滤器和格过滤器来减少网络中数据传输量的两种方法。由于它们各有利弊,提出了根据数据分布来选择合适的过滤器的自适应过滤法;另外,提出了一系列的优化方法来进一步提高算法的能量有效性。仿真和真实数据的实验结果表明,FBA及其优化方法能有效地减少连续维护传感器网络中滑动窗口轮廓时的通信代价,进而节约传感器网络的能量。

MapReduce框架下k-支配轮廓查询算法

随着维度和数据量的不断增长,已有的轮廓查询方法已无法为用户提供更好的查询支持。本文采用并行处理框架Map Reduce结合K-支配轮廓查询算法来解决此类查询问题。在对输入的数据集进行预排序的基础上,提出了基于Map Reduce的单轮扫描算法和双轮扫描算法,通过在不同维度、数据分布、节点个数等方面的实验测试及对比,验证了算法的有效性。

数据流环境下的关键词轮廓查询算法

本文针对滑动窗口模型下的连续关键词轮廓查询问题,提出了一种流数据环境下的关键词轮廓查询算法.其通过对当前窗口进行划分,过滤掉大部分不可能成为查询结果的对象,克服了数据间时序关系对算法性能带来的影响.本文还提出了关键词轮廓网格索引KSG(Keyword Skyline Grid),实现了对各分片中对象的有效关键词过滤以及轮廓过滤.另外,本文通过调整分片粒度,实现了窗口的有效划分.最后,本文通过大量实验对所提算法的性能进行了评估,实验结果表明,本文所提算法PSKSWI(Partition-based Continuous Keyw ord Skyline w ith Index)与basline算法相比,查询效率提高了71%,与不带索引的查询算法PSKS(Partition-based Continuous Keyw ord Skyline)相比,查询效率提高了32%.

基于连接操作的反轮廓查询处理算法

反轮廓查询在制定有效的市场决策方面具有重要的作用.随着信息量的增加,数据库中跨表的数据查询变得十分普遍.深入分析了基于数据表连接操作的反轮廓查询处理的性质,结合网格索引结构和两种提前终止策略,提出基本反轮廓连接查询算法(Basic Reverse Skyline Join Algorithm,BRSJ),并通过将半支配操作提至连接操作之前对算法进行了改进,提出改进的反轮廓连接算法(Progressive Reverse Skyline Join Algorithm,PRSJ).实验结果表明,两种提前终止策略可以有效的减少数据访问量,两种算法均能获得很高的性能,并且后者在时间性能上更优于前者.两个算法都大大提高了基于连接操作的反轮廓查询处理的性能.

缓存模式下的轮廓查询优化方法

研究在缓存模式下,利用一组预存储的临时轮廓快照集来高效等价重构用户新提交的轮廓查询Q,并提出一种新颖的缓存模式下轮廓查询处理算法(APSQCM)来完成该任务.APSQCM算法由两阶段组成,第一阶段捕获Q与缓存中临时轮廓快照间的内在关联,进而获取能够用来等价重构Q的所有轮廓基;而在第二阶段中,APSQCM算法使用轮廓基来快速产生Q的正确结果集.实验结果表明,APSQCM算法具有有效性和实用性.

基于轮廓查询技术的P2P智能搜索算法

资源搜索是非结构化P2P系统研究的核心问题,选取合适的邻居节点作为转发对象,可以提高资源搜索成功率。该文提出一种基于轮廓查询的P2P智能搜索算法SkyLP,在选取邻居节点转发查询消息时,综合考虑查询消息相似度和节点命中率。在两者构成的二维空间上,采用轮廓查询技术返回一个最优邻居节点集合,向此集合中的节点发送查询消息。实验结果表明,SkyLP算法能减少发送的消息数,有效提高搜索效率。

空间数据库轮廓查询关键技术分析和展望

空间查询及优化技术是研究空间数据的难点。轮廓查询技术对于各种数据库和网络应用中的空间查询及优化起着至关重要的作用,已经成为空间查询及优化领域的热点课题。该文对现有的轮廓查询关键技术进行了分析和总结,并对未来的发展方向进行了展望。

基于网格索引的数据流子空间概率轮廓查询

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间。

一种高效的分布式序敏感轮廓查询处理算法

提出了一种新颖的分布环境中的序敏感轮廓查询算法(即找出不被别的对象所"支配"的且聚集值较高的对象)。现有的算法在节点数m较大时会消耗大量的网络带宽。提出了一种新的分布式序敏感轮廓查询处理算法(Distributed Rank-aware Skylining,DRS)。DRS算法在任意数据集上只需要4次交互就能完成,并且通过剪除不必要的对象来减少通讯代价。通过模拟数据验证了DRS算法的效率。实验表明,当节点数m大于4时,DRS算法性能优于现有算法的性能。

基于动态窗口的轮廓查询技术研究

本文通过对几种轮廓查询技术的比较,选择基于动态窗口的轮廓查询技术作为研究对象,对其算法思想、算法描述和算法分析进行了详细的阐述,并结合流动人员管理信息系统对其进行了具体的设计与实现。

基于历史数据的轮廓聚合查询

轮廓查询在涉及多标准决策的空间数据库、数据挖掘、测试观察、用户偏好查询、可视化等领域起着非常重要的作用.近年来人们对于轮廓算法的研究已经趋于完善,尤其对于轮廓的计算.针对一些数据具有历史性这一特点,在具体应用领域中,提出了一种新的查询方法,即基于历史数据的轮廓聚合查询,针对不同的聚合函数,提出了基本算法CETAN. 并在此基础上对算法进行了改进,提出了AACN算法和基于过滤策略的ABT算法.实验结果表明,算法是有效的,极大改善了查询的精确性和多样性.

星型模型的轮廓连接查询算法

轮廓查询在多标准决策中具有重要应用价值,对于单表轮廓查询已有大量研究,但在实际中,轮廓查询的属性很可能分布在多张表中。如果在多表连接之后进行轮廓查询,随着维度和元组数目的增加,计算代价会越来越大。为此,针对数据仓库中星型模型的数据特点,提出了三种此模型下的多表连接轮廓查询算法并对算法进行了实验比较分析。结果表明,此算法比先连接再做单表轮廓查询的算法更为有效,并且这三种算法在不同特点的数据集合下会表现出各自的优势。

不动产登记空间数据库轮廓体更新方法

提出不动产登记空间数据库轮廓体更新方法,针对不动产登记数据的管理要求,构建空间数据库模型,依托修剪空间定理和动态查询窗口,识别空间数据轮廓。根据轮廓体更新原理,结合Addpoint_Skycube算法和Deletepoint_Skycube算法,设计轮廓体数据更新技术,再通过临时数据库的过滤,完成不动产登记数据库的准确更新。实验结果显示:所提数据库更新方法的执行时间较短,分别缩短了74.2%与68.5%。完成不动产登记空间数据库更新后,可保证不动产登记过程的完整性。

一种更新k-支配轮廓的算法

k-支配轮廓查询技术在计算高维空间数据集时,解决了查询结果集合过大的问题,更有利于用户决策;然而,现有的算法都是针对静态k值设计的,不适合k值动态变化的情况。为了解决此问题,提出一种思路,即当k值改变以后,以现有的查询结果为基础,通过对可能发生身份变化的数据点进行判断,得到新的k-支配轮廓。在此基础上分别针对k值增大和k值减小这两种情况提出了相应的更新算法。通过理论分析和实验,算法能快速完成运算并返回正确查询结果。

一种求解动态数据集中k-支配轮廓的算法

在对高维数据集进行轮廓查询时,k-支配轮廓查询算法能够返回较少的轮廓点,有利于用户的决策,但目前的算法都是针对静态数据集设计,无法对动态数据集进行处理.动态数据可分为非数据流数据和数据流数据,本文针对这两种情况提出了相应的增量求解算法,即当数据集发生变化时,以现有的k-支配轮廓为基础,通过对部分数据点进行计算得到新的k-支配轮廓.证明了算法的正确性和有效性,并通过实验对算法进行了分析和验证.