OpenRaiser/Intern-Atlas huggingface dataset:
Micro-CernVM: Slashing the Cost of Building and Deploying Virtual Machines
Venue: arXiv cs.DC 2013
Year: 2013

The traditional virtual machine building and and deployment process is centered around the virtual machine hard disk image. The packages comprising the VM operating system are carefully selected, hard disk images are built for a variety of different hypervisors, and images have to be distributed and decompressed in order to instantiate a virtual machine. Within the HEP community, the CernVM File System has been established in order to decouple the distribution from the experiment software from the building and distribution of the VM hard disk images. We show how to get rid of such pre-built hard disk images altogether. Due to the high requirements on POSIX compliance imposed by HEP application software, CernVM-FS can also be used to host and boot a Linux operating system. This allows the use of a tiny bootable CD image that comprises only a Linux kernel while the rest of the operating system is provided on demand by CernVM-FS. This approach speeds up the initial instantiation time and reduces virtual machine image sizes by an order of magnitude. Furthermore, security updates can be distributed instantaneously through CernVM-FS. By leveraging the fact that CernVM-FS is a versioning file system, a historic analysis environment can be easily re-spawned by selecting the corresponding CernVM-FS file system snapshot.
Vision-Guided Robot Hearing
Venue: arXiv cs.RO 2013
Year: 2013

Natural human-robot interaction in complex and unpredictable environments is one of the main research lines in robotics. In typical real-world scenarios, humans are at some distance from the robot and the acquired signals are strongly impaired by noise, reverberations and other interfering sources. In this context, the detection and localisation of speakers plays a key role since it is the pillar on which several tasks (e.g.: speech recognition and speaker tracking) rely. We address the problem of how to detect and localize people that are both seen and heard by a humanoid robot. We introduce a hybrid deterministic/probabilistic model. Indeed, the deterministic component allows us to map the visual information into the auditory space. By means of the probabilistic component, the visual features guide the grouping of the auditory features in order to form AV objects. The proposed model and the associated algorithm are implemented in real-time (17 FPS) using a stereoscopic camera pair and two microphones embedded into the head of the humanoid robot NAO. We performed experiments on (i) synthetic data, (ii) a publicly available data set and (iii) data acquired using the robot. The results we obtained validate the approach and encourage us to further investigate how vision can help robot hearing.
Determining Leishmania Infection Levels by Automatic Analysis of Microscopy Images
Venue: arXiv cs.CV 2013
Year: 2013

Analysis of microscopy images is one important tool in many fields of biomedical research, as it allows the quantification of a multitude of parameters at the cellular level. However, manual counting of these images is both tiring and unreliable and ultimately very time-consuming for biomedical researchers. Not only does this slow down the overall research process, it also introduces counting errors due to a lack of objectivity and consistency inherent to the researchers own human nature. This thesis addresses this issue by automatically determining infection indexes of macrophages parasite by Leishmania in microscopy images using computer vision and pattern recognition methodologies. Initially images are submitted to a pre-processing stage that consists in a normalization of illumination conditions. Three algorithms are then applied in parallel to each image. Algorithm A intends to detect macrophage nuclei and consists of segmentation via adaptive multi-threshold, and classification of resulting regions using a set of collected features. Algorithm B intends to detect parasites and is similar to Algorithm A but the adaptive multi-threshold is parameterized with a different constraints vector. Algorithm C intends to detect the macrophages and parasites cytoplasm and consists of a cut-off version of the previous two algorithms, where the classification step is skipped. Regions with multiple nuclei or parasites are processed by a voting system that employs both a Support Vector Machine and a set of region features for determining the number of objects present in each region. The previous vote is then taken into account as the number of mixtures to be used in a Gaussian Mixture Model to decluster the said region. Finally each parasite is assigned to, at most, a single macrophage using minimum Euclidean distance to a cell nucleus, thus quantifying Leishmania infection levels.
An Approximate, Efficient Solver for LP Rounding
Venue: arXiv cs.NA 2013
Year: 2013

Many problems in machine learning can be solved by rounding the solution of an appropriate linear program (LP). This paper shows that we can recover solutions of comparable quality by rounding an approximate LP solution instead of the ex- act one. These approximate LP solutions can be computed efficiently by applying a parallel stochastic-coordinate-descent method to a quadratic-penalty formulation of the LP. We derive worst-case runtime and solution quality guarantees of this scheme using novel perturbation and convergence analysis. Our experiments demonstrate that on such combinatorial problems as vertex cover, independent set and multiway-cut, our approximate rounding scheme is up to an order of magnitude faster than Cplex (a commercial LP solver) while producing solutions of similar quality.
Distance-based and continuum Fano inequalities with applications to statistical estimation
Venue: arXiv cs.IT 2013
Year: 2013

