OpenRaiser/Intern-Atlas huggingface dataset:
The Minimum Bends in a Polyline Drawing with Fixed Vertex Locations
Venue: arXiv cs.CG 2014
Year: 2014

We consider embeddings of planar graphs in $R^2$ where vertices map to points and edges map to polylines. We refer to such an embedding as a polyline drawing, and ask how few bends are required to form such a drawing for an arbitrary planar graph. It has long been known that even when the vertex locations are completely fixed, a planar graph admits a polyline drawing where edges bend a total of $O(n^2)$ times. Our results show that this number of bends is optimal. In particular, we show that $Ω(n^2)$ total bends is required to form a polyline drawing on any set of fixed vertex locations for almost all planar graphs. This result generalizes all previously known lower bounds, which only applied to convex point sets, and settles 2 open problems.
A Bengali HMM Based Speech Synthesis System
Venue: arXiv cs.SD 2014
Year: 2014

The paper presents the capability of an HMM-based TTS system to produce Bengali speech. In this synthesis method, trajectories of speech parameters are generated from the trained Hidden Markov Models. A final speech waveform is synthesized from those speech parameters. In our experiments, spectral properties were represented by Mel Cepstrum Coefficients. Both the training and synthesis issues are investigated in this paper using annotated Bengali speech database. Experimental evaluation depicts that the developed text-to-speech system is capable of producing adequately natural speech in terms of intelligibility and intonation for Bengali.
Counting perfect matchings in graphs that exclude a single-crossing minor
Venue: arXiv cs.DS 2014
Year: 2014

A graph $H$ is single-crossing if it can be drawn in the plane with at most one crossing. For any single-crossing graph $H$, we give an $O(n^4)$ time algorithm for counting perfect matchings in graphs excluding $H$ as a minor. The runtime can be lowered to $O(n^{1.5})$ when $G$ excludes $K_5$ or $K_{3,3}$ as a minor. This is the first generalization of an algorithm for counting perfect matchings in $K_{3,3}$-free graphs (Little 1974, Vazirani 1989). Our algorithm uses black-boxes for counting perfect matchings in planar graphs and for computing certain graph decompositions. Together with an independent recent result (Straub et al. 2014) for graphs excluding $K_5$, it is one of the first nontrivial algorithms to not inherently rely on Pfaffian orientations.
Regular Interval Exchange Transformations over a Quadratic Field
Venue: arXiv cs.DM 2014
Year: 2014

We describe a generalization of a result of Boshernitzan and Carroll: an extension of Lagrange's Theorem on continued fraction expansion of quadratic irrationals to interval exchange transformations. In order to do this, we use a two-sided version of the Rauzy induction. In particular, we show that starting from an interval exchange transforma- tion whose lengths are defined over a quadratic field and applying the two-sided Rauzy induction, one can obtain only a finite number of new transformations up to homothety.
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
Venue: arXiv cs.DB 2014
Year: 2014

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions. Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.
A strategy to identify components using clustering approach for component reusability
Venue: arXiv cs.SE 2014
Year: 2014

Component Based Software Engineering (CBSE) has played a very important role for building larger software systems The current practices of software industry demands development of a software within time and budget which is highly productive. It is necessary to achieve how much effectively the software component is reusable. To achieve this, the component identification is mandatory. The traditional approaches are presented in the literature. However effective reuse is still a challenging issue. In this paper, a strategy has been proposed for the identification of a business component using clustering methodology. This approach will be useful in identifying the reusable components for different domains. The proposed approach has identified the reconfigured component using the CBO measure to reduce the coupling between the objects. By considering this proposed strategy, the productivity can be increased in the organization.
Number of minimal cyclic codes with given length and dimension
Venue: arXiv cs.IT 2014
Year: 2014

In this article, we count the quantity of minimal cyclic codes of length $n$ and dimension $k$ over a finite field $\mathbb F_q$, in the case when the prime factors of $n$ satisfy a special condition. This problem is equivalent to count the quantity of irreducible factors of $x^n-1\in \mathbb F_q[x]$ of degree $k$.
An Evolutionary Approach for Optimal Citing and Sizing of Micro-Grid in Radial Distribution Systems
Venue: arXiv cs.NE 2014
Year: 2014

This Paper presents the methodology of penetration of Micro-Grids (MG) in the radial distribution system (RDS). The aim of this paper is to minimize a total real power loss that descends the performance of the radial distribution system by integrating various renewable resources as Distributed Generation (DG). The combination of different types of renewable energy resources contributes a sustainable MG. These resources are optimally sized and located using evolutionary approach in various penetration levels. The optimal solutions are experimented with IEEE 33 radial distribution system using Particle Swarm Optimization (PSO) technique. The results are quite promising and authenticate its potential to solve problem in radial distribution system effectively.
Discounting in LTL
Venue: arXiv cs.LO 2014
Year: 2014

