OpenRaiser/Intern-Atlas huggingface dataset:
Statistical physics and approximate message-passing algorithms for sparse linear estimation problems in signal processing and coding theory
Venue: arXiv cs.IT 2015
Year: 2015

This thesis is interested in the application of statistical physics methods and inference to sparse linear estimation problems. The main tools are the graphical models and approximate message-passing algorithm together with the cavity method. We will also use the replica method of statistical physics of disordered systems which allows to associate to the studied problems a cost function referred as the potential of free entropy in physics. It allows to predict the different phases of typical complexity of the problem as a function of external parameters such as the noise level or the number of measurements one has about the signal: the inference can be typically easy, hard or impossible. We will see that the hard phase corresponds to a regime of coexistence of the actual solution together with another unwanted solution of the message passing equations. In this phase, it represents a metastable state which is not the true equilibrium solution. This phenomenon can be linked to supercooled water blocked in the liquid state below its freezing critical temperature. We will use a method that allows to overcome the metastability mimicing the strategy adopted by nature itself for supercooled water: the nucleation and spatial coupling. In supercooled water, a weak localized perturbation is enough to create a crystal nucleus that will propagate in all the medium thanks to the physical couplings between closeby atoms. The same process will help the algorithm to find the signal, thanks to the introduction of a nucleus containing local information about the signal. It will then spread as a "reconstruction wave" similar to the crystal in the water. After an introduction to statistical inference and sparse linear estimation, we will introduce the necessary tools. Then we will move to applications of these notions to signal processing and coding theory problems.
Evolving hypernetwork model based on WeChat user relations
Venue: arXiv cs.SI 2015
Year: 2015

Based on the theory of hypernetwork and WeChat online social relations, the paper proposes an evolving hypernetwork model with the competitiveness and the age of nodes. In the model, nodes arrive at the system in accordance with Poisson process and are gradual aging. We analyze the model by using a Poisson process theory and a continuous technique, and give a characteristic equation of hyperdegrees. We obtain the stationary average hyperdegree distribution of the hypernetwork by the characteristic equation. The numerical simulations of the models agree with the analytical results well. It is expected that our work may give help to the study of WeChat information transmission dynamics and mobile e-commerce.
Multi-Target Tracking and Occlusion Handling with Learned Variational Bayesian Clusters and a Social Force Model
Venue: arXiv cs.CV 2015
Year: 2015

This paper considers the problem of multiple human target tracking in a sequence of video data. A solution is proposed which is able to deal with the challenges of a varying number of targets, interactions and when every target gives rise to multiple measurements. The developed novel algorithm comprises variational Bayesian clustering combined with a social force model, integrated within a particle filter with an enhanced prediction step. It performs measurement-to-target association by automatically detecting the measurement relevance. The performance of the developed algorithm is evaluated over several sequences from publicly available data sets: AV16.3, CAVIAR and PETS2006, which demonstrates that the proposed algorithm successfully initializes and tracks a variable number of targets in the presence of complex occlusions. A comparison with state-of-the-art techniques due to Khan et al., Laet et al. and Czyz et al. shows improved tracking performance.
Parallelizing Query Optimization on Shared-Nothing Architectures
Venue: arXiv cs.DB 2015
Year: 2015

Data processing systems offer an ever increasing degree of parallelism on the levels of cores, CPUs, and processing nodes. Query optimization must exploit high degrees of parallelism in order not to gradually become the bottleneck of query evaluation. We show how to parallelize query optimization at a massive scale. We present algorithms for parallel query optimization in left-deep and bushy plan spaces. At optimization start, we divide the plan space for a given query into partitions of equal size that are explored in parallel by worker nodes. At the end of optimization, each worker returns the optimal plan in its partition to the master which determines the globally optimal plan from the partition-optimal plans. No synchronization or data exchange is required during the actual optimization phase. The amount of data sent over the network, at the start and at the end of optimization, as well as the complexity of serial steps within our algorithms increase only linearly in the number of workers and in the query size. The time and space complexity of optimization within one partition decreases uniformly in the number of workers. We parallelize single- and multi-objective query optimization over a cluster with 100 nodes in our experiments, using more than 250 concurrent worker threads (Spark executors). Despite high network latency and task assignment overheads, parallelization yields speedups of up to one order of magnitude for large queries whose optimization takes minutes on a single node.
Pattern matching in $(213,231)$-avoiding permutations
Venue: arXiv cs.DS 2015
Year: 2015