In this technical note, we give two extensions of the classical Fano inequality in information theory. The first extends Fano's inequality to the setting of estimation, providing lower bounds on the probability that an estimator of a discrete quantity is within some distance $t$ of the quantity. The second inequality extends our bound to a continuum setting and provides a volume-based bound. We illustrate how these inequalities lead to direct and simple proofs of several statistical minimax lower bounds.
Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading
Venue: arXiv cs.DC 2013
Year: 2013

We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network. We present the first protocol for any expander graph $G$ with $n$ nodes such that, the protocol informs every node in $O(\log n)$ rounds with high probability, and uses $\tilde{O}(\log n)$ random bits in total. The runtime of our protocol is tight, and the randomness requirement of $\tilde{O}(\log n)$ random bits almost matches the lower bound of $Ω(\log n)$ random bits for dense graphs. We further show that, for many graph families, polylogarithmic number of random bits in total suffice to spread the rumor in $O(\mathrm{poly}\log n)$ rounds. These results together give us an almost complete understanding of the randomness requirement of this fundamental gossip process. Our analysis relies on unexpectedly tight connections among gossip processes, Markov chains, and branching programs. First, we establish a connection between rumor spreading processes and Markov chains, which is used to approximate the rumor spreading time by the mixing time of Markov chains. Second, we show a reduction from rumor spreading processes to branching programs, and this reduction provides a general framework to derandomize gossip processes. In addition to designing rumor spreading protocols, these novel techniques may have applications in studying parallel and multiple random walks, and randomness complexity of distributed algorithms.
Selection Effects in Online Sharing: Consequences for Peer Adoption
Venue: arXiv cs.SI 2013
Year: 2013

Most models of social contagion take peer exposure to be a corollary of adoption, yet in many settings, the visibility of one's adoption behavior happens through a separate decision process. In online systems, product designers can define how peer exposure mechanisms work: adoption behaviors can be shared in a passive, automatic fashion, or occur through explicit, active sharing. The consequences of these mechanisms are of substantial practical and theoretical interest: passive sharing may increase total peer exposure but active sharing may expose higher quality products to peers who are more likely to adopt. We examine selection effects in online sharing through a large-scale field experiment on Facebook that randomizes whether or not adopters share Offers (coupons) in a passive manner. We derive and estimate a joint discrete choice model of adopters' sharing decisions and their peers' adoption decisions. Our results show that active sharing enables a selection effect that exposes peers who are more likely to adopt than the population exposed under passive sharing. We decompose the selection effect into two distinct mechanisms: active sharers expose peers to higher quality products, and the peers they share with are more likely to adopt independently of product quality. Simulation results show that the user-level mechanism comprises the bulk of the selection effect. The study's findings are among the first to address downstream peer effects induced by online sharing mechanisms, and can inform design in settings where a surplus of sharing could be viewed as costly.
Practical Characterization of Large Networks Using Neighborhood Information
Venue: arXiv cs.SI 2013
Year: 2013

Characterizing large online social networks (OSNs) through node querying is a challenging task. OSNs often impose severe constraints on the query rate, hence limiting the sample size to a small fraction of the total network. Various ad-hoc subgraph sampling methods have been proposed, but many of them give biased estimates and no theoretical basis on the accuracy. In this work, we focus on developing sampling methods for OSNs where querying a node also reveals partial structural information about its neighbors. Our methods are optimized for NoSQL graph databases (if the database can be accessed directly), or utilize Web API available on most major OSNs for graph sampling. We show that our sampling method has provable convergence guarantees on being an unbiased estimator, and it is more accurate than current state-of-the-art methods. We characterize metrics such as node label density estimation and edge label density estimation, two of the most fundamental network characteristics from which other network characteristics can be derived. We evaluate our methods on-the-fly over several live networks using their native APIs. Our simulation studies over a variety of offline datasets show that by including neighborhood information, our method drastically (4-fold) reduces the number of samples required to achieve the same estimation accuracy of state-of-the-art methods.
k-DAG Based Lifetime Aware Data Collection in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Sensor Networks need to be organized for efficient data collection and lifetime maximization. In this paper, we propose a novel routing structure, namely k-DAG, to balance the load of the base station's neighbours while providing the worst-case latency guarantee for data collection, and a distributed algorithm for construction a k-DAG based on a SPD (Shortest Path DAG). In a k-DAG, the lengths of the longest path and the shortest path of each sensor node to the base station differ by at most k. By adding sibling edges to a SPD, our distributed algorithm allows critical nodes to have more routing choices. The simulation results show that our approach significantly outperforms the SPD-based data collection approach in both network lifetime and load balance.
Multiple Closed-Form Local Metric Learning for K-Nearest Neighbor Classifier
Venue: arXiv cs.LG 2013
Year: 2013

