OpenRaiser/Intern-Atlas huggingface dataset:
Statistical Distortion: Consequences of Data Cleaning
Venue: arXiv cs.DB 2012
Year: 2012

We introduce the notion of statistical distortion as an essential metric for measuring the effectiveness of data cleaning strategies. We use this metric to propose a widely applicable yet scalable experimental framework for evaluating data cleaning strategies along three dimensions: glitch improvement, statistical distortion and cost-related criteria. Existing metrics focus on glitch improvement and cost, but not on the statistical impact of data cleaning strategies. We illustrate our framework on real world data, with a comprehensive suite of experiments and analyses.
Scheduling Data Intensive Workloads through Virtualization on MapReduce based Clouds
Venue: arXiv cs.DC 2012
Year: 2012

MapReduce has become a popular programming model for running data intensive applications on the cloud. Completion time goals or deadlines of MapReduce jobs set by users are becoming crucial in existing cloud-based data processing environments like Hadoop. There is a conflict between the scheduling MR jobs to meet deadlines and "data locality" (assigning tasks to nodes that contain their input data). To meet the deadline a task may be scheduled on a node without local input data for that task causing expensive data transfer from a remote node. In this paper, a novel scheduler is proposed to address the above problem which is primarily based on the dynamic resource reconfiguration approach. It has two components: 1) Resource Predictor: which dynamically determines the required number of Map/Reduce slots for every job to meet completion time guarantee; 2) Resource Reconfigurator: that adjusts the CPU resources while not violating completion time goals of the users by dynamically increasing or decreasing individual VMs to maximize data locality and also to maximize the use of resources within the system among the active jobs. The proposed scheduler has been evaluated against Fair Scheduler on virtual cluster built on a physical cluster of 20 machines. The results demonstrate a gain of about 12% increase in throughput of Jobs
Comparison between Performances of Channel Estimation Techniques for CP-LTE and ZP-LTE Downlink Systems
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we propose to evaluate the performance of channel estimation techniques for Long Term Evolution (LTE) Downlink systems based on Zero Padding technique (ZP) instead of Cyclic Prefixing (CP). LTE Downlink system is a multiuser system based on a MIMO-OFDMA technology. Usually, in OFDM systems, a guard interval is inserted in order to mitigate both inter-carrier interference (ICI) and inter-symbol interference (ISI). LTE Downlink systems are based on CP-OFDM technique which consists of a copy a last OFDM symbols inserted at the beginning of each transmitted OFDM symbol. Although this technique shows good performances, the CP-LTE system suffers from a power efficiency loss.With the number of present OFDM symbols in LTE Downlink radio frame, the bandwidth loss becomes more important. Instead of CP, we propose to evaluate the performance of ZP-LTE systems in order to avoid the power efficiency .In this paper, we interest to evaluate the performance of channel estimation techniques for the two LTE Downlink systems. Simulations results show that although ZP-LTE systems outperform CP-LTE Downlink systems in terms of power efficiency, the CP-LTE systems show better performance than ZP-LTE systems and especially for high SNR values. MATLAB Monte-Carlo simulations are used to evaluate the performance of LS, LMMSE and Lr-LMMSE estimators in terms of Mean Square Error (MSE) and Bit Error Rate (BER) for 2x2 LTE Downlink systems.
Non-homogeneous distributed storage systems
Venue: arXiv cs.IT 2012
Year: 2012

This paper describes a non-homogeneous distributed storage systems (DSS), where there is one super node which has a larger storage size and higher reliability and availability than the other storage nodes. We propose three distributed storage schemes based on (k+2; k) maximum distance separable (MDS) codes and non-MDS codes to show the efficiency of such non-homogeneous DSS in terms of repair efficiency and data availability. Our schemes achieve optimal bandwidth (k+1/2)(M/k) when repairing 1-node failure, but require only one fourth of the minimum required file size and can operate with a smaller field size leading to significant complexity reduction than traditional homogeneous DSS. Moreover, with non-MDS codes, our scheme can achieve an even smaller repair bandwidth of M/2k . Finally, we show that our schemes can increase the data availability by 10% than the traditional homogeneous DSS scheme.
Brain tumor MRI image classification with feature selection and extraction using linear discriminant analysis
Venue: arXiv cs.CV 2012
Year: 2012

