PC Cluster环境下基于多维数组的Data Cube算法

因为需要存取大量的数据,计算datacube要花费大量的时间和存储空间。本文研究了使用便宜的PC机群计算datacube的方法。我们使用多维数组作为存储结构,并将数组划分成若干个分片,对每个分片进行压缩以节约存储空间、减少存取时间和增量维护时间,分片被分布到不同的处理机。我们提出了一个新的流水线组织方法以及对分片建立索引的思想,大大减少了外排序的代价和存取磁盘的次数。实验结果表明我们的算法具有一定的伸缩性。

Fast Computation of Sparse Data Cubes with Constraints

For a data cube there are always constraints between dimensions or among attributes in a dimension, such as functional dependencies. We introduce the problem that when there are functional dependencies, how to use them to speed up the computation of sparse data cubes. A new algorithm CFD (Computation by Functional Dependencies) is presented to satisfy this demand. CFD determines the order of dimensions by considering cardinalities of dimensions and functional dependencies between dimensions together, thus reduce the number of partitions for such dimensions. CFD also combines partitioning from bottom to up and aggregate computation from top to bottom to speed up the computation further. CFD can efficiently compute a data cube with hierarchies in a dimension from the smallest granularity to the coarsest one. Key words sparse data cube - functional dependency - dimension - partition - CFD CLC number TP 311 Foundation item: Supported by the E-Government Project of the Ministry of Science and Technology of China (2001BA110B01)Biography: Feng Yu-cai (1945-), male, Professor, research direction: database system.

基于时态层次链的Data Cube多版本维护方案

针对Data Cube的模式变动造成的多版本问题,对时态聚集关系与时态层次链进行了形式化描述,并基于这些关系实现了多个版本的Data Cube的统一生成算法,不仅可以高效地进行Data Cube多个版本的维护,而且在OLAP查询也可以基于时态层次链来执行,从而提高系统的整体效率。

基于语义的Data Cube数字水印技术

数字水印技术可以有效地保护版权,数据仓库中用于OLAP(OnLine Analyti-cal Processing,联机分析处理)的Data Cube(数据立方体,亦称多维数据集)不仅包含有价值的数据,而且其设计模式与分析模式也体现了Data Cube拥有者的知识产权.将数字水印技术引入Data Cube中,并充分利用Data Cube的语义信息,从而提供一个通用、实用的Da-ta Cube数字水印技术解决方案.

一种基于多层次链的Data Cube维层次编码

研究了Data Cube的索引技术,提出一种能够处理复杂维层次结构情况的维层次编码.维层次编码充分利用了Data Cube中维的层次性及其语义特性,结合二进制编码与维层次结构编码对维成员值进行编码,通过二进制操作,可以快速检索出与查询关键字相匹配的维层次编码.同时,基于维层次编码定义的层次链掩码,层次掩码及检索函数能够充分利用多维数据中的语义信息,实现基于语义的检索,减少了I/O开销,提高了OLAP查询效率.

一种特殊DATA CUBE的技术研究

封闭数据立方体利用元组间的关联,除去冗余信息,在减小数据立方体体积的同时,避免了查询时的解压缩。从源数据的分组角度对封闭数据立方体概念进行了解释,并在此基础上详细分析了由于源数据的更新而导致的对应封闭数据立方体的更新过程,给出了更新算法的框架。

Web Data Cube Construction in Multidimensional On-line Analytical Processing Environment

This paper investigates how to integrate Web data into a multidimensional data warehouse （cube） for comprehensive on-line analytical processing （OLAP） and decision making. An approach for Web data-based cube construction is proposed, which includes Web data modeling based on MIX （ Metadam based Integration model for data X-change ）, generic and specific mapping rules design, and a transformation algorithm for mapping Web data to a multidimensional array. Besides, the structure and implementation of the prototype of a Web data base cube are discussed.

Think global,cube local:an Earth Observation Data Cube’s contribution to the Digital Earth vision

The technological landscape for managing big Earth observation(EO)data ranges from global solutions on large cloud infrastructures with web-based access to self-hosted implementations.EO data cubes are a leading technology for facilitating big EO data analysis and can be deployed on different spatial scales:local,national,regional,or global.Several EO data cubes with a geographic focus(“local EO data cubes”)have been implemented.However,their alignment with the Digital Earth(DE)vision and the benefits and trade-offs in creating and maintaining them ought to be further examined.We investigate local EO data cubes from five perspectives(science,business and industry,government and policy,education,communities and citizens)and illustrate four examples covering three continents at different geographic scales(Swiss Data Cube,semantic EO data cube for Austria,DE Africa,Virginia Data Cube).A local EO data cube can benefit many stakeholders and players but requires several technical developments.These developments include enabling local EO data cubes based on public,global,and cloud-native EO data streaming and interoperability between local EO data cubes.We argue that blurring the dichotomy between global and local aligns with the DE vision to access the world’s knowledge and explore information about the planet.

Hierarchical Datacubes

