OpenRaiser/Intern-Atlas huggingface dataset:
New algorithms and lower bounds for circuits with linear threshold gates
Venue: arXiv cs.CC 2014
Year: 2014

Let $ACC \circ THR$ be the class of constant-depth circuits comprised of AND, OR, and MOD$m$ gates (for some constant $m > 1$), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a "midpoint" between $ACC$ (where we know nontrivial lower bounds) and depth-two linear threshold circuits (where nontrivial lower bounds remain open). We give an algorithm for evaluating an arbitrary symmetric function of $2^{n^{o(1)}}$ $ACC \circ THR$ circuits of size $2^{n^{o(1)}}$, on all possible inputs, in $2^n \cdot poly(n)$ time. Several consequences are derived: $\bullet$ The number of satisfying assignments to an $ACC \circ THR$ circuit of subexponential size can be computed in $2^{n-n^{\varepsilon}}$ time (where $\varepsilon > 0$ depends on the depth and modulus of the circuit). $\bullet$ $NEXP$ does not have quasi-polynomial size $ACC \circ THR$ circuits, nor does $NEXP$ have quasi-polynomial size $ACC \circ SYM$ circuits. Nontrivial size lower bounds were not known even for $AND \circ OR \circ THR$ circuits. $\bullet$ Every 0-1 integer linear program with $n$ Boolean variables and $s$ linear constraints is solvable in $2^{n-Ω(n/((\log M)(\log s)^{5}))}\cdot poly(s,n,M)$ time with high probability, where $M$ upper bounds the bit complexity of the coefficients. (For example, 0-1 integer programs with weights in $[-2^{poly(n)},2^{poly(n)}]$ and $poly(n)$ constraints can be solved in $2^{n-Ω(n/\log^6 n)}$ time.) We also present an algorithm for evaluating depth-two linear threshold circuits (a.k.a., $THR \circ THR$) with exponential weights and $2^{n/24}$ size on all $2^n$ input assignments, running in $2^n \cdot poly(n)$ time. This is evidence that non-uniform lower bounds for $THR \circ THR$ are within reach.
Stretching Stretch
Venue: arXiv cs.DS 2014
Year: 2014

We give a generalized definition of stretch that simplifies the efficient construction of low-stretch embeddings suitable for graph algorithms. The generalization, based on discounting highly stretched edges by taking their $p$-th power for some $0 < p < 1$, is directly related to performances of existing algorithms. This discounting of high-stretch edges allows us to treat many classes of edges with coarser granularity. It leads to a two-pass approach that combines bottom-up clustering and top-down decompositions to construct these embeddings in $\mathcal{O}(m\log\log{n})$ time. Our algorithm parallelizes readily and can also produce generalizations of low-stretch subgraphs.
N2Sky - Neural Networks as Services in the Clouds
Venue: arXiv cs.NE 2014
Year: 2014

We present the N2Sky system, which provides a framework for the exchange of neural network specific knowledge, as neural network paradigms and objects, by a virtual organization environment. It follows the sky computing paradigm delivering ample resources by the usage of federated Clouds. N2Sky is a novel Cloud-based neural network simulation environment, which follows a pure service oriented approach. The system implements a transparent environment aiming to enable both novice and experienced users to do neural network research easily and comfortably. N2Sky is built using the RAVO reference architecture of virtual organizations which allows itself naturally integrating into the Cloud service stack (SaaS, PaaS, and IaaS) of service oriented architectures.
Reduction of Error-Trellises for Tail-Biting Convolutional Codes Using Shifted Error-Subsequences
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we discuss the reduction of error-trellises for tail-biting convolutional codes. In the case where some column of a parity-check matrix has a monomial factor (with indeterminate D), we show that the associated tail-biting error-trellis can be reduced by cyclically shifting the corresponding error-subsequence by l (the power of D) time units. We see that the resulting reduced error-trellis is again tail-biting. Moreover, we show that reduction is also possible using backward-shifted error-subsequences.
Multi-Step-Ahead Time Series Prediction using Multiple-Output Support Vector Regression
Venue: arXiv cs.LG 2014
Year: 2014

