OpenRaiser/Intern-Atlas huggingface dataset:
An improved, easily computable combinatorial lower bound for weighted graph bipartitioning
Venue: arXiv cs.DS 2014
Year: 2014

There has recently been much progress on exact algorithms for the (un)weighted graph (bi)partitioning problem using branch-and-bound and related methods. In this note we present and improve an easily computable, purely combinatorial lower bound for the weighted bipartitioning problem. The bound is computable in $O(n\log n+m)$ time steps for weighted graphs with $n$ vertices and $m$ edges. In the branch-and-bound setting, the bound for each new subproblem can be updated in $O(n+(m/n)\log n)$ time steps amortized over a series of $n$ branching steps; a rarely triggered tightening of the bound requires search on the graph of unassigned vertices and can take from $O(n+m)$ to $O(nm+n^2\log n)$ steps depending on implementation and possible bound quality. Representing a subproblem uses $O(n)$ space. Although the bound is weak, we believe that it can be advantageous in a parallel setting to be able to generate many subproblems fast, possibly out-weighting the advantages of tighter, but much more expensive (algebraic, spectral, flow) lower bounds. We use a recent priority task-scheduling framework for giving a parallel implementation, and show the relative improvements in bound quality and solution speed by the different contributions of the lower bound. A detailed comparison with standardized input graphs to other lower bounds and frameworks is pending. Detailed investigations of branching and subproblem selection rules are likewise not the focus here, but various options are discussed.
Matching in Gabriel Graphs
Venue: arXiv cs.CG 2014
Year: 2014

Given a set $P$ of $n$ points in the plane, the order-$k$ Gabriel graph on $P$, denoted by $k$-$GG$, has an edge between two points $p$ and $q$ if and only if the closed disk with diameter $pq$ contains at most $k$ points of $P$, excluding $p$ and $q$. We study matching problems in $k$-$GG$ graphs. We show that a Euclidean bottleneck perfect matching of $P$ is contained in $10$-$GG$, but $8$-$GG$ may not have any Euclidean bottleneck perfect matching. In addition we show that $0$-$GG$ has a matching of size at least $\frac{n-1}{4}$ and this bound is tight. We also prove that $1$-$GG$ has a matching of size at least $\frac{2(n-1)}{5}$ and $2$-$GG$ has a perfect matching. Finally we consider the problem of blocking the edges of $k$-$GG$.
Automatic Generation of Loop-Invariants for Matrix Operations
Venue: arXiv cs.MS 2014
Year: 2014

In recent years it has been shown that for many linear algebra operations it is possible to create families of algorithms following a very systematic procedure. We do not refer to the fine tuning of a known algorithm, but to a methodology for the actual generation of both algorithms and routines to solve a given target matrix equation. Although systematic, the methodology relies on complex algebraic manipulations and non-obvious pattern matching, making the procedure challenging to be performed by hand, our goal is the development of a fully automated system that from the sole description of a target equation creates multiple algorithms and routines. We present CL1ck, a symbolic system written in Mathematica, that starts with an equation, decomposes it into multiple equations, and returns a set of loop-invariants for the algorithms -- yet to be generated -- that will solve the equation. In a successive step each loop-invariant is then mapped to its corresponding algorithm and routine. For a large class of equations, the methodology generates known algorithms as well as many previously unknown ones. Most interestingly, the methodology unifies algorithms traditionally developed in isolation. As an example, the five well known algorithms for the LU factorization are for the first time unified under a common root.
Broadcasting Automata and Patterns on Z^2
Venue: arXiv cs.FL 2014
Year: 2014

