OpenRaiser/Intern-Atlas huggingface dataset:
Quality Indicators for Collective Systems Resilience
Venue: arXiv cs.CY 2014
Year: 2014

Resilience is widely recognized as an important design goal though it is one that seems to escape a general and consensual understanding. Often mixed up with other system attributes; traditionally used with different meanings in as many different disciplines; sought or applied through diverse approaches in various application domains, resilience in fact is a multi-attribute property that implies a number of constitutive abilities. To further complicate the matter, resilience is not an absolute property but rather it is the result of the match between a system, its current condition, and the environment it is set to operate in. In this paper we discuss this problem and provide a definition of resilience as a property measurable as a system-environment fit. This brings to the foreground the dynamic nature of resilience as well as its hard dependence on the context. A major problem becomes then that, being a dynamic figure, resilience cannot be assessed in absolute terms. As a way to partially overcome this obstacle, in this paper we provide a number of indicators of the quality of resilience. Our focus here is that of collective systems, namely those systems resulting from the union of multiple individual parts, sub-systems, or organs. Through several examples of such systems we observe how our indicators provide insight, at least in the cases at hand, on design flaws potentially affecting the efficiency of the resilience strategies. A number of conjectures are finally put forward to associate our indicators with factors affecting the quality of resilience.
A new keyphrases extraction method based on suffix tree data structure for arabic documents clustering
Venue: arXiv cs.CL 2014
Year: 2014

Document Clustering is a branch of a larger area of scientific study known as data mining .which is an unsupervised classification using to find a structure in a collection of unlabeled data. The useful information in the documents can be accompanied by a large amount of noise words when using Full Text Representation, and therefore will affect negatively the result of the clustering process. So it is with great need to eliminate the noise words and keeping just the useful information in order to enhance the quality of the clustering results. This problem occurs with different degree for any language such as English, European, Hindi, Chinese, and Arabic Language. To overcome this problem, in this paper, we propose a new and efficient Keyphrases extraction method based on the Suffix Tree data structure (KpST), the extracted Keyphrases are then used in the clustering process instead of Full Text Representation. The proposed method for Keyphrases extraction is language independent and therefore it may be applied to any language. In this investigation, we are interested to deal with the Arabic language which is one of the most complex languages. To evaluate our method, we conduct an experimental study on Arabic Documents using the most popular Clustering approach of Hierarchical algorithms: Agglomerative Hierarchical algorithm with seven linkage techniques and a variety of distance functions and similarity measures to perform Arabic Document Clustering task. The obtained results show that our method for extracting Keyphrases increases the quality of the clustering results. We propose also to study the effect of using the stemming for the testing dataset to cluster it with the same documents clustering techniques and similarity/distance measures.
Cross-lingual Annotation Projection for Semantic Roles
Venue: arXiv cs.CL 2014
Year: 2014

This article considers the task of automatically inducing role-semantic annotations in the FrameNet paradigm for new languages. We propose a general framework that is based on annotation projection, phrased as a graph optimization problem. It is relatively inexpensive and has the potential to reduce the human effort involved in creating role-semantic resources. Within this framework, we present projection models that exploit lexical and syntactic information. We provide an experimental evaluation on an English-German parallel corpus which demonstrates the feasibility of inducing high-precision German semantic role annotation both for manually and automatically annotated English data.
Inferring Shallow-Transfer Machine Translation Rules from Small Parallel Corpora
Venue: arXiv cs.CL 2014
Year: 2014

This paper describes a method for the automatic inference of structural transfer rules to be used in a shallow-transfer machine translation (MT) system from small parallel corpora. The structural transfer rules are based on alignment templates, like those used in statistical MT. Alignment templates are extracted from sentence-aligned parallel corpora and extended with a set of restrictions which are derived from the bilingual dictionary of the MT system and control their application as transfer rules. The experiments conducted using three different language pairs in the free/open-source MT platform Apertium show that translation quality is improved as compared to word-for-word translation (when no transfer rules are used), and that the resulting translation quality is close to that obtained using hand-coded transfer rules. The method we present is entirely unsupervised and benefits from information in the rest of modules of the MT system in which the inferred rules are applied.
Worst-Case Scenarios for Greedy, Centrality-Based Network Protection Strategies
Venue: arXiv cs.SI 2014
Year: 2014