Many approaches have been proposed to pre-compute data cubes in order to efficiently respond to OLAP queries in data warehouses. However, few have proposed solutions integrating all of the possible outcomes, and it is this idea that leads the integration of hierarchical dimensions into these responses. To meet this need, we propose, in this paper, a complete redefinition of the framework and the formal definition of traditional database analysis through the prism of hierarchical dimensions. After characterizing the hierarchical data cube lattice, we introduce the hierarchical data cube and its most concise reduced representation, the closed hierarchical data cube. It offers compact replication so as to optimize storage space by removing redundancies of strongly correlated data. Such data are typical of data warehouses, and in particular in video games, our field of study and experimentation, where hierarchical dimension attributes are widely represented.

CUBE自动滤波在远海多波束测深中的应用

为提升远海多波束测深数据标准化处理能力,验证CUBE自动滤波在远海海域的实际应用效果,选取远海海域3个典型深度测区,使用优选的CUBE自动处理参数组,对多波束测深数据进行自动滤波处理,并从处理用时、逐点标记以及交叉点水深差值3个方面,将处理结果与多名作业人员的手工处理结果进行对比分析。实验结果表明,使用CUBE自动处理与人工处理结果基本相同,且少量处理不同之处产生的水深成果差值均在测量误差允许范围之内,且CUBE自动处理在处理效率、成果标准一致性方面均优于人工处理。本文成果对于提升远海多波束测深数据标准化处理能力具有较强的实践指导意义。

Building an Earth Observations Data Cube: lessons learned from the Swiss Data Cube (SDC) on generating Analysis Ready Data (ARD)

Pressures on natural resources are increasing and a number of challenges need to be overcome to meet the needs of a growing population in a period of environmental variability.Some of these environmental issues can be monitored using remotely sensed Earth Observations(EO)data that are increasingly available from a number of freely and openly accessible repositories.However,the full information potential of EO data has not been yet realized.They remain still underutilized mainly because of their complexity,increasing volume,and the lack of efficient processing capabilities.EO Data Cubes(DC)are a new paradigm aiming to realize the full potential of EO data by lowering the barriers caused by these Big data challenges and providing access to large spatio-temporal data in an analysis ready form.Systematic and regular provision of Analysis Ready Data(ARD)will significantly reduce the burden on EO data users.Nevertheless,ARD are not commonly produced by data providers and therefore getting uniform and consistent ARD remains a challenging task.This paper presents an approach to enable rapid data access and pre-processing to generate ARD using interoperable services chains.The approach has been tested and validated generating Landsat ARD while building the Swiss Data Cube.

Monitoring land degradation at national level using satellite Earth Observation time-series data to support SDG15-exploring the potential of data cube

Avoiding,reducing,and reversing land degradation and restoring degraded land is an urgent priority to protect the biodiversity and ecosystem services that are vital to life on Earth.To halt and reverse the current trends in land degradation,there is an immediate need to enhance national capacities to undertake quantitative assessments and mapping of their degraded lands,as required by the Sustainable Development Goals(SDGs),in particular,the SDG indicator 15.3.1(“proportion of land that is degraded over total land area”).Earth Observations(EO)can play an important role both for generating this indicator as well as complementing or enhancing national official data sources.Implementations like Trends.Earth to monitor land degradation in accordance with the SDG15.3.1 rely on default datasets of coarse spatial resolution provided by MODIS or AVHRR.Consequently,there is a need to develop methodologies to benefit from medium to high-resolution satellite EO data(e.g.Landsat or Sentinels).In response to this issue,this paper presents an initial overview of an innovative approach to monitor land degradation at the national scale in compliance with the SDG15.3.1 indicator using Landsat observations using a data cube but further work is required to improve the calculation of the three sub-indicators.

PMC： Select Materialized Cells in Data Cubes

QC-Tree is one of the most storage-efficient structures for data cubes in an MOLAP system. Although QC- Tree can achieve a high compression ratio, it is still a fully materialized data cube. In this paper, an improved structure PMC is presented allowing us to materialize only a part of the cells in a QC-Tree to save more storage space. There is a notable difference between our partially materialization algorithm and traditional materialized views selection algorithms. In a traditional algorithm, when a view is selected, all the cells in this view are to be materialized. Otherwise, if a view is not selected, all the cells in this view will not be materialized. This strategy results in the unstable query performance. The presented algorithm, however, selects and materializes data in cell level, and, along with further reduced space and update cost, it can ensure a stable query performance. A series of experiments are conducted on both synthetic and real data sets. The results show that PMC can further reduce storage space occupied by the data cube, and can shorten the time to update the cube.

Semi-Closed Cube： An Effective Approach to Trading Off Data Cube Size and Query Response Time

