Parallelizing programs with recursive data structures

A study is made of the problem of estimating interference in an imperative language with dynamic data structures. The authors focus on developing efficient and implementable methods for recursive data structures. In particular, they present interference analysis tools and parallelization techniques for imperative programs that contain dynamically updatable trees and directed acyclic graphs. The analysis methods are based on a regular-expression-like representation of the relationship between accessible nodes in the data structure. They authors have implemented their analysis, and they present some concrete examples that have been processed by this system     

Tm: A code generator for recursive data structures

The transfer of data structures between programs is often carried out using binary or ad-hoc textual formats. However, this can result in ambiguous and non-portable file formats. The program ‘Tm’ (for ‘template manager’) prevents these problems by using a textual representation of the data structures and generating the code to read and write this representation from an abstract definition of the data structures. The same program is used to generate code for the simple data-structure manipulations that are necessary in almost every program. At the moment, code can be generated for the programming languages C, Pascal, Lisp and Miranda. Support for other languages is easily added.     

Theory and benefits of recursive certificate structures

Processing of a set of multi-level digital certificates, particularly path construction and validation, can be excessively resource consuming, and even impractical in some cases. This article introduces classifications of certificate sets as minimal, surplus, and deficient and explains the new paradigm of a recursive certificate structure designed to provide the equivalent of a minimal set of conventional certificates containing only the necessary and sufficient information to minimize the effort to validate a certificate sequence, with a potential avoidance of duplication of validation previously handled by related Certification Authorities.     

Generalized linear recursive networks: topological and routing properties

This paper presents a methodology for generalizing the class of linear recursive networks (LRN) reported by Hsu et al. [IEEE Trans Parallel Distrib Syst 1997; 8(7)]. The proposed generalization relaxes the restriction on the number of isomorphic subgraphs of LRNs, which is at most 1 by Hsu et al. [IEEE Trans Parallel Distrib Syst 1997; 8(7)]. Hence, our methodology permits the design of a communication topology of size n which satisfies the linear recurrence equation G_n(A)=a₁G_n−1(A)∪a₂G_n−2(A)∪?∪a_kG_n−k(A), with a_j being any non-negative integer for each j∈{1,2,…,k} and a₁>0. In addition, we address the problem of routing of messages in an generalized linear recursive network (GLRN). The paradigm of Fibonacci cubes (FCs) is used to demonstrate the proposed technique. FCs were introduced recently as an attractive alternative to the well-known hypercube model for interconnection networks.A generalized FC, referred to as a “Fibonacci graph” (FG) of size n, is composed of an arbitrary number of such graphs of size n−1 and size n−2.The structural advantage of GLRNs, in general, and FG, in particular, manifests itself in the following ways:

1.

They allow more choices to construct systems of various sizes.

2.

They emulate other topologies, such as hypercubes, trees, rings and meshes very efficiently.

The results of this paper have important applications e.g. in multitasking and job scheduling where a job is decomposed into a set of tasks and assigned to a subset of processors with specified interconnection topology.     

Redundancy and data compression in recursive estimation

The problem of the existence of redundancy in the data in a recursive estimation problem is investigated. Given a certain data rate, should the estimator be run at the same rate? It is shown that under certain conditions there is redundancy in the data and the estimator can be run at a lower rate using compressed data with practically the same performance as when no data compression is utilized. It is also pointed out that, although at the higher rate there is redundancy in the data, the performance deteriorates noticeably when the data rate is lowered. Conditions for the existence of redundancy in the data and the procedure to remove it are presented. The procedure to compress the data is obtained such as to preserve the information in the sense of Fisher. The effect of data compression is a reduction in the computation requirements by a factor equal to the compression ratio. Such a reduction might be important in real-time applications in which the computing power is limited or too expensive. The application of this technique to the tracking of a reentry vehicle with a linearized filter is discussed in more detail and simulation results are presented.     

