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

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

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

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

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

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

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

基于MapReduce的连续概率Skyline查询

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

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

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

基于位置的路网Skyline查询处理研究

基于位置的路网Skyline查询可根据用户的需求及用户所处的位置,从大量数据中快速返回给用户期望的数据,但已有的道路网络技术需要计算大量的路网距离及数据点间支配关系的运算,导致查询效率较低。提出一种基于路网数据点的倒排索引查询算法DSR。通过计算少量数据点的路网距离求得最终结果,减小路网距离计算的代价,从而加快数据点间支配关系的判定,提升查询效率。在此基础上,在数据点更新情况下给出算法的动态维护,仅通过维护少量数据,DSR即可以快速地计算出Skyline集合。实验结果表明,与SSI、BSS等算法相比,该算法具有较高的查询效率,且时间性能明显提升。     

不确定Skyline查询技术研究

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

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

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

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

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

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

基于偏好的个性化路网匹配算法

定位技术的普遍应用,使得随时随地获取个人位置成为可能,进一步推动了基于位置的服务等新型应用的发展,产生了海量轨迹数据.精确的路网匹配对提高这些新型应用的服务质量具有重要的研究意义,然而受众多因素的影响,大部分轨迹的采样率较低,比如由签到类应用或低功耗设备生成的低采样轨迹,给路网匹配带来了巨大的挑战.研究基于偏好的个性化路网匹配（driving preference based personalized map-matching,简称DPMM）,提出了在动态道路交通网络中的用户驾驶偏好模型.基于该模型,提出了两阶段路网匹配算法：局部匹配搜索用户最可能采用的几条局部Skyline路径;设计了全局匹配的动态规划算法,该算法返回在用户驾驶偏好下最可能的多条全局路径作为最终匹配结果.实验结果充分表明,该方法是有效的和高效的,具有一定的使用价值.     

路网中位置不确定的二元反kNN查询

针对路网限制和物体位置的不确定性,提出了路网中位置不确定的二元反kNN查询（PBRkNN）,旨在查找一组位置不确定的点,使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题,首先提出一种基于Dijkstra进行剪枝处理的基本算法,即PE算法;接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度,即PPE算法;而为了进一步减小PPE算法中范围查询的开销,提出PPEE算法,利用网格索引来索引范围查询中要查询的不确定空间点,从而提升算法的效率。最后,在北京和加州路网数据集上进行了大量实验,结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。