OpenRaiser/Intern-Atlas huggingface dataset:
Arabic Text Recognition in Video Sequences
Venue: arXiv cs.MM 2013
Year: 2013

In this paper, we propose a robust approach for text extraction and recognition from Arabic news video sequence. The text included in video sequences is an important needful for indexing and searching system. However, this text is difficult to detect and recognize because of the variability of its size, their low resolution characters and the complexity of the backgrounds. To solve these problems, we propose a system performing in two main tasks: extraction and recognition of text. Our system is tested on a varied database composed of different Arabic news programs and the obtained results are encouraging and show the merits of our approach.
Lower bounds for oblivious subspace embeddings
Venue: arXiv cs.DM 2013
Year: 2013

An oblivious subspace embedding (OSE) for some eps, delta in (0,1/3) and d <= m <= n is a distribution D over R^{m x n} such that for any linear subspace W of R^n of dimension d, Pr_{Pi ~ D}(for all x in W, (1-eps) |x|_2 <= |Pi x|_2 <= (1+eps)|x|_2) >= 1 - delta. We prove that any OSE with delta < 1/3 must have m = Omega((d + log(1/delta))/eps^2), which is optimal. Furthermore, if every Pi in the support of D is sparse, having at most s non-zero entries per column, then we show tradeoff lower bounds between m and s.
Estimating Clique Composition and Size Distributions from Sampled Network Data
Venue: arXiv cs.SI 2013
Year: 2013

Cliques are defined as complete graphs or subgraphs; they are the strongest form of cohesive subgroup, and are of interest in both social science and engineering contexts. In this paper we show how to efficiently estimate the distribution of clique sizes from a probability sample of nodes obtained from a graph (e.g., by independence or link-trace sampling). We introduce two types of unbiased estimators, one of which exploits labeling of sampled nodes neighbors and one of which does not require this information. We compare the estimators on a variety of real-world graphs and provide suggestions for their use. We generalize our estimators to cases in which cliques are distinguished not only by size but also by node attributes, allowing us to estimate clique composition by size. Finally, we apply our methodology to a sample of Facebook users to estimate the clique size distribution by gender over the social graph.
Upper Bounds On the ML Decoding Error Probability of General Codes over AWGN Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, parameterized Gallager's first bounding technique (GFBT) is presented by introducing nested Gallager regions, to derive upper bounds on the ML decoding error probability of general codes over AWGN channels. The three well-known bounds, namely, the sphere bound (SB) of Herzberg and Poltyrev, the tangential bound (TB) of Berlekamp, and the tangential-sphere bound (TSB) of Poltyrev, are generalized to general codes without the properties of geometrical uniformity and equal energy. When applied to the binary linear codes, the three generalized bounds are reduced to the conventional ones. The new derivation also reveals that the SB of Herzberg and Poltyrev is equivalent to the SB of Kasami et al., which was rarely cited in the literatures.
Search-Space Characterization for Real-time Heuristic Search
Venue: arXiv cs.AI 2013
Year: 2013

Recent real-time heuristic search algorithms have demonstrated outstanding performance in video-game pathfinding. However, their applications have been thus far limited to that domain. We proceed with the aim of facilitating wider applications of real-time search by fostering a greater understanding of the performance of recent algorithms. We first introduce eight algorithm-independent complexity measures for search spaces and correlate their values with algorithm performance. The complexity measures are statistically shown to be significant predictors of algorithm performance across a set of commercial video-game maps. We then extend this analysis to a wider variety of search spaces in the first application of database-driven real-time search to domains outside of video-game pathfinding. In doing so, we gain insight into algorithm performance and possible enhancement as well as into search space complexity.
Designing secure clustering protocol with the approach of reducing energy consumption in wireless sensor networks
Venue: arXiv cs.NI 2013
Year: 2013

In recent years, many researchers have focused on wireless sensor networks and their applications. To obtain scalability potential in these networks most of the nodes are categorized as distinct groups named cluster and the node which is selected as cluster head or Aggregation Node offers the operation of data collection from other cluster nodes and aggregation and sending it to the rest of the network. Clustering and data aggregation increase network scalability and cause that limited resources of the network are used well. However, these mechanisms also make several breaches in the network, for example in clustered networks cluster head nodes are considered Desirable and attractive targets for attackers since reaching their information whether by physical attack and node capturing or by other attacks, the attacker can obtain the whole information of corresponding cluster. In this study secure clustering of the nodes are considered with the approach of reducing energy consumption of nodes and a protocol is presented that in addition to satisfying Advanced security needs of wireless sensor networks reduces the amount of energy consumption by the nodes. Due to network clustering there is scalability potential in such a network and According to frequent change of cluster head nodes load distribution is performed in the cluster and eventually increase the network lifetime.
Drawing Planar Graphs with a Prescribed Inner Face
Venue: arXiv cs.CG 2013
Year: 2013

