OpenRaiser/Intern-Atlas huggingface dataset:
Detecting Superbubbles in Assembly Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We introduce a new concept of a subgraph class called a superbubble for analyzing assembly graphs, and propose an efficient algorithm for detecting it. Most assembly algorithms utilize assembly graphs like the de Bruijn graph or the overlap graph constructed from reads. From these graphs, many assembly algorithms first detect simple local graph structures (motifs), such as tips and bubbles, mainly to find sequencing errors. These motifs are easy to detect, but they are sometimes too simple to deal with more complex errors. The superbubble is an extension of the bubble, which is also important for analyzing assembly graphs. Though superbubbles are much more complex than ordinary bubbles, we show that they can be efficiently enumerated. We propose an average-case linear time algorithm (i.e., O(n+m) for a graph with n vertices and m edges) for graphs with a reasonable model, though the worst-case time complexity of our algorithm is quadratic (i.e., O(n(n+m))). Moreover, the algorithm is practically very fast: Our experiments show that our algorithm runs in reasonable time with a single CPU core even against a very large graph of a whole human genome.
Sharp Threshold for Multivariate Multi-Response Linear Regression via Block Regularized Lasso
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we investigate a multivariate multi-response (MVMR) linear regression problem, which contains multiple linear regression models with differently distributed design matrices, and different regression and output vectors. The goal is to recover the support union of all regression vectors using $l_1/l_2$-regularized Lasso. We characterize sufficient and necessary conditions on sample complexity \emph{as a sharp threshold} to guarantee successful recovery of the support union. Namely, if the sample size is above the threshold, then $l_1/l_2$-regularized Lasso correctly recovers the support union; and if the sample size is below the threshold, $l_1/l_2$-regularized Lasso fails to recover the support union. In particular, the threshold precisely captures the impact of the sparsity of regression vectors and the statistical properties of the design matrices on sample complexity. Therefore, the threshold function also captures the advantages of joint support union recovery using multi-task Lasso over individual support recovery using single-task Lasso.
Characterizing Data Analysis Workloads in Data Centers
Venue: arXiv cs.PF 2013
Year: 2013

As the amount of data explodes rapidly, more and more corporations are using data centers to make effective decisions and gain a competitive edge. Data analysis applications play a significant role in data centers, and hence it has became increasingly important to understand their behaviors in order to further improve the performance of data center computer systems. In this paper, after investigating three most important application domains in terms of page views and daily visitors, we choose eleven representative data analysis workloads and characterize their micro-architectural characteristics by using hardware performance counters, in order to understand the impacts and implications of data analysis workloads on the systems equipped with modern superscalar out-of-order processors. Our study on the workloads reveals that data analysis applications share many inherent characteristics, which place them in a different class from desktop (SPEC CPU2006), HPC (HPCC), and service workloads, including traditional server workloads (SPECweb2005) and scale-out service workloads (four among six benchmarks in CloudSuite), and accordingly we give several recommendations for architecture and system optimizations. On the basis of our workload characterization work, we released a benchmark suite named DCBench for typical datacenter workloads, including data analysis and service workloads, with an open-source license on our project home page on http://prof.ict.ac.cn/DCBench. We hope that DCBench is helpful for performing architecture and small-to-medium scale system researches for datacenter computing.
Towards Minimax Online Learning with Unknown Time Horizon
Venue: arXiv cs.LG 2013
Year: 2013

