OpenRaiser/Intern-Atlas huggingface dataset:
Minimizing the Aggregate Movements for Interval Coverage
Venue: arXiv cs.CG 2014
Year: 2014

We consider an interval coverage problem. Given $n$ intervals of the same length on a line $L$ and a line segment $B$ on $L$, we want to move the intervals along $L$ such that every point of $B$ is covered by at least one interval and the sum of the moving distances of all intervals is minimized. As a basic geometry problem, it has applications in mobile sensor barrier coverage in wireless sensor networks. The previous work solved the problem in $O(n^2)$ time. In this paper, by discovering many interesting observations and developing new algorithmic techniques, we present an $O(n\log n)$ time algorithm. We also show an $Ω(n\log n)$ time lower bound for this problem, which implies the optimality of our algorithm.
Declaratively solving tricky Google Code Jam problems with Prolog-based ECLiPSe CLP system
Venue: arXiv cs.PL 2014
Year: 2014

In this paper we demonstrate several examples of solving challenging algorithmic problems from the Google Code Jam programming contest with the Prolog-based ECLiPSe system using declarative techniques like constraint logic programming and linear (integer) programming. These problems were designed to be solved by inventing clever algorithms and efficiently implementing them in a conventional imperative programming language, but we present relatively simple declarative programs in ECLiPSe that are fast enough to find answers within the time limit imposed by the contest rules. We claim that declarative programming with ECLiPSe is better suited for solving certain common kinds of programming problems offered in Google Code Jam than imperative programming. We show this by comparing the mental steps required to come up with both kinds of solutions.
An Algorithm to Determine Energy-aware Maximal Leaf Nodes Data Gathering Tree for Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

We propose an Energy-aware Maximal Leaf Nodes Data Gathering (EMLN-DG) algorithm for periodic data collection and transmission in wireless sensor networks. For each round of data gathering, an EMLN-DG tree spanning the entire sensor network is formed based on the residual energy level available at the nodes and the number of uncovered neighbors of a node during tree formation. Only nodes that have a relatively larger number of neighbors as well as a higher energy level are included as intermediate nodes in the EMLN-DG tree. By maximizing the number of leaf nodes in a DG tree and considering the energy level available at the nodes while forming the tree, we reduce energy consumption per round as well as balance the energy level across all the nodes in the network. This contributes to a significantly larger network lifetime, measured as the number of rounds before the first node failure due to exhaustion of battery charge. Performance comparison studies with the well-known data gathering algorithms such as LEACH and PEGASIS illustrate that EMLN-DG can help to sustain the network for a significantly larger number of rounds and at the same time incur a lower, or if not comparable, energy loss, delay and energy loss*delay per round of data gathering.
Generalized cofactors and decomposition of Boolean satisfiability problems
Venue: arXiv cs.DS 2014
Year: 2014

We propose an approach for decomposing Boolean satisfiability problems while extending recent results of \cite{sul2} on solving Boolean systems of equations. Developments in \cite{sul2} were aimed at the expansion of functions $f$ in orthonormal (ON) sets of base functions as a generalization of the Boole-Shannon expansion and the derivation of the consistency condition for the equation $f=0$ in terms of the expansion co-efficients. In this paper, we further extend the Boole-Shannon expansion over an arbitrary set of base functions and derive the consistency condition for $f=1$. The generalization of the Boole-Shannon formula presented in this paper is in terms of \emph{cofactors} as co-efficients with respect to a set of CNFs called a \emph{base} which appear in a given Boolean CNF formula itself. This approach results in a novel parallel algorithm for decomposition of a CNF formula and computation of all satisfying assignments when they exist by using the given data set of CNFs itself as the base.
Analysis, classification and detection methods of attacks via wireless sensor networks in SCADA systems
Venue: arXiv cs.CR 2014
Year: 2014

