OpenRaiser/Intern-Atlas huggingface dataset:
New Combinatorial Construction Techniques for Low-Density Parity-Check Codes and Systematic Repeat-Accumulate Codes
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents several new construction techniques for low-density parity-check (LDPC) and systematic repeat-accumulate (RA) codes. Based on specific classes of combinatorial designs, the improved code design focuses on high-rate structured codes with constant column weights 3 and higher. The proposed codes are efficiently encodable and exhibit good structural properties. Experimental results on decoding performance with the sum-product algorithm show that the novel codes offer substantial practical application potential, for instance, in high-speed applications in magnetic recording and optical communications channels.
Distributed Randomized Algorithms for the PageRank Computation
Venue: arXiv cs.SY 2012
Year: 2012

In the search engine of Google, the PageRank algorithm plays a crucial role in ranking the search results. The algorithm quantifies the importance of each web page based on the link structure of the web. We first provide an overview of the original problem setup. Then, we propose several distributed randomized schemes for the computation of the PageRank, where the pages can locally update their values by communicating to those connected by links. The main objective of the paper is to show that these schemes asymptotically converge in the mean-square sense to the true PageRank values. A detailed discussion on the close relations to the multi-agent consensus problems is also given.
A Web Aggregation Approach for Distributed Randomized PageRank Algorithms
Venue: arXiv cs.SY 2012
Year: 2012

The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus.
Online Mixed Packing and Covering
Venue: arXiv cs.DS 2012
Year: 2012

In many problems, the inputs arrive over time, and must be dealt with irrevocably when they arrive. Such problems are online problems. A common method of solving online problems is to first solve the corresponding linear program, and then round the fractional solution online to obtain an integral solution. We give algorithms for solving linear programs with mixed packing and covering constraints online. We first consider mixed packing and covering linear programs, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. No prior sublinear competitive algorithms are known for this problem. We give the first such --- a polylogarithmic-competitive algorithm for solving mixed packing and covering linear programs online. We also show a nearly tight lower bound. Our techniques for the upper bound use an exponential penalty function in conjunction with multiplicative updates. While exponential penalty functions are used previously to solve linear programs offline approximately, offline algorithms know the constraints beforehand and can optimize greedily. In contrast, when constraints arrive online, updates need to be more complex. We apply our techniques to solve two online fixed-charge problems with congestion. These problems are motivated by applications in machine scheduling and facility location. The linear program for these problems is more complicated than mixed packing and covering, and presents unique challenges. We show that our techniques combined with a randomized rounding procedure give polylogarithmic-competitive integral solutions. These problems generalize online set-cover, for which there is a polylogarithmic lower bound. Hence, our results are close to tight.
System Identification for Indoor Climate Control
Venue: arXiv cs.CE 2012
Year: 2012

The study focuses on the applicability of system identification to identify building and system dynamics for climate control design. The main problem regarding the simulation of the dynamic response of a building using building simulation software is that (1) the simulation of a large complex building is time consuming, and (2) simulation results often lack information regarding fast dynamic behaviour (in the order of seconds), since most software uses a discrete time step, usually fixed to one hour. The first objective is to study the applicability of system identification to reduce computing time for the simulation of large complex buildings. The second objective is to research the applicability of system identification to identify building dynamics based on discrete time data (one hour) for climate control design. The study illustrates that system identification is applicable for the identification of building dynamics with a frequency that is smaller as the maximum sample frequency as used for identification. The research shows that system identification offers good perspectives for the modelling of heat, air and moisture processes in a building. The main advantages of system identification models compared to the modelling of building dynamics using building simulation software are, that (1) the computing time is reduced significantly, and (2) system identification models run in a MATLAB environment, in which many building simulation tools have been developed
Extended Equal Service and Differentiated Service Models for Peer-to-Peer File Sharing
Venue: arXiv cs.NI 2012
Year: 2012

Peer-to-Peer (P2P) systems have proved to be the most effective and popular file sharing applications in recent years. Previous studies mainly focus on the equal service and the differentiated service strategies when peers have no initial data before their download. In an upload-constrained P2P file sharing system, we model both the equal service process and the differentiated service process when peers' initial data distribution satisfies some special conditions, and also show how to minimize the time to get the file to any number of peers. The proposed models can reveal the intrinsic relations among the initial data amount, the size of peer set and the minimum last finish time. By using the models, we can also provide arbitrary degree of differentiated service to a certain number of peers. We believe that our analysis process and achieved theoretical results could provide fundamental insights into studies on bandwidth allocation and data scheduling, and can give helpful reference both for improving system performance and building effective incentive mechanism in P2P file sharing systems.
Efficient Computation of Sensitivity Coefficients of Node Voltages and Line Currents in Unbalanced Radial Electrical Distribution Networks
Venue: arXiv cs.SY 2012
Year: 2012

