OpenRaiser/Intern-Atlas huggingface dataset:
Beyond Word-based Language Model in Statistical Machine Translation
Venue: arXiv cs.CL 2015
Year: 2015

Language model is one of the most important modules in statistical machine translation and currently the word-based language model dominants this community. However, many translation models (e.g. phrase-based models) generate the target language sentences by rendering and compositing the phrases rather than the words. Thus, it is much more reasonable to model dependency between phrases, but few research work succeed in solving this problem. In this paper, we tackle this problem by designing a novel phrase-based language model which attempts to solve three key sub-problems: 1, how to define a phrase in language model; 2, how to determine the phrase boundary in the large-scale monolingual data in order to enlarge the training set; 3, how to alleviate the data sparsity problem due to the huge vocabulary size of phrases. By carefully handling these issues, the extensive experiments on Chinese-to-English translation show that our phrase-based language model can significantly improve the translation quality by up to +1.47 absolute BLEU score.
A Simple Expression for Mill's Ratio of the Student's $t$-Distribution
Venue: arXiv cs.LG 2015
Year: 2015

I show a simple expression of the Mill's ratio of the Student's t-Distribution. I use it to prove Conjecture 1 in P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 47(2-3):235--256, May 2002.
Graph Partitioning for Independent Sets
Venue: arXiv cs.DS 2015
Year: 2015

Computing maximum independent sets in graphs is an important problem in computer science. In this paper, we develop an evolutionary algorithm to tackle the problem. The core innovations of the algorithm are very natural combine operations based on graph partitioning and local search algorithms. More precisely, we employ a state-of-the-art graph partitioner to derive operations that enable us to quickly exchange whole blocks of given independent sets. To enhance newly computed offsprings we combine our operators with a local search algorithm. Our experimental evaluation indicates that we are able to outperform state-of-the-art algorithms on a variety of instances.
Indexing arbitrary-length $k$-mers in sequencing reads
Venue: arXiv cs.DS 2015
Year: 2015

We propose a lightweight data structure for indexing and querying collections of NGS reads data in main memory. The data structure supports the interface proposed in the pioneering work by Philippe et al. for counting and locating $k$-mers in sequencing reads. Our solution, PgSA (pseudogenome suffix array), based on finding overlapping reads, is competitive to the existing algorithms in the space use, query times, or both. The main applications of our index include variant calling, error correction and analysis of reads from RNA-seq experiments.
Comprehensive Efficient Implementations of ECC on C54xx Family of Low-cost Digital Signal Processors
Venue: arXiv cs.CR 2015
Year: 2015

Resource constraints in smart devices demand an efficient cryptosystem that allows for low power and memory consumption. This has led to popularity of comparatively efficient Elliptic curve cryptog-raphy (ECC). Prior to this paper, much of ECC is implemented on re-configurable hardware i.e. FPGAs, which are costly and unfavorable as low-cost solutions. We present comprehensive yet efficient implementations of ECC on fixed-point TMS54xx series of digital signal processors (DSP). 160-bit prime field GF(p) ECC is implemented over a wide range of coordinate choices. This paper also implements windowed recoding technique to provide better execution times. Stalls in the programming are mini-mized by utilization of loop unrolling and by avoiding data dependence. Complete scalar multiplication is achieved within 50 msec in coordinate implementations, which is further reduced till 25 msec for windowed-recoding method. These are the best known results for fixed-point low power digital signal processor to date.
A Fingerprint-based Access Control using Principal Component Analysis and Edge Detection
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a novel approach for deciding on the appropriateness or not of an acquired fingerprint image into a given database. The process begins with the assembly of a training base in an image space constructed by combining Principal Component Analysis (PCA) and edge detection. Then, the parameter H, a new feature that helps in the decision making about the relevance of a fingerprint image in databases, is derived from a relationship between Euclidean and Mahalanobian distances. This procedure ends with the lifting of the curve of the Receiver Operating Characteristic (ROC), where the thresholds defined on the parameter H are chosen according to the acceptable rates of false positives and false negatives.
A General SIMD-based Approach to Accelerating Compression Algorithms
Venue: arXiv cs.IR 2015
Year: 2015

Compression algorithms are important for data oriented tasks, especially in the era of Big Data. Modern processors equipped with powerful SIMD instruction sets, provide us an opportunity for achieving better compression performance. Previous research has shown that SIMD-based optimizations can multiply decoding speeds. Following these pioneering studies, we propose a general approach to accelerate compression algorithms. By instantiating the approach, we have developed several novel integer compression algorithms, called Group-Simple, Group-Scheme, Group-AFOR, and Group-PFD, and implemented their corresponding vectorized versions. We evaluate the proposed algorithms on two public TREC datasets, a Wikipedia dataset and a Twitter dataset. With competitive compression ratios and encoding speeds, our SIMD-based algorithms outperform state-of-the-art non-vectorized algorithms with respect to decoding speeds.
Can Quantum Entanglement Detection Schemes Improve Search?
Venue: arXiv cs.DS 2015
Year: 2015