Effectiveness of information security of automated process control systems, as well as of SCADA, depends on data transmissions protection technologies applied on transport environments components. This article investigates the problem of detecting attacks on WSN (wireless sensor networks) of SCADA systems. As the result of analytical studies the authors developed the detailed classification of external attacks on sensor networks and brought the detailed description of attacking impacts on components of SCADA systems in accordance with selected directions of attacks. Reviewed the methods of intrusion detection in wireless sensor networks of SCADA systems and functions of WIDS (wireless intrusion detection systems). Noticed the role of anthropogenic factors in internal security threats.
Systems, Views and Models of UML
Venue: arXiv cs.SE 2014
Year: 2014

In this paper we show by using the example of UML, how a software engineering method can benefit from an integrative mathematical foundation. The mathematical foundation is given by a mathematical system model. This model provides the basis both for integrating the various description techniques of UML and for implementing methodical support. After describing the basic concepts of the system model, we give a short overview of the UML description techniques. Then we show how they fit into the system model framework and sketch an approach to structure the UML development process such that it provides methodological guidance for developers.
Evaluating Feasibility of Using Wireless Sensor Networks in a Coffee Crop Through Simulation of AODV, AOMDV, DSDV and Their Variants with 802.15.4 Mac Protocol
Venue: arXiv cs.NI 2014
Year: 2014

A Wireless Sensor Networks is a network formed with sensors that have characteristics to sensor an area to extract a specific metric, depending of the application. We would like to analyse the feasibility to use sensors in a coffee crop. In this work we are evaluating routing protocols using real dimensions and characteristics of a coffee crop. We evaluate, through simulation, AODV, DSDV and AOMDV and two variants known in this work as AODVMOD and AOMDVMOD with 802.15.4 MAC Protocol. For this comparison, we defined three performance metrics: Packet Delivery Ratio (PDR), End -to-End Delay and Average Energy Consumption. Simulation results show that AOMDVMOD overall, outperforms others routing protocols evaluated, showing that is possible to use WSN in a real coffee crop environment.
Secure and Image Retrieval based on Multipurpose Watermarking for Mammography Images Database
Venue: arXiv cs.CR 2014
Year: 2014

In the cancerology domain, we were brought to make periodic mammography images to monitor tumor patients. Oracle Database Management system (DBMS) is a solution to manage these images with patient's data recorder. Knowing the large size of medical images of mammograms, the Oracle DBMS saves these images outside the Oracle database using external LOBs. The link between these images and Oracle is done through the BFILE. At this level, two problems are raised: the first problem is that access to these images can become impossible because the link is likely to be broken. The second problem is security, the fact that the images are saved outside the Oracle database, they do not benefit from its powerful security. The protection of the integrity and confidentiality of data and patient images are a necessity defended by laws and they must be preserved against any unauthorized access, alteration or destruction. In this paper, we propose the method of reversible watermarking technique based on the difference expansion to resolve these two problems and explore its use in search and retrieval strategy of images.
On the Optimality of Treating Interference as Noise: Compound Interference Networks
Venue: arXiv cs.IT 2014
Year: 2014

In a K-user Gaussian interference channel, it has been shown by Geng et al. that 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 values in dB scale), then power control and treating interference as noise (TIN) is optimal from the perspective of generalized degrees of freedom (GDoF) and achieves the entire channel capacity region to within a constant gap. In this work, we generalize the optimality of TIN to compound networks. We show that for a K-user compound Gaussian interference channel, if in every possible state for each receiver, the channel always satisfies the TIN-optimality condition identified by Geng et al., then the GDoF region of the compound channel is the intersection of the GDoF regions of all possible network realizations, which is achievable by power control and TIN. Furthermore, we demonstrate that for a general K-user compound interference channel, regardless of the number of states of each receiver, we can always construct a counterpart K-user regular interference channel that has the same TIN region as the original compound channel. The regular interference channel has only one state for each receiver, which may be different from all of the original states. Solving the GDoF-based power control problem for the compound channel is equivalent to solving the same problem in its regular counterpart. Exploring the power control problem further we develop a centralized power control scheme for K-user compound interference channels, to achieve all the Pareto optimal GDoF tuples. Finally, based on this scheme, we devise an iterative power control algorithm which requires at most K updates to obtain the globally optimal power allocation for any feasible GDoF tuple.
Analysis of Maximum Likelihood and Mahalanobis Distance for Identifying Cheating Anchor Nodes
Venue: arXiv cs.CR 2014
Year: 2014

