OpenRaiser/Intern-Atlas huggingface dataset:
A Fast Heuristic Algorithm for Redundancy Removal
Venue: arXiv cs.DS 2015
Year: 2015

Redundancy identification is an important step of the design flow that typically follows logic synthesis and optimization. In addition to reducing circuit area, power consumption, and delay, redundancy removal also improves testability. All commercially available synthesis tools include a redundancy removal engine which is often run multiple times on the same netlist during optimization. This paper presents a fast heuristic algorithm for redundancy removal in combinational circuits. Our idea is to provide a quick partial solution which can be used for the intermediate redundancy removal runs instead of exact ATPG or SAT-based approaches. The presented approach has a higher implication power than the traditional heuristic algorithms, such as FIRE, e.g. on average it removes 37% more redundancies than FIRE with no penalty in runtime.
A novel pLSA based Traffic Signs Classification System
Venue: arXiv cs.CV 2015
Year: 2015

In this work we developed a novel and fast traffic sign recognition system, a very important part for advanced driver assistance system and for autonomous driving. Traffic signs play a very vital role in safe driving and avoiding accident. We have used image processing and topic discovery model pLSA to tackle this challenging multiclass classification problem. Our algorithm is consist of two parts, shape classification and sign classification for improved accuracy. For processing and representation of image we have used bag of features model with SIFT local descriptor. Where a visual vocabulary of size 300 words are formed using k-means codebook formation algorithm. We exploited the concept that every image is a collection of visual topics and images having same topics will belong to same category. Our algorithm is tested on German traffic sign recognition benchmark (GTSRB) and gives very promising result near to existing state of the art techniques.
Video-Based Action Recognition Using Rate-Invariant Analysis of Covariance Trajectories
Venue: arXiv cs.CV 2015
Year: 2015

Statistical classification of actions in videos is mostly performed by extracting relevant features, particularly covariance features, from image frames and studying time series associated with temporal evolutions of these features. A natural mathematical representation of activity videos is in form of parameterized trajectories on the covariance manifold, i.e. the set of symmetric, positive-definite matrices (SPDMs). The variable execution-rates of actions implies variable parameterizations of the resulting trajectories, and complicates their classification. Since action classes are invariant to execution rates, one requires rate-invariant metrics for comparing trajectories. A recent paper represented trajectories using their transported square-root vector fields (TSRVFs), defined by parallel translating scaled-velocity vectors of trajectories to a reference tangent space on the manifold. To avoid arbitrariness of selecting the reference and to reduce distortion introduced during this mapping, we develop a purely intrinsic approach where SPDM trajectories are represented by redefining their TSRVFs at the starting points of the trajectories, and analyzed as elements of a vector bundle on the manifold. Using a natural Riemannain metric on vector bundles of SPDMs, we compute geodesic paths and geodesic distances between trajectories in the quotient space of this vector bundle, with respect to the re-parameterization group. This makes the resulting comparison of trajectories invariant to their re-parameterization. We demonstrate this framework on two applications involving video classification: visual speech recognition or lip-reading and hand-gesture recognition. In both cases we achieve results either comparable to or better than the current literature.
Sampled-Data Consensus over Random Networks
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers the consensus problem for a network of nodes with random interactions and sampled-data control actions. We first show that consensus in expectation, in mean square, and almost surely are equivalent for a general random network model when the inter-sampling interval and network size satisfy a simple relation. The three types of consensus are shown to be simultaneously achieved over an independent or a Markovian random network defined on an underlying graph with a directed spanning tree. For both independent and Markovian random network models, necessary and sufficient conditions for mean-square consensus are derived in terms of the spectral radius of the corresponding state transition matrix. These conditions are then interpreted as the existence of critical value on the inter-sampling interval, below which global mean-square consensus is achieved and above which the system diverges in mean-square sense for some initial states. Finally, we establish an upper bound on the inter-sampling interval below which almost sure consensus is reached, and a lower bound on the inter-sampling interval above which almost sure divergence is reached. Some numerical simulations are given to validate the theoretical results and some discussions on the critical value of the inter-sampling intervals for the mean-square consensus are provided.
Online classifier adaptation for cost-sensitive learning
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we propose the problem of online cost-sensitive clas- sifier adaptation and the first algorithm to solve it. We assume we have a base classifier for a cost-sensitive classification problem, but it is trained with respect to a cost setting different to the desired one. Moreover, we also have some training data samples streaming to the algorithm one by one. The prob- lem is to adapt the given base classifier to the desired cost setting using the steaming training samples online. To solve this problem, we propose to learn a new classifier by adding an adaptation function to the base classifier, and update the adaptation function parameter according to the streaming data samples. Given a input data sample and the cost of misclassifying it, we up- date the adaptation function parameter by minimizing cost weighted hinge loss and respecting previous learned parameter simultaneously. The proposed algorithm is compared to both online and off-line cost-sensitive algorithms on two cost-sensitive classification problems, and the experiments show that it not only outperforms them one classification performances, but also requires significantly less running time.
Assembling thefacebook: Using heterogeneity to understand online social network assembly
Venue: arXiv cs.SI 2015
Year: 2015

