OpenRaiser/Intern-Atlas huggingface dataset:
Performance Analysis on Evolutionary Algorithms for the Minimum Label Spanning Tree Problem
Venue: arXiv cs.NE 2014
Year: 2014

Some experimental investigations have shown that evolutionary algorithms (EAs) are efficient for the minimum label spanning tree (MLST) problem. However, we know little about that in theory. As one step towards this issue, we theoretically analyze the performances of the (1+1) EA, a simple version of EAs, and a multi-objective evolutionary algorithm called GSEMO on the MLST problem. We reveal that for the MLST$_{b}$ problem the (1+1) EA and GSEMO achieve a $\frac{b+1}{2}$-approximation ratio in expected polynomial times of $n$ the number of nodes and $k$ the number of labels. We also show that GSEMO achieves a $(2ln(n))$-approximation ratio for the MLST problem in expected polynomial time of $n$ and $k$. At the same time, we show that the (1+1) EA and GSEMO outperform local search algorithms on three instances of the MLST problem. We also construct an instance on which GSEMO outperforms the (1+1) EA.
The Role of Peer Influence in Churn in Wireless Networks
Venue: arXiv cs.SI 2014
Year: 2014

Subscriber churn remains a top challenge for wireless carriers. These carriers need to understand the determinants of churn to confidently apply effective retention strategies to ensure their profitability and growth. In this paper, we look at the effect of peer influence on churn and we try to disentangle it from other effects that drive simultaneous churn across friends but that do not relate to peer influence. We analyze a random sample of roughly 10 thousand subscribers from large dataset from a major wireless carrier over a period of 10 months. We apply survival models and generalized propensity score to identify the role of peer influence. We show that the propensity to churn increases when friends do and that it increases more when many strong friends churn. Therefore, our results suggest that churn managers should consider strategies aimed at preventing group churn. We also show that survival models fail to disentangle homophily from peer influence over-estimating the effect of peer influence.
Overcoming the Curse of Sentence Length for Neural Machine Translation using Automatic Segmentation
Venue: arXiv cs.CL 2014
Year: 2014

The authors of (Cho et al., 2014a) have shown that the recently introduced neural network translation systems suffer from a significant drop in translation quality when translating long sentences, unlike existing phrase-based translation systems. In this paper, we propose a way to address this issue by automatically segmenting an input sentence into phrases that can be easily translated by the neural network translation model. Once each segment has been independently translated by the neural machine translation model, the translated clauses are concatenated to form a final translation. Empirical results show a significant improvement in translation quality for long sentences.
Improving Accessibility of Archived Raster Dictionaries of Complex Script Languages
Venue: arXiv cs.DL 2014
Year: 2014

We propose an approach to index raster images of dictionary pages which in turn would require very little manual effort to enable direct access to the appropriate pages of the dictionary for lookup. Accessibility is further improved by feedback and crowdsourcing that enables highlighting of the specific location on the page where the lookup word is found, annotation, digitization, and fielded searching. This approach is equally applicable on simple scripts as well as complex writing systems. Using our proposed approach, we have built a Web application called "Dictionary Explorer" which supports word indexes in various languages and every language can have multiple dictionaries associated with it. Word lookup gives direct access to appropriate pages of all the dictionaries of that language simultaneously. The application has exploration features like searching, pagination, and navigating the word index through a tree-like interface. The application also supports feedback, annotation, and digitization features. Apart from the scanned images, "Dictionary Explorer" aggregates results from various sources and user contributions in Unicode. We have evaluated the time required for indexing dictionaries of different sizes and complexities in the Urdu language and examined various trade-offs in our implementation. Using our approach, a single person can make a dictionary of 1,000 pages searchable in less than an hour.
MEEP: Multihop Energy Efficient Protocol For Heterogeneous Wireless Sensor Network
Venue: arXiv cs.NI 2014
Year: 2014

Energy conservation of sensor nodes for increasing the network life is the most crucial design goal while developing efficient routing protocol for wireless sensor networks. Recent technological advances help in the development of wide variety of sensor nodes. Heterogeneity takes the advantage of different types of sensor nodes and improves the energy efficiency and network life. Generally sensors are deployed randomly and densely in a sensing region so short distance multihop communication reduces the long distance transmission in the sensor network. In this research paper MEEP (multihop energy efficient protocol for heterogeneous sensor network) is proposed. The proposed protocol combines the idea of clustering and multihop communication. Heterogeneity is created in the network by using some nodes of high energy. Low energy nodes use a residual energy based scheme to become a cluster head. High energy nodes act as the relay nodes for low energy cluster head when they are not performing the duty of a cluster head to save their energy further. Protocol also suggests a sleep state for nodes in the cluster formation process for saving energy and increasing the life of sensor network. Simulation result shows that the proposed scheme is better than other two level heterogeneous sensor network protocol like SEP in energy efficiency and network life.
Model Reduction of Linear Switched Systems by Restricting Discrete Dynamics
Venue: arXiv cs.SY 2014
Year: 2014