Malicious anchor nodes will constantly hinder genuine and appropriate localization. Discovering the malicious or vulnerable anchor node is an essential problem in wireless sensor networks (WSNs). In wireless sensor networks, anchor nodes are the nodes that know its current location. Neighboring nodes or non-anchor nodes calculate its location (or its location reference) with the help of anchor nodes. Ingenuous localization is not possible in the presence of a cheating anchor node or a cheating node. Nowadays, its a challenging task to identify the cheating anchor node or cheating node in a network. Even after finding out the location of the cheating anchor node, there is no assurance, that the identified node is legitimate or not. This paper aims to localize the cheating anchor nodes using trilateration algorithm and later associate it with maximum likelihood expectation technique (MLE), and Mahalanobis distance to obtain maximum accuracy in identifying malicious or cheating anchor nodes during localization. We were able to attain a considerable reduction in the error achieved during localization. For implementation purpose we simulated our scheme using ns-3 network simulator.
Bayesian Fisher's Discriminant for Functional Data
Venue: arXiv cs.LG 2014
Year: 2014

We propose a Bayesian framework of Gaussian process in order to extend Fisher's discriminant to classify functional data such as spectra and images. The probability structure for our extended Fisher's discriminant is explicitly formulated, and we utilize the smoothness assumptions of functional data as prior probabilities. Existing methods which directly employ the smoothness assumption of functional data can be shown as special cases within this framework given corresponding priors while their estimates of the unknowns are one-step approximations to the proposed MAP estimates. Empirical results on various simulation studies and different real applications show that the proposed method significantly outperforms the other Fisher's discriminant methods for functional data.
Cause, Responsibility, and Blame: oA Structural-Model Approach
Venue: arXiv cs.AI 2014
Year: 2014

A definition of causality introduced by Halpern and Pearl, which uses structural equations, is reviewed. A more refined definition is then considered, which takes into account issues of normality and typicality, which are well known to affect causal ascriptions. Causality is typically an all-or-nothing notion: either A is a cause of B or it is not. An extension of the definition of causality to capture notions of degree of responsibility and degree of blame, due to Chockler and Halpern, is reviewed. For example, if someone wins an election 11-0, then each person who votes for him is less responsible for the victory than if he had won 6-5. Degree of blame takes into account an agent's epistemic state. Roughly speaking, the degree of blame of A for B is the expected degree of responsibility of A for B, taken over the epistemic state of an agent. Finally, the structural-equations definition of causality is compared to Wright's NESS test.
Brain Tumor Detection Based on Bilateral Symmetry Information
Venue: arXiv cs.CV 2014
Year: 2014

Advances in computing technology have allowed researchers across many fields of endeavor to collect and maintain vast amounts of observational statistical data such as clinical data,biological patient data,data regarding access of web sites,financial data,and the like.Brain Magnetic Resonance Imaging(MRI)segmentation is a complex problem in the field of medical imaging despite various presented methods.MR image of human brain can be divided into several sub regions especially soft tissues such as gray matter,white matter and cerebrospinal fluid.Although edge information is the main clue in image segmentation,it can not get a better result in analysis the content of images without combining other information.The segmentation of brain tissue in the magnetic resonance imaging(MRI)is very important for detecting the existence and outlines of tumors.In this paper,an algorithm about segmentation based on the symmetry character of brain MRI image is presented.Our goal is to detect the position and boundary of tumors automatically.Experiments were conducted on real pictures,and the results show that the algorithm is flexible and convenient.
Parameterized and Approximation Algorithms for the Load Coloring Problem
Venue: arXiv cs.DS 2014
Year: 2014

