OpenRaiser/Intern-Atlas huggingface dataset:
Stratos: A Network-Aware Orchestration Layer for Virtual Middleboxes in Clouds
Venue: arXiv cs.NI 2014
Year: 2014

Enterprises want their in-cloud services to leverage the performance and security benefits that middleboxes offer in traditional deployments. Such virtualized deployments create new opportunities (e.g., flexible scaling) as well as new challenges (e.g., dynamics, multiplexing) for middlebox management tasks such as service composition and provisioning. Unfortunately, enterprises lack systematic tools to efficiently compose and provision in-the-cloud middleboxes and thus fall short of achieving the benefits that cloud-based deployments can offer. To this end, we present the design and implementation of Stratos, an orchestration layer for virtual middleboxes. Stratos provides efficient and correct composition in the presence of dynamic scaling via software-defined networking mechanisms. It ensures efficient and scalable provisioning by combining middlebox-specific traffic engineering, placement, and horizontal scaling strategies. We demonstrate the effectiveness of Stratos using an experimental prototype testbed and large-scale simulations.
An insight into the importance of national university rankings in an international context: The case of the I-UGR Rankings of Spanish universities
Venue: arXiv cs.DL 2014
Year: 2014

The great importance international rankings have achieved in the research policy arena warns against many threats consequence of the flaws and shortcomings these tools present. One of them has to do with the inability to accurately represent national university systems as their original purpose is only to rank world-class universities. Another one has to do with the lack of representativeness of universities' disciplinary profiles as they usually provide a unique table. Although some rankings offer a great coverage and others offer league tables by fields, no international ranking does both. In order to surpass such limitation from a research policy viewpoint, this paper analyzes the possibility of using national rankings in order to complement international rankings. For this, we analyze the Spanish university system as a study case presenting the I-UGR Rankings for Spanish universities by fields and subfields. Then, we compare their results with those obtained by the Shanghai Ranking, the QS Ranking, the Leiden Ranking and the NTU Ranking, as they all have basic common grounds which allow such comparison. We conclude that it is advisable to use national rankings in order to complement international rankings, however we observe that this must be done with certain caution as they differ on the methodology employed as well as on the construction of the fields.
Automated polyp detection in colon capsule endoscopy
Venue: arXiv cs.CV 2014
Year: 2014

Colorectal polyps are important precursors to colon cancer, a major health problem. Colon capsule endoscopy (CCE) is a safe and minimally invasive examination procedure, in which the images of the intestine are obtained via digital cameras on board of a small capsule ingested by a patient. The video sequence is then analyzed for the presence of polyps. We propose an algorithm that relieves the labor of a human operator analyzing the frames in the video sequence. The algorithm acts as a binary classifier, which labels the frame as either containing polyps or not, based on the geometrical analysis and the texture content of the frame. The geometrical analysis is based on a segmentation of an image with the help of a mid-pass filter. The features extracted by the segmentation procedure are classified according to an assumption that the polyps are characterized as protrusions that are mostly round in shape. Thus, we use a best fit ball radius as a decision parameter of a binary classifier. We present a statistical study of the performance of our approach on a data set containing over 18,900 frames from the endoscopic video sequences of five adult patients. The algorithm demonstrates a solid performance, achieving 47% sensitivity per frame and over 81% sensitivity per polyp at a specificity level of 90%. On average, with a video sequence length of 3747 frames, only 367 false positive frames need to be inspected by a human operator.
An Adaptive Statistical Non-uniform Quantizer for Detail Wavelet Components in Lossy JPEG2000 Image Compression
Venue: arXiv cs.MM 2014
Year: 2014

The paper presents a non-uniform quantization method for the Detail components in the JPEG2000 standard. Incorporating the fact that the coefficients lying towards the ends of the histogram plot of each Detail component represent the structural information of an image, the quantization step sizes become smaller at they approach the ends of the histogram plot. The variable quantization step sizes are determined by the actual statistics of the wavelet coefficients. Mean and standard deviation are the two statistical parameters used iteratively to obtain the variable step sizes. Moreover, the mean of the coefficients lying within the step size is chosen as the quantized value, contrary to the deadzone uniform quantizer which selects the midpoint of the quantization step size as the quantized value. The experimental results of the deadzone uniform quantizer and the proposed non-uniform quantizer are objectively compared by using Mean-Squared Error (MSE) and Mean Structural Similarity Index Measure (MSSIM), to evaluate the quantization error and reconstructed image quality, respectively. Subjective analysis of the reconstructed images is also carried out. Through the objective and subjective assessments, it is shown that the non-uniform quantizer performs better than the deadzone uniform quantizer in the perceptual quality of the reconstructed image, especially at low bitrates. More importantly, unlike the deadzone uniform quantizer, the non-uniform quantizer accomplishes better visual quality with a few quantized values.
Translating Relational Queries into Spreadsheets
Venue: arXiv cs.DB 2014
Year: 2014