Given permutations $σ\in S_k$ and $π\in S_n$ with $k<n$, the \emph{pattern matching} problem is to decide whether $π$ matches $σ$ as an order-isomorphic subsequence. We give a linear-time algorithm in case both $π$ and $σ$ avoid the two size-$3$ permutations $213$ and $231$. For the special case where only $σ$ avoids $213$ and $231$, we present a $O(max(kn^2,n^2\log(\log(n)))$ time algorithm. We extend our research to bivincular patterns that avoid $213$ and $231$ and present a $O(kn^4)$ time algorithm. Finally we look at the related problem of the longest subsequence which avoids $213$ and $231$.
Wood Species Recognition Based on SIFT Keypoint Histogram
Venue: arXiv cs.CV 2015
Year: 2015

Traditionally, only experts who are equipped with professional knowledge and rich experience are able to recognize different species of wood. Applying image processing techniques for wood species recognition can not only reduce the expense to train qualified identifiers, but also increase the recognition accuracy. In this paper, a wood species recognition technique base on Scale Invariant Feature Transformation (SIFT) keypoint histogram is proposed. We use first the SIFT algorithm to extract keypoints from wood cross section images, and then k-means and k-means++ algorithms are used for clustering. Using the clustering results, an SIFT keypoints histogram is calculated for each wood image. Furthermore, several classification models, including Artificial Neural Networks (ANN), Support Vector Machine (SVM) and K-Nearest Neighbor (KNN) are used to verify the performance of the method. Finally, through comparing with other prevalent wood recognition methods such as GLCM and LBP, results show that our scheme achieves higher accuracy.
The Complexity of Interaction (Long Version)
Venue: arXiv cs.PL 2015
Year: 2015

In this paper, we analyze the complexity of functional programs written in the interaction-net computation model, an asynchronous, parallel and confluent model that generalizes linear-logic proof nets. Employing user-defined sized and scheduled types, we certify concrete time, space and space-time complexity bounds for both sequential and parallel reductions of interaction-net programs by suitably assigning complexity potentials to typed nodes. The relevance of this approach is illustrated on archetypal programming examples. The provided analysis is precise, compositional and is, in theory, not restricted to particular complexity classes.
Thoughts on Massively Scalable Gaussian Processes
Venue: arXiv cs.LG 2015
Year: 2015

We introduce a framework and early results for massively scalable Gaussian processes (MSGP), significantly extending the KISS-GP approach of Wilson and Nickisch (2015). The MSGP framework enables the use of Gaussian processes (GPs) on billions of datapoints, without requiring distributed inference, or severe assumptions. In particular, MSGP reduces the standard $O(n^3)$ complexity of GP learning and inference to $O(n)$, and the standard $O(n^2)$ complexity per test point prediction to $O(1)$. MSGP involves 1) decomposing covariance matrices as Kronecker products of Toeplitz matrices approximated by circulant matrices. This multi-level circulant approximation allows one to unify the orthogonal computational benefits of fast Kronecker and Toeplitz approaches, and is significantly faster than either approach in isolation; 2) local kernel interpolation and inducing points to allow for arbitrarily located data inputs, and $O(1)$ test time predictions; 3) exploiting block-Toeplitz Toeplitz-block structure (BTTB), which enables fast inference and learning when multidimensional Kronecker structure is not present; and 4) projections of the input space to flexibly model correlated inputs and high dimensional data. The ability to handle many ($m \approx n$) inducing points allows for near-exact accuracy and large scale kernel learning.
Radon-Nikodym approximation in application to image analysis
Venue: arXiv cs.CV 2015
Year: 2015

For an image pixel information can be converted to the moments of some basis $Q_k$, e.g. Fourier-Mellin, Zernike, monomials, etc. Given sufficient number of moments pixel information can be completely recovered, for insufficient number of moments only partial information can be recovered and the image reconstruction is, at best, of interpolatory type. Standard approach is to present interpolated value as a linear combination of basis functions, what is equivalent to least squares expansion. However, recent progress in numerical stability of moments estimation allows image information to be recovered from moments in a completely different manner, applying Radon-Nikodym type of expansion, what gives the result as a ratio of two quadratic forms of basis functions. In contrast with least squares the Radon-Nikodym approach has oscillation near the boundaries very much suppressed and does not diverge outside of basis support. While least squares theory operate with vectors $<fQ_k>$, Radon-Nikodym theory operates with matrices $<fQ_jQ_k>$, what make the approach much more suitable to image transforms and statistical property estimation.
SecureD: A Secure Dual Core Embedded Processor
Venue: arXiv cs.AR 2015
Year: 2015

Security of embedded computing systems is becoming of paramount concern as these devices become more ubiquitous, contain personal information and are increasingly used for financial transactions. Security attacks targeting embedded systems illegally gain access to the information in these devices or destroy information. The two most common types of attacks embedded systems encounter are code-injection and power analysis attacks. In the past, a number of countermeasures, both hardware- and software-based, were proposed individually against these two types of attacks. However, no single system exists to counter both of these two prominent attacks in a processor based embedded system. Therefore, this paper, for the first time, proposes a hardware/software based countermeasure against both code-injection attacks and power analysis based side-channel attacks in a dual core embedded system. The proposed processor, named SecureD, has an area overhead of just 3.80% and an average runtime increase of 20.0% when compared to a standard dual processing system. The overhead were measured using a set of industry standard application benchmarks, with two encryption and five other programs.
Facial Expression Recognition Using Sparse Gaussian Conditional Random Field
Venue: arXiv cs.CV 2015
Year: 2015

