Some approaches to improve tree-based nearest neighbour search algorithms

Nearest neighbour search is a widely used technique in pattern recognition. During the last three decades a large number of fast algorithms have been proposed. In this work we are interested in algorithms that can be used with any dissimilarity function provided that it fits the mathematical notion of distance.Some of such algorithms organize, in preprocessing time, the data in a tree structure that is traversed in search time to find the nearest neighbour. The speedup is obtained using some pruning rules that avoid the traversal of some parts of the tree.In this work two new decomposition methods to build the tree and three new pruning rules are explored. The behaviour of our proposal is studied through experiments with synthetic and real data.     

Approximating Node Connectivity Problems via Set Covers

Given a graph (directed or undirected) with costs on the edges, and an integer $k$, we consider the problem of finding a $k$-node connected spanning subgraph of minimum cost. For the general instance of the problem (directed or undirected), there is a simple $2k$-approximation algorithm. Better algorithms are known for various ranges of $n,k$. For undirected graphs with metric costs Khuller and Raghavachari gave a $( 2+{2(k-1)}/{n})$-approximation algorithm. We obtain the following results: (i) For arbitrary costs, a $k$-approximation algorithm for undirected graphs and a $(k+1)$-approximation algorithm for directed graphs. (ii) For metric costs, a $(2+({k-1})/{n})$-approximation algorithm for undirected graphs and a $(2+{k}/{n})$-approximation algorithm for directed graphs. For undirected graphs and $k=6,7$, we further improve the approximation ratio from $k$ to $\lceil (k+1)/2 \rceil=4$; previously, $\lceil (k+1)/2 \rceil$-approximation algorithms were known only for $k \leq 5$. We also give a fast $3$-approximation algorithm for $k=4$. The multiroot problem generalizes the min-cost $k$-connected subgraph problem. In the multiroot problem, requirements $k_u$ for every node $u$ are given, and the aim is to find a minimum-cost subgraph that contains $\max\{k_u,k_v\}$ internally disjoint paths between every pair of nodes $u,v$. For the general instance of the problem, the best known algorithm has approximation ratio $2k$, where $k=\max k_u$. For metric costs there is a 3-approximation algorithm. We consider the case of metric costs, and, using our techniques, improve for $k \leq 7$ the approximation guarantee from $3$ to $2+{\lfloor (k-1)/2 \rfloor}/{k} < 2.5$.     

New length bounds for cycle bases

Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n²) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).For weighted graphs, we construct cycle bases of length O(W⋅lognloglogn), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Ω(W⋅logn).We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases—as it is inherent to the approach of Elkin et al.—but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998).     

A decision support framework for metrics selection in goal-based measurement programs: GQM-DSFMS

Software organizations face challenges in managing and sustaining their measurement programs over time. The complexity of measurement programs increase with exploding number of goals and metrics to collect. At the same time, organizations usually have limited budget and resources for metrics collection. It has been recognized for quite a while that there is the need for prioritizing goals, which then ought to drive the selection of metrics. On the other hand, the dynamic nature of the organizations requires measurement programs to adapt to the changes in the stakeholders, their goals, information needs and priorities. Therefore, it is crucial for organizations to use structured approaches that provide transparency, traceability and guidance in choosing an optimum set of metrics that would address the highest priority information needs considering limited resources. This paper proposes a decision support framework for metrics selection (DSFMS) which is built upon the widely used Goal Question Metric (GQM) approach. The core of the framework includes an iterative goal-based metrics selection process incorporating decision making mechanisms in metrics selection, a pre-defined Attributes/Metrics Repository, and a Traceability Model among GQM elements. We also discuss alternative prioritization and optimization techniques for organizations to tailor the framework according to their needs. The evaluation of the GQM-DSFMS framework was done through a case study in a CMMI Level 3 software company.     

Convergence of multivalued mappings via approximable measurable selectors

We investigate the convergence of measurable selectors for the limit of measurable multivalued maps. The relationship between the convergence of measurable selectors and lower and upper limits of measurable multivalued mappings with closed images is also derived.     

A new clustering algorithm for coordinate-free data

This paper presents the colored farthest-neighbor graph (CFNG), a new method for finding clusters of similar objects. The method is useful because it works for both objects with coordinates and for objects without coordinates. The only requirement is that the distance between any two objects be computable. In other words, the objects must belong to a metric space. The CFNG uses graph coloring to improve on an existing technique by Rovetta and Masulli. Just as with their technique, it uses recursive partitioning to build a hierarchy of clusters. In recursive partitioning, clusters are sometimes split prematurely, and one of the contributions of this paper is a way to reduce the occurrence of such premature splits, which also result when other partition methods are used to find clusters.     

面向对象软件度量方法C＆K的改进

本文分析了面向对象软件应量的特点,着重研究现在流行的C＆K度量方法。针对其存在的不足,提出了自己的观点,并给出了度量公式。     

An uncertainty importance measure using a distance metric for the change in a cumulative distribution function

A simple measure of uncertainty importance using the entire change of cumulative distribution functions (CDFs) has been developed for use in probability safety assessments (PSAs). The entire change of CDFs is quantified in terms of the metric distance between two CDFs. The metric distance measure developed in this study reflects the relative impact of distributional changes of inputs on the change of an output distribution, while most of the existing uncertainty importance measures reflect the magnitude of relative contribution of input uncertainties to the output uncertainty. The present measure has been evaluated analytically for various analytical distributions to examine its characteristics. To illustrate the applicability and strength of the present measure, two examples are provided. The first example is an application of the present measure to a typical problem of a system fault tree analysis and the second one is for a hypothetical non-linear model. Comparisons of the present result with those obtained by existing uncertainty importance measures show that the metric distance measure is a useful tool to express the measure of uncertainty importance in terms of the relative impact of distributional changes of inputs on the change of an output distribution.     

Energy efficiency studies through 3D laser scanning and thermographic technologies

Infrared thermography is generally used in energy efficiency studies in buildings, as well as in moisture detection studies and building inspections for heat losses. Commonly, thermographic studies are qualitative, based on detection of differences of temperature between points; and they only include thermal measurements on specific points or areas, associated to many other factors such as the thermal properties of the materials and environmental temperature and humidity. But this way of working presents a lot of limitations, as there is no way of executing precise quantitative measurements, because thermographic models are simple in geometry and thermographies include geometrical distortions introduced by the camera they are taken with.Laser scanning technology can be an optimal complement for the thermographic measurement, because it provides the metric information that allows the quantification of the thermal studies if the clouds of points are texturized with thermographies.In this paper a methodology for registering thermographies in clouds of points is explained, with the following steps: procedure for processing the metric calibration of the thermal camera, register of thermographies in the cloud of points based on control points, and finally, processing the textured cloud of points to obtain rectified thermographies, with no optical distortions.