Many researches have been devoted to learn a Mahalanobis distance metric, which can effectively improve the performance of kNN classification. Most approaches are iterative and computational expensive and linear rigidity still critically limits metric learning algorithm to perform better. We proposed a computational economical framework to learn multiple metrics in closed-form.
The principles of humanism for MANETs
Venue: arXiv cs.NI 2013
Year: 2013

The proposed humanistic approach mapped the human character and behavior into a device to evade the bondages of implementation and surely succeed as we live. Human societies are the complex and most organized networks, in which many communities having different cultural livelihood. The formation of communities within a society and the way of associations can be mapped to MANET. In this work we have presented the principles of humanism for MANETs. The proposed approach is not only robust and secure but it certainly meets the existing challenges (such as name resolution, address allocation and authentication). Its object oriented design defines a service in terms of Arts, Culture, and Machine. An 'Art' is the smallest unit of work (defined as an interface), the 'Culture' is the integration and implementation of one or more Arts (defined as a class) and finally the 'Machine' which is an instance of a Culture that defines a running service. The grouping of all communicable Machines having the same Culture forms a 'Community'. We have used the term 'Society' for a MANET having one or more communities and modeled using the humanistic approach. The proposed approach is compared with GloMoSim and the implementation of file transfer service is presented using the said approach. Our approach is better in terms of implementation of the basic services, security, reliability, throughput, extensibility, scalability etc.
Localizing Grasp Affordances in 3-D Points Clouds Using Taubin Quadric Fitting
Venue: arXiv cs.RO 2013
Year: 2013

Perception-for-grasping is a challenging problem in robotics. Inexpensive range sensors such as the Microsoft Kinect provide sensing capabilities that have given new life to the effort of developing robust and accurate perception methods for robot grasping. This paper proposes a new approach to localizing enveloping grasp affordances in 3-D point clouds efficiently. The approach is based on modeling enveloping grasp affordances as a cylindrical shells that corresponds to the geometry of the robot hand. A fast and accurate fitting method for quadratic surfaces is the core of our approach. An evaluation on a set of cluttered environments shows high precision and recall statistics. Our results also show that the approach compares favorably with some alternatives, and that it is efficient enough to be employed for robot grasping in real-time.
Are Lock-Free Concurrent Algorithms Practically Wait-Free?
Venue: arXiv cs.DC 2013
Year: 2013

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock- free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.
Systems Variability Modeling: A Textual Model Mixing Class and Feature Concepts
Venue: arXiv cs.SE 2013
Year: 2013

System reuse and cost are very important in software product line design area. Developers goal is to increase system reuse and decreasing cost and efforts for building components from scratch for each software configuration. This can be reached by developing Software Product Line (SPL). To handle SPL engineering process, several approaches with several techniques were developed. One of these approaches is called separated approach. It requires separating the commonalities and variability for system components to allow configuration selection based on user defined features. Textual notation-based approaches have been used for their formal syntax and semantics to represent system features and implementations. But these approaches are still weak in mixing features (conceptual level) and classes (physical level) that guarantee smooth and automatic configuration generation for software releases. The absence of methodology supporting the mixing process is a real weakness. In this paper, we enhanced SPL reuse by introducing some meta-features, classified according to their functions. As a first consequence, mixing class and feature concepts is supported in a simple way using class interfaces and inherent features for smooth move from feature model to class model. And as a second consequence, the mixing process is supported by a textual design and implementation methodology, mixing class and feature models by combining their concepts in a single language. The supported configuration generation process is simple, coherent, and complete.
On a non-local spectrogram for denoising one-dimensional signals
Venue: arXiv cs.CV 2013
Year: 2013