Feature extraction is a method of capturing visual content of an image. The feature extraction is the process to represent raw image in its reduced form to facilitate decision making such as pattern classification. We have tried to address the problem of classification MRI brain images by creating a robust and more accurate classifier which can act as an expert assistant to medical practitioners. The objective of this paper is to present a novel method of feature selection and extraction. This approach combines the Intensity, Texture, shape based features and classifies the tumor as white matter, Gray matter, CSF, abnormal and normal area. The experiment is performed on 140 tumor contained brain MR images from the Internet Brain Segmentation Repository. The proposed technique has been carried out over a larger database as compare to any previous work and is more robust and effective. PCA and Linear Discriminant Analysis (LDA) were applied on the training sets. The Support Vector Machine (SVM) classifier served as a comparison of nonlinear techniques Vs linear ones. PCA and LDA methods are used to reduce the number of features used. The feature selection using the proposed technique is more beneficial as it analyses the data according to grouping class variable and gives reduced feature set with high classification accuracy.
Curved Space Optimization: A Random Search based on General Relativity Theory
Venue: arXiv cs.NE 2012
Year: 2012

Designing a fast and efficient optimization method with local optima avoidance capability on a variety of optimization problems is still an open problem for many researchers. In this work, the concept of a new global optimization method with an open implementation area is introduced as a Curved Space Optimization (CSO) method, which is a simple probabilistic optimization method enhanced by concepts of general relativity theory. To address global optimization challenges such as performance and convergence, this new method is designed based on transformation of a random search space into a new search space based on concepts of space-time curvature in general relativity theory. In order to evaluate the performance of our proposed method, an implementation of CSO is deployed and its results are compared on benchmark functions with state-of-the art optimization methods. The results show that the performance of CSO is promising on unimodal and multimodal benchmark functions with different search space dimension sizes.
Minimal TestCase Generation for Object-Oriented Software with State Charts
Venue: arXiv cs.SE 2012
Year: 2012

Today statecharts are a de facto standard in industry for modeling system behavior. Test data generation is one of the key issues in software testing. This paper proposes an reduction approach to test data generation for the state-based software testing. In this paper, first state transition graph is derived from state chart diagram. Then, all the required information are extracted from the state chart diagram. Then, test cases are generated. Lastly, a set of test cases are minimized by calculating the node coverage for each test case. It is also determined that which test cases are covered by other test cases. The advantage of our test generation technique is that it optimizes test coverage by minimizing time and cost. The present test data generation scheme generates test cases which satisfy transition path coverage criteria, path coverage criteria and action coverage criteria. A case study on Railway Ticket Vending Machine (RTVM) has been presented to illustrate our approach.
Balancing Lifetime and Classification Accuracy of Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

Wireless sensor networks are composed of distributed sensors that can be used for signal detection or classification. The likelihood functions of the hypotheses are often not known in advance, and decision rules have to be learned via supervised learning. A specific such algorithm is Fisher discriminant analysis (FDA), the classification accuracy of which has been previously studied in the context of wireless sensor networks. Previous work, however, does not take into account the communication protocol or battery lifetime of the sensor networks; in this paper we extend the existing studies by proposing a model that captures the relationship between battery lifetime and classification accuracy. In order to do so we combine the FDA with a model that captures the dynamics of the Carrier-Sense Multiple-Access (CSMA) algorithm, the random-access algorithm used to regulate communications in sensor networks. This allows us to study the interaction between the classification accuracy, battery lifetime and effort put towards learning, as well as the impact of the back-off rates of CSMA on the accuracy. We characterize the tradeoff between the length of the training stage and accuracy, and show that accuracy is non-monotone in the back-off rate due to changes in the training sample size and overfitting.
A Novel Feature-Based Approach to Characterize Algorithm Performance for the Traveling Salesman Problem
Venue: arXiv cs.DS 2012
Year: 2012