The problem of optimal control of power distribution systems is becoming increasingly compelling due to the progressive penetration of distributed energy resources in this specific layer of the electrical infrastructure. Distribution systems are, indeed, experiencing significant changes in terms of operation philosophies that are often based on optimal control strategies relying on the computation of linearized dependencies between controlled (e.g. voltages, frequency in case of islanding operation) and control variables (e.g. power injections, transformers tap positions). As the implementation of these strategies in real-time controllers imposes stringent time constraints, the derivation of analytical dependency between controlled and control variables becomes a non-trivial task to be solved. With reference to optimal voltage and power flow controls, this paper aims at providing an analytical derivation of node voltage and line current flows as a function of the nodal power injections and transformers tap-changers positions. Compared to other approaches presented in the literature, the one proposed here is based on the use of the [Y] compound matrix of a generic multi-phase radial unbalanced network. In order to estimate the computational benefits of the proposed approach, the relevant improvements are also quantified versus traditional methods. The validation of the proposed method is carried out by using both IEEE 13 and 34 node test feeders. The paper finally shows the use of the proposed method for the problem of optimal voltage control applied to the IEEE 34 node test feeder.
MIMO Z Channel Interference Management
Venue: arXiv cs.IT 2012
Year: 2012

MIMO Z Channel is investigated in this paper. We focus on how to tackle the interference when different users try to send their codewords to their corresponding receivers while only one user will cause interference to the other. We assume there are two transmitters and two receivers each with two antennas. We propose a strategy to remove the interference while allowing different users transmit at the same time. Our strategy is low-complexity while the performance is good. Mathematical analysis is provided and simulations are given based on our system.
Ordered Counter-Abstraction
Venue: arXiv cs.LO 2012
Year: 2012

We introduce a new symbolic representation based on an original generalization of counter abstraction. Unlike classical counter abstraction (used in the analysis of parameterized systems with unordered or unstructured topologies) the new representation is tailored for proving properties of linearly ordered parameterized systems, i.e., systems with arbitrary many finite processes placed in an array. The relative positions in the array capture the relative priorities of the processes. Configurations of such systems are finite words of arbitrary lengths. The processes communicate using global transitions constrained by their relative priorities. Intuitively, an element of the symbolic representation has a base and a set of counters. It denotes configurations that respect the constraints imposed by the counters and that have the base as a sub word. We use the new representation in a uniform and automatic Counter Example Guided Refinement scheme. We introduce a relaxation operator that allows a well quasi ordering argument for the termination of each iteration of the refinement loop. We explain how to refine the relaxation to systematically prune out false positives. We implemented a tool to illustrate the approach on a number of parameterized systems.
Rebels Lead to the Doctrine of the Mean: Opinion Dynamic in a Heterogeneous DeGroot Model
Venue: arXiv cs.SI 2012
Year: 2012

We study an extension of the DeGroot model where part of the players may be rebels. The updating rule for rebels is quite different with that of normal players (which are referred to as conformists): at each step a rebel first takes the opposite value of the weighted average of her neighbors' opinions, i.e. 1 minus that average (the opinion space is assumed to be [0,1] as usual), and then updates her opinion by taking another weighted average between that value and her own opinion in the last round. We find that the effect of rebels is rather significant: as long as there is at least one rebel in every closed and strongly connected group, under very weak conditions, the opinion of each player in the whole society will eventually tend to 0.5.
Using Fuzzy Logic to Evaluate Normalization Completeness for An Improved Database Design
Venue: arXiv cs.DB 2012
Year: 2012

A new approach, to measure normalization completeness for conceptual model, is introduced using quantitative fuzzy functionality in this paper. We measure the normalization completeness of the conceptual model in two steps. In the first step, different normalization techniques are analyzed up to Boyce Codd Normal Form (BCNF) to find the current normal form of the relation. In the second step, fuzzy membership values are used to scale the normal form between 0 and 1. Case studies to explain schema transformation rules and measurements. Normalization completeness is measured by considering completeness attributes, preventing attributes of the functional dependencies and total number of attributes such as if the functional dependency is non-preventing then the attributes of that functional dependency are completeness attributes. The attributes of functional dependency which prevent to go to the next normal form are called preventing attributes.
Expert PC Troubleshooter With Fuzzy-Logic And Self-Learning Support
Venue: arXiv cs.AI 2012
Year: 2012