In recent years, there is growing need and interest in formalizing and reasoning about the quality of software and hardware systems. As opposed to traditional verification, where one handles the question of whether a system satisfies, or not, a given specification, reasoning about quality addresses the question of \emph{how well} the system satisfies the specification. One direction in this effort is to refine the "eventually" operators of temporal logic to {\em discounting operators}: the satisfaction value of a specification is a value in $[0,1]$, where the longer it takes to fulfill eventuality requirements, the smaller the satisfaction value is. In this paper we introduce an augmentation by discounting of Linear Temporal Logic (LTL), and study it, as well as its combination with propositional quality operators. We show that one can augment LTL with an arbitrary set of discounting functions, while preserving the decidability of the model-checking problem. Further augmenting the logic with unary propositional quality operators preserves decidability, whereas adding an average-operator makes some problems undecidable. We also discuss the complexity of the problem, as well as various extensions.
Vector Clocks in Coq: An Experience Report
Venue: arXiv cs.DC 2014
Year: 2014

This report documents the process of implementing vector clocks in the Coq proof assistant for extraction and use in the distributed Dynamo-inspired data store, Riak. In this report, we focus on the technical challenges of using Core Erlang code extracted from the proof assistant in a production-grade Erlang application, as opposed to verification of the model itself.
Automatic Fado Music Classification
Venue: arXiv cs.SD 2014
Year: 2014

In late 2011, Fado was elevated to the oral and intangible heritage of humanity by UNESCO. This study aims to develop a tool for automatic detection of Fado music based on the audio signal. To do this, frequency spectrum-related characteristics were captured form the audio signal: in addition to the Mel Frequency Cepstral Coefficients (MFCCs) and the energy of the signal, the signal was further analysed in two frequency ranges, providing additional information. Tests were run both in a 10-fold cross-validation setup (97.6% accuracy), and in a traditional train/test setup (95.8% accuracy). The good results reflect the fact that Fado is a very distinctive musical style.
Stability Region of a Slotted Aloha Network with K-Exponential Backoff
Venue: arXiv cs.NI 2014
Year: 2014

Stability region of random access wireless networks is known for only simple network scenarios. The main problem in this respect is due to interaction among queues. When transmission probabilities during successive transmissions change, e.g., when exponential backoff mechanism is exploited, the interactions in the network are stimulated. In this paper, we derive the stability region of a buffered slotted Aloha network with K-exponential backoff mechanism, approximately, when a finite number of nodes exist. To this end, we propose a new approach in modeling the interaction among wireless nodes. In this approach, we model the network with inter-related quasi-birth-death (QBD) processes such that at each QBD corresponding to each node, a finite number of phases consider the status of the other nodes. Then, by exploiting the available theorems on stability of QBDs, we find the stability region. We show that exponential backoff mechanism is able to increase the area of the stability region of a simple slotted Aloha network with two nodes, more than 40\%. We also show that a slotted Aloha network with exponential backoff may perform very near to ideal scheduling. The accuracy of our modeling approach is verified by simulation in different conditions.
Teaching Software Engineering through Robotics
Venue: arXiv cs.CY 2014
Year: 2014

This paper presents a newly-developed robotics programming course and reports the initial results of software engineering education in robotics context. Robotics programming, as a multidisciplinary course, puts equal emphasis on software engineering and robotics. It teaches students proper software engineering -- in particular, modularity and documentation -- by having them implement four core robotics algorithms for an educational robot. To evaluate the effect of software engineering education in robotics context, we analyze pre- and post-class survey data and the four assignments our students completed for the course. The analysis suggests that the students acquired an understanding of software engineering techniques and principles.
Computing and Using Metrics in the ADS
Venue: arXiv cs.DL 2014
Year: 2014

Finding measures for research impact, be it for individuals, institutions, instruments or projects, has gained a lot of popularity. More papers than ever are being written on new impact measures, and problems with existing measures are being pointed out on a regular basis. Funding agencies require impact statistics in their reports, job candidates incorporate them in their resumes, and publication metrics have even been used in at least one recent court case. To support this need for research impact indicators, the SAO/NASA Astrophysics Data System (ADS) has developed a service which provides a broad overview of various impact measures. In this presentation we discuss how the ADS can be used to quench the thirst for impact measures. We will also discuss a couple of the lesser known indicators in the metrics overview and the main issues to be aware of when compiling publication-based metrics in the ADS, namely author name ambiguity and citation incompleteness.
Higher-order CIS codes
Venue: arXiv cs.IT 2014
Year: 2014