The task of allocating preventative resources to a computer network in order to protect against the spread of viruses is addressed. Virus spreading dynamics are described by a linearized SIS model and protection is framed by an optimization problem which maximizes the rate at which a virus in the network is contained given finite resources. One approach to problems of this type involve greedy heuristics which allocate all resources to the nodes with large centrality measures. We address the worst case performance of such greedy algorithms be constructing networks for which these greedy allocations are arbitrarily inefficient. An example application is presented in which such a worst case network might arise naturally and our results are verified numerically by leveraging recent results which allow the exact optimal solution to be computed via geometric programming.
An Enhanced Branch-and-bound Algorithm for the Talent Scheduling Problem
Venue: arXiv cs.AI 2014
Year: 2014

The talent scheduling problem is a simplified version of the real-world film shooting problem, which aims to determine a shooting sequence so as to minimize the total cost of the actors involved. In this article, we first formulate the problem as an integer linear programming model. Next, we devise a branch-and-bound algorithm to solve the problem. The branch-and-bound algorithm is enhanced by several accelerating techniques, including preprocessing, dominance rules and caching search states. Extensive experiments over two sets of benchmark instances suggest that our algorithm is superior to the current best exact algorithm. Finally, the impacts of different parameter settings are disclosed by some additional experiments.
Efficiently Detecting Overlapping Communities through Seeding and Semi-Supervised Learning
Venue: arXiv cs.SI 2014
Year: 2014

Seeding then expanding is a commonly used scheme to discover overlapping communities in a network. Most seeding methods are either too complex to scale to large networks or too simple to select high-quality seeds, and the non-principled functions used by most expanding methods lead to poor performance when applied to diverse networks. This paper proposes a new method that transforms a network into a corpus where each edge is treated as a document, and all nodes of the network are treated as terms of the corpus. An effective seeding method is also proposed that selects seeds as a training set, then a principled expanding method based on semi-supervised learning is applied to classify edges. We compare our new algorithm with four other community detection algorithms on a wide range of synthetic and empirical networks. Experimental results show that the new algorithm can significantly improve clustering performance in most cases. Furthermore, the time complexity of the new algorithm is linear to the number of edges, and this low complexity makes the new algorithm scalable to large networks.
Hamming's Original Paper Rewritten in Symbolic Form: A Preamble to Coding Theory
Venue: arXiv cs.IT 2014
Year: 2014

In this note we try to bring out the ideas of Hamming's classic paper on coding theory in a form understandable by undergraduate students of mathematics.
Flows over time in time-varying networks
Venue: arXiv cs.SY 2014
Year: 2014

There has been much research on network flows over time due to their important role in real world applications. This has led to many results, but the more challenging continuous time model still lacks some of the key concepts and techniques that are the cornerstones of static network flows. The aim of this paper is to advance the state of the art for dynamic network flows by developing the continuous time analogues of the theory for static network flows. Specifically, we make use of ideas from the static case to establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of network flows over time.
On Continuous-Time White Phase Noise Channels
Venue: arXiv cs.IT 2014
Year: 2014

A continuous-time model for the additive white Gaussian noise (AWGN) channel in the presence of white (memoryless) phase noise is proposed and discussed. It is shown that for linear modulation the output of the baud-sampled filter matched to the shaping waveform represents a sufficient statistic. The analysis shows that the phase noise channel has the same information rate as an AWGN channel but with a penalty on the average signal-to-noise ratio, the amount of penalty depending on the phase noise statistic.
Performance Impact of Lock-Free Algorithms on Multicore Communication APIs
Venue: arXiv cs.DC 2014
Year: 2014

Data race conditions in multi-tasking software applications are prevented by serializing access to shared memory resources, ensuring data consistency and deterministic behavior. Traditionally tasks acquire and release locks to synchronize operations on shared memory. Unfortunately, lock management can add significant processing overhead especially for multicore deployments where tasks on different cores convoy in queues waiting to acquire a lock. Implementing more than one lock introduces the risk of deadlock and using spinlocks constrains which cores a task can run on. The better alternative is to eliminate locks and validate that real-time properties are met, which is not directly considered in many embedded applications. Removing the locks is non-trivial and packaging lock-free algorithms for developers reduces the possibility of concurrency defects. This paper details how a multicore communication API implementation is enhanced to support lock-free messaging and the impact this has on data exchange latency between tasks. Throughput and latency are compared on Windows and Linux between lock-based and lock-free implementations for data exchange of messages, packets, and scalars. A model of the lock-free exchange predicts performance at the system architecture level and provides a stop criterion for the refactoring. The results show that migration from single to multicore hardware architectures degrades lock-based performance, and increases lock-free performance.
e-commerce business models in the context of web3.0 paradigm
Venue: arXiv cs.CY 2014
Year: 2014