Let $c, k$ be two positive integers and let $G=(V,E)$ be a graph. The $(c,k)$-Load Coloring Problem (denoted $(c,k)$-LCP) asks whether there is a $c$-coloring $φ: V \rightarrow [c]$ such that for every $i \in [c]$, there are at least $k$ edges with both endvertices colored $i$. Gutin and Jones (IPL 2014) studied this problem with $c=2$. They showed $(2,k)$-LCP to be fixed parameter tractable (FPT) with parameter $k$ by obtaining a kernel with at most $7k$ vertices. In this paper, we extend the study to any fixed $c$ by giving both a linear-vertex and a linear-edge kernel. In the particular case of $c=2$, we obtain a kernel with less than $4k$ vertices and less than $8k$ edges. These results imply that for any fixed $c\ge 2$, $(c,k)$-LCP is FPT and that the optimization version of $(c,k)$-LCP (where $k$ is to be maximized) has an approximation algorithm with a constant ratio for any fixed $c\ge 2$.
Model-based Path Integral Stochastic Control: A Bayesian Nonparametric Approach
Venue: arXiv cs.SY 2014
Year: 2014

Over the last few years, sampling-based stochastic optimal control (SOC) frameworks have shown impressive performances in reinforcement learning (RL) with applications in robotics. However, such approaches require a large amount of samples from many interactions with the physical systems. To improve learning efficiency, we present a novel model-based and data-driven SOC framework based on path integral formulation and Gaussian processes (GPs). The proposed approach learns explicit and time-varying optimal controls autonomously from limited sampled data. Based on this framework, we propose an iterative control scheme with improved applicability in higher-dimensional and more complex control tasks. We demonstrate the effectiveness and efficiency of the proposed framework using two nontrivial examples. Compared to state-of-the-art RL methods, the proposed framework features superior control learning efficiency.
A tool for implementation of a domain model based on fuzzy relationships
Venue: arXiv cs.CY 2014
Year: 2014

The domain model is one of the important components used by adaptive learning systems to automatically generate customized courses for the learners. In this paper our contribution is to propose a new tool for implementation of a domain model based on fuzzy relationships among concepts. This tool allows the experts and teachers to find the best parameters in order to adapt the learners's differences.
Rule reasoning for legal norm validation of FSTP facts
Venue: arXiv cs.AI 2014
Year: 2014

Non-obviousness or inventive step is a general requirement for patentability in most patent law systems. An invention should be at an adequate distance beyond its prior art in order to be patented. This short paper provides an overview on a methodology proposed for legal norm validation of FSTP facts using rule reasoning approach.
Object-centric Sampling for Fine-grained Image Classification
Venue: arXiv cs.CV 2014
Year: 2014

This paper proposes to go beyond the state-of-the-art deep convolutional neural network (CNN) by incorporating the information from object detection, focusing on dealing with fine-grained image classification. Unfortunately, CNN suffers from over-fiting when it is trained on existing fine-grained image classification benchmarks, which typically only consist of less than a few tens of thousands training images. Therefore, we first construct a large-scale fine-grained car recognition dataset that consists of 333 car classes with more than 150 thousand training images. With this large-scale dataset, we are able to build a strong baseline for CNN with top-1 classification accuracy of 81.6%. One major challenge in fine-grained image classification is that many classes are very similar to each other while having large within-class variation. One contributing factor to the within-class variation is cluttered image background. However, the existing CNN training takes uniform window sampling over the image, acting as blind on the location of the object of interest. In contrast, this paper proposes an \emph{object-centric sampling} (OCS) scheme that samples image windows based on the object location information. The challenge in using the location information lies in how to design powerful object detector and how to handle the imperfectness of detection results. To that end, we design a saliency-aware object detection approach specific for the setting of fine-grained image classification, and the uncertainty of detection results are naturally handled in our OCS scheme. Our framework is demonstrated to be very effective, improving top-1 accuracy to 89.3% (from 81.6%) on the large-scale fine-grained car classification dataset.
Web image annotation by diffusion maps manifold learning algorithm
Venue: arXiv cs.CV 2014
Year: 2014

