Partition-Based Online Aggregation with Shared Sampling in the Cloud

Online aggregation is an attractive sampling-based technology to response aggregation queries by an estimate to the final result, with the confidence interval becoming tighter over time. It has been built into a MapReduce-based cloud system for big data analytics, which allows users to monitor the query progress, and save money by killing the computation early once sufficient accuracy has been obtained. However, there are several limitations that restrict the performance of online aggregation generated from the gap between the current mechanism of MapHeduce paradigm and the requirements of online aggregation, such as： 1） the low sampling efficiency due to the lack of consideration of skewed data distribution for online aggregation in MapReduce, and 2） the large redundant I/O cost of online aggregation caused by the independent job execution mechanism of MapReduce. In this paper, we present OLACloud, a MapReduce-based cloud system to well support online aggregation for different data distributions and large-scale concurrent query processing. We propose a content-aware repartition method with a fair-allocation block placement strategy to increase the sampling efficiency and guarantee the storage and computation load balancing simultaneously. We also develop a shared sampling method to share the sampling opportunities among multiple queries to reduce redundant I/O cost. We also implement OLACloud in Hadoop, and conduct an extensive experimental study on the TPC-H benchmark for skewed data distribution. Our results demonstrate the efficiency and effectiveness of OLACloud.     

Preface

Cloud computing and big data have become increasingly popular and are changing our way of thinking about the world by providing new insights and creating new forms of value. The research of cloud data management is to address the challenges in managing large collections of data in the cloud computing environment, and identifying information of value to business, science, government, and society. The huge volumes of data in cloud computing environments pose major infrastructure challenges, including data storage at Petabyte scale, massively parallel query execution, facilities for analytical processing, online query processing, resource optimization, data privacy and security.     

Max-plus-linear model-based predictive control for constrained hybrid systems：linear programming solution

In this paper, a linear programming method is proposed to solve model predictive control for a class of hybrid systems. Firstly, using the （max, ＋） algebra, a typical subclass of hybrid systems called max-plus-linear （MPL） systems is obtained. And then, model predictive control （MPC） framework is extended to MPL systems. In general, the nonlinear optimization approach or extended linear complementarity problem （ELCP） were applied to solve the MPL-MPC optimization problem. A new optimization method based on canonical forms for max-min-plus-scaling （MMPS） functions （using the operations maximization, minimization, addition and scalar multiplication） with linear constraints on the inputs is presented. The proposed approach consists in solving several linear programming problems and is more efficient than nonlinear optimization. The validity of the algorithm is illustrated by an example.     

Continuous Probabilistic Subspace Skyline Query Processing Using Grid Projections

As an important type of multidimensional preference query, the skyline query can find a superset of optimal results when there is no given linear function to combine values for all attributes of interest. Its processing has been extensively investigated in the past. While most skyline query processing algorithms are designed based on the assumption that query processing is done for all attributes in a static dataset with deterministic attribute values, some advanced work has been done recently to remove part of such a strong assumption in order to process skyline queries for real-life applications, namely, to deal with data with multi-valued attributes （known as data uncertainty）, to support skyline queries in a subspace which is a subset of attributes selected by the user, and to support continuous queries on streaming data. Naturally, there are many application scenarios where these three complex issues must be considered together. In this paper, we tackle the problem of probabilistic subspace skyline query processing over sliding windows on uncertain data streams. That is, to retrieve all objects from the most recent window of streaming data in a user-selected subspace with a skyline probability no smaller than a given threshold. Based on the subtle relationship between the full space and an arbitrary subspace, a novel approach using a regular grid indexing structure is developed for this problem. An extensive empirical study under various settings is conducted to show the effectiveness and efficiency of our PSS algorithm.     

MABP: an optimal resource allocation approach in data center networks

In data center networks, resource allocation based on workload is an effective way to allocate the infrastructure resources to diverse cloud applications and satisfy the quality of service for the users, which refers to mapping a large number of workloads provided by cloud users/tenants to substrate network provided by cloud providers. Although the existing heuristic approaches are able to find a feasible solution, the quality of the solution is not guaranteed. Concerning this issue, based on the minimum mapping cost, this paper solves the resource allocation problem by modeling it as a distributed constraint optimization problem. Then an efficient approach is proposed to solve the resource allocation problem, aiming to find a feasible solution and ensuring the optimality of the solution. Finally, theoretical analysis and extensive experiments have demonstrated the effectiveness and efficiency of our proposed approach.     

Parallel H-Tree Based Data Cubing on Graphics Processors

