OpenRaiser/Intern-Atlas huggingface dataset:
A Graphical Language for Proof Strategies
Venue: arXiv cs.LO 2013
Year: 2013

Complex automated proof strategies are often difficult to extract, visualise, modify, and debug. Traditional tactic languages, often based on stack-based goal propagation, make it easy to write proofs that obscure the flow of goals between tactics and are fragile to minor changes in input, proof structure or changes to tactics themselves. Here, we address this by introducing a graphical language called PSGraph for writing proof strategies. Strategies are constructed visually by "wiring together" collections of tactics and evaluated by propagating goal nodes through the diagram via graph rewriting. Tactic nodes can have many output wires, and use a filtering procedure based on goal-types (predicates describing the features of a goal) to decide where best to send newly-generated sub-goals. In addition to making the flow of goal information explicit, the graphical language can fulfil the role of many tacticals using visual idioms like branching, merging, and feedback loops. We argue that this language enables development of more robust proof strategies and provide several examples, along with a prototype implementation in Isabelle.
Optimum Header Positioning in Successive Interference Cancellation (SIC) based Aloha
Venue: arXiv cs.IT 2013
Year: 2013

Random Access MAC protocols are simple and effective when the nature of the traffic is unpredictable and sporadic. In the following paper, investigations on the new Enhanced Contention Resolution ALOHA (ECRA) are presented, where some new aspects of the protocol are investigated. Mathematical derivation and numerical evaluation of the symbol interference probability after SIC are here provided. Results of the optimum header positioning which is found to be in the beginning and in the end of the packets, are exploited for the evaluation of ECRA throughput and Packet Error Rate (PER) under imperfect knowledge of packets positions. Remarkable gains in the maximum throughput are observed for ECRA w.r.t. Contention Resolution ALOHA (CRA) under this assumption.
Ensemble Sparse Models for Image Analysis
Venue: arXiv cs.CV 2013
Year: 2013

Sparse representations with learned dictionaries have been successful in several image analysis applications. In this paper, we propose and analyze the framework of ensemble sparse models, and demonstrate their utility in image restoration and unsupervised clustering. The proposed ensemble model approximates the data as a linear combination of approximations from multiple \textit{weak} sparse models. Theoretical analysis of the ensemble model reveals that even in the worst-case, the ensemble can perform better than any of its constituent individual models. The dictionaries corresponding to the individual sparse models are obtained using either random example selection or boosted approaches. Boosted approaches learn one dictionary per round such that the dictionary learned in a particular round is optimized for the training examples having high reconstruction error in the previous round. Results with compressed recovery show that the ensemble representations lead to a better performance compared to using a single dictionary obtained with the conventional alternating minimization approach. The proposed ensemble models are also used for single image superresolution, and we show that they perform comparably to the recent approaches. In unsupervised clustering, experiments show that the proposed model performs better than baseline approaches in several standard datasets.
KSU KDD: Word Sense Induction by Clustering in Topic Space
Venue: arXiv cs.CL 2013
Year: 2013

We describe our language-independent unsupervised word sense induction system. This system only uses topic features to cluster different word senses in their global context topic space. Using unlabeled data, this system trains a latent Dirichlet allocation (LDA) topic model then uses it to infer the topics distribution of the test instances. By clustering these topics distributions in their topic space we cluster them into different senses. Our hypothesis is that closeness in topic space reflects similarity between different word senses. This system participated in SemEval-2 word sense induction and disambiguation task and achieved the second highest V-measure score among all other systems.
A null space property approach to compressed sensing with frames
Venue: arXiv cs.IT 2013
Year: 2013

