Enhancing density-based clustering: Parameter reduction and outlier detection

Clustering is a widely used unsupervised data mining technique. It allows to identify structures in collections of objects by grouping them into classes, named clusters, in such a way that similarity of objects within any cluster is maximized and similarity of objects belonging to different clusters is minimized. In density-based clustering, a cluster is defined as a connected dense component and grows in the direction driven by the density. The basic structure of density-based clustering presents some common drawbacks: (i) parameters have to be set; (ii) the behavior of the algorithm is sensitive to the density of the starting object; and (iii) adjacent clusters of different densities could not be properly identified. In this paper, we address all the above problems. Our method, based on the concept of space stratification, efficiently identifies the different densities in the dataset and, accordingly, ranks the objects of the original space. Next, it exploits such a knowledge by projecting the original data into a space with one more dimension. It performs a density based clustering taking into account the reverse-nearest-neighbor of the objects. Our method also reduces the number of input parameters by giving a guideline to set them in a suitable way. Experimental results indicate that our algorithm is able to deal with clusters of different densities and outperforms the most popular algorithms DBSCAN and OPTICS in all the standard benchmark datasets.     

Visual discovery of the correlation between BGP routing and round-trip delay active measurements

Inter-domain routing data and Internet active probing measurements are two types of information commonly available in huge datasets and subject to extensive, focused analysis. However, the study of the correlation between these two complementary types of information still remains one of the most challenging problems in today’s research in networking. In this paper we describe a metaphor for the visualization of the interplay between the routing information exchanged via BGP and the round-trip delay measurements collected by several geolocated probes. We implemented a prototype based on the above metaphor. Our prototype highlights both the Autonomous System topology and the latency associated with each AS-path over time. Further, it shows how probes are partitioned into clusters associated with each border gateway, based on observed traffic patterns. The resulting visualization allows the user to explore the dynamics of the correlation between the two types of information.     

3DStreaming: an open-source flexible framework for real-time 3D streaming services

The progress of three-dimensional 3D technologies, together with the wide diffusion of both Internet and broadband technologies, is paving the way to emerging live streaming services which have been conceived for delivering 3D video contents in real-time fashion to end users. Nowadays, the only available tools supporting stereoscopic 3D video services cannot be freely downloaded and require the adoption of owner stereoscopic players. Motivated by the lack of an effective solution, we developed a freeware and open source 3D live streaming framework, namely 3DStreaming. It provides stereoscopic 3D live streaming services over the Internet. In particular, it realizes a complete server implementation, offering the support for any transmission protocol and encoding scheme, as well as the full compatibility with any network architecture (i.e., LAN, MAN, Internet, and so on). At the same time, it allows users to use the preferable stereoscopic player and to render the video through any technique available for the chosen player. The overall performances of the proposed tool have been presented by testing its behavior in several network configurations (i.e., by varying network topology, coding technique, 3D representation format, and average encoding rate). All the measured metrics, which include the number of RTP segments that are transmitted and received, the frame loss ratio, and the PSNR, fully demonstrate the right behavior of the implemented tool in all the considered scenarios. We believe that, thanks to its high flexibility, this tool can be exploited by researchers working on stereoscopic-3D related issues to design, test, and evaluate novel and innovative algorithms, protocols, and network architectures.     

Decentralized multi-robot encirclement of a 3D target with guaranteed collision avoidance

We present a control framework for achieving encirclement of a target moving in 3D using a multi-robot system. Three variations of a basic control strategy are proposed for different versions of the encirclement problem, and their effectiveness is formally established. An extension ensuring maintenance of a safe inter-robot distance is also discussed. The proposed framework is fully decentralized and only requires local communication among robots; in particular, each robot locally estimates all the relevant global quantities. We validate the proposed strategy through simulations on kinematic point robots and quadrotor UAVs, as well as experiments on differential-drive wheeled mobile robots.     

Optimizing memory bandwidth exploitation for OpenVX applications on embedded many-core accelerators