We introduce {\bf complementary information set codes} of higher-order. A binary linear code of length $tk$ and dimension $k$ is called a complementary information set code of order $t$ ($t$-CIS code for short) if it has $t$ pairwise disjoint information sets. The duals of such codes permit to reduce the cost of masking cryptographic algorithms against side-channel attacks. As in the case of codes for error correction, given the length and the dimension of a $t$-CIS code, we look for the highest possible minimum distance. In this paper, this new class of codes is investigated. The existence of good long CIS codes of order $3$ is derived by a counting argument. General constructions based on cyclic and quasi-cyclic codes and on the building up construction are given. A formula similar to a mass formula is given. A classification of 3-CIS codes of length $\le 12$ is given. Nonlinear codes better than linear codes are derived by taking binary images of $\Z_4$-codes. A general algorithm based on Edmonds' basis packing algorithm from matroid theory is developed with the following property: given a binary linear code of rate $1/t$ it either provides $t$ disjoint information sets or proves that the code is not $t$-CIS. Using this algorithm, all optimal or best known $[tk, k]$ codes where $t=3, 4, \dots, 256$ and $1 \le k \le \lfloor 256/t \rfloor$ are shown to be $t$-CIS for all such $k$ and $t$, except for $t=3$ with $k=44$ and $t=4$ with $k=37$.
Two Boolean functions with five-valued Walsh spectra and high nonlinearity
Venue: arXiv cs.IT 2014
Year: 2014

For cryptographic systems the method of confusion and diffusion is used as a fundamental technique to achieve security. Confusion is reflected in nonlinearity of certain Boolean functions describing the cryptographic transformation. In this paper, we present two balanced boolean functions which have low Walsh spectra and high nonlinearity. In the proof of the nonlinearity, a new method for evaluating some exponential sums over finite fields was provided.
Crypto multi tenant: an environment of secure computing using cloud sql
Venue: arXiv cs.CR 2014
Year: 2014

In our proposed work we mainly focus on data security of tenants so that only the authorized user can access the data. To provide this feature we use encryption and decryption process of data so that the only legal tenant can access their particular data. Hence, for security related to data of tenants we implement AES (advanced encryption standard) using cloud SQL. The result obtained from experimental methodology proved that AES gives protection for the data stored in the cloud. We make use of AES algorithm and Google App Engine to supply secured data storage, efficiency, assure availability in the condition of cloud denial-of-service attacks and data security in the cloud. This Approach is basically implemented by tenants who are going to store their data in the cloud.
Performance Comparison of Incremental K-means and Incremental DBSCAN Algorithms
Venue: arXiv cs.DB 2014
Year: 2014

Incremental K-means and DBSCAN are two very important and popular clustering techniques for today's large dynamic databases (Data warehouses, WWW and so on) where data are changed at random fashion. The performance of the incremental K-means and the incremental DBSCAN are different with each other based on their time analysis characteristics. Both algorithms are efficient compare to their existing algorithms with respect to time, cost and effort. In this paper, the performance evaluation of incremental DBSCAN clustering algorithm is implemented and most importantly it is compared with the performance of incremental K-means clustering algorithm and it also explains the characteristics of these two algorithms based on the changes of the data in the database. This paper also explains some logical differences between these two most popular clustering algorithms. This paper uses an air pollution database as original database on which the experiment is performed.
On the Application of Generic Summarization Algorithms to Music
Venue: arXiv cs.IR 2014
Year: 2014

Several generic summarization algorithms were developed in the past and successfully applied in fields such as text and speech summarization. In this paper, we review and apply these algorithms to music. To evaluate this summarization's performance, we adopt an extrinsic approach: we compare a Fado Genre Classifier's performance using truncated contiguous clips against the summaries extracted with those algorithms on 2 different datasets. We show that Maximal Marginal Relevance (MMR), LexRank and Latent Semantic Analysis (LSA) all improve classification performance in both datasets used for testing.
Path Conditions and Principal Matching: A New Approach to Access Control
Venue: arXiv cs.CR 2014
Year: 2014

