OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid architecture for satellite data processing workflow management
Venue: arXiv cs.SE 2015
Year: 2015

The ever growing demand for remote sensing data products by user community has resulted in many Indian and foreign remote sensing satellites being launched. The diversity in the remote sensing sensors has resulted in heterogeneous software and hardware environments for generating geospatial data products. The workflow automation software knows as information management system is in place at National Remote Sensing Centre (NRSC) catering to the needs of the data processing and data dissemination. The software components of workflow are interfaced in different heterogeneous environments that get executed at data processing software in automated and semi automated modes. For every new satellite being launched, the software is modified or upgraded if new business processes are introduced. In this study, we propose a software architecture that gives more flexible automation with very less manageable code. The study also addresses utilization and extraction of useful information from historic production and customer details. A comparison of the current workflow software architecture with existing practices in industry like Service Oriented Architecture (SOA), Extensible Markup Languages (XML), and Event based architectures has been made. A new hybrid approach based on the industry practices is proposed to improve the existing workflow.
Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of $H$-free Edge Modification Problems
Venue: arXiv cs.DS 2015
Year: 2015

For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two non-edges and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Additionally, we prove that, these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless Exponential Time Hypothesis fails. Furthermore, we obtain implications on the incompressibility of these problems.
Experimental Demonstration of Capacity Increase and Rate-Adaptation by Probabilistically Shaped 64-QAM
Venue: arXiv cs.IT 2015
Year: 2015

We implemented a flexible transmission system operating at adjustable data rate and fixed bandwidth, baudrate, constellation and overhead using probabilistic shaping. We demonstrated in a transmission experiment up to 15% capacity and 43% reach increase versus 200 Gbit/s 16-QAM.
Polish -English Statistical Machine Translation of Medical Texts
Venue: arXiv cs.CL 2015
Year: 2015

This new research explores the effects of various training methods on a Polish to English Statistical Machine Translation system for medical texts. Various elements of the EMEA parallel text corpora from the OPUS project were used as the basis for training of phrase tables and language models and for development, tuning and testing of the translation system. The BLEU, NIST, METEOR, RIBES and TER metrics have been used to evaluate the effects of various system and data preparations on translation results. Our experiments included systems that used POS tagging, factored phrase models, hierarchical models, syntactic taggers, and many different alignment methods. We also conducted a deep analysis of Polish data as preparatory work for automatic data correction such as true casing and punctuation normalization phase.
Finding Desirable Objects under Group Categorical Preferences
Venue: arXiv cs.DB 2015
Year: 2015

Considering a group of users, each specifying individual preferences over categorical attributes, the problem of determining a set of objects that are objectively preferable by all users is challenging on two levels. First, we need to determine the preferable objects based on the categorical preferences for each user, and second we need to reconcile possible conflicts among users' preferences. A naive solution would first assign degrees of match between each user and each object, by taking into account all categorical attributes, and then for each object combine these matching degrees across users to compute the total score of an object. Such an approach, however, performs two series of aggregation, among categorical attributes and then across users, which completely obscure and blur individual preferences. Our solution, instead of combining individual matching degrees, is to directly operate on categorical attributes, and define an objective Pareto-based aggregation for group preferences. Building on our interpretation, we tackle two distinct but relevant problems: finding the Pareto-optimal objects, and objectively ranking objects with respect to the group preferences. To increase the efficiency when dealing with categorical attributes, we introduce an elegant transformation of categorical attribute values into numerical values, which exhibits certain nice properties and allows us to use well-known index structures to accelerate the solutions to the two problems. In fact, experiments on real and synthetic data show that our index-based techniques are an order of magnitude faster than baseline approaches, scaling up to millions of objects and thousands of users.
An encoding of array verification problems into array-free Horn clauses
Venue: arXiv cs.PL 2015
Year: 2015

Automatically verifying safety properties of programs is hard, and it is even harder if the program acts upon arrays or other forms of maps. Many approaches exist for verifying programs operating upon Boolean and integer values (e.g. abstract interpretation, counterexample-guided abstraction refinement using interpolants), but transposing them to array properties has been fraught with difficulties.In contrast to most preceding approaches, we do not introduce a new abstract domain or a new interpolation procedure for arrays. Instead, we generate an abstraction as a scalar problem and feed it to a preexisting solver, with tunable precision.Our transformed problem is expressed using Horn clauses, a common format with clear and unambiguous logical semantics for verification problems. An important characteristic of our encoding is that it creates a nonlinear Horn problem, with tree unfoldings, even though following "flatly" the control-graph structure ordinarily yields a linear Horn problem, with linear unfoldings. That is, our encoding cannot be expressed by an encoding into another control-flow graph problem, and truly leverages the capacity of the Horn clause format.We illustrate our approach with a completely automated proof of the functional correctness of selection sort.
Supporting interoperability of collaborative networks through engineering of a service-based Mediation Information System (MISE 2.0)
Venue: arXiv cs.SE 2015
Year: 2015