Web 3.0 promises to have a significant effect in users and businesses. It will change how people work and play, how companies use information to market and sell their products, as well as operate their businesses. The basic shift occurring in Web 3.0 is from information-centric to knowledge-centric patterns of computing. Web 3.0 will enable people and machines to connect, evolve, share and use knowledge on an unprecedented scale and in new ways that make our experience of the Internet better. Additionally, semantic technologies have the potential to drive significant improvements in capabilities and life cycle economics through cost reductions, improved efficiencies, enhanced effectiveness, and new functionalities that were not possible or economically feasible before. In this paper we look to the semantic web and Web 3.0 technologies as enablers for the creation of value and appearance of new business models. For that, we analyze the role and impact of Web 3.0 in business and we identify nine potential business models, based in direct and undirected revenue sources, which have emerged with the appearance of semantic web technologies.
Sequential Joint Spectrum Sensing and Channel Estimation for Dynamic Spectrum Access
Venue: arXiv cs.IT 2014
Year: 2014

Dynamic spectrum access under channel uncertainties is considered. With the goal of maximizing the secondary user (SU) throughput subject to constraints on the primary user (PU) outage probability we formulate a joint problem of spectrum sensing and channel state estimation. The problem is cast into a sequential framework since sensing time minimization is crucial for throughput maximization. In the optimum solution, the sensing decision rule is coupled with the channel estimator, making the separate treatment of the sensing and channel estimation strictly suboptimal. Using such a joint structure for spectrum sensing and channel estimation we propose a distributed (cooperative) dynamic spectrum access scheme under statistical channel state information (CSI). In the proposed scheme, the SUs report their sufficient statistics to a fusion center (FC) via level-triggered sampling, a nonuniform sampling technique that is known to be bandwidth-and-energy efficient. Then, the FC makes a sequential spectrum sensing decision using local statistics and channel estimates, and selects the SU with the best transmission opportunity. The selected SU, using the sensing decision and its channel estimates, computes the transmit power and starts data transmission. Simulation results demonstrate that the proposed scheme significantly outperforms its conventional counterparts, under the same PU outage constraints, in terms of the achievable SU throughput.
Parsimonious Topic Models with Salient Word Discovery
Venue: arXiv cs.LG 2014
Year: 2014

We propose a parsimonious topic model for text corpora. In related models such as Latent Dirichlet Allocation (LDA), all words are modeled topic-specifically, even though many words occur with similar frequencies across different topics. Our modeling determines salient words for each topic, which have topic-specific probabilities, with the rest explained by a universal shared model. Further, in LDA all topics are in principle present in every document. By contrast our model gives sparse topic representation, determining the (small) subset of relevant topics for each document. We derive a Bayesian Information Criterion (BIC), balancing model complexity and goodness of fit. Here, interestingly, we identify an effective sample size and corresponding penalty specific to each parameter type in our model. We minimize BIC to jointly determine our entire model -- the topic-specific words, document-specific topics, all model parameter values, {\it and} the total number of topics -- in a wholly unsupervised fashion. Results on three text corpora and an image dataset show that our model achieves higher test set likelihood and better agreement with ground-truth class labels, compared to LDA and to a model designed to incorporate sparsity.
Probabilistic Signal Shaping for Bit-Metric Decoding
Venue: arXiv cs.IT 2014
Year: 2014

A scheme is proposed that combines probabilistic signal shaping with bit-metric decoding. The transmitter generates symbols according to a distribution on the channel input alphabet. The symbols are labeled by bit strings. At the receiver, the channel output is decoded with respect to a bit-metric. An achievable rate is derived using random coding arguments. For the 8-ASK AWGN channel, numerical results show that at a spectral efficiency of 2 bits/s/Hz, the new scheme outperforms bit-interleaved coded modulation (BICM) without shaping and BICM with bit shaping (i Fabregas and Martinez, 2010) by 0.87 dB and 0.15 dB, respectively, and is within 0.0094 dB of the coded modulation capacity. The new scheme is implemented by combining a distribution matcher with a systematic binary low-density parity-check code. The measured finite-length gains are very close to the gains predicted by the asymptotic theory.
Twofold fast arithmetic
Venue: arXiv cs.NA 2014
Year: 2014