Automatic image annotation is one of the most challenging problems in machine vision areas. The goal of this task is to predict number of keywords automatically for images captured in real data. Many methods are based on visual features in order to calculate similarities between image samples. But the computation cost of these approaches is very high. These methods require many training samples to be stored in memory. To lessen this burden, a number of techniques have been developed to reduce the number of features in a dataset. Manifold learning is a popular approach to nonlinear dimensionality reduction. In this paper, we investigate Diffusion maps manifold learning method for web image auto-annotation task. Diffusion maps manifold learning method is used to reduce the dimension of some visual features. Extensive experiments and analysis on NUS-WIDE-LITE web image dataset with different visual features show how this manifold learning dimensionality reduction method can be applied effectively to image annotation.
Candidate Constrained CRFs for Loss-Aware Structured Prediction
Venue: arXiv cs.CV 2014
Year: 2014

When evaluating computer vision systems, we are often concerned with performance on a task-specific evaluation measure such as the Intersection-Over-Union score used in the PASCAL VOC image segmentation challenge. Ideally, our systems would be tuned specifically to these evaluation measures. However, despite much work on loss-aware structured prediction, top performing systems do not use these techniques. In this work, we seek to address this problem, incorporating loss-aware prediction in a manner that is amenable to the approaches taken by top performing systems. Our main idea is to simultaneously leverage two systems: a highly tuned pipeline system as is found on top of leaderboards, and a traditional CRF. We show how to combine high quality candidate solutions from the pipeline with the probabilistic approach of the CRF that is amenable to loss-aware prediction. The result is that we can use loss-aware prediction methodology to improve performance of the highly tuned pipeline system.
fVSS: A New Secure and Cost-Efficient Scheme for Cloud Data Warehouses
Venue: arXiv cs.DB 2014
Year: 2014

Cloud business intelligence is an increasingly popular choice to deliver decision support capabilities via elastic, pay-per-use resources. However, data security issues are one of the top concerns when dealing with sensitive data. In this pa-per, we propose a novel approach for securing cloud data warehouses by flexible verifiable secret sharing, fVSS. Secret sharing encrypts and distributes data over several cloud ser-vice providers, thus enforcing data privacy and availability. fVSS addresses four shortcomings in existing secret sharing-based approaches. First, it allows refreshing the data ware-house when some service providers fail. Second, it allows on-line analysis processing. Third, it enforces data integrity with the help of both inner and outer signatures. Fourth, it helps users control the cost of cloud warehousing by balanc-ing the load among service providers with respect to their pricing policies. To illustrate fVSS' efficiency, we thoroughly compare it with existing secret sharing-based approaches with respect to security features, querying power and data storage and computing costs.
On the Formal Semantics of the Cognitive Middleware AWDRAT
Venue: arXiv cs.PL 2014
Year: 2014

The purpose of this work is two fold: on one hand we want to formalize the behavior of critical components of the self generating and adapting cognitive middleware AWDRAT such that the formalism not only helps to understand the semantics and technical details of the middleware but also opens an opportunity to extend the middleware to support other complex application domains of cybersecurity; on the other hand, the formalism serves as a pre-requisite for our proof of the behavioral correctness of the critical components to ensure the safety of the middleware itself. However, here we focus only on the core and critical component of the middleware, i.e. Execution Monitor which is a part of the module "Architectural Differencer" of AWDRAT. The role of the execution monitor is to identify inconsistencies between runtime observations of the target system and predictions of the System Architectural Model. Therefore, to achieve this goal, we first define the formal (denotational) semantics of the observations (runtime events) and predictions (executable specifications as of System Architectural Model); then based on the aforementioned formal semantices, we formalize the behavior of the "Execution Monitor" of the middleware.