OpenRaiser/Intern-Atlas huggingface dataset:
Co-evolution of Content Popularity and Delivery in Mobile P2P Networks
Venue: arXiv cs.SI 2011
Year: 2011

Mobile P2P technology provides a scalable approach to content delivery to a large number of users on their mobile devices. In this work, we study the dissemination of a \emph{single} content (e.g., an item of news, a song or a video clip) among a population of mobile nodes. Each node in the population is either a \emph{destination} (interested in the content) or a potential \emph{relay} (not yet interested in the content). There is an interest evolution process by which nodes not yet interested in the content (i.e., relays) can become interested (i.e., become destinations) on learning about the popularity of the content (i.e., the number of already interested nodes). In our work, the interest in the content evolves under the \emph{linear threshold model}. The content is copied between nodes when they make random contact. For this we employ a controlled epidemic spread model. We model the joint evolution of the copying process and the interest evolution process, and derive the joint fluid limit ordinary differential equations. We then study the selection of the parameters under the content provider's control, for the optimization of various objective functions that aim at maximizing content popularity and efficient content delivery.
Differentially Private Search Log Sanitization with Optimal Output Utility
Venue: arXiv cs.DB 2011
Year: 2011

Web search logs contain extremely sensitive data, as evidenced by the recent AOL incident. However, storing and analyzing search logs can be very useful for many purposes (i.e. investigating human behavior). Thus, an important research question is how to privately sanitize search logs. Several search log anonymization techniques have been proposed with concrete privacy models. However, in all of these solutions, the output utility of the techniques is only evaluated rather than being maximized in any fashion. Indeed, for effective search log anonymization, it is desirable to derive the optimal (maximum utility) output while meeting the privacy standard. In this paper, we propose utility-maximizing sanitization based on the rigorous privacy standard of differential privacy, in the context of search logs. Specifically, we utilize optimization models to maximize the output utility of the sanitization for different applications, while ensuring that the production process satisfies differential privacy. An added benefit is that our novel randomization strategy ensures that the schema of the output is identical to that of the input. A comprehensive evaluation on real search logs validates the approach and demonstrates its robustness and scalability.
BQP and PPAD
Venue: arXiv cs.CC 2011
Year: 2011

We initiate the study of the relationship between two complexity classes, BQP (Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument, Directed). We first give a conjecture that PPAD is contained in BQP, and show a necessary and sufficient condition for the conjecture to hold. Then we prove that the conjecture is not true under the oracle model. In the end, we raise some interesting open problems/future directions.
Modelling and Simulation of Asynchronous Real-Time Systems using Timed Rebeca
Venue: arXiv cs.SE 2011
Year: 2011

In this paper we propose an extension of the Rebeca language that can be used to model distributed and asynchronous systems with timing constraints. We provide the formal semantics of the language using Structural Operational Semantics, and show its expressiveness by means of examples. We developed a tool for automated translation from timed Rebeca to the Erlang language, which provides a first implementation of timed Rebeca. We can use the tool to set the parameters of timed Rebeca models, which represent the environment and component variables, and use McErlang to run multiple simulations for different settings. Timed Rebeca restricts the modeller to a pure asynchronous actor-based paradigm, where the structure of the model represents the service oriented architecture, while the computational model matches the network infrastructure. Simulation is shown to be an effective analysis support, specially where model checking faces almost immediate state explosion in an asynchronous setting.
Grid Information Security Functional Requirement - Fulfilling Information Security of a Smart Grid System
Venue: arXiv cs.NI 2011
Year: 2011

This paper describes the background of smart information infrastructure and the needs for smart grid information security. It introduces the conceptual analysis to the methodology with the application of hermeneutic circle and information security functional requirement identification. Information security for the grid market cover matters includes automation and communications industry that affects the operation of electric power systems and the functioning of the utilities that manage them and its awareness of this information infrastructure has become critical to the reliability of the power system. Community benefits from of cost savings, flexibility and deployment along with the establishment of wireless communications. However, concern revolves around the security protections for easily accessible devices such as the smart meter and the related communications hardware. On the other hand, the changing points between traditional versus smart grid networking trend and the information security importance on the communication field reflects the criticality of grid information security functional requirement identification. The goal of this paper is to identify the functional requirement and relate its significance addresses to the consumer requirement of an information security of a smart grid. Vulnerabilities may bring forth possibility for an attacker to penetrate a network, make headway admission to control software, alter it to load conditions that destabilize the grid in unpredictable ways. Focusing on the grid information security functional requirement is stepping ahead in developing consumer trust and satisfaction toward smart grid completeness.
Entropy Semiring Forward-backward Algorithm for HMM Entropy Computation
Venue: arXiv cs.IT 2011
Year: 2011