Meta-heuristics are frequently used to tackle NP-hard combinatorial optimization problems. With this paper we contribute to the understanding of the success of 2-opt based local search algorithms for solving the traveling salesman problem (TSP). Although 2-opt is widely used in practice, it is hard to understand its success from a theoretical perspective. We take a statistical approach and examine the features of TSP instances that make the problem either hard or easy to solve. As a measure of problem difficulty for 2-opt we use the approximation ratio that it achieves on a given instance. Our investigations point out important features that make TSP instances hard or easy to be approximated by 2-opt.
Lexicodes over Rings
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider the construction of linear lexicodes over finite chain rings by using a $B$-ordering over these rings and a selection criterion. % and a greedy Algorithm. As examples we give lexicodes over $\mathbb{Z}_4$ and $\mathbb{F}_2+u\mathbb{F}_2$. %First, greedy algorithms are presented to construct %lexicodes using a multiplicative property. Then, greedy algorithms %are given for the case when the selection criteria is not %multiplicative such as the minimum distance constraint. It is shown that this construction produces many optimal codes over rings and also good binary codes. Some of these codes meet the Gilbert bound. We also obtain optimal self-dual codes, in particular the octacode.
Optimal Number of Cluster Head Selection for Efficient Distribution of Sources in WSNs
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we compare problems of cluster formation and cluster-head selection between different protocols for data aggregation and transmission. We focus on two aspects of the problem: (i) how to guess number of clusters required to proficiently consume available sources for a sensor network, and (ii) how to select number of cluster-heads to cover up sensor networks more proficiently. A sensor in Wireless Sensor Networks (WSNs) can communicate directly only with other sensors that are within a radio range in a cluster. However, in order to enable communication between sensors not within communication range, they must form new clusters in distributed sensors. Several clustering algorithms such as LEACH, DEEC, and SEP have been proposed with the objectives of energy minimization, route-path selection, increased connectivity and network longevity. LEACH protocol and the similar ones assume an energy homogeneous system where a node is not likely to fail due to failure in connectivity and packet dropping. More recent protocols like SEP and TEEN considered the reverse that is energy heterogeneity which is more applicable to case of WSNs. We developed a bi-dimensional chain model to select average number of for DEEC. Simulation results are used to compare performance of different protocols to found optimal solutions of above mentioned problems.
On Generalized Fuzzy Multisets and their Use in Computation
Venue: arXiv cs.LO 2012
Year: 2012

An orthogonal approach to the fuzzification of both multisets and hybrid sets is presented. In particular, we introduce L-multi-fuzzy and L-fuzzy hybrid sets, which are general enough and in spirit with the basic concepts of fuzzy set theory. In addition, we study the properties of these structures. Also, the usefulness of these structures is examined in the framework of mechanical multiset processing. More specifically, we introduce a variant of fuzzy P systems and, since simple fuzzy membrane systems have been introduced elsewhere, we simply extend previously stated results and ideas.
Error Probability of OSTB Codes and Capacity Analysis with Antenna Selection over Single-Antenna AF Relay Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, the symbol error rate (SER) and the bit error rate (BER) of orthogonal space-time block codes (OSTBCs) and their achievable capacity over an amplify-and-forward (AF) relay channel with multiple antennas at source and destination and single antenna at relay node are investigated. Considered are receive antenna selection, transmit antenna selection, and joint antenna selection at both the transmitter and the receiver. The exact SERs of OSTBCs for M-PSK and square M-QAM constellations are obtained using the moment generating functions (MGFs). Also, we analyze the achievable capacity over such channels assuming antenna selection is done at the source and relay nodes. We show that a small number of selected antennas can achieve the capacity of the system in which no channel state information (CSI) is available at the source and relay nodes.
Doing More for Less -- Cache-Aware Parallel Contraction Hierarchies Preprocessing
Venue: arXiv cs.DS 2012
Year: 2012

Contraction Hierarchies is a successful speedup-technique to Dijkstra's seminal shortest path algorithm that has a convenient trade-off between preprocessing and query times. We investigate a shared-memory parallel implementation that uses $O(n+m)$ space for storing the graph and O(1) space for each core during preprocessing. The presented data structures and algorithms consequently exploits cache locality and thus exhibit competitive preprocessing times. The presented implementation is especially suitable for preprocessing graphs of planet-wide scale in practice. Also, our experiments show that optimal data structures in the PRAM model can be beaten in practice by exploiting memory cache hierarchies.
Empowered Customers in E-Health Business Process
Venue: arXiv cs.OH 2012
Year: 2012

E-health innovations support empowered customers. It offers the ability for customers to have greater control and ready access applications of health information, clinical information, and social interaction between interested groups. However, providing empowerment in any state of interaction levels to customers (patients) in a healthcare organization is challenging tasks. Customers are empowered in the sense of controlling the process of interaction between a firm with its customers, and among customers themselves. This paper discusses dimension of customers' empowerment in e-health business process. We propose reference model of Personal Health Cycle (PHC) as a holistic view of healthcare business process. The PHC is used to define and distinct electronic health record (EHR) from electronic medical record (EMR) and customers empowerment.
Hereditary properties of permutations are strongly testable
Venue: arXiv cs.DM 2012
Year: 2012