Accurate time series prediction over long future horizons is challenging and of great interest to both practitioners and academics. As a well-known intelligent algorithm, the standard formulation of Support Vector Regression (SVR) could be taken for multi-step-ahead time series prediction, only relying either on iterated strategy or direct strategy. This study proposes a novel multiple-step-ahead time series prediction approach which employs multiple-output support vector regression (M-SVR) with multiple-input multiple-output (MIMO) prediction strategy. In addition, the rank of three leading prediction strategies with SVR is comparatively examined, providing practical implications on the selection of the prediction strategy for multi-step-ahead forecasting while taking SVR as modeling technique. The proposed approach is validated with the simulated and real datasets. The quantitative and comprehensive assessments are performed on the basis of the prediction accuracy and computational cost. The results indicate that: 1) the M-SVR using MIMO strategy achieves the best accurate forecasts with accredited computational load, 2) the standard SVR using direct strategy achieves the second best accurate forecasts, but with the most expensive computational cost, and 3) the standard SVR using iterated strategy is the worst in terms of prediction accuracy, but with the least computational cost.
Progressive Filtering Using Multiresolution Histograms for Query by Humming System
Venue: arXiv cs.IR 2014
Year: 2014

The rising availability of digital music stipulates effective categorization and retrieval methods. Real world scenarios are characterized by mammoth music collections through pertinent and non-pertinent songs with reference to the user input. The primary goal of the research work is to counter balance the perilous impact of non-relevant songs through Progressive Filtering (PF) for Query by Humming (QBH) system. PF is a technique of problem solving through reduced space. This paper presents the concept of PF and its efficient design based on Multi-Resolution Histograms (MRH) to accomplish searching in manifolds. Initially the entire music database is searched to obtain high recall rate and narrowed search space. Later steps accomplish slow search in the reduced periphery and achieve additional accuracy. Experimentation on large music database using recursive programming substantiates the potential of the method. The outcome of proposed strategy glimpses that MRH effectively locate the patterns. Distances of MRH at lower level are the lower bounds of the distances at higher level, which guarantees evasion of false dismissals during PF. In due course, proposed method helps to strike a balance between efficiency and effectiveness. The system is scalable for large music retrieval systems and also data driven for performance optimization as an added advantage.
The semantic similarity ensemble
Venue: arXiv cs.CL 2014
Year: 2014

Computational measures of semantic similarity between geographic terms provide valuable support across geographic information retrieval, data mining, and information integration. To date, a wide variety of approaches to geo-semantic similarity have been devised. A judgment of similarity is not intrinsically right or wrong, but obtains a certain degree of cognitive plausibility, depending on how closely it mimics human behavior. Thus selecting the most appropriate measure for a specific task is a significant challenge. To address this issue, we make an analogy between computational similarity measures and soliciting domain expert opinions, which incorporate a subjective set of beliefs, perceptions, hypotheses, and epistemic biases. Following this analogy, we define the semantic similarity ensemble (SSE) as a composition of different similarity measures, acting as a panel of experts having to reach a decision on the semantic similarity of a set of geographic terms. The approach is evaluated in comparison to human judgments, and results indicate that an SSE performs better than the average of its parts. Although the best member tends to outperform the ensemble, all ensembles outperform the average performance of each ensemble's member. Hence, in contexts where the best measure is unknown, the ensemble provides a more cognitively plausible approach.
Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of Bits
Venue: arXiv cs.DS 2014
Year: 2014

