OpenRaiser/Intern-Atlas huggingface dataset:
EagleTree: Exploring the Design Space of SSD-Based Algorithms
Venue: arXiv cs.DB 2014
Year: 2014

Solid State Drives (SSDs) are a moving target for system designers: they are black boxes, their internals are undocumented, and their performance characteristics vary across models. There is no appropriate analytical model and experimenting with commercial SSDs is cumbersome, as it requires a careful experimental methodology to ensure repeatability. Worse, performance results obtained on a given SSD cannot be generalized. Overall, it is impossible to explore how a given algorithm, say a hash join or LSM-tree insertions, leverages the intrinsic parallelism of a modern SSD, or how a slight change in the internals of an SSD would impact its overall performance. In this paper, we propose a new SSD simulation framework, named EagleTree, which addresses these problems, and enables a principled study of SSD-Based algorithms. The demonstration scenario illustrates the design space for algorithms based on an SSD-based IO stack, and shows how researchers and practitioners can use EagleTree to perform tractable explorations of this complex design space.
Design of an Encryption-Decryption Module Oriented for Internet Information Security SOC Design
Venue: arXiv cs.AR 2014
Year: 2014

In order to protect the security of network data, a high speed chip module for encrypting and decrypting of network data packet is designed. The chip module is oriented for internet information security SOC (System on Chip) design. During the design process, AES (Advanced Encryption Standard) and 3DES (Data Encryption Standard) encryption algorithm are adopted to protect the security of network data. The following points are focused: (1) The SOC (System on Chip) design methodology based on IP (Intellectual Property) core is used. AES (Advanced Encryption Standard) and 3DES (Data Encryption Standard) IP (Intellectual Property) cores are embedded in the chip module, peripheral control sub-modules are designed to control the encryption-decryption module, which is capable of shortening the design period of the chip module. (2) The implementation of encryption-decryption with hardware was presented, which improves the safety of data through the encryption-decryption chip and reduce the load of CPU. (3) In our hardware solution, two AES (Advanced Encryption Standard) cores are used to work in parallel, which improves the speed of the encryption module. Moreover, the key length of AES (Advanced Encryption Standard) encryption algorithm is designed with three optional configurations at 128 bits, 256 bits and 192 bits respectively and six optional encryption algorithm modes: CBC (Cipher Block Chaining) mode, ECB (Electronic Code Book) mode, GCM (Galois/Counter Mode) mode, XTS(cipherteXT Stealing) mode, CTR (CounTeR) mode and 3DES respectively, which adds the flexibility to its applications.
An exact algorithm for the weighed mutually exclusive maximum set cover problem
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we introduce an exact algorithm with a time complexity of $O^*(1.325^m)$ for the {\sc weighted mutually exclusive maximum set cover} problem, where $m$ is the number of subsets in the problem. This is an NP-hard motivated and abstracted from a bioinformatics problem of identifying signaling pathways based gene mutations. Currently, this problem is addressed using heuristic algorithms, which cannot guarantee the performance of the solution. By providing a relatively efficient exact algorithm, our approach will like increase the capability of finding better solutions in the application of cancer research.
Automatic Aggregation by Joint Modeling of Aspects and Values
Venue: arXiv cs.CL 2014
Year: 2014

We present a model for aggregation of product review snippets by joint aspect identification and sentiment analysis. Our model simultaneously identifies an underlying set of ratable aspects presented in the reviews of a product (e.g., sushi and miso for a Japanese restaurant) and determines the corresponding sentiment of each aspect. This approach directly enables discovery of highly-rated or inconsistent aspects of a product. Our generative model admits an efficient variational mean-field inference algorithm. It is also easily extensible, and we describe several modifications and their effects on model structure and inference. We test our model on two tasks, joint aspect identification and sentiment analysis on a set of Yelp reviews and aspect identification alone on a set of medical summaries. We evaluate the performance of the model on aspect identification, sentiment analysis, and per-word labeling accuracy. We demonstrate that our model outperforms applicable baselines by a considerable margin, yielding up to 32% relative error reduction on aspect identification and up to 20% relative error reduction on sentiment analysis.
Coalition Structure Generation over Graphs
Venue: arXiv cs.DS 2014
Year: 2014