Can we assure math computations by automatic verifying floating-point accuracy? We define fast arithmetic (based on Dekker [1971]) over twofold approximations $z\approx z_0+z_1$, such that $z_0$ is standard result and $z_1$ assesses inaccuracy $Δz_0=z-z_0$. We propose on-fly tracking $z_1$, detecting if $Δz_0$ appears too high. We believe permanent tracking is worth its cost. C++ test code for Intel AVX available via web.
Protocol Sequences for Multiple-Packet Reception
Venue: arXiv cs.IT 2014
Year: 2014

Consider a time slotted communication channel shared by $K$ active users and a single receiver. It is assumed that the receiver has the ability of the multiple-packet reception (MPR) to correctly receive at most $γ$ ($1 \leq γ< K$) simultaneously transmitted packets. Each user accesses the channel following a specific periodical binary sequence, called the protocol sequence, and transmits a packet within a channel slot if and only if the sequence value is equal to one. The fluctuation in throughput is incurred by inevitable random relative shifts among the users due to the lack of feedback. A set of protocol sequences is said to be throughput-invariant (TI) if it can be employed to produce invariant throughput for any relative shifts, i.e., maximize the worst-case throughput. It was shown in the literature that the TI property without considering MPR (i.e., $γ=1$) can be achieved by using shift-invariant (SI) sequences, whose generalized Hamming cross-correlation is independent of relative shifts. This paper investigates TI sequences for MPR; results obtained include achievable throughput value, a lower bound on the sequence period, an optimal construction of TI sequences that achieves the lower bound on the sequence period, and intrinsic structure of TI sequences. In addition, we present a practical packet decoding mechanism for TI sequences that incorporates packet header, forward error-correcting code, and advanced physical layer blind signal separation techniques.
Properties of spatial coupling in compressed sensing
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we address a series of open questions about the construction of spatially coupled measurement matrices in compressed sensing. For hardware implementations one is forced to depart from the limiting regime of parameters in which the proofs of the so-called threshold saturation work. We investigate quantitatively the behavior under finite coupling range, the dependence on the shape of the coupling interaction, and optimization of the so-called seed to minimize distance from optimality. Our analysis explains some of the properties observed empirically in previous works and provides new insight on spatially coupled compressed sensing.
Motivating Smartphone Collaboration in Data Acquisition and Distributed Computing
Venue: arXiv cs.GT 2014
Year: 2014

This paper analyzes and compares different incentive mechanisms for a master to motivate the collaboration of smartphone users on both data acquisition and distributed computing applications. To collect massive sensitive data from users, we propose a reward-based collaboration mechanism, where the master announces a total reward to be shared among collaborators, and the collaboration is successful if there are enough users wanting to collaborate. We show that if the master knows the users' collaboration costs, then he can choose to involve only users with the lowest costs. However, without knowing users' private information, then he needs to offer a larger total reward to attract enough collaborators. Users will benefit from knowing their costs before the data acquisition. Perhaps surprisingly, the master may benefit as the variance of users' cost distribution increases. To utilize smartphones' computation resources to solve complex computing problems, we study how the master can design an optimal contract by specifying different task-reward combinations for different user types. Under complete information, we show that the master involves a user type as long as the master's preference characteristic outweighs that type's unit cost. All collaborators achieve a zero payoff in this case. If the master does not know users' private cost information, however, he will conservatively target at a smaller group of users with small costs, and has to give most benefits to the collaborators.
Nested Polar Codes Achieve the Shannon Rate-Distortion Function and the Shannon Capacity
Venue: arXiv cs.IT 2014
Year: 2014

It is shown that nested polar codes achieve the Shannon rate-distortion function for arbitrary (binary or non-binary) discrete memoryless sources and the Shannon capacity of arbitrary discrete memoryless channels.
Branch-and-price-and-cut for the Split-collection Vehicle Routing Problem with Time Windows and Linear Weight-related Cost
Venue: arXiv cs.DS 2014
Year: 2014

This paper addresses a new vehicle routing problem that simultaneously involves time windows, split collection and linear weight-related cost, which is a generalization of the split delivery vehicle routing problem with time windows (SDVRPTW). This problem consists of determining least-cost vehicle routes to serve a set of customers while respecting the restrictions of vehicle capacity and time windows. The travel cost per unit distance is a linear function of the vehicle weight and the customer demand can be fulfilled by multiple vehicles. To solve this problem, we propose a exact branch-and-price-and-cut algorithm, where the pricing subproblem is a resource-constrained elementary least-cost path problem. We first prove that at least an optimal solution to the pricing subproblem is associated with an extreme collection pattern, and then design a tailored and novel label-setting algorithm to solve it. Computational results show that our proposed algorithm can handle both the SDVRPTW and our problem effectively.