The analysis of expression and facial Action Units (AUs) detection are very important tasks in fields of computer vision and Human Computer Interaction (HCI) due to the wide range of applications in human life. Many works has been done during the past few years which has their own advantages and disadvantages. In this work we present a new model based on Gaussian Conditional Random Field. We solve our objective problem using ADMM and we show how well the proposed model works. We train and test our work on two facial expression datasets, CK+ and RU-FACS. Experimental evaluation shows that our proposed approach outperform state of the art expression recognition.
Performance Evaluation of Microservices Architectures using Containers
Venue: arXiv cs.DC 2015
Year: 2015

Microservices architecture has started a new trend for application development for a number of reasons: (1) to reduce complexity by using tiny services; (2) to scale, remove and deploy parts of the system easily; (3) to improve flexibility to use different frameworks and tools; (4) to increase the overall scalability; and (5) to improve the resilience of the system. Containers have empowered the usage of microservices architectures by being lightweight, providing fast start-up times, and having a low overhead. Containers can be used to develop applications based on monolithic architectures where the whole system runs inside a single container or inside a microservices architecture where one or few processes run inside the containers. Two models can be used to implement a microservices architecture using containers: master-slave, or nested-container. The goal of this work is to compare the performance of CPU and network running benchmarks in the two aforementioned models of microservices architecture hence provide a benchmark analysis guidance for system designers.
Traversing Grammar-Compressed Trees with Constant Delay
Venue: arXiv cs.DS 2015
Year: 2015

A grammar-compressed ranked tree is represented with a linear space overhead so that a single traversal step, i.e., the move to the parent or the i-th child, can be carried out in constant time. Moreover, we extend our data structure such that equality of subtrees can be checked in constant time.
Seven ways to improve example-based single image super resolution
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present seven techniques that everybody should know to improve example-based single image super resolution (SR): 1) augmentation of data, 2) use of large dictionaries with efficient search structures, 3) cascading, 4) image self-similarities, 5) back projection refinement, 6) enhanced prediction by consistency check, and 7) context reasoning. We validate our seven techniques on standard SR benchmarks (i.e. Set5, Set14, B100) and methods (i.e. A+, SRCNN, ANR, Zeyde, Yang) and achieve substantial improvements.The techniques are widely applicable and require no changes or only minor adjustments of the SR methods. Moreover, our Improved A+ (IA) method sets new state-of-the-art results outperforming A+ by up to 0.9dB on average PSNR whilst maintaining a low time complexity.
Climbing Mont Blanc - A Training Site for Energy Efficient Programming on Heterogeneous Multicore Processors
Venue: arXiv cs.DC 2015
Year: 2015

Climbing Mont Blanc (CMB) is an open online judge used for training in energy efficient programming of state-of-the-art heterogeneous multicores. It uses an Odroid-XU3 board from Hardkernel with an Exynos Octa processor and integrated power sensors. This processor is three-way heterogeneous containing 14 different cores of three different types. The board currently accepts C and C++ programs, with support for OpenCL v1.1, OpenMP 4.0 and Pthreads. Programs submitted using the graphical user interface are evaluated with respect to time, energy used, and energy-efficiency (EDP). A small and varied set of problems are available, and the system is currently in use in a medium sized course on parallel computing at NTNU. Other online programming judges exist, but we are not aware of any similar system that also reports energy-efficiency.
Active Perceptual Similarity Modeling with Auxiliary Information
Venue: arXiv cs.LG 2015
Year: 2015

Learning a model of perceptual similarity from a collection of objects is a fundamental task in machine learning underlying numerous applications. A common way to learn such a model is from relative comparisons in the form of triplets: responses to queries of the form "Is object a more similar to b than it is to c?". If no consideration is made in the determination of which queries to ask, existing similarity learning methods can require a prohibitively large number of responses. In this work, we consider the problem of actively learning from triplets -finding which queries are most useful for learning. Different from previous active triplet learning approaches, we incorporate auxiliary information into our similarity model and introduce an active learning scheme to find queries that are informative for quickly learning both the relevant aspects of auxiliary data and the directly-learned similarity components. Compared to prior approaches, we show that we can learn just as effectively with much fewer queries. For evaluation, we introduce a new dataset of exhaustive triplet comparisons obtained from humans and demonstrate improved performance for different types of auxiliary information.
On the Optimality of Uncoded Cache Placement
Venue: arXiv cs.IT 2015
Year: 2015