The paper presents Entropy Semiring Forwardbackward algorithm (ESRFB) and its application for memory efficient computation of the subsequence constrained entropy and state sequence entropy of a Hidden Markov Model (HMM) when an observation sequence is given. ESRFB is based on forward-backward recursion over the entropy semiring, having the lower memory requirement than the algorithm developed by Mann and MacCallum, with the same time complexity. Furthermore, when it is used with forward pass only, it is applicable for the computation of HMM entropy for a given observation sequence, with the same time and memory complexity as the previously developed algorithm by Hernando et al
Typesafe Modeling in Text Mining
Venue: arXiv cs.PL 2011
Year: 2011

Based on the concept of annotation-based agents, this report introduces tools and a formal notation for defining and running text mining experiments using a statically typed domain-specific language embedded in Scala. Using machine learning for classification as an example, the framework is used to develop and document text mining experiments, and to show how the concept of generic, typesafe annotation corresponds to a general information model that goes beyond text processing.
Sparse Recovery with Graph Constraints: Fundamental Limits and Measurement Construction
Venue: arXiv cs.IT 2011
Year: 2011

This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph $G$ with $n$ nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any $k$-sparse vector over $G$ ($M^G_{k,n}$). Our study suggests that $M^G_{k,n}$ may serve as a graph connectivity metric.
High-Performance Pseudo-Random Number Generation on Graphics Processing Units
Venue: arXiv cs.DC 2011
Year: 2011

This work considers the deployment of pseudo-random number generators (PRNGs) on graphics processing units (GPUs), developing an approach based on the xorgens generator to rapidly produce pseudo-random numbers of high statistical quality. The chosen algorithm has configurable state size and period, making it ideal for tuning to the GPU architecture. We present a comparison of both speed and statistical quality with other common parallel, GPU-based PRNGs, demonstrating favourable performance of the xorgens-based approach.
Spatial Dynamic Structures and Mobility in Computation
Venue: arXiv cs.DC 2011
Year: 2011

Membrane computing is a well-established and successful research field which belongs to the more general area of molecular computing. Membrane computing aims at defining parallel and non-deterministic computing models, called membrane systems or P Systems, which abstract from the functioning and structure of the cell. A membrane system consists of a spatial structure, a hierarchy of membranes which do not intersect, with a distinguishable membrane called skin surrounding all of them. A membrane without any other membranes inside is elementary, while a non-elementary membrane is a composite membrane. The membranes define demarcations between regions; for each membrane there is a unique associated region. Since we have a one-to-one correspondence, we sometimes use membrane instead of region, and vice-versa. The space outside the skin membrane is called the environment. In this thesis we define and investigate variants of systems of mobile membranes as models for molecular computing and as modelling paradigms for biological systems. On one hand, we follow the standard approach of research in membrane computing: defining a notion of computation for systems of mobile membranes, and investigating the computational power of such computing devices. Specifically, we address issues concerning the power of operations for modifying the membrane structure of a system of mobile membranes by mobility: endocytosis (moving a membrane inside a neighbouring membrane) and endocytosis (moving a membrane outside the membrane where it is placed). On the other hand, we relate systems of mobile membranes to process algebra (mobile ambients, timed mobile ambients, pi-calculus, brane calculus) by providing some encodings and adding some concepts inspired from process algebra in the framework of mobile membrane computing.
Policy Creation Model for Policy-Based Management in Telecommunications Networks
Venue: arXiv cs.NI 2011
Year: 2011