An interesting topic in compressive sensing concerns problems of sensing and recovering signals with sparse representations in a dictionary. In this note, we study conditions of sensing matrices A for the L1-synthesis method to accurately recover sparse, or nearly sparse signals in a given dictionary D. In particular, we propose a dictionary based null space property (D-NSP) which, to the best of our knowledge, is the first sufficient and necessary condition for the success of the L1 recovery. This new property is then utilized to detect some of those dictionaries whose sparse families cannot be compressed universally. Moreover, when the dictionary is full spark, we show that AD being NSP, which is well-known to be only sufficient for stable recovery via L1-synthesis method, is indeed necessary as well.
K Means Segmentation of Alzheimers Disease in PET scan datasets: An implementation
Venue: arXiv cs.CV 2013
Year: 2013

The Positron Emission Tomography (PET) scan image requires expertise in the segmentation where clustering algorithm plays an important role in the automation process. The algorithm optimization is concluded based on the performance, quality and number of clusters extracted. This paper is proposed to study the commonly used K Means clustering algorithm and to discuss a brief list of toolboxes for reproducing and extending works presented in medical image analysis. This work is compiled using AForge .NET framework in windows environment and MATrix LABoratory (MATLAB 7.0.1)
Coalitional Game Theoretic Approach for Cooperative Transmission in Vehicular Networks
Venue: arXiv cs.GT 2013
Year: 2013

Cooperative transmission in vehicular networks is studied by using coalitional game and pricing in this paper. There are several vehicles and roadside units (RSUs) in the networks. Each vehicle has a desire to transmit with a certain probability, which represents its data burtiness. The RSUs can enhance the vehicles' transmissions by cooperatively relaying the vehicles' data. We consider two kinds of cooperations: cooperation among the vehicles and cooperation between the vehicle and RSU. First, vehicles cooperate to avoid interfering transmissions by scheduling the transmissions of the vehicles in each coalition. Second, a RSU can join some coalition to cooperate the transmissions of the vehicles in that coalition. Moreover, due to the mobility of the vehicles, we introduce the notion of encounter between the vehicle and RSU to indicate the availability of the relay in space. To stimulate the RSU's cooperative relaying for the vehicles, the pricing mechanism is applied. A non-transferable utility (NTU) game is developed to analyze the behaviors of the vehicles and RSUs. The stability of the formulated game is studied. Finally, we present and discuss the numerical results for the 2-vehicle and 2-RSU scenario, and the numerical results verify the theoretical analysis.
DroidAnalytics: A Signature Based Analytic System to Collect, Extract, Analyze and Associate Android Malware
Venue: arXiv cs.CR 2013
Year: 2013

Smartphones and mobile devices are rapidly becoming indispensable devices for many users. Unfortunately, they also become fertile grounds for hackers to deploy malware and to spread virus. There is an urgent need to have a "security analytic & forensic system" which can facilitate analysts to examine, dissect, associate and correlate large number of mobile applications. An effective analytic system needs to address the following questions: How to automatically collect and manage a high volume of mobile malware? How to analyze a zero-day suspicious application, and compare or associate it with existing malware families in the database? How to perform information retrieval so to reveal similar malicious logic with existing malware, and to quickly identify the new malicious code segment? In this paper, we present the design and implementation of DroidAnalytics, a signature based analytic system to automatically collect, manage, analyze and extract android malware. The system facilitates analysts to retrieve, associate and reveal malicious logics at the "opcode level". We demonstrate the efficacy of DroidAnalytics using 150,368 Android applications, and successfully determine 2,494 Android malware from 102 different families, with 342 of them being zero-day malware samples from six different families. To the best of our knowledge, this is the first reported case in showing such a large Android malware analysis/detection. The evaluation shows the DroidAnalytics is a valuable tool and is effective in analyzing malware repackaging and mutations.
Using cascading Bloom filters to improve the memory usage for de Brujin graphs
Venue: arXiv cs.DS 2013
Year: 2013