Quantum computation, in particular Grover's algorithm, has aroused a great deal of interest since it allows for a quadratic speedup to be obtained in search procedures. Classical search procedures for an $N$ element database require at most $O(N)$ time complexity. Grover's algorithm is able to find a solution with high probability in $O(\sqrt{N})$ time through an amplitude amplification scheme. In this work we draw elements from both classical and quantum computation to develop an alternative search proposal based on quantum entanglement detection schemes. In 2002, Horodecki and Ekert proposed an efficient method for direct detection of quantum entanglement. Our proposition to quantum search combines quantum entanglement detection alongside entanglement inducing operators. Grover's quantum search relies on measuring a quantum superposition after having applied a unitary evolution. We deviate from the standard method by focusing on fine-tuning a unitary operator in order to infer the solution with certainty. Our proposal sacrifices space for speed and depends on the mathematical properties of linear positive maps $Λ$ which have not been operationally characterized. Whether such a $Λ$ can be easily determined remains an open question.
Censoring for Improved Sensing Performance in Infrastructure-less Cognitive Radio Networks
Venue: arXiv cs.NI 2015
Year: 2015

Censoring has been proposed to be utilized in wireless distributed detection networks with a fusion center to enhance network performance in terms of error probability in addition to the well-established energy saving gains. In this paper, we further examine the employment of censoring in infrastructure-less cognitive radio networks, where nodes employ binary consensus algorithms to take global decisions regarding a binary hypothesis test without a fusion center to coordinate such a process. We show analytically - and verify by simulations - that censoring enhances the performance of such networks in terms of error probability and convergence times. Our protocol shows performance gains up to 46.6% in terms of average error probability over its conventional counterpart, in addition to performance gains of about 48.7% in terms of average energy expenditure and savings up to 50% in incurred transmission overhead.
A Quantum Production Model
Venue: arXiv cs.AI 2015
Year: 2015

The production system is a theoretical model of computation relevant to the artificial intelligence field allowing for problem solving procedures such as hierarchical tree search. In this work we explore some of the connections between artificial intelligence and quantum computation by presenting a model for a quantum production system. Our approach focuses on initially developing a model for a reversible production system which is a simple mapping of Bennett's reversible Turing machine. We then expand on this result in order to accommodate for the requirements of quantum computation. We present the details of how our proposition can be used alongside Grover's algorithm in order to yield a speedup comparatively to its classical counterpart. We discuss the requirements associated with such a speedup and how it compares against a similar quantum hierarchical search approach.
Participatory Militias: An Analysis of an Armed Movement's Online Audience
Venue: arXiv cs.SI 2015
Year: 2015

Armed groups of civilians known as "self-defense forces" have ousted the powerful Knights Templar drug cartel from several towns in Michoacan. This militia uprising has unfolded on social media, particularly in the "VXM" ("Valor por Michoacan," Spanish for "Courage for Michoacan") Facebook page, gathering more than 170,000 fans. Previous work on the Drug War has documented the use of social media for real-time reports of violent clashes. However, VXM goes one step further by taking on a pro-militia propagandist role, engaging in two-way communication with its audience. This paper presents a descriptive analysis of VXM and its audience. We examined nine months of posts, from VXM's inception until May 2014, totaling 6,000 posts by VXM administrators and more than 108,000 comments from its audience. We describe the main conversation themes, post frequency and relationships with offline events and public figures. We also characterize the behavior of VXM's most active audience members. Our work illustrates VXM's online mobilization strategies, and how its audience takes part in defining the narrative of this armed conflict. We conclude by discussing possible applications of our findings for the design of future communication technologies.
Taxing the Internet - is that feasible ?
Venue: arXiv cs.CY 2015
Year: 2015

Governments across the globe are facing challenging times to generate more revenue because of the economic slowdown and to balance their budgets. There is a growing need to find new ways of revenue generation as spending cuts and austerity measures dont go well with most sections of the society, especially during difficult economic times. Internet Today is seen more as a necessary commodity and nobody can deny the fact that the Internet has improved peoples life in an unprecedented way than any other technology in the past.The Internet as a commodity is taxed in many countries, but the Internet usage or the transactions carried out are something thats not taxed.
Extracting verified decision procedures: DPLL and Resolution
Venue: arXiv cs.LO 2015
Year: 2015