We present a procedure for reducing the number of continuous states of discrete-time linear switched systems, such that the reduced system has the same behavior as the original system for a subset of switching sequences. The proposed method is expected to be useful for abstraction based control synthesis methods for hybrid systems.
Multilinear PageRank
Venue: arXiv cs.NA 2014
Year: 2014

In this paper, we first extend the celebrated PageRank modification to a higher-order Markov chain. Although this system has attractive theoretical properties, it is computationally intractable for many interesting problems. We next study a computationally tractable approximation to the higher-order PageRank vector that involves a system of polynomial equations called multilinear PageRank, which is a type of tensor PageRank vector. It is motivated by a novel "spacey random surfer" model, where the surfer remembers bits and pieces of history and is influenced by this information. The underlying stochastic process is an instance of a vertex-reinforced random walk. We develop convergence theory for a simple fixed-point method, a shifted fixed-point method, and a Newton iteration in a particular parameter regime. In marked contrast to the case of the PageRank vector of a Markov chain where the solution is always unique and easy to compute, there are parameter regimes of multilinear PageRank where solutions are not unique and simple algorithms do not converge. We provide a repository of these non-convergent cases that we encountered through exhaustive enumeration and randomly sampling that we believe is useful for future study of the problem.
Dynamic Homeostasis in Packet Switching Networks
Venue: arXiv cs.NI 2014
Year: 2014

In this study, we investigate the adaptation and robustness of a packet switching network (PSN), the fundamental architecture of the Internet. We claim that the adaptation introduced by a transmission control protocol (TCP) congestion control mechanism is interpretable as the self-organization of multiple attractors and stability to switch from one attractor to another. To discuss this argument quantitatively, we study the adaptation of the Internet by simulating a PSN using ns-2. Our hypothesis is that the robustness and fragility of the Internet can be attributed to the inherent dynamics of the PSN feedback mechanism called the congestion window size, or \textit{cwnd}. By varying the data input into the PSN system, we investigate the possible self-organization of attractors in cwnd temporal dynamics and discuss the adaptability and robustness of PSNs. The present study provides an example of Ashby's Law of Requisite Variety in action.
A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tile set synthesis
Venue: arXiv cs.DM 2014
Year: 2014

Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular (color) pattern. For k >= 1, k-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. A computer-assisted proof has been recently proposed for 2-PATS by Kari et al. [arXiv:1404.0967 (2014)]. In contrast, the best known manually-checkable proof is for the NP-hardness of 29-PATS by Johnsen, Kao, and Seki [ISAAC 2013, LNCS 8283, pp.~699-710]. We propose a manually-checkable proof for the NP-hardness of 11-PATS.
An Aspect-Oriented Approach for SaaS Application Customization
Venue: arXiv cs.SE 2014
Year: 2014

Multi-tenancy is one of the most important concepts for any Software as a Service (SaaS) application. Multi-tenant SaaS application serves a large number of tenants with one single application instance. Complex SaaS application that serves significant number of tenants could have a huge number of customizations with complicated relationships, which increases the customization complexity and reduces the customization understandability. Modeling such customizations, validating each tenant's customization, and adapting SaaS applications on the fly based on each tenant's requirements become very complex tasks. To mitigate these challenges, we propose an aspect-oriented approach that makes use of the Orthogonal Variability Model (OVM) and Metagraphs. The OVM is used to provide the tenants with simple and understandable customization model. A Metagraph-based algorithm has been developed to validate tenants' customizations. On the other hand, the aspect-oriented approach offers a high level of runtime adaptability.
On the Optimality of Keyless Authentication in a Noisy Model
Venue: arXiv cs.IT 2014
Year: 2014

We further study the keyless authentication problem in a noisy model in our previous work, where no secret setup is available for sender Alice and receiver Bob while there is DMC $W_1$ from Alice to Bob and a two-way noiseless but insecure channel between them. We propose a construction such that the message length over DMC $W_1$ does not depend on the size of the source space. If the source space is ${\cal S}$ and the number of channel $W_1$ uses is $n$, then our protocol only has a round complexity of $\log^*|{\cal S}|-\log^*n+4.$ In addition, we show that the round complexity of any secure protocol in our model is lower bounded by $\log^*|{\cal S}|-\log^* n-5$. We also obtain a lower bound on the success probability when the message size on DMC $W_1$ is given. Finally, we derive the capacity for a non-interactive authentication protocol under general DMCs, which extends the result under BSCs in our previous work.
Online Multi-Coloring with Advice
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight upper and lower bounds for the most standard topologies of cellular networks, paths and hexagonal graphs. For the path, negative results trivially carry over to bipartite graphs, and our positive results are also valid for bipartite graphs. The advice given represents information that is likely to be available, studying for instance the data from earlier similar periods of time.
Diophantine properties of Brownian motion: recursive aspects
Venue: arXiv cs.LO 2014
Year: 2014