Expert systems use human knowledge often stored as rules within the computer to solve problems that generally would entail human intelligence. Today, with information systems turning out to be more pervasive and with the myriad advances in information technologies, automating computer fault diagnosis is becoming so fundamental that soon every enterprise has to endorse it. This paper proposes an expert system called Expert PC Troubleshooter for diagnosing computer problems. The system is composed of a user interface, a rule-base, an inference engine, and an expert interface. Additionally, the system features a fuzzy-logic module to troubleshoot POST beep errors, and an intelligent agent that assists in the knowledge acquisition process. The proposed system is meant to automate the maintenance, repair, and operations (MRO) process, and free-up human technicians from manually performing routine, laborious, and timeconsuming maintenance tasks. As future work, the proposed system is to be parallelized so as to boost its performance and speed-up its various operations.
OCR Context-Sensitive Error Correction Based on Google Web 1T 5-Gram Data Set
Venue: arXiv cs.CL 2012
Year: 2012

Since the dawn of the computing era, information has been represented digitally so that it can be processed by electronic computers. Paper books and documents were abundant and widely being published at that time; and hence, there was a need to convert them into digital format. OCR, short for Optical Character Recognition was conceived to translate paper-based books into digital e-books. Regrettably, OCR systems are still erroneous and inaccurate as they produce misspellings in the recognized text, especially when the source document is of low printing quality. This paper proposes a post-processing OCR context-sensitive error correction method for detecting and correcting non-word and real-word OCR errors. The cornerstone of this proposed approach is the use of Google Web 1T 5-gram data set as a dictionary of words to spell-check OCR text. The Google data set incorporates a very large vocabulary and word statistics entirely reaped from the Internet, making it a reliable source to perform dictionary-based error correction. The core of the proposed solution is a combination of three algorithms: The error detection, candidate spellings generator, and error correction algorithms, which all exploit information extracted from Google Web 1T 5-gram data set. Experiments conducted on scanned images written in different languages showed a substantial improvement in the OCR error correction rate. As future developments, the proposed algorithm is to be parallelised so as to support parallel and distributed computing architectures.
Managing contextual artificial neural networks with a service-based mediator
Venue: arXiv cs.NE 2012
Year: 2012

Today, a wide variety of probabilistic and expert AI systems used to analyze real world inputs such as unstructured text, sounds, images, and statistical data. However, all these systems exist on different platforms, with different implementations, and with very different, often very specific goals in mind. This paper introduces a concept for a mediator framework for such systems and seeks to show several architectures which would support it, potential benefits in combining the signals of disparate networks for formalized, high level logic and signal processing, and its possible academic and industrial uses.
Skull-stripping for Tumor-bearing Brain Images
Venue: arXiv cs.CV 2012
Year: 2012

Skull-stripping separates the skull region of the head from the soft brain tissues. In many cases of brain image analysis, this is an essential preprocessing step in order to improve the final result. This is true for both registration and segmentation tasks. In fact, skull-stripping of magnetic resonance images (MRI) is a well-studied problem with numerous publications in recent years. Many different algorithms have been proposed, a summary and comparison of which can be found in [Fennema-Notestine, 2006]. Despite the abundance of approaches, we discovered that the algorithms which had been suggested so far, perform poorly when dealing with tumor-bearing brain images. This is mostly due to additional difficulties in separating the brain from the skull in this case, especially when the lesion is located very close to the skull border. Additionally, images acquired according to standard clinical protocols, often exhibit anisotropic resolution and only partial coverage, which further complicates the task. Therefore, we developed a method which is dedicated to skull-stripping for clinically acquired tumor-bearing brain images.
Time Synchronization Attack in Smart Grid-Part II: Cross Layer Detection Mechanism
Venue: arXiv cs.CR 2012
Year: 2012