The Broadcasting Automata model draws inspiration from a variety of sources such as Ad-Hoc radio networks, cellular automata, neighbourhood se- quences and nature, employing many of the same pattern forming methods that can be seen in the superposition of waves and resonance. Algorithms for broad- casting automata model are in the same vain as those encountered in distributed algorithms using a simple notion of waves, messages passed from automata to au- tomata throughout the topology, to construct computations. The waves generated by activating processes in a digital environment can be used for designing a vari- ety of wave algorithms. In this chapter we aim to study the geometrical shapes of informational waves on integer grid generated in broadcasting automata model as well as their potential use for metric approximation in a discrete space. An explo- ration of the ability to vary the broadcasting radius of each node leads to results of categorisations of digital discs, their form, composition, encodings and gener- ation. Results pertaining to the nodal patterns generated by arbitrary transmission radii on the plane are explored with a connection to broadcasting sequences and ap- proximation of discrete metrics of which results are given for the approximation of astroids, a previously unachievable concave metric, through a novel application of the aggregation of waves via a number of explored functions.
Distributed Widely Linear Frequency Estimation in Unbalanced Three Phase Power Systems
Venue: arXiv cs.SY 2014
Year: 2014

A novel method for distributed estimation of the frequency of power systems is introduced based on the cooperation between multiple measurement nodes. The proposed distributed widely linear complex Kalman filter (D-ACKF) and the distributed widely linear extended complex Kalman filter (D-AECKF) employ a widely linear state space and augmented complex statistics to deal with unbalanced system conditions and the generality complex signals, both second order circular (proper) and second order noncircular (improper). It is shown that the current, strictly linear, estimators are inadequate for unbalanced systems, a typical case in smart grids, as they do not account for either the noncircularity of Clarke's αβ-voltage in unbalanced conditions or the correlated nature of nodal disturbances. We illuminate the relationship between the degree of circularity of Clarke's voltage and system imbalance, and prove that the proposed widely linear estimators are optimal for such conditions, while also accounting for the correlated and noncircular nature of real-world nodal disturbances. {Synthetic and real world} case studies over a range of power system conditions illustrate the theoretical and practical advantages of the proposed methodology.
Term-Weighting Learning via Genetic Programming for Text Classification
Venue: arXiv cs.NE 2014
Year: 2014

This paper describes a novel approach to learning term-weighting schemes (TWSs) in the context of text classification. In text mining a TWS determines the way in which documents will be represented in a vector space model, before applying a classifier. Whereas acceptable performance has been obtained with standard TWSs (e.g., Boolean and term-frequency schemes), the definition of TWSs has been traditionally an art. Further, it is still a difficult task to determine what is the best TWS for a particular problem and it is not clear yet, whether better schemes, than those currently available, can be generated by combining known TWS. We propose in this article a genetic program that aims at learning effective TWSs that can improve the performance of current schemes in text classification. The genetic program learns how to combine a set of basic units to give rise to discriminative TWSs. We report an extensive experimental study comprising data sets from thematic and non-thematic text classification as well as from image classification. Our study shows the validity of the proposed method; in fact, we show that TWSs learned with the genetic program outperform traditional schemes and other TWSs proposed in recent works. Further, we show that TWSs learned from a specific domain can be effectively used for other tasks.
A Full Characterization of Irrelevant Components in Diameter Constrained Reliability
Venue: arXiv cs.DC 2014
Year: 2014

In classical network reliability analysis, the system under study is a network with perfect nodes but imperfect link, that fail stochastically and independently. There, the goal is to find the probability that the resulting random graph is connected, called \emph{reliability}. Although the exact reliability computation belongs to the class of $\mathcal{NP}$-Hard problems, the literature offers three exact methods for exact reliability computation, to know, Sum of Disjoint Products (SDPs), Inclusion-Exclusion and Factorization. Inspired in delay-sensitive applications in telecommunications, Héctor Cancela and Louis Petingi defined in 2001 the diameter-constrained reliability, where terminals are required to be connected by $d$ hops or less, being $d$ a positive integer, called diameter. Factorization theory in classical network reliability is a mature area. However, an extension to the diameter-constrained context requires at least the recognition of irrelevant links, and an extension of deletion-contraction formula. In this paper, we fully characterize the determination of irrelevant links. Diameter-constrained reliability invariants are presented, which, together with the recognition of irrelevant links, represent the building-blocks for a new factorization theory. The paper is closed with a discussion of trends for future work.
Efficient classification of billions of points into complex geographic regions using hierarchical triangular mesh
Venue: arXiv cs.DB 2014
Year: 2014