The Mediation Information System Engineering project is currently finishing its second iteration (MISE 2.0). The main objective of this scientific project is to provide any emerging collaborative situation with methods and tools to deploy a Mediation Information System (MIS). MISE 2.0 aims at defining and designing a service-based platform, dedicated to initiating and supporting the interoperability of collaborative situations among potential partners. This MISE 2.0 platform implements a model-driven engineering approach to the design of a service-oriented MIS dedicated to supporting the collaborative situation. This approach is structured in three layers, each providing their own key innovative points: (i) the gathering of individual and collaborative knowledge to provide appropriate collaborative business behaviour (key point: knowledge management, including semantics, exploitation and capitalization), (ii) deployment of a mediation information system able to computerize the previously deduced collaborative processes (key point: the automatic generation of collaborative workflows, including connection with existing devices or services) (iii) the management of the agility of the obtained collaborative network of organizations (key point: supervision of collaborative situations and relevant exploitation of the gathered data). MISE covers business issues (through BPM), technical issues (through an SOA) and agility issues of collaborative situations (through EDA).
Event-driven agility of interoperability during the Run-time of collaborative processes
Venue: arXiv cs.SE 2015
Year: 2015

The modern business environment tends to involve a large network of heterogeneous people, devices and organizations that engage in collaborative processes among themselves. Given the nature of this type of collaboration and the high degree of interoperability between partner Information Systems, these processes need to be agile in order to respond to changes in context, which may occur at any time during the collaborative situation.The objective is to build a Mediation Information System (MIS), in support of collaborative situations, whose architecture must be (i) built to be relevant to the collaborative situation under consideration, (ii) more easily integrated into the existing systems, and (iii) sufficiently agile, through its awareness of the environment and of process events, and through the way it reacts to events detected as being relevant.To apply agility mechanisms, it is crucial to detect the significant events that will lead to a subsequent evolution of the situation (detection step). Event-Driven Architecture (EDA) is used to design the structure of the part of the system that is in charge of MIS agility. This architecture takes the events into account, manages them and, if needed, uses them to trigger the adaptation of the MIS.We have defined a means to monitor the evolution of the situation. If relevant changes are detected, and if the situation does not evolve in the expected way, an adaptation is proposed. It is concluded that the principles of detection and adaptation, combined with the responsiveness of the system (provided by the automation of transitions), and based on Event Driven Architecture principles, together provide the agility required for collaborative processes.
Solving a Mathematical Problem in Square War: a Go-like Board Game
Venue: arXiv cs.AI 2015
Year: 2015

In this paper, we present a board game: Square War. The game definition of Square War is similar to the classic Chinese board game Go. Then we propose a mathematical problem of the game Square War. Finally, we show that the problem can be solved by using a method of mixed mathematics and computer science.
Community detection for interaction networks
Venue: arXiv cs.SI 2015
Year: 2015

In many applications, it is common practice to obtain a network from interaction counts by thresholding each pairwise count at a prescribed value. Our analysis calls attention to the dependence of certain methods, notably Newman--Girvan modularity, on the choice of threshold. Essentially, the threshold either separates the network into clusters automatically, making the algorithm's job trivial, or erases all structure in the data, rendering clustering impossible. By fitting the original interaction counts as given, we show that minor modifications to classical statistical methods outperform the prevailing approaches for community detection from interaction datasets. We also introduce a new hidden Markov model for inferring community structures that vary over time. We demonstrate each of these features on three real datasets: the karate club dataset, voting data from the U.S.\ Senate (2001--2003), and temporal voting data for the U.S. Supreme Court (1990--2004).
On Remote Estimation with Multiple Communication Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a sequential estimation and sensor scheduling problem in the presence of multiple communication channels. As opposed to the classical remote estimation problem that involves one perfect (noiseless) channel and one extremely noisy channel (which corresponds to not transmitting the observed state), a more realistic additive noise channel with fixed power constraint along with a more costly perfect channel is considered. It is shown, via a counter-example, that the common folklore of applying symmetric threshold policy, which is well known to be optimal (for unimodal state densities) in the classical two-channel remote estimation problem, can be suboptimal for the setting considered. Next, in order to make the problem tractable, a side channel which signals the sign of the underlying state is considered. It is shown that, under some technical assumptions, threshold-in-threshold communication scheduling is optimal for this setting. The impact of the presence of a noisy channel is analyzed numerically based on dynamic programming. This numerical analysis uncovers some rather surprising results inheriting known properties from the noisy and noiseless settings.
Clamping Improves TRW and Mean Field Approximations
Venue: arXiv cs.LG 2015
Year: 2015