We consider online learning when the time horizon is unknown. We apply a minimax analysis, beginning with the fixed horizon case, and then moving on to two unknown-horizon settings, one that assumes the horizon is chosen randomly according to some known distribution, and the other which allows the adversary full control over the horizon. For the random horizon setting with restricted losses, we derive a fully optimal minimax algorithm. And for the adversarial horizon setting, we prove a nontrivial lower bound which shows that the adversary obtains strictly more power than when the horizon is fixed and known. Based on the minimax solution of the random horizon setting, we then propose a new adaptive algorithm which "pretends" that the horizon is drawn from a distribution from a special family, but no matter how the actual horizon is chosen, the worst-case regret is of the optimal rate. Furthermore, our algorithm can be combined and applied in many ways, for instance, to online convex optimization, follow the perturbed leader, exponential weights algorithm and first order bounds. Experiments show that our algorithm outperforms many other existing algorithms in an online linear optimization setting.
Sensing as a Service Model for Smart Cities Supported by Internet of Things
Venue: arXiv cs.CY 2013
Year: 2013

The world population is growing at a rapid pace. Towns and cities are accommodating half of the world's population thereby creating tremendous pressure on every aspect of urban living. Cities are known to have large concentration of resources and facilities. Such environments attract people from rural areas. However, unprecedented attraction has now become an overwhelming issue for city governance and politics. The enormous pressure towards efficient city management has triggered various Smart City initiatives by both government and private sector businesses to invest in ICT to find sustainable solutions to the growing issues. The Internet of Things (IoT) has also gained significant attention over the past decade. IoT envisions to connect billions of sensors to the Internet and expects to use them for efficient and effective resource management in Smart Cities. Today infrastructure, platforms, and software applications are offered as services using cloud technologies. In this paper, we explore the concept of sensing as a service and how it fits with the Internet of Things. Our objective is to investigate the concept of sensing as a service model in technological, economical, and social perspectives and identify the major open challenges and issues.
Technical Report: An MGF-based Unified Framework to Determine the Joint Statistics of Partial Sums of Ordered i.n.d. Random Variables
Venue: arXiv cs.IT 2013
Year: 2013

The joint statistics of partial sums of ordered random variables (RVs) are often needed for the accurate performance characterization of a wide variety of wireless communication systems. A unified analytical framework to determine the joint statistics of partial sums of ordered independent and identically distributed (i.i.d.) random variables was recently presented. However, the identical distribution assumption may not be valid in several real-world applications. With this motivation in mind, we consider in this paper the more general case in which the random variables are independent but not necessarily identically distributed (i.n.d.). More specifically, we extend the previous analysis and introduce a new more general unified analytical framework to determine the joint statistics of partial sums of ordered i.n.d. RVs. Our mathematical formalism is illustrated with an application on the exact performance analysis of the capture probability of generalized selection combining (GSC)-based RAKE receivers operating over frequency-selective fading channels with a non-uniform power delay profile. We also discussed a couple of other sample applications of the generic results presented in this work.
Formal Probabilistic Analysis of a Wireless Sensor Network for Forest Fire Detection
Venue: arXiv cs.LO 2013
Year: 2013

Wireless Sensor Networks (WSNs) have been widely explored for forest fire detection, which is considered a fatal threat throughout the world. Energy conservation of sensor nodes is one of the biggest challenges in this context and random scheduling is frequently applied to overcome that. The performance analysis of these random scheduling approaches is traditionally done by paper-and-pencil proof methods or simulation. These traditional techniques cannot ascertain 100% accuracy, and thus are not suitable for analyzing a safety-critical application like forest fire detection using WSNs. In this paper, we propose to overcome this limitation by applying formal probabilistic analysis using theorem proving to verify scheduling performance of a real-world WSN for forest fire detection using a k-set randomized algorithm as an energy saving mechanism. In particular, we formally verify the expected values of coverage intensity, the upper bound on the total number of disjoint subsets, for a given coverage intensity, and the lower bound on the total number of nodes.
Formal verification of a proof procedure for the description logic ALC
Venue: arXiv cs.LO 2013
Year: 2013