Generalized eigenvalue problems: Lanczos algorithm with a recursive partitioning method

In this paper, the computation of the smallest eigenvalues and the corresponding eigenvectors of the generalized eigenvalue problem using Lanczos algorithm with a recursive partitioning method as well as the Sturm sequence-bisection method have been discussed. We have also presented the comparison of the numerical results and the CPU-time between the above two methodologies. Our comparative study indicates that the Lanczos with a recursive partitioning method takes relatively less computing time than that of the Sturm sequence-bisection method.     

A strict functional language with cyclic recursive data

The paper proposes a strict functional language to program with cyclic recursive data structures. In the language, each recursive datum is represented by a system of equations. Cyclic structures are naturally expressed by this representation, and the language provides a general mechanism that transforms several such systems of equations into a single new system of equations. An operational semantics and a polymorphic type system for the language are given, and a type soundness proof is sketched. Finally, it is also shown that the language can be implemented in a data-parallel fashion.     

Retrieving sinusoids from nonuniformly sampled data using recursive formulations

A heuristic procedure based on novel recursive formulation of sinusoid (RFS) and on regression with predictive least-squares (LS) enables to decompose both uniformly and nonuniformly sampled 1-d signals into a sparse set of sinusoids (SSS). An optimal SSS is found by Levenberg–Marquardt (LM) optimization of RFS parameters of near-optimal sinusoids combined with common criteria for the estimation of the number of sinusoids embedded in noise. The procedure estimates both the cardinality and the parameters of SSS. The proposed algorithm enables to identify the RFS parameters of a sinusoid from a data sequence containing only a fraction of its cycle. In extreme cases when the frequency of a sinusoid approaches zero the algorithm is able to detect a linear trend in data. Also, an irregular sampling pattern enables the algorithm to correctly reconstruct the under-sampled sinusoid. Parsimonious nature of the obtaining models opens the possibilities of using the proposed method in machine learning and in expert and intelligent systems needing analysis and simple representation of 1-d signals. The properties of the proposed algorithm are evaluated on examples of irregularly sampled artificial signals in noise and are compared with high accuracy frequency estimation algorithms based on linear prediction (LP) approach, particularly with respect to Cramer–Rao Bound (CRB).     

基于递归模式技术的股票数据可视化

可视化技术对于分析和探究大规模的多维数据集变得越来越重要，其中最重要的一种可视化技术是一种面向像素的可视化技术，其基本原理是将数据集中的每个数据值映射成屏幕上的一个像素并对这些像素按一定的规则充分地加以排列，以便将尽可能多的数据对象以人们熟悉的图形图像展现在屏幕上。递归模式技术是面向像素的可视化技术的一种，它基于简单地来回排列，允许用户参与定义结构和设置参数，主要适用于有自然顺序的数据集。在股票数据分析中，利用递归模式技术比较容易描述交易数据库中股票价格的变化情况，并预测股票的走势。     

Contextual processing of structured data by recursive cascade correlation

This paper propose a first approach to deal with contextual information in structured domains by recursive neural networks. The proposed model, i.e., contextual recursive cascade correlation (CRCC), a generalization of the recursive cascade correlation (RCC) model, is able to partially remove the causality assumption by exploiting contextual information stored in frozen units. We formally characterize the properties of CRCC showing that it is able to compute contextual transductions and also some causal supersource transductions that RCC cannot compute. Experimental results on controlled sequences and on a real-world task involving chemical structures confirm the computational limitations of RCC, while assessing the efficiency and efficacy of CRCC in dealing both with pure causal and contextual prediction tasks. Moreover, results obtained for the real-world task show the superiority of the proposed approach versus RCC when exploring a task for which it is not known whether the structural causality assumption holds.     

Recursive data structures

