Improved PLSOM algorithm

The original Parameter-Less Self-Organising Map (PLSOM) algorithm was introduced as a solution to the problems the Self-Organising Map (SOM) encounters when dealing with certain types of mapping tasks. Unfortunately the PLSOM suffers from over-sensitivity to outliers and over-reliance on the initial weight distribution. The PLSOM2 algorithm is introduced to address these problems with the PLSOM. PLSOM2 is able to cope well with outliers without exhibiting the problems associated with the standard PLSOM algorithm. The PLSOM2 requires very little computational overhead compared to the standard PLSOM, thanks to an efficient method of approximating the diameter of the inputs, and does not rely on a priori knowledge of the training input space. This paper provides a discussion of the reasoning behind the PLSOM2 and experimental results showing its effectiveness for mapping tasks.     

Understanding cost drivers of software evolution: a quantitative and qualitative investigation of change effort in two evolving software systems

Making changes to software systems can prove costly and it remains a challenge to understand the factors that affect the costs of software evolution. This study sought to identify such factors by investigating the effort expended by developers to perform 336 change tasks in two different software organizations. We quantitatively analyzed data from version control systems and change trackers to identify factors that correlated with change effort. In-depth interviews with the developers about a subset of the change tasks further refined the analysis. Two central quantitative results found that dispersion of changed code and volatility of the requirements for the change task correlated with change effort. The analysis of the qualitative interviews pointed to two important, underlying cost drivers: Difficulties in comprehending dispersed code and difficulties in anticipating side effects of changes. This study demonstrates a novel method for combining qualitative and quantitative analysis to assess cost drivers of software evolution. Given our findings, we propose improvements to practices and development tools to manage and reduce the costs.     

Reactive scheduling in the multi-mode RCPSP

The multi-mode resource-constrained project scheduling problem (MRCPSP) involves the determination of a baseline schedule of the project activities, which can be executed in multiple modes, satisfying the precedence relations and resource constraints while minimizing the project duration. During the execution of the project, the baseline schedule may become infeasible due to activity duration and resource disruptions. We propose and evaluate a number of dedicated exact reactive scheduling procedures as well as a tabu search heuristic for repairing a disrupted schedule, under the assumption that no activity can be started before its baseline starting time. We report on promising computational results obtained on a set of benchmark problems.     

The Covering Law Model Applied to Dynamical Cognitive Science: A Comment on Joel Walmsley

In a 2008 paper, Walmsley argued that the explanations employed in the dynamical approach to cognitive science, as exemplified by the Haken, Kelso and Bunz model of rhythmic finger movement, and the model of infant preservative reaching developed by Esther Thelen and her colleagues, conform to Carl Hempel and Paul Oppenheim’s deductive-nomological model of explanation (also known as the covering law model). Although we think Walmsley’s approach is methodologically sound in that it starts with an analysis of scientific practice rather than a general philosophical framework, we nevertheless feel that there are two problems with his paper. First, he focuses only on the deductivenomological model and so neglects the important fact that explanations are causal. Second, the explanations offered by the dynamical approach do not take the deductive-nomological format, because they do not deduce the explananda from exceptionless laws. Because of these two points, Walmsley makes the dynamical explanations in cognitive science appear problematic, while in fact they are not.     

Classifying species of individual trees by intensity and structure features derived from airborne laser scanner data

The objective of this study was to identify candidate features derived from airborne laser scanner (ALS) data suitable to discriminate between coniferous and deciduous tree species. Both features related to structure and intensity were considered. The study was conducted on 197 Norway spruce and 180 birch trees (leaves on conditions) in a boreal forest reserve in Norway. The ALS sensor used was capable of recording multiple echoes. The point density was 6.6 m^− 2. Laser echoes located within the vertical projection of the tree crowns, which were assumed to be circular and defined according to field measurements, were attributed to three categories: “first echoes of many”, “single echoes”, or “last echoes of many echoes”. They were denoted FIRST, SINGLE, and LAST, respectively. In tree species classification using ALS data features should be independent of tree heights. We found that many features were dependent on tree height and that this dependency influenced selection of candidate features. When we accounted for this dependency, it was revealed that FIRST and SINGLE echoes were located higher and LAST echoes lower in the birch crowns than in spruce crowns. The intensity features of the FIRST echoes differed more between species than corresponding features of the other echo categories. For the FIRST echoes the intensity values tended to be higher for birch than spruce. When using the various features for species classification, maximum overall classification accuracies of 77% and 73% were obtained for structural and intensity features, respectively. Combining candidate features related to structure and intensity resulted in an overall classification accuracy of 88%.     

