A bounded distance metric for comparing tree structure

Comparing tree-structured data for structural similarity is a recurring theme and one on which much effort has been spent. Most approaches so far are grounded, implicitly or explicitly, in algorithmic information theory, being approximations to an information distance derived from Kolmogorov complexity. In this paper we propose a novel complexity metric, also grounded in information theory, but calculated via Shannon's entropy equations. This is used to formulate a directly and efficiently computable metric for the structural difference between unordered trees. The paper explains the derivation of the metric in terms of information theory, and proves the essential property that it is a distance metric. The property of boundedness means that the metric can be used in contexts such as clustering, where second-order comparisons are required. The distance metric property means that the metric can be used in the context of similarity search and metric spaces in general, allowing trees to be indexed and stored within this domain. We are not aware of any other tree similarity metric with these properties.     

The MORPHEUS Heterogeneous Dynamically Reconfigurable Platform

Reconfigurable computing offers a wide range of low cost and efficient solutions for embedded systems. The proper choice of the reconfigurable device, the granularity of its processing elements and its memory architecture highly depend on the type of application and their data flow. Existing solutions either offer fine grain FPGAs, which rely on a hardware synthesis flow and offer the maximum degree of flexibility, or coarser grain solutions, which are usually more suitable for a particular type of data flow and applications. In this paper, we present the MORPHEUS architecture, a versatile reconfigurable heterogeneous System-on-Chip targeting streaming applications. The presented architecture exploits different reconfigurable technologies at several computation granularities that efficiently address the different applications needs. In order to efficiently exploit the presented architecture, we implemented a complete software solution to map C applications to the reconfigurable architecture. In this paper, we describe the complete toolset and provide concrete use cases of the architecture.     

Impact of orthorectification and spatial sampling on maximum NDVI composite data in mountain regions

Topography and accuracy of image geometric registration significantly affect the quality of satellite data, since pixels are displaced depending on surface elevation and viewing geometry. This effect should be corrected for through the process of accurate image navigation and orthorectification in order to meet the geolocation accuracy for systematic observations specified by the Global Climate Observing System (GCOS) requirements for satellite climate data records. We investigated the impact of orthorectification on the accuracy of maximum Normalized Difference Vegetation Index (NDVI) composite data for a mountain region in north-western Canada at various spatial resolutions (1 km, 4 km, 5 km, and 8 km). Data from AVHRR on board NOAA-11 (1989 and 1990) and NOAA-16 (2001, 2002, and 2003) processed using a system called CAPS (Canadian AVHRR Processing System) for the month of August were considered. Results demonstrate the significant impact of orthorectification on the quality of composite NDVI data in mountainous terrain. Differences between orthorectified and non-orthorectified NDVI composites (ΔNDVI) adopted both large positive and negative values, with the 1% and 99% percentiles of ΔNDVI at 1 km resolution spanning values between − 0.16 < ΔNDVI < 0.09. Differences were generally reduced to smaller numbers for coarser resolution data, but systematic positive biases for non-orthorectified composites were obtained at all spatial resolutions, ranging from 0.02 (1 km) to 0.004 (8 km). Analyzing the power spectra of maximum NDVI composites at 1 km resolution, large differences between orthorectified and non-orthorectified AVHRR data were identified at spatial scales between 4 km and 10 km. Validation of NOAA-16 AVHRR NDVI with MODIS NDVI composites revealed higher correlation coefficients (by up to 0.1) for orthorectified composites relative to the non-orthorectified case. Uncertainties due to the AVHRR Global Area Coverage (GAC) sampling scheme introduce an average positive bias of 0.02 ± 0.03 at maximum NDVI composite level that translates into an average relative bias of 10.6% ± 19.1 for sparsely vegetated mountain regions. This can at least partially explain the systematic average positive biases we observed relative to our results in AVHRR GAC-based composites from the Global Inventory Modeling and Mapping Studies (GIMMS) and Polar Pathfinder (PPF) datasets (0.19 and 0.05, respectively). With regard to the generation of AVHRR long-term climate data records, results suggest that orthorectification should be an integral part of AVHRR pre-processing, since neglecting the terrain displacement effect may lead to important biases and additional noise in time series at various spatial scales.     

Using frameworks to develop a distributed conferencing system: an experience report

Application frameworks are a powerful means to reduce software development costs while improving quality. However, at the same time they are difficult to select and understand, as well as hard to learn, use, and debug effectively and efficiently. In this paper we report the story of eConference, a distributed conferencing system that was developed as part of a broader research effort. Here we discuss the lessons learned from the evolution of our conferencing tool over four generations, which have been necessary to find good frameworks and build a flexible distributed tool. Copyright © 2009 John Wiley & Sons, Ltd.     

Space and time localization for the estimation of distributed parameters in a finite element model

In this paper we study the problem of estimating the possibly non-homogeneous material coefficients inside a physical system, from transient excitations and measurements made in a few points on the boundary. We assume there is available an adequate Finite Element (FEM) model of the system, whose distributed physical parameters must be estimated from the experimental data.We propose a space–time localization approach that gives a better conditioned estimation problem, without the need of an expensive regularization. Some experimental results obtained on an elastic system with random coefficients are given.     