We use recent results on the Fourier analysis of the zero sets of Brownian motion to explore the diophantine properties of an algorithmically random Brownian motion (also known as a complex oscillation). We discuss the construction and definability of perfect sets which are linearly independent over the rationals directly from Martin-Löf random reals. Finally we explore the recent work of Tsirelson on countable dense sets to study the diophantine properties of local minimisers of Brownian motion.
Identifying Synapses Using Deep and Wide Multiscale Recursive Networks
Venue: arXiv cs.CV 2014
Year: 2014

In this work, we propose a learning framework for identifying synapses using a deep and wide multi-scale recursive (DAWMR) network, previously considered in image segmentation applications. We apply this approach on electron microscopy data from invertebrate fly brain tissue. By learning features directly from the data, we are able to achieve considerable improvements over existing techniques that rely on a small set of hand-designed features. We show that this system can reduce the amount of manual annotation required, in both acquisition of training data as well as verification of inferred detections.
Revealing Comparative Advantages in the Backbone of Science
Venue: arXiv cs.DL 2014
Year: 2014

Mapping Science across countries is a challenging task in the field of Scientometrics. A number of efforts trying to cope with this task has been discussed in the state of the art, addressing this challenge by processing collections of scientific digital libraries and visualizing author-based measures (for instance, the h-index) or document-based measures (for instance, the averaged number of citations per document). A major drawback of these approaches is related to the presence of bias. The bigger the country, the higher the measure value. We explore the use of an econometric index to tackle this limitation, known as the Revealed Comparative Advantage measure (RCA). Using RCA, the diversity and ubiquity of each field of knowledge is mapped across countries. Then, a RCA-based proximity function is explored to visualize citation and h-index ubiquity. Science maps relating 27 knowledge areas and 237 countries are introduced using data crawled from Scimago that ranges from 1996 to 2011. Our results shows that the proposal is feasible and can be extended to ellaborate a global scientific production characterization.
Novel Methods for Activity Classification and Occupany Prediction Enabling Fine-grained HVAC Control
Venue: arXiv cs.LG 2014
Year: 2014

Much of the energy consumption in buildings is due to HVAC systems, which has motivated several recent studies on making these systems more energy- efficient. Occupancy and activity are two important aspects, which need to be correctly estimated for optimal HVAC control. However, state-of-the-art methods to estimate occupancy and classify activity require infrastructure and/or wearable sensors which suffers from lower acceptability due to higher cost. Encouragingly, with the advancement of the smartphones, these are becoming more achievable. Most of the existing occupancy estimation tech- niques have the underlying assumption that the phone is always carried by its user. However, phones are often left at desk while attending meeting or other events, which generates estimation error for the existing phone based occupancy algorithms. Similarly, in the recent days the emerging theory of Sparse Random Classifier (SRC) has been applied for activity classification on smartphone, however, there are rooms to improve the on-phone process- ing. We propose a novel sensor fusion method which offers almost 100% accuracy for occupancy estimation. We also propose an activity classifica- tion algorithm, which offers similar accuracy as of the state-of-the-art SRC algorithms while offering 50% reduction in processing.
Complexity to Find Wiener Index of Some Graphs
Venue: arXiv cs.DM 2014
Year: 2014

The Wiener index is one of the oldest graph parameter which is used to study molecular-graph-based structure. This parameter was first proposed by Harold Wiener in 1947 to determining the boiling point of paraffin. The Wiener index of a molecular graph measures the compactness of the underlying molecule. This parameter is wide studied area for molecular chemistry. It is used to study the physio-chemical properties of the underlying organic compounds. The Wiener index of a connected graph is denoted by W(G) and is defined as, that is W(G) is the sum of distances between all pairs (ordered) of vertices of G. In this paper, we give the algorithmic idea to find the Wiener index of some graphs, like cactus graphs and intersection graphs, viz. interval, circular-arc, permutation, trapezoid graphs.
Depth image hand tracking from an overhead perspective using partially labeled, unbalanced data: Development and real-world testing
Venue: arXiv cs.CV 2014
Year: 2014

We present the development and evaluation of a hand tracking algorithm based on single depth images captured from an overhead perspective for use in the COACH prompting system. We train a random decision forest body part classifier using approximately 5,000 manually labeled, unbalanced, partially labeled training images. The classifier represents a random subset of pixels in each depth image with a learned probability density function across all trained body parts. A local mode-find approach is used to search for clusters present in the underlying feature space sampled by the classified pixels. In each frame, body part positions are chosen as the mode with the highest confidence. User hand positions are translated into hand washing task actions based on proximity to environmental objects. We validate the performance of the classifier and task action proposals on a large set of approximately 24,000 manually labeled images.
Multi layer Gelfand Pinsker Strategies for the Generalized Multiple Access Channel
Venue: arXiv cs.IT 2014
Year: 2014