De Brujin graphs are widely used in bioinformatics for processing next-generation sequencing data. Due to a very large size of NGS datasets, it is essential to represent de Bruijn graphs compactly, and several approaches to this problem have been proposed recently. In this work, we show how to reduce the memory required by the algorithm of [3] that represents de Brujin graphs using Bloom filters. Our method requires 30% to 40% less memory with respect to the method of [3], with insignificant impact to construction time. At the same time, our experiments showed a better query time compared to [3]. This is, to our knowledge, the best practical representation for de Bruijn graphs.
Optimal Threshold Scheduler for Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

The conventional wireless schedulers of Unicast and Multicast either fulfill multiuser diversity or broadcast gain, but not both together. To achieve optimal system throughput we need a scheduler that exploits both the multiuser diversity gain and the Multicasting gain simultaneously. We first propose a new medianthreshold scheduler that selects all users having instantaneous SNR above the median value for transmission. The system rate equation for the proposed scheduler is also derived. We then optimize the median-threshold so that it performs well over an entire SNR range.With the help of simulation results we compare performance of the proposed scheduler with schedulers like Unicast, Multicast and other Opportunistic Multicast Schedulers (OMS) which are the best schedulers in terms of throughput and show that the proposed optimized threshold scheme outperforms all of them.
Exploiting the Accumulated Evidence for Gene Selection in Microarray Gene Expression Data
Venue: arXiv cs.CE 2013
Year: 2013

Machine Learning methods have of late made significant efforts to solving multidisciplinary problems in the field of cancer classification using microarray gene expression data. Feature subset selection methods can play an important role in the modeling process, since these tasks are characterized by a large number of features and a few observations, making the modeling a non-trivial undertaking. In this particular scenario, it is extremely important to select genes by taking into account the possible interactions with other gene subsets. This paper shows that, by accumulating the evidence in favour (or against) each gene along the search process, the obtained gene subsets may constitute better solutions, either in terms of predictive accuracy or gene size, or in both. The proposed technique is extremely simple and applicable at a negligible overhead in cost.
A Pattern Recognition Approach To Secure Cipher Documents
Venue: arXiv cs.CR 2013
Year: 2013

Natural phenomena show that many creatures form large social groups and move in regular patterns. Previous In this paper, we first propose an efficient distributed mining algorithm to jointly identify a group of moving objects and discover their movement patterns in wireless sensor networks. Afterward, we propose a compression algorithm, called 2P2D, which exploits the obtained group movement patterns to reduce the amount of delivered data. The compression algorithm includes a sequence merge and an entropy reduction phases. we formulate a Hit Item Replacement (HIR) problem and propose a Replace algorithm that obtains the optimal solution. Moreover, we devise three replacement rules and derive the maximum compression ratio.
Performance of Spatially-Coupled LDPC Codes and Threshold Saturation over BICM Channels
Venue: arXiv cs.IT 2013
Year: 2013

We study the performance of binary spatially-coupled low-density parity-check codes (SC-LDPC) when used with bit-interleaved coded-modulation (BICM) schemes. This paper considers the cases when transmission takes place over additive white Gaussian noise (AWGN)channels and Rayleigh fast-fading channels. The technique of upper bounding the maximum-a-posteriori (MAP) decoding performance of LDPC codes using an area theorem is extended for BICM schemes. The upper bound is computed for both the optimal MAP demapper and the suboptimal max-log-MAP (MLM) demapper. It is observed that this bound approaches the noise threshold of BICM channels for regular LDPC codes with large degrees. The rest of the paper extends these techniques to SC-LDPC codes and the phenomenon of threshold saturation is demonstrated numerically. Based on numerical evidence, we conjecture that the belief-propagation (BP) decoding threshold of SC-LDPC codes approaches the MAP decoding threshold of the underlying LDPC ensemble on BICM channels. Numerical results also show that SC-LDPC codes approach the BICM capacity over different channels and modulation schemes.
New Online Algorithm for Dynamic Speed Scaling with Sleep State
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we consider an energy-efficient scheduling problem where $n$ jobs $J_1, J_2, ..., J_n$ need to be executed such that the total energy usage of these jobs is minimized while ensuring that each job is finished within it's deadline. We work in an online setting where a job is known only at it's arrival time, along with it's processing volume and deadline. In such a setting, the currently best-known algorithm by Han et al. \cite{han} provides a competitive ratio max $\{4, 2 + α^α\}$ of energy usage. In this paper, we present a new online algorithm SqOA which provides a competitive ratio max $\{4, 2 + (2-1/α)^α2^{α-1}\}$ of energy usage. For $α\geq 3$, the competitive ratio of our algorithm is better than that of any other existing algorithms for this problem.
Object-oriented programming: some history, and challenges for the next fifty years
Venue: arXiv cs.PL 2013
Year: 2013