Graphics processing units (GPUs) have an SIMD architecture and have been widely used recently as powerful general-purpose co-processors for the CPU. In this paper, we investigate efficient GPU-based data cubing because the most frequent operation in data cube computation is aggregation, which is an expensive operation well suited for SIMD parallel processors. H-tree is a hyper-linked tree structure used in both top-k H-cubing and the stream cube. Fast H-tree construction, update and real-time query response are crucial in many OLAP applications. We design highly efficient GPU-based parallel algorithms for these H-tree based data cube operations. This has been made possible by taking effective methods, such as parallel primitives for segmented data and efficient memory access patterns, to achieve load balance on the GPU while hiding memory access latency. As a result, our GPU algorithms can often achieve more than an order of magnitude speedup when compared with their sequential counterparts on a single CPU. To the best of our knowledge, this is the first attempt to develop parallel data cubing algorithms on graphics processors.     

Fast filtering false active subspaces for efficient high dimensional similarity processing

The query space of a similarity query is usually narrowed down by pruning inactive query subspaces which contain no query results and keeping active query subspaces which may contain objects corre-sponding to the request. However,some active query subspaces may contain no query results at all,those are called false active query subspaces. It is obvious that the performance of query processing degrades in the presence of false active query subspaces. Our experiments show that this problem becomes seriously when the data are high dimensional and the number of accesses to false active sub-spaces increases as the dimensionality increases. In order to solve this problem,this paper proposes a space mapping approach to reducing such unnecessary accesses. A given query space can be re-fined by filtering within its mapped space. To do so,a mapping strategy called maxgap is proposed to improve the efficiency of the refinement processing. Based on the mapping strategy,an index structure called MS-tree and algorithms of query processing are presented in this paper. Finally,the performance of MS-tree is compared with that of other competitors in terms of range queries on a real data set.     

Task-resource scheduling problem

Cloud computing is a new and rapidly emerging computing paradigm where applications,data and IT services are provided over the Internet.The task-resource management is the key role in cloud computing systems.Task-resource scheduling problems are premier which relate to the efficiency of the whole cloud computing facilities.Task-resource scheduling problem is NPcomplete.In this paper,we consider an approach to solve this problem optimally.This approach is based on constructing a logical model for the problem.Using this model,we can apply algorithms for the satisfiability problem(SAT) to solve the task-resource scheduling problem.Also,this model allows us to create a testbed for particle swarm optimization algorithms for scheduling workflows.     

Dynamic Query Optimization Approach for Semantic Database Grid

Fundamentally, semantic grid database is about bringing globally distributed databases together in order to coordinate resource sharing and problem solving in which information is given well-defined meaning, and DartGrid II is the implemented database gird system whose goal is to provide a semantic solution for integrating database resources on the Web. Although many algorithms have been proposed for optimizing query-processing in order to minimize costs and/or response time, associated with obtaining the answer to query in a distributed database system, database grid query optimization problem is fundamentally different from traditional distributed query optimization. These differences are shown to be the consequences of autonomy and heterogeneity of database nodes in database grid. Therefore, more challenges have arisen for query optimization in database grid than traditional distributed database. Following this observation, the design of a query optimizer in DartGrid II is presented, and a heuristic, dynamic and parallel query optimization approach to processing query in database grid is proposed. A set of semantic tools supporting relational database integration and semantic-based information browsing has also been implemented to realize the above vision.     

Effect of Count Estimation in Finding Frequent Itemsets over Online Transactional Data Streams

A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Due to this reason, most algorithms for data streams sacrifice the correctness of their results for fast processing time. The processing time is greatly influenced by the amount of information that should be maintained. This issue becomes more serious in finding frequent itemsets or frequency counting over an online transactional data stream since there can be a large number of itemsets to be monitored. We have proposed a method called the estDec method for finding frequent itemsets over an online data stream. In order to reduce the number of monitored itemsets in this method, monitoring the count of an itemset is delayed until its support is large enough to become a frequent itemset in the near future. For this purpose, the count of an itemset should be estimated. Consequently, how to estimate the count of an itemset is a critical issue in minimizing memory usage as well as processing time. In this paper, the effects of various count estimation methods for finding frequent itemsets are analyzed in terms of mining accuracy, memory usage and processing time.     

基于分布密度的直方图与选择率估计

查询选择率估计是查询处理和优化中的关键之一。提出一种基于区域分布密度的方法,用于构造直方图,使其每个桶具有均匀分布或近似均匀分布,利用直方图估计查询选择率。实验结果表明,该方法对低维数据估计得到的查询选择率精度较高,并能对高维数据进行估计。     

Shapeme histogram projection and matching for partial object recognition

Histograms of shape signature or prototypical shapes, called shapemes, have been used effectively in previous work for 2D/3D shape matching and recognition. We extend the idea of shapeme histogram to recognize partially observed query objects from a database of complete model objects. We propose representing each model object as a collection of shapeme histograms and match the query histogram to this representation in two steps: 1) compute a constrained projection of the query histogram onto the subspace spanned by all the shapeme histograms of the model and 2) compute a match measure between the query histogram and the projection. The first step is formulated as a constrained optimization problem that is solved by a sampling algorithm. The second step is formulated under a Bayesian framework, where an implicit feature selection process is conducted to improve the discrimination capability of shapeme histograms. Results of matching partially viewed range objects with a 243 model database demonstrate better performance than the original shapeme histogram matching algorithm and other approaches.     