Caching is an efficient way to reduce peak-hour network traffic congestion by storing some contents at user's local cache without knowledge of later demands. Maddah-Ali and Niesen initiated a fundamental study of caching systems; they proposed a scheme (with uncoded cache placement and linear network coding delivery) that is provably optimal to within a factor 12. In this paper, by noticing that when the cache contents and the demands are fixed, the caching problem can be seen as an index coding problem, we show the optimality of Maddah-Ali and Niesen's scheme assuming that cache placement is restricted to be uncoded and the number of users is not less than the number of files. Furthermore, this result states that further improvement to the Maddah-Ali and Niesen's scheme in this regimes can be obtained only by coded cache placement.
Deterministic Annealing Based Optimization for Zero-Delay Source-Channel Coding in Networks
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies the problem of global optimization of zero-delay source-channel codes that map between the source space and the channel space, under a given transmission power constraint and for the mean square error distortion. Particularly, we focus on two well known network settings: the Wyner-Ziv setting where only a decoder has access to side information and the distributed setting where independent encoders transmit over independent channels to a central decoder. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic noisy channel relaxation method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization in more complicated settings considered in this paper. We propose a powerful non-convex optimization method based on the concept of deterministic annealing -- which is derived from information theoretic principles and was successfully employed in several problems including vector quantization, classification and regression. We present comparative numerical results that show strict superiority of the proposed method over greedy optimization methods as well as prior approaches in literature.
Review of Person Re-identification Techniques
Venue: arXiv cs.CV 2015
Year: 2015

Person re-identification across different surveillance cameras with disjoint fields of view has become one of the most interesting and challenging subjects in the area of intelligent video surveillance. Although several methods have been developed and proposed, certain limitations and unresolved issues remain. In all of the existing re-identification approaches, feature vectors are extracted from segmented still images or video frames. Different similarity or dissimilarity measures have been applied to these vectors. Some methods have used simple constant metrics, whereas others have utilised models to obtain optimised metrics. Some have created models based on local colour or texture information, and others have built models based on the gait of people. In general, the main objective of all these approaches is to achieve a higher-accuracy rate and lowercomputational costs. This study summarises several developments in recent literature and discusses the various available methods used in person re-identification. Specifically, their advantages and disadvantages are mentioned and compared.
Suboptimal Spatial Diversity Scheme for 60 GHz Millimeter-Wave WLAN
Venue: arXiv cs.IT 2015
Year: 2015

This letter revisits the equal-gain (EG) spatial diversity technique, which was proposed to combat the human-induced shadowing for 60 GHz wireless local area network, under a more practical frequency-selective multi-input multi-output channel. Subsequently, a suboptimal spatial diversity scheme called maximal selection (MS) is proposed by tracing the shadowing process, owing to a considerably high data rate. Comparisons show that MS outperforms EG in terms of link margin and saves computation complexity.
Opposites Attract: Virtual Cluster Embedding for Profit
Venue: arXiv cs.NI 2015
Year: 2015

It is well-known that cloud application performance critically depends on the network. Accordingly, new abstractions for cloud applications are proposed which extend the performance isolation guarantees to the network. The most common abstraction is the Virtual Cluster V C(n, b): the n virtual machines of a customer are connected to a virtual switch at bandwidth b. However, today, not much is known about how to efficiently embed and price virtual clusters. This paper makes two contributions. (1) We present an algorithm called Tetris that efficiently embeds virtual clusters arriving in an online fashion, by jointly optimizing the node and link resources. We show that this algorithm allows to multiplex more virtual clusters over the same physical infrastructure compared to existing algorithms, hence improving the provider profit. (2) We present the first demand-specific pricing model called DSP for virtual clusters. Our pricing model is fair in the sense that a customer only needs to pay for what he or she asked. Moreover, it features other desirable properties, such as price independence from mapping locations.
Anonymous On-line Communication Between Program Analyses
Venue: arXiv cs.PL 2015
Year: 2015

We propose a light-weight client-server model of communication between program analyses. Clients are individual analyses and the server mediates their communication. A client cannot see properties of any other and the communication is anonymous. There is no central algorithm standing above clients which would tell them when to communicate what information. Clients communicate with others spontaneously, according to their actual personal needs. The model is based on our observation that a piece of information provided to an analysis at a right place may (substantially) improve its result. We evaluated the proposed communication model for all possible combinations of three clients on more than 400 benchmarks and the results show that the communication model performs well in practice.
A Chinese POS Decision Method Using Korean Translation Information
Venue: arXiv cs.CL 2015
Year: 2015

In this paper we propose a method that imitates a translation expert using the Korean translation information and analyse the performance. Korean is good at tagging than Chinese, so we can use this property in Chinese POS tagging.