A novel time synchronization attack (TSA) on wide area monitoring systems in smart grid has been identified in the first part of this paper. A cross layer detection mechanism is proposed to combat TSA in part II of this paper. In the physical layer, we propose a GPS carrier signal noise ratio (C/No) based spoofing detection technique. In addition, a patch-monopole hybrid antenna is applied to receive GPS signal. By computing the standard deviation of the C/No difference from two GPS receivers, a priori probability of spoofing detection is fed to the upper layer, where power system state is estimated and controlled. A trustworthiness based evaluation method is applied to identify the PMU being under TSA. Both the physical layer and upper layer algorithms are integrated to detect the TSA, thus forming a cross layer mechanism. Experiment is carried out to verify the effectiveness of the proposed TSA detection algorithm.
A collaborative ant colony metaheuristic for distributed multi-level lot-sizing
Venue: arXiv cs.AI 2012
Year: 2012

The paper presents an ant colony optimization metaheuristic for collaborative planning. Collaborative planning is used to coordinate individual plans of self-interested decision makers with private information in order to increase the overall benefit of the coalition. The method consists of a new search graph based on encoded solutions. Distributed and private information is integrated via voting mechanisms and via a simple but effective collaborative local search procedure. The approach is applied to a distributed variant of the multi-level lot-sizing problem and evaluated by means of 352 benchmark instances from the literature. The proposed approach clearly outperforms existing approaches on the sets of medium and large sized instances. While the best method in the literature so far achieves an average deviation from the best known non-distributed solutions of 46 percent for the set of the largest instances, for example, the presented approach reduces the average deviation to only 5 percent.
On the number of radial orderings of planar point sets
Venue: arXiv cs.CG 2012
Year: 2012

Given a set $S$ of $n$ points in the plane, a \emph{radial ordering} of $S$ with respect to a point $p$ (not in $S$) is a clockwise circular ordering of the elements in $S$ by angle around $p$. If $S$ is two-colored, a \emph{colored radial ordering} is a radial ordering of $S$ in which only the colors of the points are considered. In this paper, we obtain bounds on the number of distinct non-colored and colored radial orderings of $S$. We assume a strong general position on $S$, not three points are collinear and not three lines---each passing through a pair of points in $S$---intersect in a point of $\R^2\setminus S$. In the colored case, $S$ is a set of $2n$ points partitioned into $n$ red and $n$ blue points, and $n$ is even. We prove that: the number of distinct radial orderings of $S$ is at most $O(n^4)$ and at least $Ω(n^3)$; the number of colored radial orderings of $S$ is at most $O(n^4)$ and at least $Ω(n)$; there exist sets of points with $Θ(n^4)$ colored radial orderings and sets of points with only $O(n^2)$ colored radial orderings.
Multi-level agent-based modeling with the Influence Reaction principle
Venue: arXiv cs.MA 2012
Year: 2012

This paper deals with the specification and the implementation of multi-level agent-based models, using a formal model, IRM4MLS (an Influence Reaction Model for Multi-Level Simulation), based on the Influence Reaction principle. Proposed examples illustrate forms of top-down control in (multi-level) multi-agent based-simulations.
Compressed Sensing for Denoising in Adaptive System Identification
Venue: arXiv cs.IT 2012
Year: 2012

We propose a new technique for adaptive identification of sparse systems based on the compressed sensing (CS) theory. We manipulate the transmitted pilot (input signal) and the received signal such that the weights of adaptive filter approach the compressed version of the sparse system instead of the original system. To this end, we use random filter structure at the transmitter to form the measurement matrix according to the CS framework. The original sparse system can be reconstructed by the conventional recovery algorithms. As a result, the denoising property of CS can be deployed in the proposed method at the recovery stage. The experiments indicate significant performance improvement of proposed method compared to the conventional LMS method which directly identifies the sparse system. Furthermore, at low levels of sparsity, our method outperforms a specialized identification algorithm that promotes sparsity.
Bounded Counter Languages
Venue: arXiv cs.FL 2012
Year: 2012

We show that deterministic finite automata equipped with $k$ two-way heads are equivalent to deterministic machines with a single two-way input head and $k-1$ linearly bounded counters if the accepted language is strictly bounded, i.e., a subset of $a_1^*a_2^*... a_m^*$ for a fixed sequence of symbols $a_1, a_2,..., a_m$. Then we investigate linear speed-up for counter machines. Lower and upper time bounds for concrete recognition problems are shown, implying that in general linear speed-up does not hold for counter machines. For bounded languages we develop a technique for speeding up computations by any constant factor at the expense of adding a fixed number of counters.
Densities and entropies in cellular automata
Venue: arXiv cs.CC 2012
Year: 2012

Following work by Hochman and Meyerovitch on multidimensional SFT, we give computability-theoretic characterizations of the real numbers that can appear as the topological entropies of one-dimensional and two-dimensional cellular automata.