We give the analysis of the computational complexity of coalition structure generation over graphs. Given an undirected graph G = (N,E) and a valuation function v : P(N) \to R over the subsets of nodes, the problem is to find a partition of N into connected subsets, that maximises the sum of the components values. This problem is generally NP-complete; in particular, it is hard for a defined class of valuation functions which are independent of disconnected members - that is, two nodes have no effect on each other's marginal contribution to their vertex separator. Nonetheless, for all such functions we provide bounds on the complexity of coalition structure generation over general and minor-free graphs. Our proof is constructive and yields algorithms for solving corresponding instances of the problem. Furthermore, we derive linear time bounds for graphs of bounded treewidth. However, as we show, the problem remains NP-complete for planar graphs, and hence, for any K_k minor free graphs where k \geq 5. Moreover, a 3-SAT problem with m clauses can be represented by a coalition structure generation problem over a planar graph with O(m^2) nodes. Importantly, our hardness result holds for a particular subclass of valuation functions, termed edge sum, where the value of each subset of nodes is simply determined by the sum of given weights of the edges in the induced subgraph.
A Universal Decoder Relative to a Given Family of Metrics
Venue: arXiv cs.IT 2014
Year: 2014

Consider the following framework of universal decoding suggested in [MerhavUniversal]. Given a family of decoding metrics and random coding distribution (prior), a single, universal, decoder is optimal if for any possible channel the average error probability when using this decoder is better than the error probability attained by the best decoder in the family up to a subexponential multiplicative factor. We describe a general universal decoder in this framework. The penalty for using this universal decoder is computed. The universal metric is constructed as follows. For each metric, a canonical metric is defined and conditions for the given prior to be normal are given. A sub-exponential set of canonical metrics of normal prior can be merged to a single universal optimal metric. We provide an example where this decoder is optimal while the decoder of [MerhavUniversal] is not.
Kinematics analysis and three-dimensional simulation of the rehabilitation lower extremity exoskeleton robot
Venue: arXiv cs.RO 2014
Year: 2014

The kinematics recursive equation was built by using the modified D-H method after the structure of rehabilitation lower extremity exoskeleton was analyzed. The numerical algorithm of inverse kinematics was given too. Then the three-dimensional simulation model of the exoskeleton robot was built using MATLAB software, based on the model, 3D reappearance of a complete gait was achieved. Finally, the reliability of numerical algorithm of inverse kinematics was verified by the simulation result. All jobs above lay a foundation for developing a three-dimensional simulation platform of exoskeleton robot.
Infinite square-free self-shuffling words
Venue: arXiv cs.DM 2014
Year: 2014

In this paper we answer two recent questions from Charlier et al. and Harju about self-shuffling words. An infinite word $w$ is called self-shuffling, if $w=\prod_{i=0}^\infty U_iV_i=\prod_{i=0}^\infty U_i=\prod_{i=0}^\infty V_i$ for some finite words $U_i$, $V_i$. Harju recently asked whether square-free self-shuffling words exist. We answer this question affirmatively. Besides that, we build an infinite word such that no word in its shift orbit closure is self-shuffling, answering positively a question from Charlier et al.
Deverbal semantics and the Montagovian generative lexicon
Venue: arXiv cs.CL 2014
Year: 2014