压缩数据库中一种自适应直方图的构建

直方图在查询优化过程中起着重要作用.在压缩数据库中利用查询处理的特点构建自适应直方图以便于查询优化或近似回答查询是尚待解决的问题.通过对查询缓冲池内的查询进行调度来追踪热点数据,并用查询结果中的反馈信息构建自适应直方图以加快自适应直方图的收敛速度.另外,还提出一种参数化方法来估计未被任何桶覆盖的区域中元组的个数.该直方图可以增量式地被维护.实验结果表明,这种直方图具有良好的平均精度、更快的收敛速度和更强的自适应能力.     

纯Peer to Peer环境下有效的Top-k查询

目前大多数的Peer-to-Peer(P2P)系统只支持基于文件标识的搜索,用户不能根据文件的内容进行搜索.Top-k查询被广泛地应用于搜索引擎中,获得了巨大的成功.可是,由于P2P系统是一个动态的、分散的系统,在纯的P2P环境下进行top-k查询是具有挑战性的.提出了一种基于直方图的分层top-k查询算法.首先,采用层次化的方法实现分布式的top-k查询,将结果的合并和排序分散到P2P网络中的各个节点上,充分利用了网络中的资源.其次,根据节点返回的结果为节点构建直方图,利用直方图估计节点可能的分数上限,对节点进行选择,提高了查询效率.实验证明,top-k查询提高了查询效果,而直方图则提高了查询效率.     

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

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

Approximate query processing using wavelets

Approximate query processing has emerged as a cost-effective approach for dealing with the huge data volumes and stringent response-time requirements of today's decision support systems (DSS). Most work in this area, however, has so far been limited in its query processing scope, typically focusing on specific forms of aggregate queries. Furthermore, conventional approaches based on sampling or histograms appear to be inherently limited when it comes to approximating the results of complex queries over high-dimensional DSS data sets. In this paper, we propose the use of multi-dimensional wavelets as an effective tool for general-purpose approximate query processing in modern, high-dimensional applications. Our approach is based on building wavelet-coefficient synopses of the data and using these synopses to provide approximate answers to queries. We develop novel query processing algorithms that operate directly on the wavelet-coefficient synopses of relational tables, allowing us to process arbitrarily complex queries entirely in the wavelet-coefficient domain. This guarantees extremely fast response times since our approximate query execution engine can do the bulk of its processing over compact sets of wavelet coefficients, essentially postponing the expansion into relational tuples until the end-result of the query. We also propose a novel wavelet decomposition algorithm that can build these synopses in an I/O-efficient manner. Finally, we conduct an extensive experimental study with synthetic as well as real-life data sets to determine the effectiveness of our wavelet-based approach compared to sampling and histograms. Our results demonstrate that our techniques: (1) provide approximate answers of better quality than either sampling or histograms; (2) offer query execution-time speedups of more than two orders of magnitude; and (3) guarantee extremely fast synopsis construction times that scale linearly with the size of the data. Received: 7 August 2000 / Accepted: 1 April 2001 Published online: 7 June 2001     

基于云计算的多重查询优化系统

在常规海量数据分析作业中,CPU/IO密集型的查询语句通常复杂、耗时并存在大量可复用的公共部分。如何检测、共享和复用回归查询集中语句间的公共部分成为亟需解决的问题。为此,提出特征值索引方法,并构建适用于云计算场景的LSShare多重查询优化系统。基于查询语句的抽象语法树将语句划分为不同的查询层次,针对每个查询层次抽取特征向量并计算特征值。建立简单高效的特征值索引表以识别多重查询语句间的公共部分,并结合SQL重写技术来复用其中的公共部分。随着运行迭代次数的增加,LSShare系统将逐步优化云计算场景中的回归查询集。实验结果表明,该系统在运行效率上优于传统查询语句系统,可节约近1/3的执行时间。     

分布式上下文敏感复杂事件处理方法

针对物联网事件云的复杂事件处理面临的海量事件规模、分布式数据处理、上下文相关等挑战,提出一种分布式的上下文敏感复杂事件处理方法。该方法基于模糊本体进行事件上下文的表示和推理,通过查询重写支持事件上下文处理,并基于查询规划和数据划分进行分布式处理与启发式优化。实验结果表明,该方法能够处理模糊事件上下文,对于大规模物联网事件云上下文敏感复杂事件的处理具有比一般方法更好的性能和可伸缩性。     

数据仓库索引启发式查询优化方法

在大型数据仓库查询过程中,经常涉及多事实表的连接操作。传统的查询优化方法是在计算多关系连接时尽可能地减少中间关系的大小,并没有考虑到数据仓库中数据的海量,以读为主且事实表一般建有索引的特点,往往无法取得最优的效果。针对数据仓库查询的特点,提出了一种利用索引加快查询的启发式优化方法。理论分析与实验表明,该方法在查询处理代价和执行时间上都明显减少,方法具有有效性。