We present a case study about the spatial indexing and regional classification of billions of geographic coordinates from geo-tagged social network data using Hierarchical Triangular Mesh (HTM) implemented for Microsoft SQL Server. Due to the lack of certain features of the HTM library, we use it in conjunction with the GIS functions of SQL Server to significantly increase the efficiency of pre-filtering of spatial filter and join queries. For example, we implemented a new algorithm to compute the HTM tessellation of complex geographic regions and precomputed the intersections of HTM triangles and geographic regions for faster false-positive filtering. With full control over the index structure, HTM-based pre-filtering of simple containment searches outperforms SQL Server spatial indices by a factor of ten and HTM-based spatial joins run about a hundred times faster.
Im2Fit: Fast 3D Model Fitting and Anthropometrics using Single Consumer Depth Camera and Synthetic Data
Venue: arXiv cs.CV 2014
Year: 2014

Recent advances in consumer depth sensors have created many opportunities for human body measurement and modeling. Estimation of 3D body shape is particularly useful for fashion e-commerce applications such as virtual try-on or fit personalization. In this paper, we propose a method for capturing accurate human body shape and anthropometrics from a single consumer grade depth sensor. We first generate a large dataset of synthetic 3D human body models using real-world body size distributions. Next, we estimate key body measurements from a single monocular depth image. We combine body measurement estimates with local geometry features around key joint positions to form a robust multi-dimensional feature vector. This allows us to conduct a fast nearest-neighbor search to every sample in the dataset and return the closest one. Compared to existing methods, our approach is able to predict accurate full body parameters from a partial view using measurement parameters learned from the synthetic dataset. Furthermore, our system is capable of generating 3D human mesh models in real-time, which is significantly faster than methods which attempt to model shape and pose deformations. To validate the efficiency and applicability of our system, we collected a dataset that contains frontal and back scans of 83 clothed people with ground truth height and weight. Experiments on real-world dataset show that the proposed method can achieve real-time performance with competing results achieving an average error of 1.9 cm in estimated measurements.
Sequence Design for Cognitive CDMA Communications under Arbitrary Spectrum Hole Constraint
Venue: arXiv cs.IT 2014
Year: 2014

To support interference-free quasi-synchronous code-division multiple-access (QS-CDMA) communication with low spectral density profile in a cognitive radio (CR) network, it is desirable to design a set of CDMA spreading sequences with zero-correlation zone (ZCZ) property. However, traditional ZCZ sequences (which assume the availability of the entire spectral band) cannot be used because their orthogonality will be destroyed by the spectrum hole constraint in a CR channel. To date, analytical construction of ZCZ CR sequences remains open. Taking advantage of the Kronecker sequence property, a novel family of sequences (called "quasi-ZCZ" CR sequences) which displays zero cross-correlation and near-zero auto-correlation zone property under arbitrary spectrum hole constraint is presented in this paper. Furthermore, a novel algorithm is proposed to jointly optimize the peak-to-average power ratio (PAPR) and the periodic auto-correlations of the proposed quasi-ZCZ CR sequences. Simulations show that they give rise to single-user bit-error-rate performance in CR-CDMA systems which outperform traditional non-contiguous multicarrier CDMA and transform domain communication systems; they also lead to CR-CDMA systems which are more resilient than non-contiguous OFDM systems to spectrum sensing mismatch, due to the wideband spreading.
Facial Feature Point Detection: A Comprehensive Survey
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a comprehensive survey of facial feature point detection with the assistance of abundant manually labeled images. Facial feature point detection favors many applications such as face recognition, animation, tracking, hallucination, expression analysis and 3D face modeling. Existing methods can be categorized into the following four groups: constrained local model (CLM)-based, active appearance model (AAM)-based, regression-based, and other methods. CLM-based methods consist of a shape model and a number of local experts, each of which is utilized to detect a facial feature point. AAM-based methods fit a shape model to an image by minimizing texture synthesis errors. Regression-based methods directly learn a mapping function from facial image appearance to facial feature points. Besides the above three major categories of methods, there are also minor categories of methods which we classify into other methods: graphical model-based methods, joint face alignment methods, independent facial feature point detectors, and deep learning-based methods. Though significant progress has been made, facial feature point detection is limited in its success by wild and real-world conditions: variations across poses, expressions, illuminations, and occlusions. A comparative illustration and analysis of representative methods provide us a holistic understanding and deep insight into facial feature point detection, which also motivates us to explore promising future directions.
Generating abbreviations using Google Books library
Venue: arXiv cs.CL 2014
Year: 2014

