Nonsingular Data Transformations: Definition, Validity, and Applications

This paper describes a unifying framework for nonsingular data transformations. It shows that a wide class of existing transformations may be expressed in this framework, allowing compound transformations to be performed in one step. Validity conditions for such transformations are developed as is the form of the transformed program and data. Constructive algorithms to generate data transformations for different applications are described and applied to example programs. It is shown that they can have a significant impact on program performance and may be used in situations where traditional loop transformations are inappropriate.     

A Matrix-Based Approach to Global Locality Optimization

Global locality optimization is a technique for improving the cache performance of a sequence of loop nests through a combination of loop and data layout transformations. Pure loop transformations are restricted by data dependencies and may not be very successful in optimizing imperfectly nested loops and explicitly parallelized programs. Although pure data transformations are not constrained by data dependencies, the impact of a data transformation on an array might be program-wide; that is, it can affect all the references to that array in all the loop nests. Therefore, in this paper we argue for an integrated approach that employs both loop and data transformations. The method enjoys the advantages of most of the previous techniques for enhancing locality and is efficient. In our approach, the loop nests in a program are processed one by one and the data layout constraints obtained from one nest are propagated for optimizing the remaining loop nests. We show a simple and effective matrix-based framework to implement this process. The search space that we consider for possible loop transformations can be represented by general nonsingular linear transformation matrices and the data layouts that we consider are those that can be expressed using hyperplanes. Experiments with several floating-point programs on an 8-processor SGI Origin 2000 distributed-shared-memory machine demonstrate the efficacy of our approach.     

Compressing heap data for improved memory performance

We introduce a class of transformations that modify the representation of dynamic data structures used in programs with the objective of compressing their sizes. Based upon a profiling study of data value characteristics, we have developed the common‐prefix and narrow‐data transformations that respectively compress a 32 bit address pointer and a 32 bit integer field into 15 bit entities. A pair of fields that have been compressed by the above compression transformations are packed together into a single 32 bit word. The above transformations are designed to apply to data structures that are partially compressible, that is, they compress portions of data structures to which transformations apply and provide a mechanism to handle the data that is not compressible. The accesses to compressed data are efficiently implemented by designing data compression extensions (DCX) to the processor's instruction set. We have observed average reductions in heap allocated storage of 25% and average reductions in execution time and power consumption of 30%. If DCX support is not provided the reductions in execution times fall from 30% to 18%. Copyright © 2006 John Wiley & Sons, Ltd.     

The adaptive algorithm of information unmistakable embedding into digital images based on the discrete Fourier transformation

Multimedia Tools and Applications - Many effective methods of the data embedding into digital images are based on the frequency transformations. However use of similar transformations is connected...     

算法到脉动阵列处理器的映射

文中讨论了将含有循环的算法映射到脉动阵列的一般方法。这一映射方法是建立在下标集和数据相关向量的数学变换基础上，并给出了带有常数据相关的算法中存在有效变换的充要条件。最后给出了许所有点对之间最短路径问题的映射过程。     

Extending ER models to capture database transformations to build data sets for data mining

In a data mining project developed on a relational database, a significant effort is required to build a data set for analysis. The main reason is that, in general, the database has a collection of normalized tables that must be joined, aggregated and transformed in order to build the required data set. Such scenario results in many complex SQL queries that are written independently from each other, in a disorganized manner. Therefore, the database grows with many tables and views that are not present as entities in the ER model and similar SQL queries are written multiple times, creating problems in database evolution and software maintenance. In this paper, we classify potential database transformations, we extend an ER diagram with entities capturing database transformations and we introduce an algorithm which automates the creation of such extended ER model. We present a case study with a public database illustrating database transformations to build a data set to compute a typical data mining model.     

Transformations for semi-continuous data