A $\textit{compression scheme}$ $A$ for a class $\mathbb{G}$ of graphs consists of an encoding algorithm $\textit{Encode}_A$ that computes a binary string $\textit{Code}_A(G)$ for any given graph $G$ in $\mathbb{G}$ and a decoding algorithm $\textit{Decode}_A$ that recovers $G$ from $\textit{Code}_A(G)$. A compression scheme $A$ for $\mathbb{G}$ is $\textit{optimal}$ if both $\textit{Encode}_A$ and $\textit{Decode}_A$ run in linear time and the number of bits of $\textit{Code}_A(G)$ for any $n$-node graph $G$ in $\mathbb{G}$ is information-theoretically optimal to within lower-order terms. Trees and plane triangulations were the only known nontrivial graph classes that admit optimal compression schemes. Based upon Goodrich's separator decomposition for planar graphs and Djidjev and Venkatesan's planarizers for bounded-genus graphs, we give an optimal compression scheme for any hereditary (i.e., closed under taking subgraphs) class $\mathbb{G}$ under the premise that any $n$-node graph of $\mathbb{G}$ to be encoded comes with a genus-$o(\frac{n}{\log^2 n})$ embedding. By Mohar's linear-time algorithm that embeds a bounded-genus graph on a genus-$O(1)$ surface, our result implies that any hereditary class of genus-$O(1)$ graphs admits an optimal compression scheme. For instance, our result yields the first-known optimal compression schemes for planar graphs, plane graphs, graphs embedded on genus-$1$ surfaces, graphs with genus $2$ or less, $3$-colorable directed plane graphs, $4$-outerplanar graphs, and forests with degree at most $5$. For non-hereditary graph classes, we also give a methodology for obtaining optimal compression schemes. From this methodology, we give the first known optimal compression schemes for triangulations of genus-$O(1)$ surfaces and floorplans.
Association Rules Mining Based Clinical Observations
Venue: arXiv cs.DB 2014
Year: 2014

Healthcare institutes enrich the repository of patients' disease related information in an increasing manner which could have been more useful by carrying out relational analysis. Data mining algorithms are proven to be quite useful in exploring useful correlations from larger data repositories. In this paper we have implemented Association Rules mining based a novel idea for finding co-occurrences of diseases carried by a patient using the healthcare repository. We have developed a system-prototype for Clinical State Correlation Prediction (CSCP) which extracts data from patients' healthcare database, transforms the OLTP data into a Data Warehouse by generating association rules. The CSCP system helps reveal relations among the diseases. The CSCP system predicts the correlation(s) among primary disease (the disease for which the patient visits the doctor) and secondary disease/s (which is/are other associated disease/s carried by the same patient having the primary disease).
A Survey of Volunteered Open Geo-Knowledge Bases in the Semantic Web
Venue: arXiv cs.DL 2014
Year: 2014

Over the past decade, rapid advances in web technologies, coupled with innovative models of spatial data collection and consumption, have generated a robust growth in geo-referenced information, resulting in spatial information overload. Increasing 'geographic intelligence' in traditional text-based information retrieval has become a prominent approach to respond to this issue and to fulfill users' spatial information needs. Numerous efforts in the Semantic Geospatial Web, Volunteered Geographic Information (VGI), and the Linking Open Data initiative have converged in a constellation of open knowledge bases, freely available online. In this article, we survey these open knowledge bases, focusing on their geospatial dimension. Particular attention is devoted to the crucial issue of the quality of geo-knowledge bases, as well as of crowdsourced data. A new knowledge base, the OpenStreetMap Semantic Network, is outlined as our contribution to this area. Research directions in information integration and Geographic Information Retrieval (GIR) are then reviewed, with a critical discussion of their current limitations and future prospects.
Sentiment Analysis Using Collaborated Opinion Mining
Venue: arXiv cs.IR 2014
Year: 2014

Opinion mining and Sentiment analysis have emerged as a field of study since the widespread of World Wide Web and internet. Opinion refers to extraction of those lines or phrase in the raw and huge data which express an opinion. Sentiment analysis on the other hand identifies the polarity of the opinion being extracted. In this paper we propose the sentiment analysis in collaboration with opinion extraction, summarization, and tracking the records of the students. The paper modifies the existing algorithm in order to obtain the collaborated opinion about the students. The resultant opinion is represented as very high, high, moderate, low and very low. The paper is based on a case study where teachers give their remarks about the students and by applying the proposed sentiment analysis algorithm the opinion is extracted and represented.
Towards a Generic Framework for the Development of Unicode Based Digital Sindhi Dictionaries
Venue: arXiv cs.CL 2014
Year: 2014