We propose a lexical account of action nominals, in particular of deverbal nominalisations, whose meaning is related to the event expressed by their base verb. The literature about nominalisations often assumes that the semantics of the base verb completely defines the structure of action nominals. We argue that the information in the base verb is not sufficient to completely determine the semantics of action nominals. We exhibit some data from different languages, especially from Romance language, which show that nominalisations focus on some aspects of the verb semantics. The selected aspects, however, seem to be idiosyncratic and do not automatically result from the internal structure of the verb nor from its interaction with the morphological suffix. We therefore propose a partially lexicalist approach view of deverbal nouns. It is made precise and computable by using the Montagovian Generative Lexicon, a type theoretical framework introduced by Bassac, Mery and Retoré in this journal in 2010. This extension of Montague semantics with a richer type system easily incorporates lexical phenomena like the semantics of action nominals in particular deverbals, including their polysemy and (in)felicitous copredications.
Never forget, whom was my ancestors: A cross-cultural analysis from Yonsei (fourth-generation Nikkei) in four societies using Data Mining
Venue: arXiv cs.SI 2014
Year: 2014

This research explains the importance of transculturality in social networking in a wide variety of activities of our daily life. We focus our analysis to online activities that use social richness, analyzing societies in Yakutia (A Russian Republic), Macau in China, Uberlândia in Brazil and Juarez City in Mexico, all with people descending from Japanese people. To this end, we performed surveys to gathering information about salient aspects of upgrade and combined them using social data mining techniques to profile a number of behavioural patterns and choices that describe social networking behaviours in these societies.
Iterative Approximate Consensus in the presence of Byzantine Link Failures
Venue: arXiv cs.DC 2014
Year: 2014

This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each directed link of the underlying communication graph represents a communication channel between a pair of nodes. We adopt the transient Byzantine link failure model [15, 16], where an omniscient adversary controls a subset of the directed communication links, but the nodes are assumed to be fault-free. Recent work has addressed the problem of reaching approximate consen- sus in incomplete graphs with Byzantine nodes using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations [22, 21, 23, 12]. However, to the best of our knowledge, we are the first to consider approximate consensus in the presence of Byzan- tine links. We extend our past work that provided exact characterization of graphs in which the iterative approximate consensus problem in the presence of Byzantine node failures is solvable [22, 21]. In particular, we prove a tight necessary and sufficient condition on the underlying com- munication graph for the existence of iterative approximate consensus algorithms under transient Byzantine link model. The condition answers (part of) the open problem stated in [16].
Particle Swarm Optimization for Mobility Load Balancing SON in LTE Networks
Venue: arXiv cs.NI 2014
Year: 2014

This paper presents a self-optimizing solution for Mobility Load Balancing (MLB). The MLB-SON is performed in two phases. In the first, a MLB controller is designed using Multi-Objective Particle Swarm Optimization (MO-PSO) which incorporates a priori expert knowledge to considerably reduce the search space and optimization time. The dynamicity of the optimization phase is addressed. In the second phase, the controller is pushed into the base stations to implement the MLB SON. The method is applied to dynamically adapt Handover Margin parameters of a large scale LTE network in order to balance traffic of the network eNodeBs. Numerical results illustrate the benefits of the proposed solution.
Resilient Flow Decomposition of Unicast Connections with Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we close the gap between end-to-end diversity coding and intra-session network coding for unicast connections resilient against single link failures. In particular, we show that coding operations are sufficient to perform at the source and receiver if the user data can be split into at most two parts over the filed GF(2). Our proof is purely combinatorial and based on standard graph and network flow techniques. It is a linear time construction that defines the route of subflows A, B and A+B between the source and destination nodes. The proposed resilient flow decomposition method generalizes the 1+1 protection and the end-to-end diversity coding approaches while keeping both of their benefits. It provides a simple yet resource efficient protection method feasible in 2-connected backbone topologies. Since the core switches do not need to be modified, this result can bring benefits to current transport networks.
On giant components and treewidth in the layers model
Venue: arXiv cs.DM 2014
Year: 2014