We study a two-user state-dependent generalized multiple-access channel (GMAC) with correlated states. It is assumed that each encoder has \emph{noncausal} access to channel state information (CSI). We develop an achievable rate region by employing rate-splitting, block Markov encoding, Gelfand--Pinsker multicoding, superposition coding and joint typicality decoding. In the proposed scheme, the encoders use a partial decoding strategy to collaborate in the next block, and the receiver uses a backward decoding strategy with joint unique decoding at each stage. Our achievable rate region includes several previously known regions proposed in the literature for different scenarios of multiple-access and relay channels. Then, we consider two Gaussian GMACs with additive interference. In the first model, we assume that the interference is known noncausally at both of the encoders and construct a multi-layer Costa precoding scheme that removes \emph{completely} the effect of the interference. In the second model, we consider a doubly dirty Gaussian GMAC in which each of interferences is known noncausally only at one encoder. We derive an inner bound and analyze the achievable rate region for the latter model and interestingly prove that if one of the encoders knows the full CSI, there exists an achievable rate region which is \emph{independent} of the power of interference.
A Computational Model of the Short-Cut Rule for 2D Shape Decomposition
Venue: arXiv cs.CV 2014
Year: 2014

We propose a new 2D shape decomposition method based on the short-cut rule. The short-cut rule originates from cognition research, and states that the human visual system prefers to partition an object into parts using the shortest possible cuts. We propose and implement a computational model for the short-cut rule and apply it to the problem of shape decomposition. The model we proposed generates a set of cut hypotheses passing through the points on the silhouette which represent the negative minima of curvature. We then show that most part-cut hypotheses can be eliminated by analysis of local properties of each. Finally, the remaining hypotheses are evaluated in ascending length order, which guarantees that of any pair of conflicting cuts only the shortest will be accepted. We demonstrate that, compared with state-of-the-art shape decomposition methods, the proposed approach achieves decomposition results which better correspond to human intuition as revealed in psychological experiments.
Quantifying Privacy: A Novel Entropy-Based Measure of Disclosure Risk
Venue: arXiv cs.CR 2014
Year: 2014

It is well recognised that data mining and statistical analysis pose a serious treat to privacy. This is true for financial, medical, criminal and marketing research. Numerous techniques have been proposed to protect privacy, including restriction and data modification. Recently proposed privacy models such as differential privacy and k-anonymity received a lot of attention and for the latter there are now several improvements of the original scheme, each removing some security shortcomings of the previous one. However, the challenge lies in evaluating and comparing privacy provided by various techniques. In this paper we propose a novel entropy based security measure that can be applied to any generalisation, restriction or data modification technique. We use our measure to empirically evaluate and compare a few popular methods, namely query restriction, sampling and noise addition.
Design and Realization of an S-Band Microwave Low-Noise Amplifier for Wireless RF Subsystems
Venue: arXiv cs.OH 2014
Year: 2014

This study undertakes the theoretical design, CAD modeling, realization, and performance analysis of a microwave low-noise amplifier (LNA) which has been accurately developed for operation at 3.0 GHz (S-band). The objective of this research is to thoroughly analyze and develop a reliable microstrip LNA intended for a potential employment in wireless communication systems, and satellite applications. The S-band microwave LNA demonstrates the appropriateness to develop a high-performance and well-established device realization for wireless RF systems. The microwave amplifier simulations have been conducted using the latest version of the AWR Design Environment software.
On Demand Data Analysis and Filtering for Inaccurate Flight Trajectories
Venue: arXiv cs.SE 2014
Year: 2014

This paper reports on work performed in the context of the COMPASS SESAR-JU WP-E project, on developing an approach for identifying and filtering inaccurate trajectories (ghost flights) in historical data originating from the EUROCONTROL-operated Demand Data Repository (DDR).
MontiArcAutomaton: Modeling Architecture and Behavior of Robotic Systems
Venue: arXiv cs.SE 2014
Year: 2014

Robotics poses a challenge for software engineering as the vast numbers of different robot platforms impose different requirements on robot control architectures. The platform dependent development of robotic applications impedes reusability and portability. The lack of reusability hampers broad propagation of robotics applications. The MontiArcAutomaton architecture and behavior modeling framework provides an integrated, platform independent structure and behavior modeling language with an extensible code generation framework. MontiArcAutomaton's central concept is encapsulation and decomposition known from Component & Connector Architecture Description Languages. This concept is extended from the modeling language to the code generation and target runtime framework to bridge the gap of platform specific and independent implementations along well designed interfaces. This facilitates the reuse of robot applications and makes their development more efficient.