Given a plane graph $G$ (i.e., a planar graph with a fixed planar embedding) and a simple cycle $C$ in $G$ whose vertices are mapped to a convex polygon, we consider the question whether this drawing can be extended to a planar straight-line drawing of $G$. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, it can be computed in the same running time.
Models of on-line social networks
Venue: arXiv cs.SI 2013
Year: 2013

We present a deterministic model for on-line social networks (OSNs) based on transitivity and local knowledge in social interactions. In the Iterated Local Transitivity (ILT) model, at each time-step and for every existing node $x$, a new node appears which joins to the closed neighbour set of $x.$ The ILT model provably satisfies a number of both local and global properties that were observed in OSNs and other real-world complex networks, such as a densification power law, decreasing average distance, and higher clustering than in random graphs with the same average degree. Experimental studies of social networks demonstrate poor expansion properties as a consequence of the existence of communities with low number of inter-community edges. Bounds on the spectral gap for both the adjacency and normalized Laplacian matrices are proved for graphs arising from the ILT model, indicating such bad expansion properties. The cop and domination number are shown to remain the same as the graph from the initial time-step $G_0$, and the automorphism group of $G_0$ is a subgroup of the automorphism group of graphs generated at all later time-steps. A randomized version of the ILT model is presented, which exhibits a tuneable densification power law exponent, and maintains several properties of the deterministic model.
Guiding Designs of Self-Organizing Swarms: Interactive and Automated Approaches
Venue: arXiv cs.NE 2013
Year: 2013

Self-organization of heterogeneous particle swarms is rich in its dynamics but hard to design in a traditional top-down manner, especially when many types of kinetically distinct particles are involved. In this chapter, we discuss how we have been addressing this problem by (1) utilizing and enhancing interactive evolutionary design methods and (2) realizing spontaneous evolution of self organizing swarms within an artificial ecosystem.
Source Code Retrieval Using Sequence Based Similarity
Venue: arXiv cs.SE 2013
Year: 2013

Duplicated code has a negative impact on the quality of software systems and should be detected at least. In this paper, we discuss an approach that improves source code retrieval using the structural information about the programs. We developed a lexical parser to extract control statements and method identifiers from Java programs. We propose a similarity measure that is defined by the ratio of the number of sequentially full matching statements to the number of sequentially partial matching ones. The similarity measure is considered to be an extension of a set based similarity index, e.g., Sorensen-Dice index. Our key contribution of this research is the development of a similarity retrieval algorithm that derives meaningful search conditions from a given sequence, and then performs retrieval using all of the derived conditions. Experiments show that our retrieval model outperforms the other retrieval models up to 90.9% in the number of retrieved methods.
Timing Analysis of SSL/TLS Man in the Middle Attacks
Venue: arXiv cs.CR 2013
Year: 2013

Man in the middle attacks are a significant threat to modern e-commerce and online communications, even when such transactions are protected by TLS. We intend to show that it is possible to detect man-in-the-middle attacks on SSL and TLS by detecting timing differences between a standard SSL session and an attack we created.
QuPARA: Query-Driven Large-Scale Portfolio Aggregate Risk Analysis on MapReduce
Venue: arXiv cs.DC 2013
Year: 2013

Stochastic simulation techniques are used for portfolio risk analysis. Risk portfolios may consist of thousands of reinsurance contracts covering millions of insured locations. To quantify risk each portfolio must be evaluated in up to a million simulation trials, each capturing a different possible sequence of catastrophic events over the course of a contractual year. In this paper, we explore the design of a flexible framework for portfolio risk analysis that facilitates answering a rich variety of catastrophic risk queries. Rather than aggregating simulation data in order to produce a small set of high-level risk metrics efficiently (as is often done in production risk management systems), the focus here is on allowing the user to pose queries on unaggregated or partially aggregated data. The goal is to provide a flexible framework that can be used by analysts to answer a wide variety of unanticipated but natural ad hoc queries. Such detailed queries can help actuaries or underwriters to better understand the multiple dimensions (e.g., spatial correlation, seasonality, peril features, construction features, and financial terms) that can impact portfolio risk. We implemented a prototype system, called QuPARA (Query-Driven Large-Scale Portfolio Aggregate Risk Analysis), using Hadoop, which is Apache's implementation of the MapReduce paradigm. This allows the user to take advantage of large parallel compute servers in order to answer ad hoc risk analysis queries efficiently even on very large data sets typically encountered in practice. We describe the design and implementation of QuPARA and present experimental results that demonstrate its feasibility. A full portfolio risk analysis run consisting of a 1,000,000 trial simulation, with 1,000 events per trial, and 3,200 risk transfer contracts can be completed on a 16-node Hadoop cluster in just over 20 minutes.
A Convex Framework for Optimal Investment on Disease Awareness in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