In recent years, image processing has been a key application area for mobile and embedded computing platforms. In this context, many-core accelerators are a viable solution to efficiently execute highly parallel kernels. However, architectural constraints impose hard limits on the main memory bandwidth, and push for software techniques which optimize the memory usage of complex multi-kernel applications. In this work, we propose a set of techniques, mainly based on graph analysis and image tiling, targeted to accelerate the execution of image processing applications expressed as standard OpenVX graphs on cluster-based many-core accelerators. We have developed a run-time framework which implements these techniques using a front-end compliant to the OpenVX standard, and based on an OpenCL extension that enables more explicit control and efficient reuse of on-chip memory and greatly reduces the recourse to off-chip memory for storing intermediate results. Experiments performed on the STHORM many-core accelerator demonstrate that our approach leads to massive reduction of time and bandwidth, even when the main memory bandwidth for the accelerator is severely constrained.     

Missing data imputation, matching and other applications of random recursive partitioning

Applications of the random recursive partitioning (RRP) method are described. This method generates a proximity matrix which can be used in non-parametric matching problems such as hot-deck missing data imputation and average treatment effect estimation. RRP is a Monte Carlo procedure that randomly generates non-empty recursive partitions of the data and calculates the proximity between observations as the empirical frequency in the same cell of these random partitions over all the replications. Also, the method in the presence of missing data is invariant under monotonic transformations of the data but no other formal properties of the method are known yet. Therefore, Monte Carlo experiments were conducted in order to explore the performance of the method. A companion software is available as a package for the R statistical environment.     

Accurate Implicit–Explicit General Linear Methods with Inherent Runge–Kutta Stability

We investigate implicit–explicit (IMEX) general linear methods (GLMs) with inherent Runge–Kutta stability (IRKS) for differential systems with non-stiff and stiff processes. The construction of such formulas starts with implicit GLMs with IRKS which are A- and L-stable, and then we ‘remove’ implicitness in non-stiff terms by extrapolating unknown stage derivatives by stage derivatives which are already computed by the method. Then we search for IMEX schemes with large regions of absolute stability of the ‘explicit part’ of the method assuming that the ‘implicit part’ of the scheme is \(A(\alpha )\)-stable for some \(\alpha \in (0,\pi /2]\). Examples of highly stable IMEX GLMs are provided of order \(1\le p\le 4\). Numerical examples are also given which illustrate good performance of these schemes.     

WINSTODEC: a stochastic deconvolution interactive program for physiological and pharmacokinetic systems.

Deconvolution allows the reconstruction of non-accessible inputs (e.g. hormone secretion rate) from their causally-related measurable effects (e.g. hormone plasma concentration). Deconvolution is challenging under several aspects both general (e.g. determination of a suitable trade-off between data fit and solution smoothness in order to contrast ill-conditioning, assessment of the confidence intervals) as well as specific of physiological systems (e.g. non-uniform and infrequent data sampling). Recently, a stochastic regularization approach has been proposed and validated to handle these difficulties (De Nicolao et al., Automatica 33 (1997) 851-870). In this paper, an interactive program, WINSTODEC, is presented to allow the clinical investigator to easily obtain the solution of a deconvolution problem by this approach.     

Synthesis with rational environments

Synthesis is the automated construction of a system from its specification. The system has to satisfy its specification in all possible environments. The environment often consists of agents that have objectives of their own. Thus, it makes sense to soften the universal quantification on the behavior of the environment and take the objectives of its underlying agents into an account. Fisman et al. introduced rational synthesis: the problem of synthesis in the context of rational agents. The input to the problem consists of temporal logic formulas specifying the objectives of the system and the agents that constitute the environment, and a solution concept (e.g., Nash equilibrium). The output is a profile of strategies, for the system and the agents, such that the objective of the system is satisfied in the computation that is the outcome of the strategies, and the profile is stable according to the solution concept; that is, the agents that constitute the environment have no incentive to deviate from the strategies suggested to them. In this paper we continue to study rational synthesis. First, we suggest an alternative definition to rational synthesis, in which the agents are rational but not cooperative. We call such problem strong rational synthesis. In the strong rational synthesis setting, one cannot assume that the agents that constitute the environment take into account the strategies suggested to them. Accordingly, the output is a strategy for the system only, and the objective of the system has to be satisfied in all the compositions that are the outcome of a stable profile in which the system follows this strategy. We show that strong rational synthesis is 2ExpTime-complete, thus it is not more complex than traditional synthesis or rational synthesis. Second, we study a richer specification formalism, where the objectives of the system and the agents are not Boolean but quantitative. In this setting, the objective of the system and the agents is to maximize their outcome. The quantitative setting significantly extends the scope of rational synthesis, making the game-theoretic approach much more relevant. Finally, we enrich the setting to one that allows coalitions of agents that constitute the system or the environment.