Description Logics (DLs) are a family of languages used for the representation and reasoning on the knowledge of an application domain, in a structured and formal manner. In order to achieve this objective, several provers, such as RACER and FaCT++, have been implemented, but these provers themselves have not been yet certified. In order to ensure the soundness of derivations in these DLs, it is necessary to formally verify the deductions applied by these reasoners. Formal methods offer powerful tools for the specification and verification of proof procedures, among them there are methods for proving properties such as soundness, completeness and termination of a proof procedure. In this paper, we present the definition of a proof procedure for the Description Logic ALC, based on a semantic tableau method. We ensure validity of our prover by proving its soundness, completeness and termination properties using Isabelle proof assistant. The proof proceeds in two phases, first by establishing these properties on an abstract level, and then by instantiating them for an implementation based on lists.
Multi-Version Conflict Notion
Venue: arXiv cs.DC 2013
Year: 2013

This paper introduces the useful notion of Multi-Version Conflict notion.
SDN-like: The Next Generation of Pub/Sub
Venue: arXiv cs.NI 2013
Year: 2013

Software-Defined Networking (SDN) has raised the boundaries of cloud computing by offering unparalleled levels of control and flexibility to system administrators over their virtualized environments. To properly embrace this new era of SDN-driven network architectures, the research community must not only consider the impact of SDN over the protocol stack, but also on its overlying networked applications. In this big ideas paper, we study the impact of SDN on the design of future message-oriented middleware, specifically pub/sub systems. We argue that key concepts put forth by SDN can be applied in a meaningful fashion to the next generation of pub/sub systems. First, pub/sub can adopt a logically centralized controller model for maintenance, monitoring, and control of the overlay network. We establish a parallel with existing work on centralized pub/sub routing and discuss how the logically centralized controller model can be implemented in a distributed manner. Second, we investigate the separation of the control and data plane, which is integral to SDN, which can be adopted to raise the level of decoupling in pub/sub. We introduce a new model of pub/sub which separates the traditional publisher and subscriber roles into flow regulators and producer/consumers of data. We then present use cases that benefit from this approach and study the impact of decoupling for performance.
An Improved Parameterized Algorithm for the Independent Feedback Vertex Set Problem
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we develop a new parameterized algorithm for the {\sc Independent Feedback Vertex Set} (IFVS) problem. Given a graph $G=(V,E)$, the goal of the problem is to determine whether there exists a vertex subset $F\subseteq V$ such that $V-F$ induces a forest in $G$ and $F$ is an independent set. We show that there exists a parameterized algorithm that can determine whether a graph contains an IFVS of size $k$ or not in time $O(4^kn^{2})$. To our best knowledge, this result improves the known upper bound for this problem, which is $O^{*}(5^{k}n^{O(1)})$.
Near-optimal phase retrieval of sparse vectors
Venue: arXiv cs.IT 2013
Year: 2013

In many areas of imaging science, it is difficult to measure the phase of linear measurements. As such, one often wishes to reconstruct a signal from intensity measurements, that is, perform phase retrieval. In several applications the signal in question is believed to be sparse. In this paper, we use ideas from the recently developed polarization method for phase retrieval and provide an algorithm that is guaranteed to recover a sparse signal from a number of phaseless linear measurements that scales linearly with the sparsity of the signal (up to logarithmic factors). This is particularly remarkable since it is known that a certain popular class of convex methods is not able to perform recovery unless the number of measurements scales with the square of the sparsity of the signal. This is a shorter version of a more complete publication that will appear elsewhere.
Learning Robust Subspace Clustering
Venue: arXiv cs.CV 2013
Year: 2013