Online social networks represent a popular and diverse class of social media systems. Despite this variety, each of these systems undergoes a general process of online social network assembly, which represents the complicated and heterogeneous changes that transform newly born systems into mature platforms. However, little is known about this process. For example, how much of a network's assembly is driven by simple growth? How does a network's structure change as it matures? How does network structure vary with adoption rates and user heterogeneity, and do these properties play different roles at different points in the assembly? We investigate these and other questions using a unique dataset of online connections among the roughly one million users at the first 100 colleges admitted to Facebook, captured just 20 months after its launch. We first show that different vintages and adoption rates across this population of networks reveal temporal dynamics of the assembly process, and that assembly is only loosely related to network growth. We then exploit natural experiments embedded in this dataset and complementary data obtained via Internet archaeology to show that different subnetworks matured at different rates toward similar end states. These results shed light on the processes and patterns of online social network assembly, and may facilitate more effective design for online social systems.
Massive MIMO as a Big Data System: Random Matrix Models and Testbed
Venue: arXiv cs.IT 2015
Year: 2015

The paper has two parts. The first one deals with how to use large random matrices as building blocks to model the massive data arising from the massive (or large-scale) MIMO system. As a result, we apply this model for distributed spectrum sensing and network monitoring. The part boils down to the streaming, distributed massive data, for which a new algorithm is obtained and its performance is derived using the central limit theorem that is recently obtained in the literature. The second part deals with the large-scale testbed using software-defined radios (particularly USRP) that takes us more than four years to develop this 70-node network testbed. To demonstrate the power of the software defined radio, we reconfigure our testbed quickly into a testbed for massive MIMO. The massive data of this testbed is of central interest in this paper. It is for the first time for us to model the experimental data arising from this testbed. To our best knowledge, we are not aware of other similar work.
Loop-Free Backpressure Routing Using Link-Reversal Algorithms
Venue: arXiv cs.NI 2015
Year: 2015

The backpressure routing policy is known to be a throughput optimal policy that supports any feasible traffic demand in data networks, but may have poor delay performance when packets traverse loops in the network. In this paper, we study loop-free backpressure routing policies that forward packets along directed acyclic graphs (DAGs) to avoid the looping problem. These policies use link reversal algorithms to improve the DAGs in order to support any achievable traffic demand. For a network with a single commodity, we show that a DAG that supports a given traffic demand can be found after a finite number of iterations of the link-reversal process. We use this to develop a joint link-reversal and backpressure routing policy, called the loop free backpressure (LFBP) algorithm. This algorithm forwards packets on the DAG, while the DAG is dynamically updated based on the growth of the queue backlogs. We show by simulations that such a DAG-based policy improves the delay over the classical backpressure routing policy. We also propose a multicommodity version of the LFBP algorithm, and via simulation we show that its delay performance is better than that of backpressure.
Unsupervised Video Analysis Based on a Spatiotemporal Saliency Detector
Venue: arXiv cs.CV 2015
Year: 2015

Visual saliency, which predicts regions in the field of view that draw the most visual attention, has attracted a lot of interest from researchers. It has already been used in several vision tasks, e.g., image classification, object detection, foreground segmentation. Recently, the spectrum analysis based visual saliency approach has attracted a lot of interest due to its simplicity and good performance, where the phase information of the image is used to construct the saliency map. In this paper, we propose a new approach for detecting spatiotemporal visual saliency based on the phase spectrum of the videos, which is easy to implement and computationally efficient. With the proposed algorithm, we also study how the spatiotemporal saliency can be used in two important vision task, abnormality detection and spatiotemporal interest point detection. The proposed algorithm is evaluated on several commonly used datasets with comparison to the state-of-art methods from the literature. The experiments demonstrate the effectiveness of the proposed approach to spatiotemporal visual saliency detection and its application to the above vision tasks
Straight Line Triangle Representations
Venue: arXiv cs.CG 2015
Year: 2015