The subsequence composition of a string

Words that appear as constrained subsequences in a text-string are considered as possible indicators of the host string structure, hence also as a possible means of sequence comparison and classification. The constraint consists of imposing a bound on the number ω$\omega$ of positions in the text that may intervene between any two consecutive characters of a subsequence. A subset of such ω$\omega$-sequences is then characterized that consists, in intuitive terms, of sequences that could not be enriched with more characters without losing some occurrence in the text. A compact spatial representation is then proposed for these representative sequences, within which a number of parameters can be defined and measured. In the final part of the paper, such parameters are empirically analyzed on a small collection of text-strings endowed with various degrees of structure.     

Robust stabilization of second-order image-based affine systems

In this paper, the problem of robust relative positioning between a 6-DOF robot camera and an object of interest is considered. Assuming weak perspective camera model and local linear approximation of visible object's surface, an image-based state space representation of robot camera–object interaction model is derived, based on the matrix of 2-D affine transformations. Dynamic extension of the visual model permits to estimate 3-D parameters directly as functions of state variables. The proposed nonlinear robust control law ensures asymptotic stability but at image singularities, assuming exact model and state measurements. In the presence of bounded uncertainties, under appropriate choice of control gains, ultimate boundedness of the state error is also formally proved. Simulation results validate the theoretical framework both in terms of system convergence and control robustness.     

Evaluating ASP and Commercial Solvers on the CSPLib

This paper deals with four solvers for combinatorial problems: the commercial state-of-the-art solver ILOG oplstudio, and the research answer set programming (ASP) systems dlv, smodels and cmodels. The first goal of this research is to evaluate the relative performance of such systems when used in a purely declarative way, using a reproducible and extensible experimental methodology. In particular, we consider a third-party problem library, i.e., the CSPLib, and uniform rules for modelling and instance selection. The second goal is to analyze the marginal effects of popular reformulation techniques on the various solving technologies. In particular, we consider structural symmetry breaking, the adoption of global constraints, and the addition of auxiliary predicates. Finally, we evaluate, on a subset of the problems, the impact of numbers and arithmetic constraints on the different solving technologies. Results show that there is not a single solver winning on all problems, and that reformulation is almost always beneficial: symmetry-breaking may be a good choice, but its complexity has to be carefully chosen, by taking into account also the particular solver used. Global constraints often, but not always, help opl, and the addition of auxiliary predicates is usually worth, especially when dealing with ASP solvers. Moreover, interesting synergies among the various modelling techniques exist.     

Modeling and Managing Interactions among Business Processes

Most workflow management systems (WfMSs) only support the separate andindependent execution of business processes. However, processes often needto interact with each other, in order to synchronize the execution of theiractivities, to exchange process data, to request execution of services, orto notify progresses in process execution. Recent market trends also raisethe need for cooperation and interaction between processes executed in differentorganizations, posing additional challenges. In fact, in order to reduce costsand provide better services, companies are pushed to increase cooperation and toform virtual enterprises, where business processes span across organizationalboundaries and are composed of cooperating workflows executed in differentorganizations. Workflow interaction in a cross-organizational environment iscomplicated by the heterogeneity of workflow management platforms on top ofwhich workflows are defined and executed and by the different and possiblycompeting business policies and business goals that drive process executionin each organization.In this paper we propose a model and system that enable interactionbetween workflows executed in the same or in different organizations. Weextend traditional workflow models by allowing workflows to publish andsubscribe to events, and by enabling the definition of points in the processexecution where events should be sent or received. Event notifications aremanaged by a suitable event service that is capable of filtering andcorrelating events, and of dispatching them to the appropriate targetworkflow instances. The extended model can be easily mapped onto anyworkflow model, since event specific constructs can be specified by means ofordinary workflow activities, for which we provide the implementation. Inaddition, the event service is easily portable to different platforms, anddoes not require integration with the WfMS that supports the cooperatingworkflows. Therefore, the proposed approach is applicable in virtually anyenvironment and is independent on the specific platform adopted     

Modelling Calculi with Name Mobility using Graphs with Equivalences

In the theory of graph rewriting, the use of coalescing rules, i.e., of rules which besides deleting and generating graph items, can coalesce some parts of the graph, turns out to be quite useful for modelling purposes, but, at the same time, problematic for the development of a satisfactory partial order concurrent semantics for rewrites. Rewriting over graphs with equivalences, i.e., (typed hyper)-graphs equipped with an equivalence over nodes provides a technically convenient replacement of graph rewriting with coalescing rules, for which a truly concurrent semantics can be easily defined. The expressivity of such a formalism is tested in a setting where coalescing rules typically play a basic role: the encoding of calculi with name passing as graph rewriting systems. Specifically, we show how the (monadic fragment) of the solo calculus, one of the dialect of those calculi whose distinctive feature is name fusion, can be encoded as a rewriting system over graph with equivalences.