Approximation of graph edit distance based on Hausdorff matching

Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet it can only be calculated for small graphs in practice due to its exponential time complexity when considering unconstrained graphs. In this paper we propose a quadratic time approximation of graph edit distance based on Hausdorff matching. In a series of experiments we analyze the performance of the proposed Hausdorff edit distance in the context of graph classification and compare it with a cubic time algorithm based on the assignment problem. Investigated applications include nearest neighbor classification of graphs representing letter drawings, fingerprints, and molecular compounds as well as hidden Markov model classification of vector space embedded graphs representing handwriting. In many cases, a substantial speedup is achieved with only a minor loss in accuracy or, in one case, even with a gain in accuracy. Overall, the proposed Hausdorff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy.     

Search combinators

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.     

On preconditioning for a parallel solution of the Richards equation

In this paper, we present a class of preconditioning methods for a parallel solution of the three-dimensional Richards equation. The preconditioning methods Jacobi scaling, block-Jacobi, incomplete lower–upper, incomplete Cholesky and algebraic multigrid were applied in combination with a parallel conjugate gradient solver and tested for robustness and convergence using two model scenarios. The first scenario was an infiltration into initially dry, sandy soil discretised in 500,000 nodes. The second scenario comprised spatially distributed soil properties using 275,706 numerical nodes and atmospheric boundary conditions. Computational results showed a high efficiency of the nonlinear parallel solution procedure for both scenarios using up to 64 processors. Using 32 processors for the first scenario reduced the wall clock time to slightly more than 1% of the single processor run. For scenario 2 the use of 64 processors reduces the wall clock time to slightly more than 20% of the 8 processors wall clock time. The difference in the efficiency of the various preconditioning methods is moderate but not negligible. The use of the multigrid preconditioning algorithm is recommended, since on average it performed best for both scenarios.     

Hidden Markov model-based ensemble methods for offline handwritten text line recognition

This paper investigates various ensemble methods for offline handwritten text line recognition. To obtain ensembles of recognisers, we implement bagging, random feature subspace, and language model variation methods. For the combination, the word sequences returned by the individual ensemble members are first aligned. Then a confidence-based voting strategy determines the final word sequence. A number of confidence measures based on normalised likelihoods and alternative candidates are evaluated. Experiments show that the proposed ensemble methods can improve the recognition accuracy over an optimised single reference recogniser.     

SplitLab: A shear-wave splitting environment in Matlab

We present a graphical user interface to facilitate the processing of teleseismic shear-wave splitting observations. In contrast to a fully automated technique, we present a manual, per-event approach that maintains user control during the sequence of processing. The SplitLab environment is intended to undertake the repetitive processing steps while enabling the user to focus on quality control and eventually the interpretation of the results. Pre-processing modules of SplitLab create a database of events and link the corresponding seismogram files. The seismogram viewer tool uses this database to perform the measurement interactively. Post-processing of the combined results of such a project includes a viewer and export option. Our emphasis lies in the application to teleseismic shear-wave splitting analysis, but our code can be extended easily for other purposes. SplitLab can be downloaded at http://www.gm.univ-montp2.fr/splitting/.     

Evidence for Glass–glass Interfaces in a Columnar Cu–Zr Nanoglass

Comprehensive analyses of the atomic structure using advanced analytical transmission electron microscopy-based methods combined with atom probe tomography confirm the presence of distinct glass–glass interfaces in a columnar Cu-Zr nanoglass synthesized by magnetron sputtering. These analyses provide first-time in-depth characterization of sputtered film nanoglasses and indicate that glass–glass interfaces indeed present an amorphous phase with reduced mass density as compared to the neighboring amorphous regions. Moreover, dedicated analyses of the diffusion kinetics by time-of-flight secondary ion mass spectroscopy (ToF SIMS) prove significantly enhanced diffusivity, suggesting fast transport along the low density glass–glass interfaces. The present results further indicate that sputter deposition is a feasible technique for reliable production of nanoglasses and that some of the concepts proposed for this new class of glassy materials are applicable.     

Enterprise networks: The re-engineering of complex software systems

Today technology design can no longer be understood as a design process on a green site. Design and implementation of new technology are always dependent on existing technology and the way it is used by people. In this respect Software-Engineering has also changed to the characteristics of normal technology design taking into account existing computer systems. Experiences show that the conditions and needs of such Software-Reengineering projects are highly complex and differ in their special characteristics ranging from aspects of quality of existing system documentation to organizational structures of the computer departments concerned. The Task-Artifact Cycle presented here gives a suitable reengineering approach emphasizing both analysis and design in Software-Reengineering.     

GPU-based real-time approximation of the ablation zone for radiofrequency ablation

Percutaneous radiofrequency ablation (RFA) is becoming a standard minimally invasive clinical procedure for the treatment of liver tumors. However, planning the applicator placement such that the malignant tissue is completely destroyed, is a demanding task that requires considerable experience. In this work, we present a fast GPU-based real-time approximation of the ablation zone incorporating the cooling effect of liver vessels. Weighted distance fields of varying RF applicator types are derived from complex numerical simulations to allow a fast estimation of the ablation zone. Furthermore, the heat-sink effect of the cooling blood flow close to the applicator's electrode is estimated by means of a preprocessed thermal equilibrium representation of the liver parenchyma and blood vessels. Utilizing the graphics card, the weighted distance field incorporating the cooling blood flow is calculated using a modular shader framework, which facilitates the real-time visualization of the ablation zone in projected slice views and in volume rendering. The proposed methods are integrated in our software assistant prototype for planning RFA therapy. The software allows the physician to interactively place virtual RF applicator models. The real-time visualization of the corresponding approximated ablation zone facilitates interactive evaluation of the tumor coverage in order to optimize the applicator's placement such that all cancer cells are destroyed by the ablation.     

Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic

This paper presents a new algorithm for the dynamic multi-level capacitated lot sizing problem with setup carry-overs (MLCLSP-L). The MLCLSP-L is a big-bucket model that allows the production of any number of products within a period, but it incorporates partial sequencing of the production orders in the sense that the first and the last products produced in a period are determined by the model. We solve a model which is applicable to general bill-of-material structures and which includes minimum lead times of one period and multi-period setup carry-overs. Our algorithm solves a series of mixed-integer linear programs in an iterative so-called fix-and-optimize approach. In each instance of these mixed-integer linear programs a large number of binary setup variables is fixed whereas only a small subset of these variables is optimized, together with the complete set of the inventory and lot size variables. A numerical study shows that the algorithm provides high-quality results and that the computational effort is moderate.