Object-oriented programming is inextricably linked to the pioneering work of Ole-Johan Dahl and Kristen Nygaard on the design of the Simula language, which started at the Norwegian Computing Centre in the Spring of 1961. However, object-orientation, as we think of it today---fifty years later---is the result of a complex interplay of ideas, constraints and people. Dahl and Nygaard would certainly recognise it as their progeny, but might also be amazed at how much it has grown up. This article is based on a lecture given on 22nd August 2011, on the occasion of the scientific opening of the Ole-Johan Dahl hus at the University of Oslo. It looks at the foundational ideas from Simula that stand behind object-orientation, how those ideas have evolved to become the dominant programming paradigm, and what they have to offer as we approach the challenges of the next fifty years of informatics.
Detecting and resolving spatial ambiguity in text using named entity extraction and self learning fuzzy logic techniques
Venue: arXiv cs.IR 2013
Year: 2013

Information extraction identifies useful and relevant text in a document and converts unstructured text into a form that can be loaded into a database table. Named entity extraction is a main task in the process of information extraction and is a classification problem in which words are assigned to one or more semantic classes or to a default non-entity class. A word which can belong to one or more classes and which has a level of uncertainty in it can be best handled by a self learning Fuzzy Logic Technique. This paper proposes a method for detecting the presence of spatial uncertainty in the text and dealing with spatial ambiguity using named entity extraction techniques coupled with self learning fuzzy logic techniques
Learning Stable Multilevel Dictionaries for Sparse Representations
Venue: arXiv cs.CV 2013
Year: 2013

Sparse representations using learned dictionaries are being increasingly used with success in several data processing and machine learning applications. The availability of abundant training data necessitates the development of efficient, robust and provably good dictionary learning algorithms. Algorithmic stability and generalization are desirable characteristics for dictionary learning algorithms that aim to build global dictionaries which can efficiently model any test data similar to the training samples. In this paper, we propose an algorithm to learn dictionaries for sparse representations from large scale data, and prove that the proposed learning algorithm is stable and generalizable asymptotically. The algorithm employs a 1-D subspace clustering procedure, the K-hyperline clustering, in order to learn a hierarchical dictionary with multiple levels. We also propose an information-theoretic scheme to estimate the number of atoms needed in each level of learning and develop an ensemble approach to learn robust dictionaries. Using the proposed dictionaries, the sparse code for novel test data can be computed using a low-complexity pursuit procedure. We demonstrate the stability and generalization characteristics of the proposed algorithm using simulations. We also evaluate the utility of the multilevel dictionaries in compressed recovery and subspace learning applications.
Genetic Programming for Document Segmentation and Region Classification Using Discipulus
Venue: arXiv cs.CV 2013
Year: 2013

Document segmentation is a method of rending the document into distinct regions. A document is an assortment of information and a standard mode of conveying information to others. Pursuance of data from documents involves ton of human effort, time intense and might severely prohibit the usage of data systems. So, automatic information pursuance from the document has become a big issue. It is been shown that document segmentation will facilitate to beat such problems. This paper proposes a new approach to segment and classify the document regions as text, image, drawings and table. Document image is divided into blocks using Run length smearing rule and features are extracted from every blocks. Discipulus tool has been used to construct the Genetic programming based classifier model and located 97.5% classification accuracy.
Comparison of the Information Technology Development in Slovakia and Hungary
Venue: arXiv cs.CY 2013
Year: 2013