The results of data cube will occupy huge amount of disk space when the base table is of a large number of attributes. A new type of data cube, compact data cube like condensed cube and quotient cube, was proposed to solve the problem. It compresses data cube dramatically. However, its query cost is so high that it cannot be used in most applications. This paper introduces the semi-closed cube to reduce the size of data cube and achieve almost the same query response time as the data cube does. Semi-closed cube is a generalization of condensed cube and quotient cube and is constructed from a quotient cube. When the query cost of quotient cube is higher than a given threshold, semi-closed cube selects some views and picks a fellow for each of them. All the tuples of those views are materialized except those closed by their fellows. To find a tuple of those views, users only need to scan the view and its fellow. Thus, their query performance is improved. Experiments were conducted using a real-world data set. The results show that semi-closed cube is an effective approach of data cube.

Rapid,high-resolution detection of environmental change over continental scales from satellite data–the Earth Observation Data Cube

The effort and cost required to convert satellite Earth Observation(EO)data into meaningful geophysical variables has prevented the systematic analysis of all available observations.To overcome these problems,we utilise an integrated High Performance Computing and Data environment to rapidly process,restructure and analyse the Australian Landsat data archive.In this approach,the EO data are assigned to a common grid framework that spans the full geospatial and temporal extent of the observations–the EO Data Cube.This approach is pixel-based and incorporates geometric and spectral calibration and quality assurance of each Earth surface reflectance measurement.We demonstrate the utility of the approach with rapid time-series mapping of surface water across the entire Australian continent using 27 years of continuous,25 m resolution observations.Our preliminary analysis of the Landsat archive shows how the EO Data Cube can effectively liberate high-resolution EO data from their complex sensor-specific data structures and revolutionise our ability to measure environmental change.

Cache-Conscious Data Cube Computation on a Modern Processor

Data cube computation is an important problem in the field of data warehousing and OLAP （online analytical processing）. Although it has been studied extensively in the past, most of its algorithms are designed without considering CPU and cache behavior. In this paper, we first propose a cache-conscious cubing approach called CC-Cubing to efficiently compute data cubes on a modern processor. This method can enhance CPU and cache performances. It adopts an integrated depth-first and breadth-first partitioning order and partitions multiple dimensions simultaneously. The partitioning scheme improves the data spatial locality and increases the utilization of cache lines. Software prefetching techniques are then applied in the sorting phase to hide the expensive cache misses associated with data scans. In addition, a cache-aware method is used in CC-Cubing to switch the sort algorithm dynamically. Our performance study shows that CC-Cubing outperforms BUC, Star-Cubing and MM-Cubing in most cases. Then, in order to fully utilize an SMT （simultaneous multithreading） processor, we present a thread-based CC-Cubing-SMT method. This parallel method provides an improvement up to 27% for the single-threaded CC-Cubing algorithm.

Watermarking Data Cubes

We propose a robust watermarking scheme and several extensions for digital right management of data cubes.The ownership information is hidden into a data cube by modifying a set of selected cell values.Its owner can use his private key to control all the watermarking parameters freely.Neither original data cube nor the watermark is required in watermark detection.Detailed analysis and extensive experiments are conducted for the proposed schemes in terms of watermark detectability,robustness and efficiency.Our results show that the scheme performs well in actual applications.

Modeling and OLAP Cubes for Database of Ground and Municipal Water Supply

Modeling plays an important role for the solution of the complex research problems. When the database became large and complex then it is necessary to create a unified model for getting the desired information in the minimum time and to implement the model in a better way. The present paper deals with the modeling for searching of the desired information from a large database by storing the data inside the three dimensional data cubes. A sample case study is considered as a real data related to the ground water and municipal water supply, which contains the data from the various localities of a city. For the demonstration purpose, a sample size is taken as nine but when it becomes very large for number of localities of different cities then it is necessary to store the data inside data cubes. A well known object-oriented Unified Modeling Language (UML) is used to create Unified class and state models. For verification purpose, sample queries are also performed and corresponding results are depicted.

Parallel Data Cube Storage Structure for Range Sum Queries and Dynamic Updates

I/O parallelism is considered to be a promising approach to achieving highperformance in parallel data warehousing systems where huge amounts of data and complex analyticalqueries have to be processed. This paper proposes a parallel secondary data cube storage structure(PHC for short) to efficiently support the processing of range sum queries and dynamic updates ondata cube using parallel computing systems. Based on PHC, two parallel algorithms for processingrange sum queries and updates are proposed also. Both the algorithms have the same time complexity,O(log^d n/P). The analytical and experimental results show that PHC and the parallel algorithms havehigh performance and achieve optimum speedup.

CUBE算法及其在多波束数据处理中的应用

阐述了一种基于表面生成的多波束数据处理方法——CUBE(Combined Uncertainty and Bathymetry Estimator)算法,用该方法可以对观测区域网格节点"真实"水深及相关误差进行估计。与从测量水深中选择出"最佳"数据的手工交互方式的多波束数据编辑手段不同,CUBE算法具有很强的抗差性和较高的效率,适合于实时多波束数据处理。对南海某测区多波束数据处理结果表明,在没有人工干预的情况下,利用CUBE算法去噪生成的海底DTM图与手工编辑生成的相当吻合。CUBE算法和手工编辑方法综合对比得出,CUBE算法能够很好地保留水深地形细节,在计算效率、误差评估、实时处理等方面比手工编辑方法具有较大的优势。