We consider the problem of controlling the propagation of an epidemic outbreak in an arbitrary network of contacts by investing on disease awareness throughout the network. We model the effect of agent awareness on the dynamics of an epidemic using the SAIS epidemic model, an extension of the SIS epidemic model that includes a state of "awareness". This model allows to derive a condition to control the spread of an epidemic outbreak in terms of the eigenvalues of a matrix that depends on the network structure and the parameters of the model. We study the problem of finding the cost-optimal investment on disease awareness throughout the network when the cost function presents some realistic properties. We propose a convex framework to find cost-optimal allocation of resources. We validate our results with numerical simulations in a real online social network.
On Sparsification for Computing Treewidth
Venue: arXiv cs.CC 2013
Year: 2013

We investigate whether an n-vertex instance (G,k) of Treewidth, asking whether the graph G has treewidth at most k, can efficiently be made sparse without changing its answer. By giving a special form of OR-cross-composition, we prove that this is unlikely: if there is an e > 0 and a polynomial-time algorithm that reduces n-vertex Treewidth instances to equivalent instances, of an arbitrary problem, with O(n^{2-e}) bits, then NP is in coNP/poly and the polynomial hierarchy collapses to its third level. Our sparsification lower bound has implications for structural parameterizations of Treewidth: parameterizations by measures that do not exceed the vertex count, cannot have kernels with O(k^{2-e}) bits for any e > 0, unless NP is in coNP/poly. Motivated by the question of determining the optimal kernel size for Treewidth parameterized by vertex cover, we improve the O(k^3)-vertex kernel from Bodlaender et al. (STACS 2011) to a kernel with O(k^2) vertices. Our improved kernel is based on a novel form of treewidth-invariant set. We use the q-expansion lemma of Fomin et al. (STACS 2011) to find such sets efficiently in graphs whose vertex count is superquadratic in their vertex cover number.
Graph Colouring Problem Based on Discrete Imperialist Competitive Algorithm
Venue: arXiv cs.AI 2013
Year: 2013

In graph theory, Graph Colouring Problem (GCP) is an assignment of colours to vertices of any given graph such that the colours on adjacent vertices are different. The GCP is known to be an optimization and NP-hard problem. Imperialist Competitive Algorithm (ICA) is a meta-heuristic optimization and stochastic search strategy which is inspired from socio-political phenomenon of imperialistic competition. The ICA contains two main operators: the assimilation and the imperialistic competition. The ICA has excellent capabilities such as high convergence rate and better global optimum achievement. In this research, a discrete version of ICA is proposed to deal with the solution of GCP. We call this algorithm as the DICA. The performance of the proposed method is compared with Genetic Algorithm (GA) on seven well-known graph colouring benchmarks. Experimental results demonstrate the superiority of the DICA for the benchmarks. This means DICA can produce optimal and valid solutions for different GCP instances.
Implementation Of Back-Propagation Neural Network For Isolated Bangla Speech Recognition
Venue: arXiv cs.CL 2013
Year: 2013

This paper is concerned with the development of Back-propagation Neural Network for Bangla Speech Recognition. In this paper, ten bangla digits were recorded from ten speakers and have been recognized. The features of these speech digits were extracted by the method of Mel Frequency Cepstral Coefficient (MFCC) analysis. The mfcc features of five speakers were used to train the network with Back propagation algorithm. The mfcc features of ten bangla digit speeches, from 0 to 9, of another five speakers were used to test the system. All the methods and algorithms used in this research were implemented using the features of Turbo C and C++ languages. From our investigation it is seen that the developed system can successfully encode and analyze the mfcc features of the speech signal to recognition. The developed system achieved recognition rate about 96.332% for known speakers (i.e., speaker dependent) and 92% for unknown speakers (i.e., speaker independent).
Asynchronous Source Clock Frequency Recovery through Aperiodic Packet Streams
Venue: arXiv cs.NI 2013
Year: 2013

We consider the most general case of source clock frequency recovery (SCFR) in packet networks, i.e., asynchronous SCFR through aperiodic packet streams, where there is neither a common reference clock nor any relation between packet generation intervals and a source clock frequency. We formulate the problem of asynchronous SCFR with timestamps as a linear case of regression through the origin (RTO) and propose two schemes, one based on recursive least squares (RLS) method and the other based on simple heuristics of cumulative ratio of interarrival and interdeparture times, which provide better estimates of the source clock frequency with faster convergence than conventional phase-locked loop (PLL)-based schemes.
Bat Algorithm: Literature Review and Applications
Venue: arXiv cs.AI 2013
Year: 2013