Effects of different sensors, flying altitudes, and pulse repetition frequencies on forest canopy metrics and biophysical stand properties derived from small-footprint airborne laser data

Canopy height distributions were created from small-footprint airborne laser scanner (ALS) data collected over 40 field sample plots with size 1000 m² located in mature conifer forest. ALS data were collected with two different instruments, i.e., the ALTM 1233 and ALTM 3100 laser scanners (Optech Inc.). The ALTM 1233 data were acquired at a flying altitude of 1200 m and a pulse repetition frequency (PRF) of 33 kHz. Three different acquisitions were carried out with ALTM 3100, i.e., (1) a flying altitude of 1100 m and a PRF of 50 kHz, (2) a flying altitude of 1100 m and a PRF of 100 kHz, and (3) a flying altitude of 2000 m and a PRF of 50 kHz. Height percentiles, mean and maximum height values, coefficients of variation of the heights, and canopy density at different height intervals above the ground were derived from the four different ALS datasets and for single + first and last echoes of the ALS data separately. The ALS-derived height- and density variables were assessed in pair-wise comparisons to evaluate the effects of (a) instrument, (b) flying altitude, and (c) PRF. A systematic shift in height values of up to 0.3 m between sensors when the first echoes were compared was demonstrated. Also the density-related variables differed significantly between the two instruments. Comparisons of flying altitudes and PRFs revealed upwards shifted canopy height distributions for the highest flying altitude (2000 m) and the lowest PRF (50 kHz). The distribution of echoes on different echo categories, i.e., single and multiple (first and last) echoes, differed significantly between acquisitions. The proportion of multiple echoes decreased with increasing flying altitude and PRF. Different echo categories have different properties since it is likely that single echoes tend to occur in the densest parts of the tree crowns, i.e., near the apex where the concentration of biological matter is highest and distance to the ground is largest. To assess the influence of instrument, flying altitude, and PRF on biophysical properties derived from ALS data, regression analysis was carried out to relate ALS-derived metrics to mean tree height (h_L) and timber volume (V). Cross validation revealed only minor differences in precision for the different ALS acquisitions, but systematic differences between acquisitions of up to 2.5% for h_L and 10.7% for V were found when comparing data from different acquisitions.     

Design patterns for user interface for mobile applications

The topic of this paper is a collection of user interface (UI) design patterns for mobile applications. In the paper we present the structure of the patterns collection – the patterns are suggested solutions to problems that are grouped into a set of problem areas that are further grouped into three main problem areas – a structure which is valuable both as an index to identifying patterns to use, and it gives a fairly comprehensive overview of issues when designing user interfaces for mobile applications. To show the breadth of the patterns collection we present six individual problems with connected design patterns in some detail – each coming from different problem areas. They represent important and relevant problems, and are on different levels of abstraction, thus showing how patterns may be used to present problems and solutions on different levels of detail. To show the relevance and usefulness of the patterns collection for usability professionals with a mixed background, we present some relevant findings from a validation of the patterns collection. In addition to verifying the relevance and usefulness of the patterns collection, it also shows both expected and surprising correlations between background and perceived relevance and usefulness. One important finding from the validation is an indication that the patterns collection is best suited for experienced UI developers wanting to start developing mobile UIs. Using a patterns collection for documenting design knowledge and experience has been a mixed experience, so we discuss pros and cons of this. Finally, we present related work and future research.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

Improved Approximations for Guarding 1.5-Dimensional Terrains

We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629–640, 2006). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.