A straight line triangle representation (SLTR) of a planar graph is a straight line drawing such that all the faces including the outer face have triangular shape. Such a drawing can be viewed as a tiling of a triangle using triangles with the input graph as skeletal structure. In this paper we present a characterization of graphs that have an SLTR. The characterization is based on flat angle assignments, i.e., selections of angles of the graph that have size~$π$ in the representation. We also provide a second characterization in terms of contact systems of pseudosegments. With the aid of discrete harmonic functions we show that contact systems of pseudosegments that respect certain conditions are stretchable. The stretching procedure is then used to get straight line triangle representations. Since the discrete harmonic function approach is quite flexible it allows further applications, we mention some of them. The drawback of the characterization of SLTRs is that we are not able to effectively check whether a given graph admits a flat angle assignment that fulfills the conditions. Hence it is still open to decide whether the recognition of graphs that admit straight line triangle representation is polynomially tractable.
Slime Mould Inspired Generalised Voronoi Diagrams with Repulsive Fields
Venue: arXiv cs.ET 2015
Year: 2015

The giant single-celled amoeboid organism Physarum polycephalum constructs minimising transport networks but can also approximate the Voronoi diagram using two different mechanisms. In the first method Voronoi bisectors are rep- resented by deformation of a pre-existing plasmodial network by repellent sources acting as generating points. In the second method generating points act as inoculation sites for grow- ing plasmodia and Voronoi bisectors are represented by vacant regions before the plasmodia fuse. To explore the behaviour of minimising networks in the presence of repulsion fields we utilise a computational model of Physarum as a distributed virtual computing material. We characterise the different types of computational behaviours elicited by attraction and repulsion stimuli and demonstrate the approximation Voronoi diagrams using growth towards attractants, avoidance of repellents, and combinations of both. Approximation of Voronoi diagrams for point data sources, complex planar shapes and circle sets is demonstrated. By altering repellent con- centration we found that partition of data sources was maintained but the internal network connectivity was minimised by the contractile force of the transport network. To conclude, we find that the repertoire of unconventional computation methods is enhanced by the addition of stimuli presented by repellent fields, suggesting novel approaches to plane-division, packing, and minimisation problems.
Online Monaural Speech Enhancement Based on Periodicity Analysis and A Priori SNR Estimation
Venue: arXiv cs.SD 2015
Year: 2015

This paper describes an online algorithm for enhancing monaural noisy speech. Firstly, a novel phase-corrected low-delay gammatone filterbank is derived for signal subband decomposition and resynthesis; the subband signals are then analyzed frame by frame. Secondly, a novel feature named periodicity degree (PD) is proposed to be used for detecting and estimating the fundamental period (P0) in each frame and for estimating the signal-to-noise ratio (SNR) in each frame-subband signal unit. The PD is calculated in each unit as the multiplication of the normalized autocorrelation and the comb filter ratio, and shown to be robust in various low-SNR conditions. Thirdly, the noise energy level in each signal unit is estimated recursively based on the estimated SNR for units with high PD and based on the noisy signal energy level for units with low PD. Then the a priori SNR is estimated using a decision-directed approach with the estimated noise level. Finally, a revised Wiener gain is calculated, smoothed, and applied to each unit; the processed units are summed across subbands and frames to form the enhanced signal. The P0 detection accuracy of the algorithm was evaluated on two corpora and showed comparable performance on one corpus and better performance on the other corpus when compared to a recently published pitch detection algorithm. The speech enhancement effect of the algorithm was evaluated on one corpus with two objective criteria and showed better performance in one highly non-stationary noise and comparable performance in two other noises when compared to a state-of-the-art statistical-model based algorithm.
Property-based Polynomial Invariant Generation using Sums-of-Squares Optimization
Venue: arXiv cs.LO 2015
Year: 2015

While abstract interpretation is not theoretically restricted to specific kinds of properties, it is, in practice, mainly developed to compute linear over-approximations of reachable sets, aka. the collecting semantics of the program. The verification of user-provided properties is not easily compatible with the usual forward fixpoint computation using numerical abstract domains. We propose here to rely on sums-of-squares programming to characterize a property-driven polynomial invariant. This invariant generation can be guided by either boundedness, or in contrary, a given zone of the state space to avoid. While the target property is not necessarily inductive with respect to the program semantics, our method identifies a stronger inductive polynomial invariant using numerical optimization. Our method applies to a wide set of programs: a main while loop composed of a disjunction (if-then-else) of polynomial updates e.g. piecewise polynomial controllers. It has been evaluated on various programs.
A QoS aware Novel Probabilistic strategy for Dynamic Resource Allocation
Venue: arXiv cs.DC 2015
Year: 2015

