EAPSC:有效聚类skyline对象集方法

提出SkyCluster的概念,对skyline对象进行基于密度的聚类.另一方面,由于skyline查询和聚类处理均是CPU-敏感的.因此,为了提高获取SkyCluster的效率,提出一种有效聚类skyline对象集的方法EAPSC.EAPSC算法基于文章给出的SLT索引树,并利用SLT索引树的多个有效性质来快速产生所有的SkyCluster聚类.理论分析和实验结果表明,该方法具有有效性和实用性.     

面向多请求的Web服务全局优化选择模型研究

在大量相似Web服务共存竞争的环境下,基于服务质量的Web服务选择成为服务计算领域的热点问题之一.现有的Web服务选择方法主要研究单个服务请求或多个合作关系的服务请求共同选择某一个服务的情形,未考虑多个独立的服务请求同时请求同种功能服务的互相竞争性.针对该问题,根据Web服务与服务需求之间的匹配度,利用0-1整数规划建立全局优化服务选择模型,并结合实际提出通用可行的解决多请求的全局优化服务选择算法(global optimal service selection for multiple requests, GOSSMR),在保证Web服务需求质量得到满足的情况下,避免过多的请求同时选择同一个服务,做到资源合理利用,避免服务负载失衡,提高系统的性能.仿真实验验证了模型算法的可行性和有效性.     

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

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

An efficient approach to finding potential products continuously

Skyline points and queries are important in the context of processing datasets with multiple dimensions. As skyline points can be viewed as representing marketable products that are useful for clients and business owners, one may also consider non-skyline points that are highly competitive with the current skyline points. We address the problem of continuously finding such potential products from a dynamic d-dimensional dataset, and formally define a potential product and its upgrade promotion cost. In this paper, we propose the CP-Sky algorithm, an efficient approach for continuously evaluating potential products by utilizing a second-order skyline set, which consists of candidate points that are closest to regular skyline points (also termed the first-order skyline set), to facilitate efficient computations and updates for potential products. With the knowledge of the second-order skyline set, CP-Sky enables the system to (1) efficiently find substitute skyline points from the second-order skyline set only if a first-order skyline point is removed, and (2) continuously retrieve the top-k potential products. Within this context, the Approximate Exclusive Dominance Region algorithm (AEDR) is proposed to reduce the computational complexity of determining a candidate set for second-order skyline updates over a dynamic data set without affecting the result accuracy. Additionally, we extend the CP-Sky algorithm to support the computations of top-k potential products. Finally, we present experimental results on data sets with various distributions to demonstrate the performance and utility of our approach.     

基于Skyline的三维地形建模实现——以甘肃省政务地理信息平台为例

以航空影像、卫星影像、数字高程模型和相关专题数据为数据源,利用Skyline软件完成甘肃省政务地理信息平台的三维场景建设,重点阐述了在海量数据前提下,运用多CPU协同计算的方式构建三维地形模型的流程和方法,最后通过案例介绍了平台三维系统的应用方向和价值。     

基于MapReduce的Skyline查询处理算法

Skyline查询是一个典型的多目标优化查询,在多目标优化、数据挖掘等领域有着广泛的应用。现有的Skyline查询处理算法大都假定数据集存放在单一数据库服务器中,查询处理算法通常也被设计成针对单一服务器的串行算法。随着数据量的急剧增长,特别是在大数据背景下,传统的基于单机的串行Skyline算法已经远远不能满足用户的需求。基于流行的分布式并行编程框架MapReduce,研究了适用于大数据集的并行Skyline查询算法。针对影响MapReduce计算的因素,对现有基于角度的划分策略进行了改进,提出了Balanced Angular划分策略;同时,为了减少Reduce过程的计算量,提出了在Map端预先进行数据过滤的策略。实验结果显示所提出的Skyline查询算法能显著提升系统性能。     

Scalable skyline computation using a balanced pivot selection technique

Skyline queries have recently received considerable attention as an alternative decision-making operator in the database community. The conventional skyline algorithms have primarily focused on optimizing the dominance of points in order to remove non-skyline points as efficiently as possible, but have neglected to take into account the incomparability of points in order to bypass unnecessary comparisons. To design a scalable skyline algorithm, we first analyze a cost model that copes with both dominance and incomparability, and develop a novel technique to select a cost-optimal point, called a pivot point, that minimizes the number of comparisons in point-based space partitioning. We then implement the proposed pivot point selection technique in the existing sorting- and partitioning-based algorithms. For point insertions/deletions, we also discuss how to maintain the current skyline using a skytree, derived from recursive point-based space partitioning. Furthermore, we design an efficient greedy algorithm for the k representative skyline using the skytree. Experimental results demonstrate that the proposed algorithms are significantly faster than the state-of-the-art algorithms.     

更新数据流上的连续Skyline计算

本文考虑＂更新数据流＂场景下的连续Skyline计算问题。在该环境下,数据不再满足＂先进先出＂特性,使得传统基于滑动窗口数据流上的连续Skyline计算方法不再适用。在对问题进行了形式化描述后,本文提出了基本算法BUSM,在分析其不足的基础上提出了一种网格索引数据结构,基于该结构提出了GUSM算法。该算法利用了更新数据流中删除和添加操作成对同时出现的特性,以网格为单位表示影响区域并进行快速排除预处理。理论分析和实验结果证明了上述方法在更新数据流上连续计算Skyline的有效性。     

基于容斥原理的Skyband基数估计方法

Skyband查询是决策支持领域一类非常重要的查询.为了使数据库系统有效支持Skyband查询,必须解决Skyband基数估计的问题,即估计Skyband查询结果中包含的Skyband元素数,因为Skyband基数估计对于扩展数据库系统查询优化器的代价模型以便能够对Skyband查询进行优化非常重要.基于容斥原理的推广形式对Skyband基数进行理论分析并给出了时间和空间代价很小的对Skyband基数进行估计的算法.实验结果表明,该方法能够准确地对Skyband基数进行估计.     

A fast and progressive algorithm for skyline queries with totally- and partially-ordered domains

We devise a skyline algorithm that can efficiently mitigate the enormous overhead of processing millions of tuples on totally- and partially-ordered domains (henceforth, TODs and PODs). With massive datasets, existing techniques spend a significant amount of time on a dominance comparison because of both a large number of skyline points and the unprogressive method of skyline computing with PODs. (If data has high dimensionality, the situation is undoubtedly aggravated.) The progressiveness property turns out to be the key feature for solving all remaining problems. This article presents a FAST-SKY algorithm that deals successfully with these two obstacles and improves skyline query processing time strikingly, even with high-dimensional data. Progressive skyline evaluation with PODs is guaranteed by new index structures and topological sorting order. A stratification technique is adopted to index data on PODs, and we propose two new index structures: stratified R-trees (SR-trees) for low-dimensional data and stratified MinMax treaps (SM-treaps) for high-dimensional data. A fast dominance comparison is achieved by using a reporting query instead of a dominance query, and a dimensionality reduction technique. Experimental results suggest that in general cases (anti-correlated and uniform distributions) FAST-SKY is orders of magnitude faster than existing algorithms.