Spreadsheets are among the most commonly used applications for data management and analysis. Perhaps they are even among the most widely used computer applications of all kinds. They combine in a natural and intuitive way data processing with very diverse supplementary features: statistical functions, visualization tools, pivot tables, pivot charts, linear programming solvers, Web queries periodically downloading data from external sources, etc. However, the spreadsheet paradigm of computation still lacks sufficient analysis. In this article we demonstrate that a spreadsheet can implement all data transformations definable in SQL, without any use of macros or built-in programming languages, merely by utilizing spreadsheet formulas. We provide a query compiler, which translates any given SQL query into a worksheet of the same semantics, including NULL values. Thereby database operations become available to the users who do not want to migrate to a database. They can define their queries using a high-level language and then get their execution plans in a plain vanilla spreadsheet. No sophisticated database system, no spreadsheet plugins or macros are needed. The functions available in spreadsheets impose severe limitations on the algorithms one can implement. In this paper we offer $O(n\log^2n)$ sorting spreadsheet, but using a non-constant number of rows, improving on the previously known $O(n^2)$ ones. It is therefore surprising, that a spreadsheet can implement, as we demonstrate, Depth-First-Search and Breadth-First-Search on graphs, thereby reaching beyond queries definable in SQL-92.
Corrupted Sensing: Novel Guarantees for Separating Structured Signals
Venue: arXiv cs.IT 2014
Year: 2014

We study the problem of corrupted sensing, a generalization of compressed sensing in which one aims to recover a signal from a collection of corrupted or unreliable measurements. While an arbitrary signal cannot be recovered in the face of arbitrary corruption, tractable recovery is possible when both signal and corruption are suitably structured. We quantify the relationship between signal recovery and two geometric measures of structure, the Gaussian complexity of a tangent cone and the Gaussian distance to a subdifferential. We take a convex programming approach to disentangling signal and corruption, analyzing both penalized programs that trade off between signal and corruption complexity, and constrained programs that bound the complexity of signal or corruption when prior information is available. In each case, we provide conditions for exact signal recovery from structured corruption and stable signal recovery from structured corruption with added unstructured noise. Our simulations demonstrate close agreement between our theoretical recovery bounds and the sharp phase transitions observed in practice. In addition, we provide new interpretable bounds for the Gaussian complexity of sparse vectors, block-sparse vectors, and low-rank matrices, which lead to sharper guarantees of recovery when combined with our results and those in the literature.
Applications of Compressed Sensing in Communications Networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper presents a tutorial for CS applications in communications networks. The Shannon's sampling theorem states that to recover a signal, the sampling rate must be as least the Nyquist rate. Compressed sensing (CS) is based on the surprising fact that to recover a signal that is sparse in certain representations, one can sample at the rate far below the Nyquist rate. Since its inception in 2006, CS attracted much interest in the research community and found wide-ranging applications from astronomy, biology, communications, image and video processing, medicine, to radar. CS also found successful applications in communications networks. CS was applied in the detection and estimation of wireless signals, source coding, multi-access channels, data collection in sensor networks, and network monitoring, etc. In many cases, CS was shown to bring performance gains on the order of 10X. We believe this is just the beginning of CS applications in communications networks, and the future will see even more fruitful applications of CS in our field.
Cancellation-Free Circuits in Unbounded and Bounded Depth
Venue: arXiv cs.CC 2014
Year: 2014

We study the notion of "cancellation-free" circuits. This is a restriction of linear Boolean circuits (XOR circuits), but can be considered as being equivalent to previously studied models of computation. The notion was coined by Boyar and Peralta in a study of heuristics for a particular circuit minimization problem. They asked how large a gap there can be between the smallest cancellation-free circuit and the smallest linear circuit. We show that the difference can be a factor $Ω(n/\log^{2}n)$. This improves on a recent result by Sergeev and Gashkov who have studied a similar problem. Furthermore, our proof holds for circuits of constant depth. We also study the complexity of computing the Sierpinski matrix using cancellation-free circuits and give a tight $Ω(n\log n)$ lower bound.
Abstracting Abstract Control (Extended)
Venue: arXiv cs.PL 2014
Year: 2014