The paper proposes a two player game based strategy for resource allocation in service computing domain such as cloud, grid etc. The players are modeled as demand/workflows for the resource and represent multiple types of qualitative and quantitative factors. The proposed strategy will classify them in two classes. The proposed system would forecast outcome using a priori information available and measure/estimate existing parameters such as utilization and delay in an optimal load-balanced paradigm. Keywords: Load balancing; service computing; Logistic Regression; probabilistic estimation
Cost-Optimal Switching Protection Strategy in Adaptive Networks
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we study a model of network adaptation mechanism to control spreading processes over switching contact networks, called adaptive susceptible-infected-susceptible model. The edges in the network model are randomly removed or added depending on the risk of spread through them. By analyzing the joint evolution of the spreading dynamics "in the network" and the structural dynamics "of the network", we derive conditions on the adaptation law to control the dynamics of the spread in the resulting switching network. In contrast with the results in the literature, we allow the initial topology of the network to be an arbitrary graph. Furthermore, assuming there is a cost associated to switching edges in the network, we propose an optimization framework to find the cost-optimal network adaptation law, i.e., the cost-optimal edge switching probabilities. Under certain conditions on the switching costs, we show that the optimal adaptation law can be found using convex optimization. We illustrate our results with numerical simulations.
Computational methods for stochastic control with metric interval temporal logic specifications
Venue: arXiv cs.SY 2015
Year: 2015

This paper studies an optimal control problem for continuous-time stochastic systems subject to reachability objectives specified in a subclass of metric interval temporal logic specifications, a temporal logic with real-time constraints. We propose a probabilistic method for synthesizing an optimal control policy that maximizes the probability of satisfying a specification based on a discrete approximation of the underlying stochastic system. First, we show that the original problem can be formulated as a stochastic optimal control problem in a state space augmented with finite memory and states of some clock variables. Second, we present a numerical method for computing an optimal policy with which the given specification is satisfied with the maximal probability in point-based semantics in the discrete approximation of the underlying system. We show that the policy obtained in the discrete approximation converges to the optimal one for satisfying the specification in the continuous or dense-time semantics as the discretization becomes finer in both state and time. Finally, we illustrate our approach with a robotic motion planning example.
A Rule-Based Short Query Intent Identification System
Venue: arXiv cs.IR 2015
Year: 2015

Using SMS (Short Message System), cell phones can be used to query for information about various topics. In an SMS based search system, one of the key problems is to identify a domain (broad topic) associated with the user query; so that a more comprehensive search can be carried out by the domain specific search engine. In this paper we use a rule based approach, to identify the domain, called Short Query Intent Identification System (SQIIS). We construct two different rule-bases using different strategies to suit query intent identification. We evaluate the two rule-bases experimentally.
Mixed polarity reversible Peres gates
Venue: arXiv cs.ET 2015
Year: 2015

Reversible Peres gates with more than two all over binary-valued control signals are discussed. Methods are disclosed for the low cost realization of this kind of Peres gates without requiring ancillary lines. Proper distribution of the controlled gates and their inverses allow driving the reversible Peres gate with control signals of different polarities.
Sum Secrecy Rate in MISO Full-Duplex Wiretap Channel with Imperfect CSI
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the achievable sum secrecy rate in MISO (multiple-input-single-output) {\em full-duplex} wiretap channel in the presence of a passive eavesdropper and imperfect channel state information (CSI). We assume that the users participating in full-duplex communication have multiple transmit antennas, and that the users and the eavesdropper have single receive antenna each. The users have individual transmit power constraints. They also transmit jamming signals to improve the secrecy rates. We obtain the achievable perfect secrecy rate region by maximizing the worst case sum secrecy rate. We also obtain the corresponding transmit covariance matrices associated with the message signals and the jamming signals. Numerical results that show the impact of imperfect CSI on the achievable secrecy rate region are presented.
Automated Verification Of Role-Based Access Control Policies Constraints Using Prover9
Venue: arXiv cs.CR 2015
Year: 2015

Access control policies are used to restrict access to sensitive records for authorized users only. One approach for specifying policies is using role based access control (RBAC) where authorization is given to roles instead of users. Users are assigned to roles such that each user can access all the records that are allowed to his/her role. RBAC has a great interest because of its flexibility. One issue in RBAC is dealing with constraints. Usually, policies should satisfy pre-defined constraints as for example separation of duty (SOD) which states that users are not allowed to play two conflicting roles. Verifying the satisfiability of constraints based on policies is time consuming and may lead to errors. Therefore, an automated verification is essential. In this paper, we propose a theory for specifying policies and constraints in first order logic. Furthermore, we present a comprehensive list of constraints. We identity constraints based on the relation between users and roles, between roles and permission on records, between users and permission on records, and between users, roles, and permission on records. Then, we use a general purpose theorem prover tool called Prover9 for proving the satisfaction of constraints.