The article describes the original method of creating a dictionary of abbreviations based on the Google Books Ngram Corpus. The dictionary of abbreviations is designed for Russian, yet as its methodology is universal it can be applied to any language. The dictionary can be used to define the function of the period during text segmentation in various applied systems of text processing. The article describes difficulties encountered in the process of its construction as well as the ways to overcome them. A model of evaluating a probability of first and second type errors (extraction accuracy and fullness) is constructed. Certain statistical data for the use of abbreviations are provided.
Security Formalizations and Their Relationships for Encryption and Key Agreement in Information-Theoretic Cryptography
Venue: arXiv cs.CR 2014
Year: 2014

This paper revisits formalizations of information-theoretic security for symmetric-key encryption and key agreement protocols which are very fundamental primitives in cryptography. In general, we can formalize information-theoretic security in various ways: some of them can be formalized as stand-alone security by extending (or relaxing) Shannon's perfect secrecy or by other ways such as semantic security; some of them can be done based on composable security. Then, a natural question about this is: what is the gap between the formalizations? To answer the question, we investigate relationships between several formalizations of information-theoretic security for symmetric-key encryption and key agreement protocols. Specifically, for symmetric-key encryption protocols in a general setting including the case where there exist decryption-errors, we deal with the following formalizations of security: formalizations extended (or relaxed) from Shannon's perfect secrecy by using mutual information and statistical distance; information-theoretic analogues of indistinguishability and semantic security by Goldwasser and Micali; and composable security by Maurer et al. and Canetti. Then, we explicitly show the equivalence and non-equivalence between those formalizations. Under the model, we also derive lower bounds on the adversary's (or distinguisher's) advantage and the size of secret-keys required under all of the above formalizations. Although some of them may be already known, we can explicitly derive them all at once through our relationships between the formalizations. In addition, we briefly observe impossibility results which easily follow from the lower bounds. The similar results are also shown for key agreement protocols in a general setting including the case where there exist agreement-errors in the protocols.
Corpora Preparation and Stopword List Generation for Arabic data in Social Network
Venue: arXiv cs.CL 2014
Year: 2014

This paper proposes a methodology to prepare corpora in Arabic language from online social network (OSN) and review site for Sentiment Analysis (SA) task. The paper also proposes a methodology for generating a stopword list from the prepared corpora. The aim of the paper is to investigate the effect of removing stopwords on the SA task. The problem is that the stopwords lists generated before were on Modern Standard Arabic (MSA) which is not the common language used in OSN. We have generated a stopword list of Egyptian dialect and a corpus-based list to be used with the OSN corpora. We compare the efficiency of text classification when using the generated lists along with previously generated lists of MSA and combining the Egyptian dialect list with the MSA list. The text classification was performed using Naïve Bayes and Decision Tree classifiers and two feature selection approaches, unigrams and bigram. The experiments show that the general lists containing the Egyptian dialects words give better performance than using lists of MSA stopwords only.
Network Performance Rank: An Approach for Comparison of Complex Networks
Venue: arXiv cs.SI 2014
Year: 2014