We show that for every hereditary permutation property P and every eps>0, there exists an integer M such that if a permutation p is eps-far from P in the Kendall's tau distance, then a random subpermutation of p of order M has the property P with probability at most eps. This settles an open problem whether hereditary permutation properties are strongly testable, i.e., testable with respect to the Kendall's tau distance. In addition, our method also yields a proof of a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio on the relation of the rectangular distance and the Kendall's tau distance of a permutation from a hereditary property.
Shannon Information Theory Without Shedding Tears Over Delta \& Epsilon Proofs or Typical Sequences
Venue: arXiv cs.IT 2012
Year: 2012

This paper begins with a discussion of integration over probability types (p-types). After doing that, the paper re-visits 3 mainstay problems of classical (non-quantum) Shannon Information Theory (SIT): source coding without distortion, channel coding, and source coding with distortion. The paper proves well-known, conventional results for each of these 3 problems. However, the proofs given for these results are not conventional. They are based on complex integration techniques (approximations obtained by applying the method of steepest descent to p-type integrals) instead of the usual delta & epsilon and typical sequences arguments. Another unconventional feature of this paper is that we make ample use of classical Bayesian networks (CB nets). This paper showcases some of the benefits of using CB nets to do classical SIT.
On the specification of operations on the rational behaviour of systems
Venue: arXiv cs.LO 2012
Year: 2012

Structural operational semantics can be studied at the general level of distributive laws of syntax over behaviour. This yields specification formats for well-behaved algebraic operations on final coalgebras, which are a domain for the behaviour of all systems of a given type functor. We introduce a format for specification of algebraic operations that restrict to the rational fixpoint of a functor, which captures the behaviour of finite systems. In other words, we show that rational behaviour is closed under operations specified in our format. As applications we consider operations on regular languages, regular processes and finite weighted transition systems.
Entry times in automata with simple defect dynamics
Venue: arXiv cs.FL 2012
Year: 2012

In this paper, we consider a simple cellular automaton with two particles of different speeds that annihilate on contact. Following a previous work by K\r urka et al., we study the asymptotic distribution, starting from a random configuration, of the waiting time before a particle crosses the central column after time n. Drawing a parallel between the behaviour of this automata on a random initial configuration and a certain random walk, we approximate this walk using a Brownian motion, and we obtain explicit results for a wide class of initial measures and other automata with similar dynamics.
Intrinsic Simulations between Stochastic Cellular Automata
Venue: arXiv cs.FL 2012
Year: 2012

The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in a unifying and composable manner. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the caracterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.
Boolean networks synchronism sensitivity and XOR circulant networks convergence time
Venue: arXiv cs.FL 2012
Year: 2012

In this paper are presented first results of a theoretical study on the role of non-monotone interactions in Boolean automata networks. We propose to analyse the contribution of non-monotony to the diversity and complexity in their dynamical behaviours according to two axes. The first one consists in supporting the idea that non-monotony has a peculiar influence on the sensitivity to synchronism of such networks. It leads us to the second axis that presents preliminary results and builds an understanding of the dynamical behaviours, in particular concerning convergence times, of specific non-monotone Boolean automata networks called XOR circulant networks.
Strictly Temporally Periodic Points in Cellular Automata
Venue: arXiv cs.FL 2012
Year: 2012

We study the set of strictly periodic points in surjective cellular automata, i.e., the set of those configurations which are temporally periodic for a given automaton but they not spatially periodic. This set turns out to be dense for almost equicontinuous surjective cellular automata while it is empty for the positively expansive ones. In the class of additive cellular automata, the set of strictly periodic points can be either dense or empty. The latter happens if and only if the cellular automaton is topologically transitive.
Mapping Strategies for the PERCS Architecture
Venue: arXiv cs.DC 2012
Year: 2012

The PERCS system was designed by IBM in response to a DARPA challenge that called for a high-productivity high-performance computing system. The IBM PERCS architecture is a two level direct network having low diameter and high bisection bandwidth. Mapping and routing strategies play an important role in the performance of applications on such a topology. In this paper, we study mapping strategies for PERCS architecture, that examine how to map tasks of a given job on to the physical processing nodes. We develop and present fundamental principles for designing good mapping strategies that minimize congestion. This is achieved via a theoretical study of some common communication patterns under both direct and indirect routing mechanisms supported by the architecture.