Semi-continuous data arise in many applications where naturally-continuous data become contaminated by the data generating mechanism. The resulting data contain several values that are “too frequent”, and in that sense are a hybrid between discrete and continuous data. The main problem is that standard statistical methods, which are geared towards continuous or discrete data, cannot be applied adequately to semi-continuous data. We propose a new set of two transformations for semi-continuous data that “iron out” the too-frequent values thereby transforming the data to completely continuous. We show that the transformed data maintain the properties of the original data, but are suitable for standard analysis. The transformations and their performance are illustrated using simulated data and real auction data from the online auction site eBay.     

Feature space theory in data mining: transformations between extensions and intensions in knowledge representation

Knowledge representation is one of the important topics in data mining research. In this paper, based on the feature space theory in data mining, the transformation between extensions and intensions of concepts is discussed in detail. First, inner projections of fuzzy relations, as a basic mathematical tool, are defined, and properties of inner projections are discussed. Then inner transformation of fuzzy relations, inverse inner transformations, and related properties are introduced. The concept structure is shown by feature spaces. Lastly, transformations between extensions and intensions are discussed.     

Learning the Lie groups of visual invariance

A fundamental problem in biological and machine vision is visual invariance: How are objects perceived to be the same despite transformations such as translations, rotations, and scaling? In this letter, we describe a new, unsupervised approach to learning invariances based on Lie group theory. Unlike traditional approaches that sacrifice information about transformations to achieve invariance, the Lie group approach explicitly models the effects of transformations in images. As a result, estimates of transformations are available for other purposes, such as pose estimation and visuomotor control. Previous approaches based on first-order Taylor series expansions of images can be regarded as special cases of the Lie group approach, which utilizes a matrix-exponential-based generative model of images and can handle arbitrarily large transformations. We present an unsupervised expectation-maximization algorithm for learning Lie transformation operators directly from image data containing examples of transformations. Our experimental results show that the Lie operators learned by the algorithm from an artificial data set containing six types of affine transformations closely match the analytically predicted affine operators. We then demonstrate that the algorithm can also recover novel transformation operators from natural image sequences. We conclude by showing that the learned operators can be used to both generate and estimate transformations in images, thereby providing a basis for achieving visual invariance.     

交互式数据清理系统的研究

当今数据清理方案需要反复进行数据质量分析以查找错误，为修复它们而进行的转换需要运行很长的时间。用户需要忍受长时间的等待，而且经常需要撰写复杂的转换脚本。我们所探讨的交互式数据清理系统，它能紧密地将转换和偏差检测集成在一起，只要发现偏差，用户就可以交互式地使用简单的图表操作、实例描述逐渐建立一个转换，无需书写复杂的程序或忍受很长的延时。     

Program Development as a Formal Activity

A methodology of program development by transformations is outlined. In particular, ways of representing the transformation rules are discussed, and the relationship between notions of their correctness and the semantic definition of programming languages is studied. How transformation techniques are complemented by the use of abstract data types and assertions is described. In the resulting calculus of transformations, the single rules not only represent design or optimization techniques, but they also incorporate verification principles. To illustrate this approach, the Warshall algorithm is developed by successive applications of transformations.     

FOPE：一个面向FORTRAN的程序设计环境

本文介绍一个面向ＦＯＲＴＲＡＮ的程序设计环境ＦＯＰＥ（ＦＯＲＴＲＡＮＯｒｉｅｎｔｅｄＰｒｏｇｒａｍｍｉｎｇＥｎｖｉｒｏｎｍｅｎｔ）。ＦＯＰＥ提供对ＦＯＲＴＲＡＮ程序的静态分析、动态分析、程序变换、ＤＯ循环变换、文档生成等功能，文中详细地介绍了这些功能。ＦＯＰＥ的一个重要特点是可视化。可视化工具有程序调用关系图、过程控制流图和数据依赖图三种，它能做到对程序的静态结构和动态运行过程用图形显示。ＦＯＰＥ环境以Ｘ－Ｗｉｎｄｏｗ为基础，建立了窗口用户界面，大大地方便了使用。     