Researchers have typically concentrated on analyzing what happens internally in a complex network and using this to distinguish between nodes. However, there has been less effort towards comparing between different networks. In this paper, we proposed a novel approach to rank alternative complex networks based on their performances. We consider this as a ranking problem in decision analysis based on occurring positive/negative frequent events as criteria, and using the TOPSIS method to rank alternatives. In order to assign a score to the networks for each criterion, a statistical method that estimates the expected value of positive/negative frequent events on a random node is presented. The proposed technique is efficient in terms of algorithm complexity and is capable of discriminating events occurring between important nodes over those between less significant nodes. The experiments, conducted on several synthetic networks, demonstrate the feasibility and applicability of the ranking methodology.
Necessary and Sufficient Conditions on Partial Orders for Modeling Concurrent Computations
Venue: arXiv cs.DC 2014
Year: 2014

Partial orders are used extensively for modeling and analyzing concurrent computations. In this paper, we define two properties of partially ordered sets: width-extensibility and interleaving-consistency, and show that a partial order can be a valid state based model: (1) of some synchronous concurrent computation iff it is width-extensible, and (2) of some asynchronous concurrent computation iff it is width-extensible and interleaving-consistent. We also show a duality between the event based and state based models of concurrent computations, and give algorithms to convert models between the two domains. When applied to the problem of checkpointing, our theory leads to a better understanding of some existing results and algorithms in the field. It also leads to efficient detection algorithms for predicates whose evaluation requires knowledge of states from all the processes in the system.
Bayesian regression and Bitcoin
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we discuss the method of Bayesian regression and its efficacy for predicting price variation of Bitcoin, a recently popularized virtual, cryptographic currency. Bayesian regression refers to utilizing empirical data as proxy to perform Bayesian inference. We utilize Bayesian regression for the so-called "latent source model". The Bayesian regression for "latent source model" was introduced and discussed by Chen, Nikolov and Shah (2013) and Bresler, Chen and Shah (2014) for the purpose of binary classification. They established theoretical as well as empirical efficacy of the method for the setting of binary classification. In this paper, instead we utilize it for predicting real-valued quantity, the price of Bitcoin. Based on this price prediction method, we devise a simple strategy for trading Bitcoin. The strategy is able to nearly double the investment in less than 60 day period when run against real data trace.
Spin Orbit Torque Based Electronic Neuron
Venue: arXiv cs.ET 2014
Year: 2014

A device based on current-induced spin-orbit torque (SOT) that functions as an electronic neuron is proposed in this work. The SOT device implements an artificial neuron's thresholding (transfer) function. In the first step of a two-step switching scheme, a charge current places the magnetization of a nano-magnet along the hard-axis i.e. an unstable point for the magnet. In the second step, the SOT device (neuron) receives a current (from the synapses) which moves the magnetization from the unstable point to one of the two stable states. The polarity of the synaptic current encodes the excitatory and inhibitory nature of the neuron input, and determines the final orientation of the magnetization. A resistive crossbar array, functioning as synapses, generates a bipolar current that is a weighted sum of the inputs. The simulation of a two layer feed-forward Artificial Neural Network (ANN) based on the SOT electronic neuron shows that it consumes ~3X lower power than a 45nm digital CMOS implementation, while reaching ~80% accuracy in the classification of one hundred images of handwritten digits from the MNIST dataset.
Combined Algorithm for Data Mining using Association rules
Venue: arXiv cs.DB 2014
Year: 2014

Association Rule mining is one of the most important fields in data mining and knowledge discovery. This paper proposes an algorithm that combines the simple association rules derived from basic Apriori Algorithm with the multiple minimum support using maximum constraints. The algorithm is implemented, and is compared to its predecessor algorithms using a novel proposed comparison algorithm. Results of applying the proposed algorithm show faster performance than other algorithms without scarifying the accuracy.