云计算环境下的容错并行Skyline查询算法研究

云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时,其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能,不能保证故障情况下查询继续正确执行。为此,提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline,FTPS)。该算法通过故障监测和任务迁移,使得能够在查询过程中及时发现故障,并将故障节点的计算任务迁移到副本节点,保证查询的正确执行。理论分析和实验证明,FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。     

Efficient skycube computation using point and domain-based filtering

Skyline queries have been increasingly used in multi-criteria decision making and data mining applications. They retrieve a set of interesting points from a potentially large set of data points. A point is said to be interesting if it is not dominated by any other point. Skyline cube (skycube) consists of skylines of all possible non-empty subsets of a given set of dimensions. In this paper, we propose two algorithms for computing skycube using bitmaps that are derivable from indexes. The Point-based skycube algorithm is an improvement over the existing Bitmap algorithm, extended to compute skycube. The Point-based algorithm processes one point at a time to check for skylines in all subspaces. The Domain-based skycube algorithm views points as value combinations and probes entire search space for potential skyline points. It significantly reduces bitmap access for low cardinality dimensions. Our experimental study shows that the two algorithms strictly dominate, or at least comparable to, the current skycube algorithm in most of the cases, suggesting that such an approach could be a useful addition to the set of skyline query processing techniques.     

不确定移动对象概率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查询算法,该算法对道路网建立QG-tree索引,提高聚合距离的计算效率;同时对兴趣点集建立倒排索引,结合剪枝策略对兴趣点进行检索,减少聚合距离计算和支配判定的开销,有效地提高查询效率。在真实道路网上的实验表明,所提出的算法效率比现有算法DSR和N3S快1~3个数量级,可以有效地处理道路网环境下多源Skyline查询问题。     

Skyline在数字矿山中的应用研究

矿山的三维建模及虚拟场景搭建是数字矿山的基础.Skyline Terrasuite平台为矿山三维建模及虚拟场景的实现提供了实用的手段和方法.通过对相关建模技术和方法进行研究,分析矿山各类实体的特征并对其分类,充分结合矿山区域高分辨率影像、大比例尺地形图和实地拍摄的照片等构建实体模型,在Skyline Terrasuite中完成矿山三维场景的虚拟仿真.本文在矿山现有数据的基础上,研究了地面建筑和地下巷道等主要物体的建模方法.实验结果表明,三维矿山实现动态的、逼真的模型表达,为数字矿山的建设提供了一种有效的方法.     

基于Skyline的城市地下三维管线建立研究

传统二维管线系统难以直观地反映各管线之间的立体空间位置关系。旧管线更新、新管线规划、管线设计施工、土建工程的破土动工等都需要准确掌握地下管线的现状信息,如果盲目开挖就会引起自来水管爆裂、煤气泄露、停电、通信信号中断等事故。以地下管线为研究对象,以Skyline为平台,C#为开发语言建立城市三维管网系统,在错综复杂的条件下展现各管线之间以及管线与周边地物之间的空间位置关系,实现管线的查询和分析功能。     

面向大规模数据集的并行化Top-k Skyline查询算法

随着数据规模的日益庞大,在大规模数据集中帮助用户定位出数据量可控的代表性信息显得越发重要。虽然Top-k Skyline查询能够找到数据集中前k个最具代表性的信息,在获取代表性信息的同时又控制了结果规模,满足了上述要求,但是现有的Top-k Skyline查询在面对大规模数据集时效率较低,并不适用于大规模数据集。为了解决这个问题,将Top-k Skyline查询与并行化处理相结合,提出了一种面向大规模数据集的并行化Top-k Skyline查询算法PTKS（parallel Top-k Skyline）,通过充分利用分布式资源,将原有查询进行有效的并行化处理,同时设计了基于用户偏好的用于缩减结果数据量的筛选规则,满足用户需求。在真实数据集上进行了相关实验,并与现有方法进行了对比,结果表明PTKS在大规模数据集上的查询效率更具有优势,能很好地适用于大规模数据集。     

两层传感器网络隐私保护Skyline查询协议

无线传感器网络中隐私保护技术已经成为研究热点,其中隐私保护精确Skyline查询协议已成为富有挑战性的研究问题.提出一种两层传感器网络隐私保护Skyline查询协议(PPSQ).该协议通过采用Z-O编码技术并结合HMAC机制,使得存储节点可以在无需感知数据明文的情况下判断出元组的支配关系,从而得出密文查询结果,保护了数据的隐私安全性;并通过辅助计算节点计算的验证码来保证查询结果的完整性.理论分析和实验结果表明,PPSQ协议能够保证感知数据、查询结果的隐私安全性和查询结果的完整性,且性能优于现有工作.     

海洋数据质量检验方案中残差优化选择算法磁

随着信息化的快速发展,海洋数据的获取手段变得多种多样,海洋数据的“量”急剧增大,如何保证海洋大数据的质量问题成为热点。抽样检验是一个较成熟的课题,但适用于海洋数据特性的抽样方案研究较少。结合海洋数据的特点,利用 Skyline 的思想,提出了分批排序的优化抽样检验方案选择算法。通过各抽样检验方案残差的 Skyline 集合,选择优化的质量检验方案,提高海洋数据质量检验精度的同时保证海洋数据的检验费用。     

武汉市长江两桥之间沿江景观规划初探

在城市总体规划的指导下,通过对长江一桥、二桥之间沿江地区用地布局、景观构成要素的设置及交通组织等方面的结合分析,划定和沿江标志性景观分区,确定各分区的景观特征,提出城市设计要求,为下一步进行详细规划奠定基础,引导该地区发展成为武汉市城市形象的标志性景观区。