The strength of a dynamic language is also its weakness: run-time flexibility comes at the cost of compile-time predictability. Many of the hallmarks of dynamic languages such as closures, continuations, various forms of reflection, and a lack of static types make many programmers rejoice, while compiler writers, tool developers, and verification engineers lament. The dynamism of these features simply confounds statically reasoning about programs that use them. Consequently, static analyses for dynamic languages are few, far between, and seldom sound. The "abstracting abstract machines" (AAM) approach to constructing static analyses has recently been proposed as a method to ameliorate the difficulty of designing analyses for such language features. The approach, so called because it derives a function for the sound and computable approximation of program behavior starting from the abstract machine semantics of a language, provides a viable approach to dynamic language analysis since all that is required is a machine description of the interpreter. The original AAM recipe produces finite state abstractions, which cannot faithfully represent an interpreter's control stack. Recent advances have shown that higher-order programs can be approximated with pushdown systems. However, these automata theoretic models either break down on features that inspect or modify the control stack. In this paper, we tackle the problem of bringing pushdown flow analysis to the domain of dynamic language features. We revise the abstracting abstract machines technique to target the stronger computational model of pushdown systems. In place of automata theory, we use only abstract machines and memoization. As case studies, we show the technique applies to a language with closures, garbage collection, stack-inspection, and first-class composable continuations.
Micropublications: a Semantic Model for Claims, Evidence, Arguments and Annotations in Biomedical Communications
Venue: arXiv cs.DL 2014
Year: 2014

The Micropublications semantic model for scientific claims, evidence, argumentation and annotation in biomedical publications, is a metadata model of scientific argumentation, designed to support several key requirements for exchange and value-addition of semantic metadata across the biomedical publications ecosystem. Micropublications allow formalizing the argument structure of scientific publications so that (a) their internal structure is semantically clear and computable; (b) citation networks can be easily constructed across large corpora; (c) statements can be formalized in multiple useful abstraction models; (d) statements in one work may cite statements in another, individually; (e) support, similarity and challenge of assertions can be modelled across corpora; (f) scientific assertions, particularly in review articles, may be transitively closed to supporting evidence and methods. The model supports natural language statements; data; methods and materials specifications; discussion and commentary; as well as challenge and disagreement. A detailed analysis of nine use cases is provided, along with an implementation in OWL 2 and SWRL, with several example instantiations in RDF.
An efficient parallel immersed boundary algorithm using a pseudo-compressible fluid solver
Venue: arXiv cs.DC 2014
Year: 2014

We propose an efficient algorithm for the immersed boundary method on distributed-memory architectures, with the computational complexity of a completely explicit method and excellent parallel scaling. The algorithm utilizes the pseudo-compressibility method recently proposed by Guermond and Minev [Comptes Rendus Mathematique, 348:581-585, 2010] that uses a directional splitting strategy to discretize the incompressible Navier-Stokes equations, thereby reducing the linear systems to a series of one-dimensional tridiagonal systems. We perform numerical simulations of several fluid-structure interaction problems in two and three dimensions and study the accuracy and convergence rates of the proposed algorithm. For these problems, we compare the proposed algorithm against other second-order projection-based fluid solvers. Lastly, the strong and weak scaling properties of the proposed algorithm are investigated.
A Review of Automated Formal Verification of Ad Hoc Routing Protocols for Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper surveys how formal verification can be used to prove the correctness of ad hoc routing protocols, which are fundamental infrastructure of wireless sensor networks. The existing techniques fall into two classes: verification on small-scale networks and verification on unbounded networks. The former one is always fully automatic and easy to use, thanks to the limited state space generated in verification. However, it cannot prove the correctness over all cases. The latter one can provide a complete proof based on abstractions of unbounded network. However, it usually needs user intervention and expertise in verification. The two kinds of technique are illustrated by verifications against some key properties such as stability, loop-freedom and deadlock-freedom. To conclude, they can be used to find faults and prove correctness, respectively. We believe that they can together aid the development of correct ad hoc routing protocols and their reliable implementations.
Learning-Based Adaptive Transmission for Limited Feedback Multiuser MIMO-OFDM
Venue: arXiv cs.IT 2014
Year: 2014

Performing link adaptation in a multiantenna and multiuser system is challenging because of the coupling between precoding, user selection, spatial mode selection and use of limited feedback about the channel. The problem is exacerbated by the difficulty of selecting the proper modulation and coding scheme when using orthogonal frequency division multiplexing (OFDM). This paper presents a data-driven approach to link adaptation for multiuser multiple input mulitple output (MIMO) OFDM systems. A machine learning classifier is used to select the modulation and coding scheme, taking as input the SNR values in the different subcarriers and spatial streams. A new approximation is developed to estimate the unknown interuser interference due to the use of limited feedback. This approximation allows to obtain SNR information at the transmitter with a minimum communication overhead. A greedy algorithm is used to perform spatial mode and user selection with affordable complexity, without resorting to an exhaustive search. The proposed adaptation is studied in the context of the IEEE 802.11ac standard, and is shown to schedule users and adjust the transmission parameters to the channel conditions as well as to the rate of the feedback channel.
LLAMA: Leveraging Learning to Automatically Manage Algorithms
Venue: arXiv cs.AI 2014
Year: 2014

