Online segmentation of time series based on polynomial least-squares approximations

The paper presents SwiftSeg, a novel technique for online time series segmentation and piecewise polynomial representation. The segmentation approach is based on a least-squares approximation of time series in sliding and/or growing time windows utilizing a basis of orthogonal polynomials. This allows the definition of fast update steps for the approximating polynomial, where the computational effort depends only on the degree of the approximating polynomial and not on the length of the time window. The coefficients of the orthogonal expansion of the approximating polynomial-obtained by means of the update steps-can be interpreted as optimal (in the least-squares sense) estimators for average, slope, curvature, change of curvature, etc., of the signal in the time window considered. These coefficients, as well as the approximation error, may be used in a very intuitive way to define segmentation criteria. The properties of SwiftSeg are evaluated by means of some artificial and real benchmark time series. It is compared to three different offline and online techniques to assess its accuracy and runtime. It is shown that SwiftSeg-which is suitable for many data streaming applications-offers high accuracy at very low computational costs.     

World lines

In this paper we present World Lines as a novel interactive visualization that provides complete control over multiple heterogeneous simulation runs. In many application areas, decisions can only be made by exploring alternative scenarios. The goal of the suggested approach is to support users in this decision making process. In this setting, the data domain is extended to a set of alternative worlds where only one outcome will actually happen. World Lines integrate simulation, visualization and computational steering into a single unified system that is capable of dealing with the extended solution space. World Lines represent simulation runs as causally connected tracks that share a common time axis. This setup enables users to interfere and add new information quickly. A World Line is introduced as a visual combination of user events and their effects in order to present a possible future. To quickly find the most attractive outcome, we suggest World Lines as the governing component in a system of multiple linked views and a simulation component. World Lines employ linking and brushing to enable comparative visual analysis of multiple simulations in linked views. Analysis results can be mapped to various visual variables that World Lines provide in order to highlight the most compelling solutions. To demonstrate this technique we present a flooding scenario and show the usefulness of the integrated approach to support informed decision making.     

Estimating aboveground carbon in a catchment of the Siberian forest tundra: Combining satellite imagery and field inventory

This study was part of an interdisciplinary research project on soil carbon and phytomass dynamics of boreal and arctic permafrost landscapes. The 45 ha study area was a catchment located in the forest tundra in northern Siberia, approximately 100 km north of the Arctic Circle.The objective of this study was to estimate aboveground carbon (AGC) and assess and model its spatial variability. We combined multi-spectral high resolution remote sensing imagery and sample based field inventory data by means of the k-nearest neighbor (k-NN) technique and linear regression.Field data was collected by stratified systematic sampling in August 2006 with a total sample size of n = 31 circular nested sample plots of 154 m² for trees and shrubs and 1 m² for ground vegetation. Destructive biomass samples were taken on a sub-sample for fresh weight and moisture content. Species-specific allometric biomass models were constructed to predict dry biomass from diameter at breast height (dbh) for trees and from elliptic projection areas for shrubs.Quickbird data (standard imagery product), acquired shortly before the field campaign and archived ASTER data (Level-1B product) of 2001 were geo-referenced, converted to calibrated radiances at sensor and used as carrier data. Spectral information of the pixels which were located in the inventory plots were extracted and analyzed as reference set. Stepwise multiple linear regression was applied to identify suitable predictors from the set of variables of the original satellite bands, vegetation indices and texture metrics. To produce thematic carbon maps, carbon values were predicted for all pixels of the investigated satellite scenes. For this prediction, we compared the kNN distance-weighted classifier and multiple linear regression with respect to their predictions.The estimated mean value of aboveground carbon from stratified sampling in the field is 15.3 t/ha (standard error SE = 1.50 t/ha, SE% = 9.8%). Zonal prediction from the k-NN method for the Quickbird image as carrier is 14.7 t/ha with a root mean square error RMSE = 6.42 t/ha, RMSE_r = 44%) resulting from leave-one-out cross-validation. The k-NN-approach allows mapping and analysis of the spatial variability of AGC. The results show high spatial variability with AGC predictions ranging from 4.3 t/ha to 28.8 t/ha, reflecting the highly heterogeneous conditions in those permafrost-influenced landscapes. The means and totals of linear regression and k-NN predictions revealed only small differences but some regional distinctions were recognized in the maps.     

Continuous-time quantum Monte Carlo impurity solvers

Continuous-time quantum Monte Carlo impurity solvers are algorithms that sample the partition function of an impurity model using diagrammatic Monte Carlo techniques. The present paper describes codes that implement the interaction expansion algorithm originally developed by Rubtsov, Savkin, and Lichtenstein, as well as the hybridization expansion method developed by Werner, Millis, Troyer, et al. These impurity solvers are part of the ALPS-DMFT application package and are accompanied by an implementation of dynamical mean-field self-consistency equations for (single orbital single site) dynamical mean-field problems with arbitrary densities of states.

Program summary

Program title: dmftCatalogue identifier: AEIL_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEIL_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: ALPS LIBRARY LICENSE version 1.1No. of lines in distributed program, including test data, etc.: 899 806No. of bytes in distributed program, including test data, etc.: 32 153 916Distribution format: tar.gzProgramming language: C++Operating system: The ALPS libraries have been tested on the following platforms and compilers:

• • 

  Linux with GNU Compiler Collection (g++ version 3.1 and higher), and Intel C++ Compiler (icc version 7.0 and higher)

• • 

  MacOS X with GNU Compiler (g++ Apple-version 3.1, 3.3 and 4.0)

• • 

  IBM AIX with Visual Age C++ (xlC version 6.0) and GNU (g++ version 3.1 and higher) compilers

• • 

  Compaq Tru64 UNIX with Compq C++ Compiler (cxx)

• • 

  SGI IRIX with MIPSpro C++ Compiler (CC)

• • 

  HP-UX with HP C++ Compiler (aCC)

• • 

  Windows with Cygwin or coLinux platforms and GNU Compiler Collection (g++ version 3.1 and higher)

RAM: 10 MB–1 GBClassification: 7.3External routines: ALPS [1], BLAS/LAPACK, HDF5Nature of problem: (See [2].) Quantum impurity models describe an atom or molecule embedded in a host material with which it can exchange electrons. They are basic to nanoscience as representations of quantum dots and molecular conductors and play an increasingly important role in the theory of “correlated electron” materials as auxiliary problems whose solution gives the “dynamical mean field” approximation to the self-energy and local correlation functions.Solution method: Quantum impurity models require a method of solution which provides access to both high and low energy scales and is effective for wide classes of physically realistic models. The continuous-time quantum Monte Carlo algorithms for which we present implementations here meet this challenge. Continuous-time quantum impurity methods are based on partition function expansions of quantum impurity models that are stochastically sampled to all orders using diagrammatic quantum Monte Carlo techniques. For a review of quantum impurity models and their applications and of continuous-time quantum Monte Carlo methods for impurity models we refer the reader to [2].Additional comments: Use of dmft requires citation of this paper. Use of any ALPS program requires citation of the ALPS [1] paper.Running time: 60 s–8 h per iteration.References:

• [1] 

  A. Albuquerque, F. Alet, P. Corboz, et al., J. Magn. Magn. Mater. 310 (2007) 1187.

• [2] 

  http://arxiv.org/abs/1012.4474, Rev. Mod. Phys., in press.

     

The State of the Art in Topology‐Based Visualization of Unsteady Flow

Vector fields are a common concept for the representation of many different kinds of flow phenomena in science and engineering. Methods based on vector field topology are known for their convenience for visualizing and analysing steady flows, but a counterpart for unsteady flows is still missing. However, a lot of good and relevant work aiming at such a solution is available. We give an overview of previous research leading towards topology‐based and topology‐inspired visualization of unsteady flow, pointing out the different approaches and methodologies involved as well as their relation to each other, taking classical (i.e. steady) vector field topology as our starting point. Particularly, we focus on Lagrangian methods, space–time domain approaches, local methods and stochastic and multifield approaches. Furthermore, we illustrate our review with practical examples for the different approaches.     

Dynamic Programming for Minimum Steiner Trees

We present a new dynamic programming algorithm that solves the minimum Steiner tree problem on graphs with k terminals in time O^*(c^k) for any c > 2. This improves the running time of the previously fastest parameterized algorithm by Dreyfus-Wagner of order O^*(3^k) and the so-called "full set dynamic programming" algorithm solving rectilinear instances in time O^*(2.38^k).     

Profiles of Random Trees: Limit Theorems for Random Recursive Trees and Binary Search Trees

We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio α of the level and the logarithm of tree size lies in [0,e). Convergence of all moments is shown to hold only for α ∈ [0,1] (with only convergence of finite moments when α ∈ (1,e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for α = 0 and a "quicksort type" limit law for α = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.     

Frequency dependence of MR relaxation times. I. Paramagnetic ions

T1 and T2 of paramagnetic ions in free and chelated form were measured over the range of clinical magnetic resonance imaging field strengths (0.02-1.5 T). T1 values agreed with published data; however, to our knowledge, the field dependence of T2 has not been systematically studied before Mn2+, Cr3+, and Fe3+ all showed T2 reduction at high field strengths, although reduction due to Fe3+ was minimal. This is believed to be due to "contact" interactions, which have been previously noted for manganese. No such T2 reduction was seen in the chelates, except that dysprosium chelate (but not free ion) showed an anomalous decrease in T2 at high field strengths, which may possibly be explained by a dephasing effect caused by the large magnetic moment of Dy3+.     

Optimal structural topologies with transmissible loads

In optimal topological design of structures one obtains the configuration of optimal structures when the design domain, the displacement boundary conditions and the applied loads are specified. In the optimal structure one often notices a marked difference between the main bearing structure and the load transfer zones. The latter are composed of relatively light elements the exact nature of which is not always very distinct. The main purpose of this paper is to allow the main bearing part of the structure to emerge. Moreover the actual location of the load along its line of action is not always a design requirement. In order to include this relaxed condition regarding the loading position the concept of transmissible or sliding forces is introduced in topological design of structures. A transmissible force is a force of given magnitude and direction which can be applied at any point along the line of action of the force. The optimization formulation is similar to standard topological design procedure in addition to the condition of transmissability of the forces. It is shown that this condition reduces to an equal displacement constraint along the line of action of the forces. The method is illustrated by typical structural examples. It is observed that this numerical method produces indeed crisp images of the main structural components, unblurred by the secondary load transfer elements. It is also indicated that many results are often replicas of Prager structures which were previously obtained by analytical methods. Received March 3, 1999