不确定移动对象概率Skyline集的查询更新

Skyline查询的研究已从传统的静态Skyline操作延伸到动态的、不确定数据集上的Skyline查询和计算上。研究了移动环境下,查询点位置固定、目标点处于运动状态并且位置不确定情况下的连续概率Skyline计算问题。这个过程中,移动对象与查询对象之间的距离随时间不断变化。移动对象由于其运动状态导致位置无法精确定位,因此移动对象之间的支配关系只能采用概率形式表示,且随时间不断变化。给出了移动对象间的支配概率的定义,以及移动对象Skyline概率的定义,并定义了触发事件来记录对象支配概率发生变化的时刻,实现概率Skyline计算的连续跟踪和动态更新。提出了基于事件触发的连续概率Skyline查询算法(event triggered continuous probabilistic Skyline query for uncertain moving object,U-ECPS),对移动环境下的Skyline集进行连续查询和更新。大量的实验结果验证了U-ECPS算法的有效性。     

基于MapReduce的连续概率Skyline查询

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

基于事件的位置不确定移动对象连续概率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集合。该方法大大减少了算法的查找和计算开销,提高了运算效率。     

面向服务环境中的NServiceBus服务总线应用研究

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

不确定Skyline查询技术研究

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

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

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

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

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

路网中速度不确定移动对象的k近邻查询

目前在基于道路网的移动对象的各类查询研究中,大多都是在假定移动对象速度固定不变的基础上进行的.而实际上因为外界环境和自身情况等不确定性因素的影响,对象的速度可能会发生变化.基于此,本文提出一种基于路网的速度不确定的移动对象的k近邻查询处理方法.在查询时刻根据查询点位置执行查询操作,得到构成查询点k近邻的候选对象集合,再根据概率计算方法得到结果集及其概率.实验结果表明本文所提方法是有效的.     

非完整数据库Skyline-join查询*

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

曼哈顿路网中移动数据点的连续概率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.     

k-dominant Skyline query algorithm for dynamic datasets

At present,most k-dominant Skyline query algorithms are oriented to static datasets,this paper proposes a k-dominant Skyline query algorithm for dynamic datasets.The algorithm is recursive circularly.First,we compute the dominant ability of each object and sort objects in descending order by dominant ability.Then,we maintain an inverted index of the dominant index by k-dominant Skyline point calculation algorithm.When the data changes,it is judged whether the update point will afect the k dominant Skyline point set.So the k-dominant Skyline point of the new data set is obtained by inserting and deleting algorithm.The proposed algorithm resolves maintenance isue of a frequently updated database by dynamically updating the data sets.The experimental results show that the query algorithm can efectively improve query eficiency.     

Fuzzy Distance-Based Range Queries over Uncertain Moving Objects

Data obtained from real world are imprecise or uncertain due to the accuracy of positioning devices,updating protocols or characteristics of applications.On the other hand,users sometimes prefer to qualitatively express their requests with vague conditions and different parts of search region are in-equally important in some applications.We address the problem of efficiently processing the fuzzy range queries for uncertain moving objects whose whereabouts in time are not known exactly,for which the basic syntax is find objects always/sometimes near to the query issuer with the qualifying guarantees no less than a given threshold during a given temporal interval.We model the location uncertainty of moving objects on the utilization of probability density functions and describe the indeterminate boundary of query range with fuzzy set.We present the qualifying guarantee evaluation of objects,and propose pruning techniques based on the α-cut of fuzzy set to shrink the search space efficiently.We also design rules to reject non-qualifying objects and validate qualifying objects in order to avoid unnecessary costly numeric integrations in the refinement step.An extensive empirical study has been conducted to demonstrate the efficiency and effectiveness of algorithms under various experimental     

面向存在不确定对象的组最近邻查询方法

组最近邻查询是空间对象查询领域的一类重要查询,通过该查询可找到距离给定查询点集最近的空间对象.由于图像分辨率或解析度的限制等因素,空间对象的存在不确定性广泛存在于某些涉及图像处理的查询应用中.这些对象位置数据的存在不确定性会对组最近邻查询结果产生影响.本文给出面向存在不确定对象的概率阈值组最近邻查询定义,设计了高效的查询处理机制,通过剪枝优化等手段提高概率阈值组最近邻查询效率,并进一步提出了高效概率阈值组最近邻查询算法.采用多个真实数据集对概率阈值组最近邻算法进行了实验验证,结果表明所提算法具有良好的查询效率.     

基于高斯模型的不确定数据流Skyline查询方法

由于数据的动态性及不确定性等特征,使得不确定数据流上Skyline查询研究面临挑战.不确定对象一般采用多元概率密度函数(PDF)表示,现有的不确定数据流Skyline查询方法均采用离散型随机变量建模.然而不确定数据流中的对象可能是连续变化的,离散模型对连续性随机变量难以适用.针对连续PDF建模的不确定数据流Skyline查询进行了研究,提出了基于高斯模型的不确定数据流Skyline查询方法(SGMU),该方法包含2个过程:1)动态高斯建模算法(DGM):对滑动窗口采样并建立高斯模型,将原始的数据流转化为不确定对象PDF的参数流;2)提出了基于高斯树的查询算法(GTS)以建立空间索引结构和执行Skyline查询.实验结果表明,SGMU算法不仅能够对连续型不确定对象进行有效建模以辅助Skyline查询,而且能够有效地减少查询对象个数,提高Skyline查询效率.     

Finding the least influenced set in uncertain databases

Due to the inherent existence of uncertainty in many real-world applications, in this paper, we investigate an important query in uncertain databases, namely probabilistic least influenced set (PLIS) query, which retrieves all the uncertain objects in an uncertain database such that they are the least affected by a given query object with high probabilities. Such a PLIS query is useful in applications such as business planning. We propose and tackle both monochromatic and bichromatic versions (i.e. M-PLIS and B-PLIS, respectively) of the PLIS query. In order to efficiently answer PLIS queries, we present three pruning methods, MINMAX, Regional, and Candidate pruning, which can effectively reduce the PLIS search space. The proposed pruning methods can be seamlessly integrated into efficient query procedures. Moreover, we also study important variants of PLIS query with uncertain query object (i.e. UQ-PLIS). Furthermore, we formulate and tackle the PLIS problem on uncertain moving objects (i.e. UMOD-PLIS). Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approaches under various settings.     

复杂障碍空间中基于移动对象运动规律的不确定轨迹预测

现有移动对象的轨迹预测大部分是针对路网空间,然而在实际地理环境中往往存在障碍物,移动对象的运动基本在障碍空间中进行。近年来,已有较多关于路网空间中移动对象轨迹预测的研究以及障碍空间中障碍范围查询、最近邻查询等的研究,但是目前尚没有障碍空间中移动对象不确定轨迹预测的相关研究。为此,提出障碍空间中基于移动对象运动规律的不确定轨迹预测方法。首先,利用障碍物之间的区域关系对障碍空间进行剪枝;其次,提出障碍空间期望距离概念,对障碍空间的轨迹数据进行轨迹聚类,从而挖掘移动对象的热点区域;然后,根据各热点区域间的障碍距离和历史访问习惯得到转移的综合概率,提出基于移动对象运动规律的轨迹预测算法;最后,通过实验验证了算法的准确性和高效性。