Bat algorithm (BA) is a bio-inspired algorithm developed by Yang in 2010 and BA has been found to be very efficient. As a result, the literature has expanded significantly in the last 3 years. This paper provides a timely review of the bat algorithm and its new variants. A wide range of diverse applications and case studies are also reviewed and summarized briefly here. Further research topics are also discussed.
Efficient Approximation of Well-Founded Justification and Well-Founded Domination (Corrected and Extended Version)
Venue: arXiv cs.LO 2013
Year: 2013

Many native ASP solvers exploit unfounded sets to compute consequences of a logic program via some form of well-founded negation, but disregard its contrapositive, well-founded justification (WFJ), due to computational cost. However, we demonstrate that this can hinder propagation of many relevant conditions such as reachability. In order to perform WFJ with low computational cost, we devise a method that approximates its consequences by computing dominators in a flowgraph, a problem for which linear-time algorithms exist. Furthermore, our method allows for additional unfounded set inference, called well-founded domination (WFD). We show that the effect of WFJ and WFD can be simulated for a important classes of logic programs that include reachability. This paper is a corrected and extended version of a paper published at the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2013). It has been adapted to exclude Theorem 10 and its consequences, but provides all missing proofs.
Towards an Abstract Domain for Resource Analysis of Logic Programs Using Sized Types
Venue: arXiv cs.PL 2013
Year: 2013

We present a novel general resource analysis for logic programs based on sized types.Sized types are representations that incorporate structural (shape) information and allow expressing both lower and upper bounds on the size of a set of terms and their subterms at any position and depth. They also allow relating the sizes of terms and subterms occurring at different argument positions in logic predicates. Using these sized types, the resource analysis can infer both lower and upper bounds on the resources used by all the procedures in a program as functions on input term (and subterm) sizes, overcoming limitations of existing analyses and enhancing their precision. Our new resource analysis has been developed within the abstract interpretation framework, as an extension of the sized types abstract domain, and has been integrated into the Ciao preprocessor, CiaoPP. The abstract domain operations are integrated with the setting up and solving of recurrence equations for both, inferring size and resource usage functions. We show that the analysis is an improvement over the previous resource analysis present in CiaoPP and compares well in power to state of the art systems.
A Literature Survey of Benchmark Functions For Global Optimization Problems
Venue: arXiv cs.AI 2013
Year: 2013

Test functions are important to validate and compare the performance of optimization algorithms. There have been many test or benchmark functions reported in the literature; however, there is no standard list or set of benchmark functions. Ideally, test functions should have diverse properties so that can be truly useful to test new algorithms in an unbiased way. For this purpose, we have reviewed and compiled a rich set of 175 benchmark functions for unconstrained optimization problems with diverse properties in terms of modality, separability, and valley landscape. This is by far the most complete set of functions so far in the literature, and tt can be expected this complete set of functions can be used for validation of new optimization in the future.
Using Modularity Metrics to assist Move Method Refactoring of Large System
Venue: arXiv cs.SE 2013
Year: 2013

For large software systems, refactoring activities can be a challenging task, since for keeping component complexity under control the overall architecture as well as many details of each component have to be considered. Product metrics are therefore often used to quantify several parameters related to the modularity of a software system. This paper devises an approach for automatically suggesting refactoring opportunities on large software systems. We show that by assessing metrics for all components, move methods refactoring an be suggested in such a way to improve modularity of several components at once, without hindering any other. However, computing metrics for large software systems, comprising thousands of classes or more, can be a time consuming task when performed on a single CPU. For this, we propose a solution that computes metrics by resorting to GPU, hence greatly shortening computation time. Thanks to our approach precise knowledge on several properties of the system can be continuously gathered while the system evolves, hence assisting developers to quickly assess several solutions for reducing modularity issues.
Counter-Strategy Guided Refinement of GR(1) Temporal Logic Specifications
Venue: arXiv cs.LO 2013
Year: 2013

The reactive synthesis problem is to find a finite-state controller that satisfies a given temporal-logic specification regardless of how its environment behaves. Developing a formal specification is a challenging and tedious task and initial specifications are often unrealizable. In many cases, the source of unrealizability is the lack of adequate assumptions on the environment of the system. In this paper, we consider the problem of automatically correcting an unrealizable specification given in the generalized reactivity (1) fragment of linear temporal logic by adding assumptions on the environment. When a temporal-logic specification is unrealizable, the synthesis algorithm computes a counter-strategy as a witness. Our algorithm then analyzes this counter-strategy and synthesizes a set of candidate environment assumptions that can be used to remove the counter-strategy from the environment's possible behaviors. We demonstrate the applicability of our approach with several case studies.
Chaotic Characteristic of Discrete-time Linear Inclusion Dynamical Systems
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, we study the fiber-chaos of switched linear dynamical systems.