This article is concerned with the application of the program extraction technique to a new class of problems: the synthesis of decision procedures for the classical satisfiability problem that are correct by construction. To this end, we formalize a completeness proof for the DPLL proof system and extract a SAT solver from it. When applied to a propositional formula in conjunctive normal form the program produces either a satisfying assignment or a DPLL derivation showing its unsatisfiability. We use non-computational quantifiers to remove redundant computational content from the extracted program and translate it into Haskell to improve performance. We also prove the equivalence between the resolution proof system and the DPLL proof system with a bound on the size of the resulting resolution proof. This demonstrates that it is possible to capture quantitative information about the extracted program on the proof level. The formalization is carried out in the interactive proof assistant Minlog.
Power Efficient Resource Allocation for Full-Duplex Radio Distributed Antenna Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the resource allocation algorithm design for distributed antenna multiuser networks with full-duplex (FD) radio base stations (BSs) which enable simultaneous uplink and downlink communications. The considered resource allocation algorithm design is formulated as an optimization problem taking into account the antenna circuit power consumption of the BSs and the quality of service (QoS) requirements of both uplink and downlink users. We minimize the total network power consumption by jointly optimizing the downlink beamformer, the uplink transmit power, and the antenna selection. To overcome the intractability of the resulting problem, we reformulate it as an optimization problem with decoupled binary selection variables and non-convex constraints. The reformulated problem facilitates the design of an iterative resource allocation algorithm which obtains an optimal solution based on the generalized Bender's decomposition (GBD) and serves as a benchmark scheme. Furthermore, to strike a balance between computational complexity and system performance, a suboptimal algorithm with polynomial time complexity is proposed. Simulation results illustrate that the proposed GBD based iterative algorithm converges to the global optimal solution and the suboptimal algorithm achieves a close-to-optimal performance. Our results also demonstrate the trade-off between power efficiency and the number of active transmit antennas when the circuit power consumption is taken into account. In particular, activating an exceedingly large number of antennas may not be a power efficient solution for reducing the total system power consumption. In addition, our results reveal that FD systems facilitate significant power savings compared to traditional half-duplex systems, despite the non-negligible self-interference.
Marching Surfaces: Isosurface Approximation using G$^1$ Multi-Sided Surfaces
Venue: arXiv cs.GR 2015
Year: 2015

Marching surfaces is a method for isosurface extraction and approximation based on a $G^1$ multi-sided patch interpolation scheme. Given a 3D grid of scalar values, an underlying curve network is formed using second order information and cubic Hermite splines. Circular arc fitting defines the tangent vectors for the Hermite curves at specified isovalues. Once the boundary curve network is formed, a loop of curves is determined for each grid cell and then interpolated with multi-sided surface patches, which are $G^1$ continuous at the joins. The data economy of the method and its continuity preserving properties provide an effective compression scheme, ideal for indirect volume rendering on mobile devices, or collaborating on the Internet, while enhancing visual fidelity. The use of multi-sided patches enables a more natural way to approximate the isosurfaces than using a fixed number of sides or polygons as is proposed in the literature. This assertion is supported with comparisons to the traditional Marching Cubes algorithm and other $G^1$ methods.
On the Greedy Algorithm for Combinatorial Auctions with a Random Order
Venue: arXiv cs.GT 2015
Year: 2015

In this note we study the greedy algorithm for combinatorial auctions with submodular bidders. It is well known that this algorithm provides an approximation ratio of $2$ for every order of the items. We show that if the valuations are vertex cover functions and the order is random then the expected approximation ratio imrpoves to $\frac 7 4$.
Real World Applications of Machine Learning Techniques over Large Mobile Subscriber Datasets
Venue: arXiv cs.LG 2015
Year: 2015

Communication Service Providers (CSPs) are in a unique position to utilize their vast transactional data assets generated from interactions of subscribers with network elements as well as with other subscribers. CSPs could leverage its data assets for a gamut of applications such as service personalization, predictive offer management, loyalty management, revenue forecasting, network capacity planning, product bundle optimization and churn management to gain significant competitive advantage. However, due to the sheer data volume, variety, velocity and veracity of mobile subscriber datasets, sophisticated data analytics techniques and frameworks are necessary to derive actionable insights in a useable timeframe. In this paper, we describe our journey from a relational database management system (RDBMS) based campaign management solution which allowed data scientists and marketers to use hand-written rules for service personalization and targeted promotions to a distributed Big Data Analytics platform, capable of performing large scale machine learning and data mining to deliver real time service personalization, predictive modelling and product optimization. Our work involves a careful blend of technology, processes and best practices, which facilitate man-machine collaboration and continuous experimentation to derive measurable economic value from data. Our platform has a reach of more than 500 million mobile subscribers worldwide, delivering over 1 billion personalized recommendations annually, processing a total data volume of 64 Petabytes, corresponding to 8.5 trillion events.
LineSwitch: Efficiently Managing Switch Flow in Software-Defined Networking while Effectively Tackling DoS Attacks
Venue: arXiv cs.NI 2015
Year: 2015