We examine the effect of clamping variables for approximate inference in undirected graphical models with pairwise relationships and discrete variables. For any number of variable labels, we demonstrate that clamping and summing approximate sub-partition functions can lead only to a decrease in the partition function estimate for TRW, and an increase for the naive mean field method, in each case guaranteeing an improvement in the approximation and bound. We next focus on binary variables, add the Bethe approximation to consideration and examine ways to choose good variables to clamp, introducing new methods. We show the importance of identifying highly frustrated cycles, and of checking the singleton entropy of a variable. We explore the value of our methods by empirical analysis and draw lessons to guide practitioners.
#Bieber + #Blast = #BieberBlast: Early Prediction of Popular Hashtag Compounds
Venue: arXiv cs.SI 2015
Year: 2015

Compounding of natural language units is a very common phenomena. In this paper, we show, for the first time, that Twitter hashtags which, could be considered as correlates of such linguistic units, undergo compounding. We identify reasons for this compounding and propose a prediction model that can identify with 77.07% accuracy if a pair of hashtags compounding in the near future (i.e., 2 months after compounding) shall become popular. At longer times T = 6, 10 months the accuracies are 77.52% and 79.13% respectively. This technique has strong implications to trending hashtag recommendation since newly formed hashtag compounds can be recommended early, even before the compounding has taken place. Further, humans can predict compounds with an overall accuracy of only 48.7% (treated as baseline). Notably, while humans can discriminate the relatively easier cases, the automatic framework is successful in classifying the relatively harder cases.
Achievable Degrees of Freedom on K-user MIMO Multi-way Relay Channel with Common and Private Messages
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the achievable total degrees of freedom (DoF) of the MIMO multi-way relay channel that consists of K users, where each user is equipped with M antennas, and a decode-and-forward relay equipped with N antennas. In this channel, each user wants to convey K-1 private messages to the other users in addition to a common message to all of them. Due to the absence of direct links between the users, communication occurs through the relay in two phases; a multiple access channel phase (MAC) and a broadcast (BC) phase. We drive cut-set bounds on the total DoF of the network, and show that the network has DoF less than or equal to K min(N,M). Achievability of the upper bound is shown by using signal space alignment for network coding in the MAC phase, and zero-forcing precoding in the BC phase. We show that introducing the common messages besides the private messages leads to achieving higher total DoF than using the private messages only.
An Asynchronous Implementation of the Limited Memory CMA-ES
Venue: arXiv cs.NE 2015
Year: 2015

We present our asynchronous implementation of the LM-CMA-ES algorithm, which is a modern evolution strategy for solving complex large-scale continuous optimization problems. Our implementation brings the best results when the number of cores is relatively high and the computational complexity of the fitness function is also high. The experiments with benchmark functions show that it is able to overcome its origin on the Sphere function, reaches certain thresholds faster on the Rosenbrock and Ellipsoid function, and surprisingly performs much better than the original version on the Rastrigin function.
Response to Liu, Xu, and Liang (2015) and Ferrer-i-Cancho and Gómez-Rodríguez (2015) on Dependency Length Minimization
Venue: arXiv cs.CL 2015
Year: 2015