Policy-based management (PBM) is being used as technological solution on the managing and controlling complex networks and systems. One of the most important issues involved in the life-cycle of PBM is the policies creation because the future decisions made by the management system depend on this, and therefore, the network behavior. In this paper we present a novel model for creating management policies in telecommunications networks. We propose a model which includes a Policy Creation Process, Actors, Policy Abstraction Levels and a Procedure for Creating Policies. An implementation of the proposed model over the Technology Division at University of Cauca is included.
A Fault Tolerant Trajectory Clustering (FTTC) for selecting cluster heads inWireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Wireless sensor networks (WSNs) suffers from the hot spot problem where the sensor nodes closest to the base station are need to relay more packet than the nodes farther away from the base station. Thus, lifetime of sensory network depends on these closest nodes. Clustering methods are used to extend the lifetime of a wireless sensor network. However, current clustering algorithms usually utilize two techniques; selecting cluster heads with more residual energy, and rotating cluster heads periodically to distribute the energy consumption among nodes in each cluster and lengthen the network lifetime. Most of the algorithms use random selection for selecting the cluster heads. Here, we propose a Fault Tolerant Trajectory Clustering (FTTC) technique for selecting the cluster heads in WSNs. Our algorithm selects the cluster heads based on traffic and rotates periodically. It provides the first Fault Tolerant Trajectory based clustering technique for selecting the cluster heads and to extenuate the hot spot problem by prolonging the network lifetime.
Outage Constrained Robust Transmit Optimization for Multiuser MISO Downlinks: Tractable Approximations by Conic Optimization
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we consider a probabilistic signal-to-interference and-noise ratio (SINR) constrained problem for transmit beamforming design in the presence of imperfect channel state information (CSI), under a multiuser multiple-input single-output (MISO) downlink scenario. In particular, we deal with outage-based quality-of-service constraints, where the probability of each user's SINR not satisfying a service requirement must not fall below a given outage probability specification. The study of solution approaches to the probabilistic SINR constrained problem is important because CSI errors are often present in practical systems and they may cause substantial SINR outages if not handled properly. However, a major technical challenge is how to process the probabilistic SINR constraints. To tackle this, we propose a novel relaxation- restriction (RAR) approach, which consists of two key ingredients-semidefinite relaxation (SDR), and analytic tools for conservatively approximating probabilistic constraints. The underlying goal is to establish approximate probabilistic SINR constrained formulations in the form of convex conic optimization problems, so that they can be readily implemented by available solvers. Using either an intuitive worst-case argument or specialized probabilistic results, we develop various conservative approximation schemes for processing probabilistic constraints with quadratic uncertainties. Consequently, we obtain several RAR alternatives for handling the probabilistic SINR constrained problem. Our techniques apply to both complex Gaussian CSI errors and i.i.d. bounded CSI errors with unknown distribution. Moreover, results obtained from our extensive simulations show that the proposed RAR methods significantly improve upon existing ones, both in terms of solution quality and computational complexity.
On the scalability and convergence of simultaneous parameter identification and synchronization of dynamical systems
Venue: arXiv cs.SY 2011
Year: 2011

The synchronization of dynamical systems is a method that allows two systems to have identical state trajectories, appart from an error converging to zero. This method consists in an appropriate unidirectional coupling from one system (drive) to the other (response). This requires that the response system shares the same dynamical model with the drive. For the cases where the drive is unknown, Chen proposed in 2002 a method to adapt the response system such that synchronization is achieved, provided that (1) the response dynamical model is linear with a vector of parameters, and (2) there is a parameter vector that makes both system dynamics identical. However, this method has two limitations: first, it does not scale well for complex parametric models (e.g., if the number of parameters is greater than the state dimension), and second, the model parameters are not guaranteed to converge, namely as the synchronization error approaches zero. This paper presents an adaptation law addressing these two limitations. Stability and convergence proofs, using Lyapunov's second method, support the proposed adaptation law. Finally, numerical simulations illustrate the advantages of the proposed method, namely showing cases where the Chen's method fail, while the proposed one does not.
On Two-generated Non-commutative Algebras Subject to the Affine Relation
Venue: arXiv cs.SC 2011
Year: 2011

We consider algebras over a field K, generated by two variables x and y subject to the single relation yx = qxy + ax + by + c for q in K^* and a, b, c in K. We prove, that among such algebras there are precisely five isomorphism classes. The representatives of these classes, which are ubiquitous operator algebras, are called model algebras. We derive explicit multiplication formulas for y^m*x^n in terms of standard monomials x^i*y^j for many algebras of the considered type. Such formulas are used in establishing formulas of binomial type and in implementing non-commutative multiplication in a computer algebra system. By using the formulas we also study centers and ring-theoretic properties of the non-commutative model algebras.
The Impact of Information Technology in Nigeria's Banking Industry
Venue: arXiv cs.OH 2011
Year: 2011

Today, information technology (IT) has become a key element in economic development and a backbone of knowledge-based economies in terms of operations, quality delivery of services and productivity of services. Therefore, taking advantage of information technologies (IT) is an increasing challenge for developing countries. There is now growing evidence that Knowledge-driven innovation is a decisive factor in the competitiveness of nations, industries, organizations and firms. Organizations like the banking sector have benefited substantially from e-banking, which is one among the IT applications for strengthening the competitiveness. This paper presents the current trend in the application of IT in the banking industries in Nigeria and gives an insight into how quality banking has been enhanced via IT. The paper further reveals that the deployment of IT facilities in the Nigerian Banking industry has brought about fundamental changes in the content and quality of banking business in the country. This analysis and clarification of how Nigerian Banks have used IT to reengineer their operations is detailed through literature review and observation. Three categories of variables that relate to the use and implementation of information technology devices were considered in this paper. These include the nature and degree of adoption of innovative technologies; degree of utilization of the identified technologies; and the impact of the adoption of IT devices on the bank operations.
Development of a Window Based Security System for Electronic Data Interchange
Venue: arXiv cs.CR 2011
Year: 2011