Given an undirected $n$-vertex graph $G(V,E)$ and an integer $k$, let $T_k(G)$ denote the random vertex induced subgraph of $G$ generated by ordering $V$ according to a random permutation $π$ and including in $T_k(G)$ those vertices with at most $k-1$ of their neighbors preceding them in this order. The distribution of subgraphs sampled in this manner is called the \emph{layers model with parameter} $k$. The layers model has found applications in studying $\ell$-degenerate subgraphs, the design of algorithms for the maximum independent set problem, and in bootstrap percolation. In the current work we expand the study of structural properties of the layers model. We prove that there are $3$-regular graphs $G$ for which with high probability $T_3(G)$ has a connected component of size $Ω(n)$. Moreover, this connected component has treewidth $Ω(n)$. This lower bound on the treewidth extends to many other random graph models. In contrast, $T_2(G)$ is known to be a forest (hence of treewidth~1), and we establish that if $G$ is of bounded degree then with high probability the largest connected component in $T_2(G)$ is of size $O(\log n)$. We also consider the infinite two-dimensional grid, for which we prove that the first four layers contain a unique infinite connected component with probability $1$.
Multivariate sparse interpolation using randomized Kronecker substitutions
Venue: arXiv cs.SC 2014
Year: 2014

We present new techniques for reducing a multivariate sparse polynomial to a univariate polynomial. The reduction works similarly to the classical and widely-used Kronecker substitution, except that we choose the degrees randomly based on the number of nonzero terms in the multivariate polynomial, that is, its sparsity. The resulting univariate polynomial often has a significantly lower degree than the Kronecker substitution polynomial, at the expense of a small number of term collisions. As an application, we give a new algorithm for multivariate interpolation which uses these new techniques along with any existing univariate interpolation algorithm.
Improve the Sustainability of Internet of Things Through Trading-based Value Creation
Venue: arXiv cs.CY 2014
Year: 2014

Internet of Things (IoT) has been widely discussed over the past few years in technology point of view. However, the social aspects of IoT are seldom studied to date. In this paper, we discuss the IoT in social point of view. Specifically, we examine the strategies to increase the adoption of IoT in a sustainable manner. Such discussion is essential in today's context where adoption of IoT solutions by non-technical community is slow. Specially, large number of IoT solutions making their way into the market every day. We propose an trading-based value creation model based on sensing as a service paradigm in order to fuel the adoption of IoT. We discuss the value creation and its impact towards the society especially to households and their occupants. We also present results of two different surveys we conducted in order to examine the potential acceptance of the proposed model among the general public.
On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets
Venue: arXiv cs.LO 2014
Year: 2014

We show that there are $Σ_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition, or equivalently by Büchi blind counter automata. This shows that omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.
Kaldi+PDNN: Building DNN-based ASR Systems with Kaldi and PDNN
Venue: arXiv cs.LG 2014
Year: 2014

The Kaldi toolkit is becoming popular for constructing automated speech recognition (ASR) systems. Meanwhile, in recent years, deep neural networks (DNNs) have shown state-of-the-art performance on various ASR tasks. This document describes our open-source recipes to implement fully-fledged DNN acoustic modeling using Kaldi and PDNN. PDNN is a lightweight deep learning toolkit developed under the Theano environment. Using these recipes, we can build up multiple systems including DNN hybrid systems, convolutional neural network (CNN) systems and bottleneck feature systems. These recipes are directly based on the Kaldi Switchboard 110-hour setup. However, adapting them to new datasets is easy to achieve.
Criptografia com Curvas Elípticas
Venue: arXiv cs.CR 2014
Year: 2014

This paper presents an overview of the use of elliptic curves in cryptography. The security of this cryptosystem is based on the discrete logarithm problem, which appears to be much harder compared to the discrete logarithm problem in other cryptosystems. An overview of common cryptosystems is given, such as Diffie-Hellman and RSA, and an elliptic curve cryptography scheme is discussed. -------- Este trabalho apresenta o uso das curvas elípticas em criptografia. Sua segurança está baseada no problema do logaritmo discreto. Este problema aparentemente é significativamente mais difícil de resolver, comparado com o problema do logaritmo discreto usado por outros sistemas de criptografia. É dada uma visão geral de sistemas de criptografia comuns, como Diffie-Hellman e RSA, e discute-se um esquema de criptografia usando curvas elípticas.
Reverse Edge Cut-Set Bounds for Secure Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of secure communication over a network in the presence of wiretappers. We give a new cut-set bound on secrecy capacity which takes into account the contribution of both forward and backward edges crossing the cut, and the connectivity between their endpoints in the rest of the network. We show the bound is tight on a class of networks, which demonstrates that it is not possible to find a tighter bound by considering only cut set edges and their connectivity.
Cellular Downlink Performance with Base Station Sleeping, User Association, and Scheduling
Venue: arXiv cs.NI 2014
Year: 2014