A New Matrix Vector Product Systolic Array

The array size of parallel processor implementations designed by the data dependence method is not optimal. Nonlinear transformations applied on some symmetric transformations offer more efficient arrays and smaller processor array size. The Kung-Leiserson matrix vector multiplication linear systolic array is used as an example of a symmetric linear mapping. Two procedures are introduced to express the folding idea by choosing different axes of symmetry and nonlinear transformations. The first procedure that uses folding and retiming results in an irregular data flow. The folding is reallocated in the second procedure which results in a regular data flow. The new systolic implementations have many advantages over the conventional such as more efficient processor use, circular data flow, one I/O processor and the most important: use of 40% up to 50% less processors. The processors are provided by an extra switching function between the inputs and outputs being the only disadvantage.     

A class of parallelizing transformations

The paper considers the correctness of a parametric family of parallelizing transformations. The proposed transformations are based on static detection of parallelism and are intended for MIMD computer systems with local memory and data exchanges.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 90–98, September–October, 1991.     

Stratified Generalized Procrustes Analysis

Generalized procrustes analysis computes the best set of transformations that relate matched shape data. In shape analysis the transformations are usually chosen as similarities, while in general statistical data analysis other types of transformation groups such as the affine group may be used. Generalized procrustes analysis has a nonlinear and nonconvex formulation. The classical approach alternates the computation of a so-called reference shape and the computation of transformations relating this reference shape to each shape datum in turn. We propose the stratified approach to generalized procrustes analysis. It first uses the affine transformation group to analyze the data and then upgrades the solution to the sought after group, whether Euclidean or similarity. We derive a convex formulation for each of these two steps, and efficient practical algorithms that gracefully handle missing data (incomplete shapes). Extensive experimental results show that our approaches perform well on simulated and real data. In particular our closed-form solution gives very accurate results for generalized procrustes analysis of Euclidean data.     

Trajectory databases: Data models,uncertainty and complete query languages

Moving objects produce trajectories. We describe a data model for trajectories and trajectory samples and an efficient way of modeling uncertainty via beads for trajectory samples. We study transformations of the ambient space for which important physical properties of trajectories, such as speed, are invariant. We also determine which transformations preserve beads. We give conceptually easy first-order complete query languages and computationally complete query languages for trajectory databases, which allow to talk directly about speed and uncertainty in terms of beads. The queries expressible in these languages are invariant under speed- and bead-preserving transformations.     

The use of asymmetric power transformation in data-based quasi-likelihood analysis

The object of “data-based” quasi-likelihood analysis is to estimate the variance function from the data itself. Asymmetric power transformations, which are (possibly different) transformations applied to the mean sm; as well as to the observed variable y, are shown to be powerful diagnostic aids for checking first- and second-order model assumptions in the class of quasi-likelihood models. Asymmetric transformations to normality, coupled with the relation between transformation to normality and the variance function in the exponential family is a useful first step in an analysis leading to the optimum data-based variance function.     

A linear algebra framework for automatic determination of optimaldata layouts

This paper presents a data layout optimization technique for sequential and parallel programs based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines suitable memory layouts that can be expressed by hyperplanes for each array that is referenced. We discuss the cases where data transformations are preferable to loop transformations and show that under certain conditions a loop nest can be optimized for perfect spatial locality by using data transformations. We argue that data transformations can also optimize spatial locality for some arrays without distorting temporal/spatial locality exhibited by others. We divide the problem of optimizing data layout into two independent subproblems: 1) determining optimal static data layouts, and 2) determining data transformation matrices to implement the optimal layouts. By postponing the determination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts. We then present an algorithm that considers optimizing parallelism and spatial locality simultaneously. Our results on eight programs on two distributed shared-memory multiprocessors, the Convex Exemplar SPP-2000 and the SGI Origin 2000, show that the layout optimizations are effective in optimizing spatial locality and parallelism