In previous works, we investigated the use of local filters based on partial differential equations (PDE) to denoise one-dimensional signals through the image processing of time-frequency representations, such as the spectrogram. In this image denoising algorithms, the particularity of the image was hardly taken into account. We turn, in this paper, to study the performance of non-local filters, like Neighborhood or Yaroslavsky filters, in the same problem. We show that, for certain iterative schemes involving the Neighborhood filter, the computational time is drastically reduced with respect to Yaroslavsky or nonlinear PDE based filters, while the outputs of the filtering processes are similar. This is heuristically justified by the connection between the (fast) Neighborhood filter applied to a spectrogram and the corresponding Nonlocal Means filter (accurate) applied to the Wigner-Ville distribution of the signal. This correspondence holds only for time-frequency representations of one-dimensional signals, not to usual images, and in this sense the particularity of the image is exploited. We compare though a series of experiments on synthetic and biomedical signals the performance of local and non-local filters.
Nonparametric Estimation of Multi-View Latent Variable Models
Venue: arXiv cs.LG 2013
Year: 2013

Spectral methods have greatly advanced the estimation of latent variable models, generating a sequence of novel and efficient algorithms with strong theoretical guarantees. However, current spectral algorithms are largely restricted to mixtures of discrete or Gaussian distributions. In this paper, we propose a kernel method for learning multi-view latent variable models, allowing each mixture component to be nonparametric. The key idea of the method is to embed the joint distribution of a multi-view latent variable into a reproducing kernel Hilbert space, and then the latent parameters are recovered using a robust tensor power method. We establish that the sample complexity for the proposed method is quadratic in the number of latent components and is a low order polynomial in the other relevant parameters. Thus, our non-parametric tensor approach to learning latent variable models enjoys good sample and computational efficiencies. Moreover, the non-parametric tensor power method compares favorably to EM algorithm and other existing spectral algorithms in our experiments.
The STONE Transform: Multi-Resolution Image Enhancement and Real-Time Compressive Video
Venue: arXiv cs.CV 2013
Year: 2013

Compressed sensing enables the reconstruction of high-resolution signals from under-sampled data. While compressive methods simplify data acquisition, they require the solution of difficult recovery problems to make use of the resulting measurements. This article presents a new sensing framework that combines the advantages of both conventional and compressive sensing. Using the proposed \stone transform, measurements can be reconstructed instantly at Nyquist rates at any power-of-two resolution. The same data can then be "enhanced" to higher resolutions using compressive methods that leverage sparsity to "beat" the Nyquist limit. The availability of a fast direct reconstruction enables compressive measurements to be processed on small embedded devices. We demonstrate this by constructing a real-time compressive video camera.
A new information dimension of complex networks
Venue: arXiv cs.SI 2013
Year: 2013

The fractal and self-similarity properties are revealed in many real complex networks. However, the classical information dimension of complex networks is not practical for real complex networks. In this paper, a new information dimension to characterize the dimension of complex networks is proposed. The difference of information for each box in the box-covering algorithm of complex networks is considered by this measure. The proposed method is applied to calculate the fractal dimensions of some real networks. Our results show that the proposed method is efficient for fractal dimension of complex networks.
Enhancing the Energy Efficiency of Radio Base Stations
Venue: arXiv cs.IT 2013
Year: 2013

This thesis is concerned with the energy efficiency of cellular networks. It studies the dominant power consumer in future cellular networks, the Long Term Evolution radio base stations (BS), and proposes mechanisms that enhance the BS energy efficiency by reducing its power consumption under target rate constraints. These mechanisms trade spare capacity for power saving.
A Bayesian approach to sparse channel estimation in OFDM systems
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we address the problem of estimating sparse communication channels in OFDM systems in the presence of carrier frequency offset (CFO) and unknown noise variance. To this end, we consider a convex optimization problem, including a probability function, accounting for the sparse nature of the communication channel. We use the Expectation-Maximization (EM) algorithm to solve the corresponding Maximum A Posteriori (MAP) estimation problem. We show that, by concentrating the cost function in one variable, namely the CFO, the channel estimate can be obtained in closed form within the EM framework in the maximization step. We present an example where we estimate the communication channel, the CFO, the symbol, the noise variance, and the parameter defining the prior distribution of the estimates. We compare the bit error rate performance of our proposed MAP approach against Maximum Likelihood.