Dictionaries are essence of any language providing vital linguistic recourse for the language learners, researchers and scholars. This paper focuses on the methodology and techniques used in developing software architecture for a UBSESD (Unicode Based Sindhi to English and English to Sindhi Dictionary). The proposed system provides an accurate solution for construction and representation of Unicode based Sindhi characters in a dictionary implementing Hash Structure algorithm and a custom java Object as its internal data structure saved in a file. The System provides facilities for Insertion, Deletion and Editing of new records of Sindhi. Through this framework any type of Sindhi to English and English to Sindhi Dictionary (belonging to different domains of knowledge, e.g. engineering, medicine, computer, biology etc.) could be developed easily with accurate representation of Unicode Characters in font independent manner.
On the Optimality of Treating Interference as Noise for $K$ user Parallel Gaussian Interference Networks
Venue: arXiv cs.IT 2014
Year: 2014

It has been shown recently by Geng et al. that in a $K$ user Gaussian interference network, if for each user the desired signal strength is no less than the sum of the strengths of the strongest interference from this user and the strongest interference to this user (all signal strengths measured in dB scale), then power control and treating interference as noise (TIN) is sufficient to achieve the entire generalized degrees of freedom (GDoF) region. Motivated by the intuition that the deterministic model of Avestimehr et al. (ADT deterministic model) is particularly suited for exploring the optimality of TIN, the results of Geng et al. are first re-visited under the ADT deterministic model, and are shown to directly translate between the Gaussian and deterministic settings. Next, we focus on the extension of these results to parallel interference networks, from a sum-capacity/sum-GDoF perspective. To this end, we interpret the explicit characterization of the sum-capacity/sum-GDoF of a TIN optimal network (without parallel channels) as a minimum weighted matching problem in combinatorial optimization, and obtain a simple characterization in terms of a partition of the interference network into vertex-disjoint cycles. Aided by insights from the cyclic partition, the sum-capacity optimality of TIN for $K$ user parallel interference networks is characterized for the ADT deterministic model, leading ultimately to corresponding GDoF results for the Gaussian setting. In both cases, subject to a mild invertibility condition the optimality of TIN is shown to extend to parallel networks in a separable fashion.
On List-decodability of Random Rank Metric Codes
Venue: arXiv cs.IT 2014
Year: 2014

In the present paper, we consider list decoding for both random rank metric codes and random linear rank metric codes. Firstly, we show that, for arbitrary $0<R<1$ and $ε>0$ ($ε$ and $R$ are independent), if $0<\frac{n}{m}\leq ε$, then with high probability a random rank metric code in $F_{q}^{m\times n}$ of rate $R$ can be list-decoded up to a fraction $(1-R-ε)$ of rank errors with constant list size $L$ satisfying $L\leq O(1/ε)$. Moreover, if $\frac{n}{m}\geqΘ_R(ε)$, any rank metric code in $F_{q}^{m\times n}$ with rate $R$ and decoding radius $ρ=1-R-ε$ can not be list decoded in ${\rm poly}(n)$ time. Secondly, we show that if $\frac{n}{m}$ tends to a constant $b\leq 1$, then every $F_q$-linear rank metric code in $F_{q}^{m\times n}$ with rate $R$ and list decoding radius $ρ$ satisfies the Gilbert-Varsharmov bound, i.e., $R\leq (1-ρ)(1-bρ)$. Furthermore, for arbitrary $ε>0$ and any $0<ρ<1$, with high probability a random $F_q$-linear rank metric codes with rate $R=(1-ρ)(1-bρ)-ε$ can be list decoded up to a fraction $ρ$ of rank errors with constant list size $L$ satisfying $L\leq O(\exp(1/ε))$.
A Rule-based Model for Customized Risk Identification in Distributed Software Development Projects
Venue: arXiv cs.SE 2014
Year: 2014