Nowadays the role of information is increasingly important, so every company has to provide the efficient procurement, processing, storage and visualization of this special resource in hope to stay competitive. More and more enterprises introduce Enterprise Resource Planning System to be able to perform the listed functions. The article illustrates the usage of these systems in Hungary and Slovakia, as well as tests the following presumption: the level of Information Technology (IT) development is lower in Hungary than our northern neighbor.
Quantitative Characterization of Randomly Roving Agents
Venue: arXiv cs.NI 2013
Year: 2013

Quantitative characterization of randomly roving agents in Agent Based Intrusion Detection Environment (ABIDE) is studied. Formula simplifications regarding known results and publications are given. Extended Agent Based Intrusion Detection Environment (EABIDE) is introduced and quantitative characterization of roving agents in EABIDE is studies.
Average Rate of Downlink Heterogeneous Cellular Networks over Generalized Fading Channels - A Stochastic Geometry Approach
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we introduce an analytical framework to compute the average rate of downlink heterogeneous cellular networks. The framework leverages recent application of stochastic geometry to other-cell interference modeling and analysis. The heterogeneous cellular network is modeled as the superposition of many tiers of Base Stations (BSs) having different transmit power, density, path-loss exponent, fading parameters and distribution, and unequal biasing for flexible tier association. A long-term averaged maximum biased-received-power tier association is considered. The positions of the BSs in each tier are modeled as points of an independent Poisson Point Process (PPP). Under these assumptions, we introduce a new analytical methodology to evaluate the average rate, which avoids the computation of the Coverage Probability (Pcov) and needs only the Moment Generating Function (MGF) of the aggregate interference at the probe mobile terminal. The distinguishable characteristic of our analytical methodology consists in providing a tractable and numerically efficient framework that is applicable to general fading distributions, including composite fading channels with small- and mid-scale fluctuations. In addition, our method can efficiently handle correlated Log-Normal shadowing with little increase of the computational complexity. The proposed MGF-based approach needs the computation of either a single or a two-fold numerical integral, thus reducing the complexity of Pcov-based frameworks, which require, for general fading distributions, the computation of a four-fold integral.
A Newer User Authentication, File encryption and Distributed Server Based Cloud Computing Security Architecture
Venue: arXiv cs.DC 2013
Year: 2013

The cloud computing platform gives people the opportunity for sharing resources, services and information among the people of the whole world. In private cloud system, information is shared among the persons who are in that cloud. For this, security or personal information hiding process hampers. In this paper we have proposed new security architecture for cloud computing platform. This ensures secure communication system and hiding information from others. AES based file encryption system and asynchronous key system for exchanging information or data is included in this model. This structure can be easily applied with main cloud computing features, e.g. PaaS, SaaS and IaaS. This model also includes onetime password system for user authentication process. Our work mainly deals with the security system of the whole cloud computing platform.
Space--Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
Venue: arXiv cs.DS 2013
Year: 2013

The technique of Schroeppel and Shamir (SICOMP, 1981) has long been the most efficient way to trade space against time for the SUBSET SUM problem. In the random-instance setting, however, improved tradeoffs exist. In particular, the recently discovered dissection method of Dinur et al. (CRYPTO 2012) yields a significantly improved space--time tradeoff curve for instances with strong randomness properties. Our main result is that these strong randomness assumptions can be removed, obtaining the same space--time tradeoffs in the worst case. We also show that for small space usage the dissection algorithm can be almost fully parallelized. Our strategy for dealing with arbitrary instances is to instead inject the randomness into the dissection process itself by working over a carefully selected but random composite modulus, and to introduce explicit space--time controls into the algorithm by means of a "bailout mechanism".