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

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

存在级不确定数据上的概率Skyline计算

概率Skyline计算是在不确定对象集合中找出Skyline概率大于给定阈值的对象,在多目标决策应用中有重要价值.现有的存在级不确定数据上的概率Skyline算法均需要预先建立索引,在数据量很大、维度很高或数据频繁更新时,建立索引往往不可行或者不会带来性能的提升,因此有必要设计通用的非索引算法.提出了存在级不确定数据上概率Skyline的首个非索引算法,用已扫描的数据动态地维护一个概率约束空间,未来落入该空间的对象可以被安全地裁剪.在标准的模拟数据集上维度不超过4时裁剪比率超过99.8%,相比不用裁剪规则的基本算法,查询时间节省50%以上.

基于道路网络不确定移动对象的连续概率Skyline查询

Skyline查询是基于位置服务LBS的一项重要操作,其目的是发现数据集中不被其它点支配的点的集合。对道路网络环境下移动对象的连续概率Skyline查询进行了研究。在对道路网络和移动对象建模的基础上,定义了基于道路网络的数据间支配概率和Skyline概率的表示方式,提出了两类可能引起p-Skyline集合变动的event事件,并提出4条剪枝方案进行优化。在此基础上,设计了对网络受限的不确定移动对象进行连续概率Skyline查询的动态增量算法U-CPSQRN。该算法通过对event的跟踪计算实现了对p-Skyline的连续更新操作,减少了算法的查找和计算开销。实验结果显示了算法的有效性。

分布式不确定数据上的概率Skyline计算

提出了分布式不确定数据上概率skyline的低通信开销算法。首先给出了一种间接的对象分布信息——剪枝空间,分布节点通过共享全局剪枝空间,能够减少通信开销。为了降低传输剪枝空间带来的额外通信开销,对表示剪枝空间的虚拟对象集合进行基于距离的压缩。与基本算法相比,100个分布节点时,在真实数据集上节省了69%的通信开销;在均匀、正相关、反相关三种标准模拟数据上分别节省60.5%、41.8%、24.5%的通信开销。

传感器网络中基于过滤的概率Skyline查询算法

针对感知数据固有的不确定性问题,研究了无线传感器网络中概率Skyline查询的处理与优化技术.首先分析了概率Skyline查询的性质,证明了概率Skyline查询的不可分解性,因而无法直接利用网内计算方法求解;进而提出了无线传感器网络中基于过滤的概率Skyline查询处理算法(filter-based probabilistic Skyline query processing algorithm in WSN,FPSP).FPSP算法将感知数据划分为候选数据、相关数据和无关数据;只需要候选数据和相关数据即可求得概率Skyline查询结果,可以在传感器节点过滤无关数据以避免大量的数据网内传输.仿真实验结果表明,FPSP算法可以有效降低传感器节点的数据传输量,极大地延长了无线传感器网络的使用寿命.

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

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

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

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

不确定移动对象概率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的概率,并得到一个p-t-Skyline结果集,此集合包含所有在t时刻Skyline概率至少是p的移动对象。在实际应用中,计算大量不确定移动对象的Skyline概率过程繁琐,代价高昂。为提高概率Skyline查询过程的计算效率,本文提出包含"采样-限定-修剪-精炼"4个步骤的解决方案。同时,为进一步减少Skyline运算开销,本文使用一个多维索引结构VCI树以加快数据检索的效率。实验结果表明该解决方案在不同数据规模以及维度的数据集上均具有较高的效率。

移动环境下的连续概率Skyline查询

主要研究查询点固定,目标对象移动且移动对象在位置不确定的情况下,成为Skyline对象的可能性(采用概率形式表示),并实现移动对象位置不确定条件下的连续Skyline查询。定义了影响P-Skyline集合的Events,提出了一个基于事件的算法E-CPS,该算法并通过计算,跟踪和处理Events来更新P-Skyline集合。该方法大大减少了算法的查找和计算开销,提高了运算效率。

曼哈顿路网中移动数据点的连续概率Skyline查询