Many project risks in distributed software development are very different from the ones in collocated development and therefore are often overlooked. At the same time, they depend to a large extent on project-specific characteristics. This article presents a model for identifying risks early in a project. This model systematically captures experiences from past projects and is based on a set of logical rules describing how project characteristics influence typical risks in distributed development. Thus, the model is able to assess risks individually for each project. It was developed by applying qualitative content analysis to 19 interviews with practitioners. An evaluation using expert interviews showed that the risks identified by the model matched the actual experiences in 81% of the cases; of these, 40% have not been regarded yet at project start. The article describes the concepts of the model, its instantiation and evaluation, followed by a conclusion and future work.
Fault Detection for RC4 Algorithm and its Implementation on FPGA Platform
Venue: arXiv cs.AR 2014
Year: 2014

In hardware implementation of a cryptographic algorithm, one may achieve leakage of secret information by creating scopes to introduce controlled faulty bit(s) even though the algorithm is mathematically a secured one. The technique is very effective in respect of crypto processors embedded in smart cards. In this paper few fault detecting architectures for RC4 algorithm are designed and implemented on Virtex5(ML505, LX110t) FPGA board. The results indicate that the proposed architectures can handle most of the faults without loss of throughput consuming marginally additional hardware and power.
Transformation of Attributed Structures with Cloning (Long Version)
Venue: arXiv cs.SE 2014
Year: 2014

Copying, or cloning, is a basic operation used in the specification of many applications in computer science. However, when dealing with complex structures, like graphs, cloning is not a straightforward operation since a copy of a single vertex may involve (implicitly)copying many edges. Therefore, most graph transformation approaches forbid the possibility of cloning. We tackle this problem by providing a framework for graph transformations with cloning. We use attributed graphs and allow rules to change attributes. These two features (cloning/changing attributes) together give rise to a powerful formal specification approach. In order to handle different kinds of graphs and attributes, we first define the notion of attributed structures in an abstract way. Then we generalise the sesqui-pushout approach of graph transformation in the proposed general framework and give appropriate conditions under which attributed structures can be transformed. Finally, we instantiate our general framework with different examples, showing that many structures can be handled and that the proposed framework allows one to specify complex operations in a natural way.
Application of the Modified Fractal Signature Method for Terrain Classification from Synthetic Aperture Radar Images
Venue: arXiv cs.CV 2014
Year: 2014

In this paper the Modified Fractal Signature method is applied to real Synthetic Aperture Radar images provided to our research group by SET 163 Working Group on SAR radar techniques. This method uses the blanket technique to provide useful information for SAR image classification. It is based on the calculation of the volume of a blanket, corresponding to the image to be classified, and then on the calculation of the corresponding Fractal Area curve and Fractal Dimension curve of the image. The main idea concerning this proposed technique is the fact that different terrain types encountered in SAR images yield different values of Fractal Area curves and Fractal Dimension curves, upon which classification of different types of terrain is possible. As a result, a classification technique for five different terrain types, i.e. urban, suburban, rural, mountain and sea, is presented in this paper.
A survey of methods to ease the development of highly multilingual text mining applications
Venue: arXiv cs.CL 2014
Year: 2014

Multilingual text processing is useful because the information content found in different languages is complementary, both regarding facts and opinions. While Information Extraction and other text mining software can, in principle, be developed for many languages, most text analysis tools have only been applied to small sets of languages because the development effort per language is large. Self-training tools obviously alleviate the problem, but even the effort of providing training data and of manually tuning the results is usually considerable. In this paper, we gather insights by various multilingual system developers on how to minimise the effort of developing natural language processing applications for many languages. We also explain the main guidelines underlying our own effort to develop complex text mining software for tens of languages. While these guidelines - most of all: extreme simplicity - can be very restrictive and limiting, we believe to have shown the feasibility of the approach through the development of the Europe Media Monitor (EMM) family of applications (http://emm.newsbrief.eu/overview.html). EMM is a set of complex media monitoring tools that process and analyse up to 100,000 online news articles per day in between twenty and fifty languages. We will also touch upon the kind of language resources that would make it easier for all to develop highly multilingual text mining applications. We will argue that - to achieve this - the most needed resources would be freely available, simple, parallel and uniform multilingual dictionaries, corpora and software tools.