We propose a low-rank transformation-learning framework to robustify subspace clustering. Many high-dimensional data, such as face images and motion sequences, lie in a union of low-dimensional subspaces. The subspace clustering problem has been extensively studied in the literature to partition such high-dimensional data into clusters corresponding to their underlying low-dimensional subspaces. However, low-dimensional intrinsic structures are often violated for real-world observations, as they can be corrupted by errors or deviate from ideal models. We propose to address this by learning a linear transformation on subspaces using matrix rank, via its convex surrogate nuclear norm, as the optimization criteria. The learned linear transformation restores a low-rank structure for data from the same subspace, and, at the same time, forces a high-rank structure for data from different subspaces. In this way, we reduce variations within the subspaces, and increase separations between the subspaces for more accurate subspace clustering. This proposed learned robust subspace clustering framework significantly enhances the performance of existing subspace clustering methods. To exploit the low-rank structures of the transformed subspaces, we further introduce a subspace clustering technique, called Robust Sparse Subspace Clustering, which efficiently combines robust PCA with sparse modeling. We also discuss the online learning of the transformation, and learning of the transformation while simultaneously reducing the data dimensionality. Extensive experiments using public datasets are presented, showing that the proposed approach significantly outperforms state-of-the-art subspace clustering methods.
Domain-invariant Face Recognition using Learned Low-rank Transformation
Venue: arXiv cs.CV 2013
Year: 2013

We present a low-rank transformation approach to compensate for face variations due to changes in visual domains, such as pose and illumination. The key idea is to learn discriminative linear transformations for face images using matrix rank as the optimization criteria. The learned linear transformations restore a shared low-rank structure for faces from the same subject, and, at the same time, force a high-rank structure for faces from different subjects. In this way, among the transformed faces, we reduce variations caused by domain changes within the classes, and increase separations between the classes for better face recognition across domains. Extensive experiments using public datasets are presented to demonstrate the effectiveness of our approach for face recognition across domains. The potential of the approach for feature extraction in generic object recognition and coded aperture design are discussed as well.
Sparse arrays of signatures for online character recognition
Venue: arXiv cs.CV 2013
Year: 2013

In mathematics the signature of a path is a collection of iterated integrals, commonly used for solving differential equations. We show that the path signature, used as a set of features for consumption by a convolutional neural network (CNN), improves the accuracy of online character recognition---that is the task of reading characters represented as a collection of paths. Using datasets of letters, numbers, Assamese and Chinese characters, we show that the first, second, and even the third iterated integrals contain useful information for consumption by a CNN. On the CASIA-OLHWDB1.1 3755 Chinese character dataset, our approach gave a test error of 3.58%, compared with 5.61% for a traditional CNN [Ciresan et al.]. A CNN trained on the CASIA-OLHWDB1.0-1.2 datasets won the ICDAR2013 Online Isolated Chinese Character recognition competition. Computationally, we have developed a sparse CNN implementation that make it practical to train CNNs with many layers of max-pooling. Extending the MNIST dataset by translations, our sparse CNN gets a test error of 0.31%.
A New 3D Geometric Approach to Focus and Context Lens Effect Simulation
Venue: arXiv cs.GR 2013
Year: 2013

We present a novel methodology based on geometric approach to simulate magnification lens effects. Our aim is to promote new applications of powerful geometric modeling techniques in visual computing. Conventional image processing/visualization methods are computed in two dimensional space (2D). We examine this conventional 2D manipulation from a completely innovative perspective of 3D geometric processing. Compared with conventional optical lens design, 3D geometric method are much more capable of preserving shape features and minimizing distortion. We magnify an area of interest to better visualize the interior details, while keeping the rest of area without perceivable distortion. We flatten the mesh back into 2D space for viewing, and further applications in the screen space. In both steps, we devise an iterative deformation scheme to minimize distortion around both focus and context region, while avoiding the noncontinuous transition region between the focus and context areas. Particularly, our method allows the user to flexibly modify the ROI shapes to accommodate complex feature. The user can also easily specify a spectrum of metrics for different visual effects. Various experimental results demonstrate the effectiveness, robustness, and efficiency of our framework.
Improved Watermarking Scheme Using Discrete Cosine Transform and Schur Decomposition
Venue: arXiv cs.MM 2013
Year: 2013