We address recent criticisms (Liu et al., 2015; Ferrer-i-Cancho and Gómez-Rodríguez, 2015) of our work on empirical evidence of dependency length minimization across languages (Futrell et al., 2015). First, we acknowledge error in failing to acknowledge Liu (2008)'s previous work on corpora of 20 languages with similar aims. A correction will appear in PNAS. Nevertheless, we argue that our work provides novel, strong evidence for dependency length minimization as a universal quantitative property of languages, beyond this previous work, because it provides baselines which focus on word order preferences. Second, we argue that our choices of baselines were appropriate because they control for alternative theories.
Effective Object Tracking in Unstructured Crowd Scenes
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we are presenting a rotation variant Oriented Texture Curve (OTC) descriptor based mean shift algorithm for tracking an object in an unstructured crowd scene. The proposed algorithm works by first obtaining the OTC features for a manually selected object target, then a visual vocabulary is created by using all the OTC features of the target. The target histogram is obtained using codebook encoding method which is then used in mean shift framework to perform similarity search. Results are obtained on different videos of challenging scenes and the comparison of the proposed approach with several state-of-the-art approaches are provided. The analysis shows the advantages and limitations of the proposed approach for tracking an object in unstructured crowd scenes.
A Note on Easy and Efficient Computation of Full Abelian Periods of a Word
Venue: arXiv cs.DS 2015
Year: 2015

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(n\log\log n)$-time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem.
HTML5 Zero Configuration Covert Channels: Security Risks and Challenges
Venue: arXiv cs.CR 2015
Year: 2015

In recent months there has been an increase in the popularity and public awareness of secure, cloudless file transfer systems. The aim of these services is to facilitate the secure transfer of files in a peer-to- peer (P2P) fashion over the Internet without the need for centralised authentication or storage. These services can take the form of client installed applications or entirely web browser based interfaces. Due to their P2P nature, there is generally no limit to the file sizes involved or to the volume of data transmitted - and where these limitations do exist they will be purely reliant on the capacities of the systems at either end of the transfer. By default, many of these services provide seamless, end-to-end encryption to their users. The cybersecurity and cyberforensic consequences of the potential criminal use of such services are significant. The ability to easily transfer encrypted data over the Internet opens up a range of opportunities for illegal use to cybercriminals requiring minimal technical know-how. This paper explores a number of these services and provides an analysis of the risks they pose to corporate and governmental security. A number of methods for the forensic investigation of such transfers are discussed.
Towards a Fully Abstract Compiler Using Micro-Policies: Secure Compilation for Mutually Distrustful Components
Venue: arXiv cs.PL 2015
Year: 2015

Secure compilation prevents all low-level attacks on compiled code and allows for sound reasoning about security in the source language. In this work we propose a new attacker model for secure compilation that extends the well-known notion of full abstraction to ensure protection for mutually distrustful components. We devise a compiler chain (compiler, linker, and loader) and a novel security monitor that together defend against this strong attacker model. The monitor is implemented using a recently proposed, generic tag-based protection framework called micro-policies, which comes with hardware support for efficient caching and with a formal verification methodology. Our monitor protects the abstractions of a simple object-oriented language---class isolation, the method call discipline, and type safety---against arbitrary low-level attackers.
P-trac Procedure: The Dispersion and Neutralization of Contrasts in Lexicon
Venue: arXiv cs.CL 2015
Year: 2015

Cognitive acoustic cues have an important role in shaping the phonological structure of language as a means to optimal communication. In this paper we introduced P-trac procedure in order to track dispersion of contrasts in different contexts in lexicon. The results of applying P-trac procedure to the case of dispersion of contrasts in pre- consonantal contexts and in consonantal positions of CVCC sequences in Persian provide Evidence in favor of phonetic basis of dispersion argued by Licensing by Cue hypothesis and the Dispersion Theory of Contrast. The P- trac procedure is proved to be very effective in revealing the dispersion of contrasts in lexicon especially when comparing the dispersion of contrasts in different contexts.
On the Rate of Convergence of Mean-Field Models: Stein's Method Meets the Perturbation Theory
Venue: arXiv cs.PF 2015
Year: 2015

This paper studies the rate of convergence of a family of continuous-time Markov chains (CTMC) to a mean-field model. When the mean-field model is a finite-dimensional dynamical system with a unique equilibrium point, an analysis based on Stein's method and the perturbation theory shows that under some mild conditions, the stationary distributions of CTMCs converge (in the mean-square sense) to the equilibrium point of the mean-field model if the mean-field model is globally asymptotically stable and locally exponentially stable. In particular, the mean square difference between the $M$th CTMC in the steady state and the equilibrium point of the mean-field system is $O(1/M),$ where $M$ is the size of the $M$th CTMC. This approach based on Stein's method provides a new framework for studying the convergence of CTMCs to their mean-field limit by mainly looking into the stability of the mean-field model, which is a deterministic system and is often easier to analyze than the CTMCs. More importantly, this approach quantifies the rate of convergence, which reveals the approximation error of using mean-field models for approximating finite-size systems.