The Electronic Data Interchange (EDI) is the exchange of standardized documents between computer systems for business use. The objective of this study is to make Electronic Data Interchange secure to use and to eliminate human intervention in the transfer of data between business partners so that productivity and efficiency can be improved and also promote its usage between two or more trading organizations. This paper provides an overview of EDI by describing the traditional problems of exchanging information in business environments and how the EDI solves those problems and gives benefits to the company that makes use of EDI. This paper also introduces the common EDI Standards and explains how it works, how it is used over the internet and the security measures implemented. The system was executed on both local area network and wide area network after a critical study of the existing EDI methods and also implemented using VB.Net programming language. Finally, an interactive program was developed that handles the transfer of files, with special attention to the security of the items that are being transferred from one computer workstation to another.
On generic erasure correcting sets and related problems
Venue: arXiv cs.IT 2011
Year: 2011

Motivated by iterative decoding techniques for the binary erasure channel Hollmann and Tolhuizen introduced and studied the notion of generic erasure correcting sets for linear codes. A generic $(r,s)$--erasure correcting set generates for all codes of codimension $r$ a parity check matrix that allows iterative decoding of all correctable erasure patterns of size $s$ or less. The problem is to derive bounds on the minimum size $F(r,s)$ of generic erasure correcting sets and to find constructions for such sets. In this paper we continue the study of these sets. We derive better lower and upper bounds. Hollmann and Tolhuizen also introduced the stronger notion of $(r,s)$--sets and derived bounds for their minimum size $G(r,s)$. Here also we improve these bounds. We observe that these two conceps are closely related to so called $s$--wise intersecting codes, an area, in which $G(r,s)$ has been studied primarily with respect to ratewise performance. We derive connections. Finally, we observed that hypergraph covering can be used for both problems to derive good upper bounds.
Learning Representations by Maximizing Compression
Venue: arXiv cs.CV 2011
Year: 2011

We give an algorithm that learns a representation of data through compression. The algorithm 1) predicts bits sequentially from those previously seen and 2) has a structure and a number of computations similar to an autoencoder. The likelihood under the model can be calculated exactly, and arithmetic coding can be used directly for compression. When training on digits the algorithm learns filters similar to those of restricted boltzman machines and denoising autoencoders. Independent samples can be drawn from the model by a single sweep through the pixels. The algorithm has a good compression performance when compared to other methods that work under random ordering of pixels.
Combinatorial Algorithms for Capacitated Network Design
Venue: arXiv cs.DS 2011
Year: 2011

We focus on designing combinatorial algorithms for the Capacitated Network Design problem (Cap-SNDP). The Cap-SNDP is the problem of satisfying connectivity requirements when edges have costs and hard capacities. We begin by showing that the Group Steiner tree problem (GST) is a special case of Cap-SNDP even when there is connectivity requirement between only one source-sink pair. This implies the first poly-logarithmic lower bound for the Cap-SNDP. We next provide combinatorial algorithms for several special cases of this problem. The Cap-SNDP is equivalent to its special case when every edge has either zero cost or infinite capacity. We consider a special case, called Connected Cap-SNDP, where all infinite-capacity edges in the solution are required to form a connected component containing the sinks. This problem is motivated by its similarity to the Connected Facility Location problem [G+01,SW04]. We solve this problem by reducing it to Submodular tree cover problem, which is a common generalization of Connected Cap-SNDP and Group Steiner tree problem. We generalize the recursive greedy algorithm [CEK] achieving a poly-logarithmic approximation algorithm for Submodular tree cover problem. This result is interesting in its own right and gives the first poly-logarithmic approximation algorithms for Connected hard capacities set multi-cover and Connected source location. We then study another special case of Cap-SNDP called Unbalanced point-to-point connection problem. Besides its practical applications to shift design problems [EKS], it generalizes many problems such as k-MST, Steiner Forest and Point-to-Point Connection. We give a combinatorial logarithmic approximation algorithm for this problem by reducing it to degree-bounded SNDP.