Skyline查询广泛应用于基于位置的服务系统中。近年来,曼哈顿道路网中的各种应用查询也广泛受到人们的关注。本文考虑到路网环境中目标数据点的不确定连续移动性,主要研究曼哈顿道路网中不确定移动数据点连续概率Skyline查询问题。在该查询中,查询点被视为静止的,而路网中兴趣点被视为移动目标数据点,具有被概率密度函数描述的不确定性。首先,根据目标数据点的初始位置和静态属性获得初始Skyline结果集;然后,根据移动数据点之间的支配关系计算可能导致Skyline结果集发生变化的事件;最后,根据计算获得的事件发生的先后顺序,更新概率Skyline结果集,从而实现连续概率Skyline查询。实验结果表明所提方法的可行性与准确性。

REPS:一种高效的容错并行概率流Skyline查询方法

概率数据流的并行Skyline查询作为当前大数据分析的一个重要方面,在诸多实际应用中发挥着重要作用。针对并行概率流Skyline查询过程中因发生故障而导致查询结果不准确和查询中断等问题,提出了一种基于复制的容错并行Skyline查询方法 REPS。该方法选择参与并行处理的计算节点作为副本节点,并采用层次-循环式数据副本放置策略,选择优先级高的副本恢复数据来保证数据恢复的高效性;同时将故障检测、丢失数据恢复和查询过程恢复贯穿于整个查询更新过程中,以减少容错处理的额外通信和计算开销,并实现快速的容错并行查询。实验结果表明,REPS方法不仅在无故障发生和单个节点失效时具有较高的查询处理效率,而且对于多节点失效情形,仍然能够保持较高的查询处理速率且满足查询需求。

位置不确定移动对象的连续概率反Skyline查询

反Skyline查询现在已经被广泛用于商业规划、环境监测及其它领域。当前的研究多集中在目标对象静止条件下的反Skyline计算。对移动环境下的目标对象不断运动变化并且位置不确定情况下的连续概率反Skyline计算进行了研究。在对移动对象间反支配关系进行细致分析的基础上,定义了反支配概率和反Skyline概率以及导致反Skyline集变化的process,提出了一种基于过程事件的算法来处理位置不确定移动对象的连续概率反Skyline查询算法,以通过计算、跟踪、更新这些process来快速找出p-RSky集合,并提出两个剪枝规则进行优化,避免了大量的无效计算。大量的实验证实了该算法的有效性。

非完整数据库Skyline-join查询

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

不确定场境下近似Skyline查询处理算法

近年来,不确定Skyline查询成为当前不确定数据查询研究的一个重要方面.Skyline查询结果通常与用户的偏好相关,而用户的偏好往往受当前场境的影响,并且现实中的场境往往来源于感知设备,具有不确定性.首次提出了不确定场境偏好可能世界语义建模下启发式算法和基于Monte Carlo思想的近似Skyline查询算法.首先,采用可能世界语义模型对不确定场境下偏好进行建模,并提出不确定场境下Skyline查询语义;其次,由于不确定场境下偏好构成的可能世界实例过于庞大,精确Skyline算法ESA是#P问题,提出LHSA和C&T两种启发式Skyline算法,从而大量裁减不满足最终结果的可能世界实例;进而,为了在保证用户指定精度的基础上提高Skyline查询效率提出了两种Monte Carlo近似算法:两阶段Monte Carlo近似算法PMA和改进的两阶段Monte Carlo近似算法MPMA;最后,通过实验对比5种算法,表明LHSA和C&T可以裁减大量可能世界实例,同时在确保精度的前提下,PMA和MPMA比启发式算法更有效,并且MPMA算法优于PMA算法.

P2P环境下面向不确定数据的Top-k查询

分布式环境中的top-k查询已经有了广泛的研究.由于仪器不精确和网络延时等原因,大多数分布式数据都存在不确定性.文中基于水平分布在P2P网络中的不确定数据提出了一个有效的top-k查询处理方法.首先利用Quad-tree构建一个分布式的不确定数据的索引,并基于索引提出了一个空间剪枝算法.然后,根据局部top-k概率与全局top-k概率之间的关系提出不确定数据成为top-k概率的上界,根据top-k概率与skyline概率之间的关系提出不确定数据成为top-k概率的下界,通过两种概率剪枝算法来减少top-k查询在网络中的传输和计算代价,并且进一步减少候选集大小.最后文中采用采样的方法来计算候选集的top-k概率以确定最终的top-k查询结果.大量的实验验证了算法的有效性.