Watermarking is a technique which consists in introducing a brand, the name or the logo of the author, in an image in order to protect it against illegal copy. The capacity of the existing watermark channel is often limited. We propose in this paper a new robust method which consists in adding the triangular matrix of the mark obtained after the Schur decomposition to the DCT transform of the host image. The unitary matrix acts as secret key for the extraction of the mark. Unlike most watermarking algorithms, the host image and the mark have the same size. The results show that our method is robust against attack techniques as : JPEG compression, colors reducing, adding noise, filtering, cropping, low rotations, and histogram spreading.
New RIC Bounds via l_q-minimization with 0<q<=1 in Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

The restricted isometry constants (RICs) play an important role in exact recovery theory of sparse signals via l_q(0<q<=1) relaxations in compressed sensing. Recently, Cai and Zhang[6] have achieved a sharp bound δ_tk<\sqrt{1-1/t} for t>=4/3 to guarantee the exact recovery of k sparse signals through the l_1 minimization. This paper aims to establish new RICs bounds via l_q(0<q<=1) relaxation. Based on a key inequality on l_q norm, we show that (i) the exact recovery can be succeeded via l_{1/2} and l_1 minimizations if δ_tk<\sqrt{1-1/t} for any t>1, (ii)several sufficient conditions can be derived, such as for any 0<q<1/2, δ_2k<0.5547 when k>=2, for any 1/2<q<1, δ_2k<0.6782 when k>=1, (iii) the bound on δ_k is given as well for any 0<q<=1, especially for q=1/2,1, we obtain δ_k<1/3 when k(>=2) is even or δ_k<0.3203 when k(>=3) is odd.
The Effects Of Computerizing Banking Operations
Venue: arXiv cs.CY 2013
Year: 2013

Computerizing banking operation has a far-reaching consequences,both positively and negatively.But here,i have been able to deal with both effects and proffer solutions on the best way to go about computerizing banking operations.
Sparsely-Packetized Predictive Control by Orthogonal Matching Pursuit
Venue: arXiv cs.SY 2013
Year: 2013

We study packetized predictive control, known to be robust against packet dropouts in networked systems. To obtain sparse packets for rate-limited networks, we design control packets via an L0 optimization, which can be effectively solved by orthogonal matching pursuit. Our formulation ensures asymptotic stability of the control loop in the presence of bounded packet dropouts.
Towards realistic artificial benchmark for community detection algorithms evaluation
Venue: arXiv cs.SI 2013
Year: 2013

Assessing the partitioning performance of community detection algorithms is one of the most important issues in complex network analysis. Artificially generated networks are often used as benchmarks for this purpose. However, previous studies showed their level of realism have a significant effect on the algorithms performance. In this study, we adopt a thorough experimental approach to tackle this problem and investigate this effect. To assess the level of realism, we use consensual network topological properties. Based on the LFR method, the most realistic generative method to date, we propose two alternative random models to replace the Configuration Model originally used in this algorithm, in order to increase its realism. Experimental results show both modifications allow generating collections of community-structured artificial networks whose topological properties are closer to those encountered in real-world networks. Moreover, the results obtained with eleven popular community identification algorithms on these benchmarks show their performance decrease on more realistic networks.
New extremal binary self-dual codes of length 68 from quadratic residue codes over f_2+uf_2+u^2f_2
Venue: arXiv cs.IT 2013
Year: 2013

In this work, quadratic reside codes over the ring F2 +uF2 +u^2F2 with u^3 = u are considered. A duality and distance preserving Gray map from F2 + uF2 + u^2F2 to (F_2)^3 is defined. By using quadratic double circulant, quadratic bordered double circulant constructions and their extensions self- dual codes of different lengths are obtained. As Gray images of these codes and their extensions, a substantial number of new extremal self-dual binary codes are found. More precisely, thirty two new extremal binary self-dual codes of length 68, 363 Type I codes of parameters [72; 36; 12], a Type II [72; 36; 12] code and a Type II [96; 48; 16] code with new weight enumerators are obtained through these constructions. The results are tabulated.