Base station (BS) sleeping has emerged as a viable solution to enhance the overall network energy efficiency by inactivating the underutilized BSs. However, it affects the performance of users in sleeping cells depending on their BS association criteria, their channel conditions towards the active BSs, and scheduling criteria and traffic loads at the active BSs. This paper characterizes the performance of cellular systems with BS sleeping by developing a systematic framework to derive the spectral efficiency and outage probability of downlink transmission to the sleeping cell users taking into account the aforementioned factors. In this context, we develop a user association scheme in which a typical user in a sleeping cell selects a BS with \textbf{M}aximum best-case \textbf{M}ean channel \textbf{A}ccess \textbf{P}robability (MMAP) which is calculated by all active BSs based on their existing traffic loads. We consider both greedy and round-robin schemes at active BSs for scheduling users in a channel. Once the association is performed, the exact access probability for a typical sleeping cell user and the statistics of its received signal and interference powers are derived to evaluate the spectral and energy efficiencies of transmission. For the sleeping cell users, we also consider the conventional \textbf{M}aximum \textbf{R}eceived \textbf{S}ignal \textbf{P}ower (MRSP)-based user association scheme along with greedy and round-robin schemes at the BSs. The impact of cell-zooming is incorporated in the derivations to analyze its feasibility in reducing the coverage holes created by BS sleeping. Numerical results show the trade-offs between spectral efficiency and energy efficiency in various network scenarios. The accuracy of the analysis is verified through Monte-Carlo simulations.
Block-Fading Channels with Delayed CSIT at Finite Blocklength
Venue: arXiv cs.IT 2014
Year: 2014

In many wireless systems, the channel state information at the transmitter (CSIT) can not be learned until after a transmission has taken place and is thereby outdated. In this paper, we study the benefits of delayed CSIT on a block-fading channel at finite blocklength. First, the achievable rates of a family of codes that allows the number of codewords to expand during transmission, based on delayed CSIT, are characterized. A fixed-length and a variable-length characterization of the rates are provided using the dependency testing bound and the variable-length setting introduced by Polyanskiy et al. Next, a communication protocol based on codes with expandable message space is put forth, and numerically, it is shown that higher rates are achievable compared to coding strategies that do not benefit from delayed CSIT.
A Software Design through Electrical System for a Building
Venue: arXiv cs.OH 2014
Year: 2014

Computer aided design of lighting systems made new installations of lighting dimensioning and verification of existing lighting systems for both indoor and outdoor lighting systems.The design of the building light system was in a dedicated software, named DiaLux, version 4.11.
Spatially-Coupled MacKay-Neal Codes with No Bit Nodes of Degree Two Achieve the Capacity of BEC
Venue: arXiv cs.IT 2014
Year: 2014

Obata et al. proved that spatially-coupled (SC) MacKay-Neal (MN) codes achieve the capacity of BEC. However, the SC-MN codes codes have many variable nodes of degree two and have higher error floors. In this paper, we prove that SC-MN codes with no variable nodes of degree two achieve the capacity of BEC.
Polar coding for interference networks
Venue: arXiv cs.IT 2014
Year: 2014

A polar coding scheme for interference networks is introduced. The scheme combines Arikan's monotone chain rules for multiple-access channels and a method by Hassani and Urbanke to 'align' two incompatible polarization processes. It achieves the Han--Kobayashi inner bound for two-user interference channels and generalizes to interference networks.