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

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

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

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

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

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

基于曼哈顿距离的不确定移动对象概率Skyline查询

在众多应用中,由于受到测量仪器精度、更新延迟、网络带宽等限制,不同形式的数据不确定性广泛存在。目前,不确定数据中的信息查询受到数据库研究领域学者的关注,并且为不确定数据寻找高效的分析方法也成为了一个热门课题。本文针对基于曼哈顿距离的不确定移动对象概率Skyline查询问题,提出一个基于曼哈顿距离的概率Skyline模型用于求解不确定移动对象在某时刻是Skyline的概率,并得到一个p-t-Skyline结果集,此集合包含所有在t时刻Skyline概率至少是p的移动对象。在实际应用中,计算大量不确定移动对象的Skyline概率过程繁琐,代价高昂。为提高概率Skyline查询过程的计算效率,本文提出包含“采样-限定-修剪-精炼”4个步骤的解决方案。同时,为进一步减少Skyline运算开销,本文使用一个多维索引结构VCI树以加快数据检索的效率。实验结果表明该解决方案在不同数据规模以及维度的数据集上均具有较高的效率。     

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

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

不确定Skyline查询技术研究

当前不确定数据广泛存在于诸如传感器网络、RFID网络、基于位置服务、移动对象管理网上购物和市场监控等各种实际应用中.不确定Skyline查询作为不确定数据管理的一个重要方面,由于其在决策制定、市场分析、环境监控和数据挖掘等方面的重要作用,近年来在数据库和网络计算领域受到广泛关注.首先,概述了各种不确定数据类型上的Skyline查询定义,包括离散、连续概率分布模型以及不完全数据上的Skyline查询定义;其次,分析了不确定Skyline查询的特点,并在此基础上综述了现有的各种不确定数据集上的集中式和分布式Skyline查询方法,重点分析了各种算法的原理和优缺点;再次,介绍了不确定数据流上的Skyline查询定义并综述了各种不确定数据流上的Skyline查询方法;最后,基于最新研究动态指出了未来不确定Skyline查询研究的趋势.     

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

Skyline queries are widely used in location-based service systems. In recent years, various application queries in Manhattan road network have received considerable attention. Considering the uncertain continuous movement of objects in road networks, we mainly research the problem of continuous probabilistic Skyline queries for uncertain moving data points in Manhattan road networks. In such queries, the query point is considered to be stationary, and the objects in road network are treated as moving data points, which are described by the probability density function. First, we acquire the initial Skyline result set according to the initial location and static attributes of the data points, then, calculate the events that could cause the Skyline result set to change by the domination relations among those moving data points, and at last, update the probability Skyline result set according to the calculated events order so as to achieve continuous probability Skyline query. Experimental results show the efficiency and effectiveness of our proposed methods.     

基于MapReduce的连续概率Skyline查询

大数据对传统的Skyline研究产生了挑战,利用并行框架MapReduce计算大数据下的Skyline已成为一个研究热点。研究了不确定移动对象的Skyline查询问题,提出了一种MapReduce框架下基于事件跟踪的连续概率Skyline查询算法——MR-DTrack(domination-track algorithm based on MapReduce)。首先采用基于角度的划分方法保证负载均衡,通过预计算获取Skyline集可能变化的时刻,在Reduce阶段获取候选概率Skyline集;然后利用局部过滤点剪枝,减少计算开销;最后合并计算出全局概率Skyline集。在人工数据集和真实数据集上的实验验证了算法的有效性。     

不确定数据流上的并行Skyline查询算法

不确定数据流上的Skyline查询技术逐步引起研究者的关注,传统的集中式流处理算法难以满足海量数据的查询需求,并且云计算所提供的海量计算资源和有效的存储管理模式,为研究并行Skyline查询技术提供了充足的条件。基于上述事实,提出了一种不确定数据流上的并行Skyline查询算法(parallel Skyline over uncertain data streams,PSUDS)。该算法通过交叉划分滑动窗口的方式,将集中式流查询转化为并行处理,以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明,该算法具有较好的并行可扩展性。     

支持频繁位置更新的不确定移动对象索引策略

移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需求,如何在频繁位置更新应用中索引不确定移动对象的当前及未来位置信息成为当前的研究热点之一.TPU树是针对不确定移动对象的当前及未来位置信息索引的策略,其具有较高的概率域查询效率,但是其采用的传统自顶向下更新算法,存在频繁位置更新效率低下的问题.通过在TPU树上增加一个记录不确定移动对象状态特征的更新备忘录(UM)内存结构,文中提出了一种支持频繁位置更新的不确定移动对象索引策略TPU2M树,并在此基础之上提出了一种改进的基于备忘录(MMBU/I)的更新/插入算法.代价分析和实验仿真表明,采用MMBU/I算法的TPU2M树频繁更新性能大大优于TPU树和ABx树索引,且概率查询性能与传统索引大致相当,因此具有很好的实用价值和广泛的应用前景.     

基于TPU-tree的Skyline分支定界查询算法(英文)

提出了一种新的限定性skyline查询理念,并给出了高效的处理技术。分支定界方法是当前skyline查询处理效率较高的技术之一,在一种不确定移动对象的索引策略TPU-tree之上,基于分支定界方法提出了B2CPS可限定性skyline查询处理算法。实验结果表明,提出的基于TPU-tree的B2CPS算法可以很大程度地提高限定性skyline查询的效率,在移动对象频繁更新的情况下亦能保持较高的查询性能,因此具有较好的实用价值。     

移动对象的连续最近邻查询算法

介绍了一种索引结构———TPR树和静态环境中基本的最近邻查询算法,并提出了影响时间这一概念,将其运用到最近邻查询算法中,可以完成移动对象的连续最近邻查询。     

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

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

时间区间上的不确定移动对象距离范围查询

针对目标对象与查询发出者皆为不确定移动对象的情况,提出了一种时间区间上的距离范围查询（DRqTI）.此类查询搜索出数据集中在给定时间区间内,到查询发出者距离不超过阈值的目标对象,查询结果中包含对象满足查询条件的有效时间段和匹配度.提出了基于轨迹、基于时间区间和基于距离的三种剪枝策略,并给出了精炼和匹配度计算方法,在此基础上设计了查询处理算法.实验分析表明,三种剪枝策略中基于距离的方法性能最佳,提出的算法能有效处理DRqTI问题.     

Main Memory Evaluation of Monitoring Queries Over Moving Objects

In this paper we evaluate several in-memory algorithms for efficient and scalable processing of continuous range queries over collections of moving objects. Constant updates to the index are avoided by query indexing. No constraints are imposed on the speed or path of moving objects or fraction of objects that move at any moment in time. We present a detailed analysis of a grid approach which shows the best results for both skewed and uniform data. A sorting based optimization is developed for significantly improving the cache hit-rate. Experimental evaluation establishes that indexing queries using the grid index yields orders of magnitude better performance than other index structures such as R*-trees.