Traditional authorization policies are user-centric, in the sense that authorization is defined, ultimately, in terms of user identities. We believe that this user-centric approach is inappropriate for many applications, and that what should determine authorization is the relationships that exist between entities in the system. While recent research has considered the possibility of specifying authorization policies based on the relationships that exist between peers in social networks, we are not aware of the application of these ideas to general computing systems. We develop a formal access control model that makes use of ideas from relationship-based access control and a two-stage method for evaluating policies. Our policies are defined using path conditions, which are similar to regular expressions. We define semantics for path conditions, which we use to develop a rigorous method for evaluating policies. We describe the algorithm required to evaluate policies and establish its complexity. Finally, we illustrate the advantages of our model using an example and describe a preliminary implementation of our algorithm.
Rain Attenuation Prediction for Terrestrial Microwave Link in Bangladesh
Venue: arXiv cs.NI 2014
Year: 2014

Rain attenuation is a major shortcoming of microwave transmission. As a subtropical country, Bangladesh is one of the highest rainy areas of the world. Thus, designing a terrestrial microwave link is a serious challenge to the engineers. In this paper, the annual rain rate and monthly variation of rate are predicted for different percentage of time of the year from the measured rainfall data. Using ITU rain model for terrestrial microwave communication, the rain attenuation is predicted for five major cities of Bangladesh, namely Dhaka, Chittagong, Rajshahi, Sylhet, and Khulna. It is found that rain attenuation is the most severe in Sylhet and least in Rajshahi. The attenuation is estimated for different frequency and polarization. A horizontally polarized signal encounters 15% more rain attenuation than that of vertically polarized signal. It is also found that attenuation in Rajshahi is about 20% lesser than that in Sylhet. Thus, the horizontally polarized transmission in Rajshahi experiences about 5% less attenuation than the vertically polarized transmission in Sylhet.
Robust Outlier Detection Technique in Data Mining: A Univariate Approach
Venue: arXiv cs.CV 2014
Year: 2014

Outliers are the points which are different from or inconsistent with the rest of the data. They can be novel, new, abnormal, unusual or noisy information. Outliers are sometimes more interesting than the majority of the data. The main challenges of outlier detection with the increasing complexity, size and variety of datasets, are how to catch similar outliers as a group, and how to evaluate the outliers. This paper describes an approach which uses Univariate outlier detection as a pre-processing step to detect the outlier and then applies K-means algorithm hence to analyse the effects of the outliers on the cluster analysis of dataset.
MRF-based Background Initialisation for Improved Foreground Detection in Cluttered Surveillance Videos
Venue: arXiv cs.CV 2014
Year: 2014

Robust foreground object segmentation via background modelling is a difficult problem in cluttered environments, where obtaining a clear view of the background to model is almost impossible. In this paper, we propose a method capable of robustly estimating the background and detecting regions of interest in such environments. In particular, we propose to extend the background initialisation component of a recent patch-based foreground detection algorithm with an elaborate technique based on Markov Random Fields, where the optimal labelling solution is computed using iterated conditional modes. Rather than relying purely on local temporal statistics, the proposed technique takes into account the spatial continuity of the entire background. Experiments with several tracking algorithms on the CAVIAR dataset indicate that the proposed method leads to considerable improvements in object tracking accuracy, when compared to methods based on Gaussian mixture models and feature histograms.
Distributed Consensus Observers Based H-infinity Control of Dissipative PDE Systems Using Sensor Networks
Venue: arXiv cs.SY 2014
Year: 2014

This paper considers the problem of finite dimensional output feedback H-infinity control for a class of nonlinear spatially distributed processes (SDPs) described by highly dissipative partial differential equations (PDEs), whose state is observed by a sensor network (SN) with a given topology. A highly dissipative PDE system typically involves a spatial differential operator with eigenspectrum that can be partitioned into a finite-dimensional slow one and an infinite-dimensional stable fast complement. Motivated by this fact, the modal decomposition and singular perturbation techniques are initially applied to the PDE system to derive a finite dimensional ordinary differential equation model, which accurately captures the dynamics of the slow modes of the PDE system. Subsequently, based on the slow system and the topology of the SN, a set of finite dimensional distributed consensus observers are constructed to estimate the state of the slow system. Then, a centralized control scheme, which only uses the available estimates from a specified group of SN nodes, is proposed for the PDE system. An H-infinity control design method is developed in terms of bilinear matrix inequality (BMI), such that the original closed-loop PDE system is exponentially stable and a prescribed level of disturbance attenuation is satisfied for the slow system. Furthermore, a suboptimal H-infinity controller is also provided to make the attenuation level as small as possible, which can be obtained via a local optimization algorithm that treats the BMI as double linear matrix inequality. Finally, the proposed method is applied to the control of one dimensional Kuramoto-Sivashinsky equation (KSE) system.