The power and convenience of a programming language may be enhanced for certain applications by permitting treelike data structures to be defined by recursion. This paper suggests a pleasing notation by which such structures can be declared and processed; it gives the axioms which specify their properties, and suggests an efficient implementation method. It shows how a recursive data structure may be used to represent another data type, for example, a set. It then discusses two ways in which significant gains in efficiency can be made by selective updating of structures, and gives the relevant proof rules and hints for implementation. The examples show that a certain range of applications in symbol manipulation can be efficiently programmed without introducing the low-level concept of a reference into a high-level programming language.The work on this paper was supported in part by National Science Foundation under grant number GJ 36473X and ARPA Research Contract DAHC 15-73-0435.     

Low-contention data structures

We consider the problem of minimizing contention in static (read-only) dictionary data structures, where contention is measured with respect to a fixed query distribution by the maximum expected number of probes to any given cell. The query distribution is known by the algorithm that constructs the data structure but not by the algorithm that queries it. Assume that the dictionary has n$n$ items. When all queries in the dictionary are equiprobable, and all queries not in the dictionary are equiprobable, we show how to construct a data structure in O(n)$O\left(n\right)$ space where queries require O(1)$O\left(1\right)$ probes and the contention is O(1/n)$O(1/n)$. Asymptotically, all of these quantities are optimal. For arbitrary   query distributions, we construct a data structure in O(n)$O\left(n\right)$ space where each query requires O(logn/loglogn)$O(logn/loglogn)$ probes and the contention is O(logn/(nloglogn))$O(logn/(nloglogn))$. The lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: for a large class of algorithms, we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(loglogn)$\Omega (loglogn)$.     

Associative tabular data structures

Attention is drawn to a method of implementing data structures in core memory by means of associative links instead of pointers. The properties of associative links are discussed and the way in which they may be exploited in a program for formal differentiation is illustrated. There is a section on microprogramming support for the associative search operations involved.     

Generalized addressing schemes for data graphs

Addressable data graphs enjoy structural properties which are at once mathematically attractive and practically useful. This paper is devoted to studying generalizations of addressability, with a twofold goal. The first aim of the paper is to gain understanding of what features of addressing schemes account for the attractive properties of addressable data graphs. The second purpose of the paper is to seek a variant of the property of addressability, which retains the practical concomitants of the original property, but which is enjoyed by a broader class of data graphs. Two such variants are discovered,quasi-addressability andweak-addressability. Although most data graphs do not enjoy any form of addressability, every data graph can be slightly modified to render it quasi or weakly addressable—in sharp contrast to the stringent demands of addressability. However, the added breadth of these new addressabilities is obtained at the expense of the invariance and selectivity which accompany the original property.     

Experimenting with data structures

Research in robust data structures can be done both by theoretical analysis of properties of abstract implementations and by empirical study of real implementations. Empirical study requires a support environment for the actual implementation. In particular, if the response of the implementation to errors is being studied, a mechanism must exist for artificially injecting appropriate kinds of errors. This paper discusses techniques used in empirical investigations of data structure robustness, with particular reference to tools developed for this purpose at the University of Waterloo.     

Optimized succinct data structures for massive data

Succinct data structures provide the same functionality as their corresponding traditional data structure in compact space. We improve on functions rank and select, which are the basic building blocks of FM‐indexes and other succinct data structures. First, we present a cache‐optimal, uncompressed bitvector representation that outperforms all existing approaches. Next, we improve, in both space and time, on a recent result by Navarro and Providel on compressed bitvectors. Last, we show techniques to perform rank and select on 64‐bit words that are up to three times faster than existing methods. In our experimental evaluation, we first show how our improvements affect cache and runtime performance of both operations on data sets larger than commonly used in the evaluation of succinct data structures. Our experiments show that our improvements to these basic operations significantly improve the runtime performance and compression effectiveness of FM‐indexes on small and large data sets. To our knowledge, our improvements result in FM‐indexes that are either smaller or faster than all current state of the art implementations. Copyright © 2013 John Wiley & Sons, Ltd.