Software Defined Networking (SDN) is a new networking architecture which aims to provide better decoupling between network control (control plane) and data forwarding functionalities (data plane). This separation introduces several benefits, such as a directly programmable and (virtually) centralized network control. However, researchers showed that the required communication channel between the control and data plane of SDN creates a potential bottleneck in the system, introducing new vulnerabilities. Indeed, this behavior could be exploited to mount powerful attacks, such as the control plane saturation attack, that can severely hinder the performance of the whole network. In this paper we present LineSwitch, an efficient and effective solution against control plane saturation attack. LineSwitch combines SYN proxy techniques and probabilistic blacklisting of network traffic. We implemented LineSwitch as an extension of OpenFlow, the current reference implementation of SDN, and evaluate our solution considering different traffic scenarios (with and without attack). The results of our preliminary experiments confirm that, compared to the state-of-the-art, LineSwitch reduces the time overhead up to 30%, while ensuring the same level of protection.
A High-Performance Solid-State Disk with Double-Data-Rate NAND Flash Memory
Venue: arXiv cs.AR 2015
Year: 2015

We propose a novel solid-state disk (SSD) architecture that utilizes a double-data-rate synchronous NAND flash interface for improving read and write performance. Unlike the conventional design, the data transfer rate in the proposed design is doubled in harmony with synchronous signaling. The new architecture does not require any extra pins with respect to the conventional architecture, thereby guaranteeing backward compatibility. For performance evaluation, we simulated various SSD designs that adopt the proposed architecture and measured their performance in terms of read/write bandwidths and energy consumption. Both NAND flash cell types, namely single-level cells (SLCs) and multi-level cells (MLCs), were considered. In the experiments using SLC-type NAND flash chips, the read and write speeds of the proposed architecture were 1.65-2.76 times and 1.09-2.45 times faster than those of the conventional architecture, respectively. Similar improvements were observed for the MLC-based architectures tested. It was particularly effective to combine the proposed architecture with the way-interleaving technique that multiplexes the data channel between the controller and each flash chip. For a reasonably high degree of way interleaving, the read/write performance and the energy consumption of our approach were notably better than those of the conventional design.
SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
Venue: arXiv cs.LG 2015
Year: 2015

We propose a new algorithm for minimizing regularized empirical loss: Stochastic Dual Newton Ascent (SDNA). Our method is dual in nature: in each iteration we update a random subset of the dual variables. However, unlike existing methods such as stochastic dual coordinate ascent, SDNA is capable of utilizing all curvature information contained in the examples, which leads to striking improvements in both theory and practice - sometimes by orders of magnitude. In the special case when an L2-regularizer is used in the primal, the dual problem is a concave quadratic maximization problem plus a separable term. In this regime, SDNA in each step solves a proximal subproblem involving a random principal submatrix of the Hessian of the quadratic function; whence the name of the method. If, in addition, the loss functions are quadratic, our method can be interpreted as a novel variant of the recently introduced Iterative Hessian Sketch.
Protecting Memory-Performance Critical Sections in Soft Real-Time Applications
Venue: arXiv cs.OS 2015
Year: 2015

Soft real-time applications such as multimedia applications often show bursty memory access patterns---regularly requiring a high memory bandwidth for a short duration of time. Such a period is often critical for timely data processing. Hence, we call it a memory-performance critical section. Unfortunately, in multicore architecture, non-real-time applications on different cores may also demand high memory bandwidth at the same time, which can substantially increase the time spent on the memory performance critical sections. In this paper, we present BWLOCK, user-level APIs and a memory bandwidth control mechanism that can protect such memory performance critical sections of soft real-time applications. BWLOCK provides simple lock like APIs to declare memory-performance critical sections. If an application enters a memory-performance critical section, the memory bandwidth control system then dynamically limit other cores' memory access rates to protect memory performance of the application until the critical section finishes. From case studies with real-world soft real-time applications, we found (1) such memory-performance critical sections do exist and are often easy to identify; and (2) applying BWLOCK for memory critical sections significantly improve performance of the soft real-time applications at a small or no cost in throughput of non real-time applications.
The extensional realizability model of continuous functionals and three weakly non-constructive classical theorems
Venue: arXiv cs.LO 2015
Year: 2015

We investigate wether three statements in analysis, that can be proved classically, are realizable in the realizability model of extensional continuous functionals induced by Kleene's second model $K_2$. We prove that a formulation of the Riemann Permutation Theorem as well as the statement that all partially Cauchy sequences are Cauchy cannot be realized in this model, while the statement that the product of two anti-Specker spaces is anti-Specker can be realized.