Algorithm portfolio and selection approaches have achieved remarkable improvements over single solvers. However, the implementation of such systems is often highly customised and specific to the problem domain. This makes it difficult for researchers to explore different techniques for their specific problems. We present LLAMA, a modular and extensible toolkit implemented as an R package that facilitates the exploration of a range of different portfolio techniques on any problem domain. It implements the algorithm selection approaches most commonly used in the literature and leverages the extensive library of machine learning algorithms and techniques in R. We describe the current capabilities and limitations of the toolkit and illustrate its usage on a set of example SAT problems.
Contagious Sets in Expanders
Venue: arXiv cs.DM 2014
Year: 2014

We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least $r$ active neighbors, where $r>1$ is the activation threshold. A \emph{contagious set} is a set whose activation results with the entire graph being active. Given a graph $G$, let $m(G,r)$ be the minimal size of a contagious set. Computing $m(G,r)$ is NP-hard. It is known that for every $d$-regular or nearly $d$-regular graph on $n$ vertices, $m(G,r) \le O(\frac{nr}{d})$. We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion (e.g., $λ(G)=O(\sqrt{d})$, or girth $Ω(\log \log d)$) implies that $m(G,2) \le O(\frac{n}{d^2})$ (and more generally, $m(G,r) \le O(\frac{n}{d^{r/(r-1)}})$). Significantly weaker expansion properties suffice in order to imply that $m(G,2)\le O(\frac{n \log d}{d^2})$. For example, we show this for graphs of girth at least~7, and for graphs with $λ(G)<(1-ε)d$, provided the graph has no 4-cycles. Nearly $d$-regular expander graphs can be obtained by considering the binomial random graph $G(n,p)$ with $p \simeq \frac{d}{n}$ and $d > \log n$. For such graphs we prove that $Ω(\frac{n}{d^2 \log d}) \le m(G,2) \le O(\frac{n\log\log d}{d^2\log d})$ almost surely. Our results are algorithmic, entailing simple and efficient algorithms for selecting contagious sets.
Space-Efficient Parallel Algorithms for Combinatorial Search Problems
Venue: arXiv cs.DS 2014
Year: 2014

We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an $n$-node tree of height $h$ under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a $p$-processor distributed-memory machine. For backtrack search, we give a deterministic algorithm running in $O(n/p+h\log p)$ time, and a Las Vegas algorithm requiring optimal $O(n/p+h)$ time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in $O((n/p+h\log p \log n)h\log^2 n)$ time, with high probability. A remarkable feature of our algorithms is the use of only constant space per processor, which constitutes a significant improvement upon previous algorithms whose space requirements per processor depend on the (possibly huge) tree to be explored.
Spread Spectrum Codes for Continuous-Phase Modulated Systems
Venue: arXiv cs.IT 2014
Year: 2014

We study the theoretical performance of a combined approach to demodulation and decoding of binary continuous-phase modulated signals under repetition-like codes. This technique is motivated by a need to transmit packetized or framed data bursts in high noise regimes where many powerful, short-length codes are ineffective. In channels with strong noise, we mathematically study the asymptotic bit error rates of this combined approach and quantify the performance improvement over performing demodulation and decoding separately as the code rate increases. In this context, we also discuss a simple variant of repetition coding involving pseudorandom code words, based on direct-sequence spread spectrum methods, that preserves the spectral density of the encoded signal in order to maintain resistance to narrowband interference. We describe numerical simulations that demonstrate the advantages of this approach as an inner code which can be used underneath modern coding schemes in high noise environments.
Algorithms for distance problems in planar complexes of global nonpositive curvature
Venue: arXiv cs.CG 2014
Year: 2014

CAT(0) metric spaces and hyperbolic spaces play an important role in combinatorial and geometric group theory. In this paper, we present efficient algorithms for distance problems in CAT(0) planar complexes. First of all, we present an algorithm for answering single-point distance queries in a CAT(0) planar complex. Namely, we show that for a CAT(0) planar complex K with n vertices, one can construct in O(n^2 log n) time a data structure D of size O(n^2) so that, given a point x in K, the shortest path gamma(x,y) between x and the query point y can be computed in linear time. Our second algorithm computes the convex hull of a finite set of points in a CAT(0) planar complex. This algorithm is based on Toussaint's algorithm for computing the convex hull of a finite set of points in a simple polygon and it constructs the convex hull of a set of k points in O(n^2 log n + nk log k) time, using a data structure of size O(n^2 + k).