OpenRaiser/Intern-Atlas huggingface dataset:
k-Modulus Method for Image Transformation
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we propose a new algorithm to make a novel spatial image transformation. The proposed approach aims to reduce the bit depth used for image storage. The basic technique for the proposed transformation is based of the modulus operator. The goal is to transform the whole image into multiples of predefined integer. The division of the whole image by that integer will guarantee that the new image surely less in size from the original image. The k-Modulus Method could not be used as a stand alone transform for image compression because of its high compression ratio. It could be used as a scheme embedded in other image processing fields especially compression. According to its high PSNR value, it could be amalgamated with other methods to facilitate the redundancy criterion.
Bertrand Networks
Venue: arXiv cs.GT 2013
Year: 2013

We study scenarios where multiple sellers of a homogeneous good compete on prices, where each seller can only sell to some subset of the buyers. Crucially, sellers cannot price-discriminate between buyers. We model the structure of the competition by a graph (or hyper-graph), with nodes representing the sellers and edges representing populations of buyers. We study equilibria in the game between the sellers, prove that they always exist, and present various structural, quantitative, and computational results about them. We also analyze the equilibria completely for a few cases. Many questions are left open.
On Design of Opportunistic Spectrum Access in the Presence of Reactive Primary Users
Venue: arXiv cs.IT 2013
Year: 2013

Opportunistic spectrum access (OSA) is a key technique enabling the secondary users (SUs) in a cognitive radio (CR) network to transmit over the "spectrum holes" unoccupied by the primary users (PUs). In this paper, we focus on the OSA design in the presence of reactive PUs, where PU's access probability in a given channel is related to SU's past access decisions. We model the channel occupancy of the reactive PU as a 4-state discrete-time Markov chain. We formulate the optimal OSA design for SU throughput maximization as a constrained finite-horizon partially observable Markov decision process (POMDP) problem. We solve this problem by first considering the conventional short-term conditional collision probability (SCCP) constraint. We then adopt a long-term PU throughput (LPUT) constraint to effectively protect the reactive PU transmission. We derive the structure of the optimal OSA policy under the LPUT constraint and propose a suboptimal policy with lower complexity. Numerical results are provided to validate the proposed studies, which reveal some interesting new tradeoffs between SU throughput maximization and PU transmission protection in a practical interaction scenario.
Phase Transition and Strong Predictability
Venue: arXiv cs.IT 2013
Year: 2013

The statistical mechanical interpretation of algorithmic information theory (AIT, for short) was introduced and developed in our former work [K. Tadaki, Local Proceedings of CiE 2008, pp.425-434, 2008], where we introduced the notion of thermodynamic quantities into AIT. These quantities are real functions of temperature T>0. The values of all the thermodynamic quantities diverge when T exceeds 1. This phenomenon corresponds to phase transition in statistical mechanics. In this paper we introduce the notion of strong predictability for an infinite binary sequence and then apply it to the partition function Z(T), which is one of the thermodynamic quantities in AIT. We then reveal a new computational aspect of the phase transition in AIT by showing the critical difference of the behavior of Z(T) between T=1 and T<1 in terms of the strong predictability for the base-two expansion of Z(T).
A Deterministic Annealing Approach to Optimization of Zero-delay Source-Channel Codes
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies optimization of zero-delay source-channel codes, and specifically the problem of obtaining globally optimal transformations that map between the source space and the channel space, under a given transmission power constraint and for the mean square error distortion. Particularly, we focus on the setting where the decoder has access to side information, whose cost surface is known to be riddled with local minima. Prior work derived the necessary conditions for optimality of the encoder and decoder mappings, along with a greedy optimization algorithm that imposes these conditions iteratively, in conjunction with the heuristic "noisy channel relaxation" method to mitigate poor local minima. While noisy channel relaxation is arguably effective in simple settings, it fails to provide accurate global optimization results in more complicated settings including the decoder with side information as considered in this paper. We propose a global optimization algorithm based on the ideas of "deterministic annealing"- a non-convex optimization method, derived from information theoretic principles with analogies to statistical physics, and successfully employed in several problems including clustering, vector quantization and regression. We present comparative numerical results that show strict superiority of the proposed algorithm over greedy optimization methods as well as over the noisy channel relaxation.
Euclidean Upgrade from a Minimal Number of Segments
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we propose an algebraic approach to upgrade a projective reconstruction to a Euclidean one, and aim at computing the rectifying homography from a minimal number of 9 segments of known length. Constraints are derived from these segments which yield a set of polynomial equations that we solve by means of Gröbner bases. We explain how a solver for such a system of equations can be constructed from simplified template data. Moreover, we present experiments that demonstrate that the given problem can be solved in this way.
Spéculation et auto-stabilisation
Venue: arXiv cs.DC 2013
Year: 2013

Self-stabilization ensures that, after any transient fault, the system recovers in a finite time and eventually exhibits a correct behaviour. Speculation consists in guaranteeing that the system satisfies its requirements for any execution but exhibits significantly better performances for a subset of executions that are more probable. A speculative protocol is in this sense supposed to be both robust and efficient in practice. We introduce the notion of speculative stabilization which we illustrate through the mutual exclusion problem. We then present a novel speculatively stabilizing mutual exclusion protocol. Our protocol is self-stabilizing for any asynchronous execution. We prove that its stabilization time for synchronous executions is diam(g)/2 steps (where diam(g) denotes the diameter of the system). This complexity result is of independent interest. The celebrated mutual exclusion protocol of Dijkstra stabilizes in n steps (where n is the number of processes) in synchronous executions and the question whether the stabilization time could be strictly smaller than the diameter has been open since then (almost 40 years). We show that this is indeed possible for any underlying topology. We also provide a lower bound proof that shows that our new stabilization time of diam(g)/2 steps is optimal for synchronous executions, even if asynchronous stabilization is not required.
Network Control Systems RTAI framework A Review
Venue: arXiv cs.OS 2013
Year: 2013

With the advancement in the automation industry, to perform complex remote operations is required. Advancements in the networking technology has led to the development of different architectures to implement control from a large distance. In various control applications of the modern industry, the agents, such as sensors, actuators, and controllers are basically geographically distributed. For efficient working of a control application, all of the agents have to exchange information through a communication media. At present, an increasing number of distributed control systems are based on platforms made up of conventional PCs running open-source real-time operating systems. Often, these systems needed to have networked devices supporting synchronized operations with respect to each node. A framework is studied that relies on standard software and protocol as RTAI, EtherCAT, RTnet and IEEE 1588. RTAI and its various protocols are studied in network control systems environment.
Recovery of bilevel causal signals with finite rate of innovation using positive sampling kernels
Venue: arXiv cs.IT 2013
Year: 2013

Bilevel signal $x$ with maximal local rate of innovation $R$ is a continuous-time signal that takes only two values 0 and 1 and that there is at most one transition position in any time period of 1/R.In this note, we introduce a recovery method for bilevel causal signals $x$ with maximal local rate of innovation $R$ from their uniform samples $x*h(nT), n\ge 1$, where the sampling kernel $h$ is causal and positive on $(0, T)$, and the sampling rate $τ:=1/T$ is at (or above) the maximal local rate of innovation $R$. We also discuss stability of the bilevel signal recovery procedure in the presence of bounded noises.
Staged Self-Assembly and Polyomino Context-Free Grammars
Venue: arXiv cs.CC 2013
Year: 2013

Previous work by Demaine et al. (2012) developed a strong connection between smallest context-free grammars and staged self-assembly systems for one-dimensional strings and assemblies. We extend this work to two-dimensional polyominoes and assemblies, comparing staged self-assembly systems to a natural generalization of context-free grammars we call polyomino context-free grammars (PCFGs). We achieve nearly optimal bounds on the largest ratios of the smallest PCFG and staged self-assembly system for a given polyomino with n cells. For the ratio of PCFGs over assembly systems, we show the smallest PCFG can be an Omega(n/(log(n))^3)-factor larger than the smallest staged assembly system, even when restricted to square polyominoes. For the ratio of assembly systems over PCFGs, we show that the smallest staged assembly system is never more than a O(log(n))-factor larger than the smallest PCFG and is sometimes an Omega(log(n)/loglog(n))-factor larger.
A new Watermarking Technique for Secure Database
Venue: arXiv cs.DB 2013
Year: 2013

Digital multimedia watermarking technology was suggested in the last decade to embed copyright information in digital objects such images, audio and video. However, the increasing use of relational database systems in many real-life applications created an ever increasing need for watermarking database systems. As a result, watermarking relational database systems is now merging as a research area that deals with the legal issue of copyright protection of database systems. Approach: In this study, we proposed an efficient database watermarking algorithm based on inserting binary image watermarks in non-numeric mutli-word attributes of selected database tuples. Results: The algorithm is robust as it resists attempts to remove or degrade the embedded watermark and it is blind as it does not require the original database in order to extract the embedded watermark. Conclusion: Experimental results demonstrated blindness and the robustness of the algorithm against common database attacks.
Proximity Factors of Lattice Reduction-Aided Precoding for Multiantenna Broadcast
Venue: arXiv cs.IT 2013
Year: 2013

Lattice precoding is an effective strategy for multiantenna broadcast. In this paper, we show that approximate lattice precoding in multiantenna broadcast is a variant of the closest vector problem (CVP) known as $η$-CVP. The proximity factors of lattice reduction-aided precoding are defined, and their bounds are derived, which measure the worst-case loss in power efficiency compared to sphere precoding. Unlike decoding applications, this analysis does not suffer from the boundary effect of a finite constellation, since the underlying lattice in multiantenna broadcast is indeed infinite.
A Novel approach for Hybrid Database
Venue: arXiv cs.DB 2013
Year: 2013

In the current world of economic crises, the cost control is one of the chief concerns for all types of industries, especially for the small venders. The small vendors are suppose to minimize their budget on Information Technology by reducing the initial investment in hardware and costly database servers like ORACLE, SQL Server, SYBASE, etc. for the purpose of data processing and storing. In other divisions, the electronic devices manufacturing companies want to increase the demand and reduce the manufacturing cost by introducing the low cost technologies. The new small devices like ipods, iphones, palm top etc. are now-a-days used as data computation and storing tools. For both the cases mentioned above, instead of going for the costly database servers which additionally requires extra hardware as well as the extra expenses in training and handling, the flat file may be considered as a candidate due to its easy handling nature, fast accessing, and of course free of cost. But the main hurdle is the security aspects which are not up to the optimum level. In this paper, we propose a methodology that combines all the merit of the flat file and with the help of a novel steganographic technique we can maintain the utmost security fence. The new proposed methodology will undoubtedly be highly beneficial for small vendors as well as for the above said electronic devices manufacturer
PAV ontology: Provenance, Authoring and Versioning
Venue: arXiv cs.DL 2013
Year: 2013

Provenance is a critical ingredient for establishing trust of published scientific content. This is true whether we are considering a data set, a computational workflow, a peer-reviewed publication or a simple scientific claim with supportive evidence. Existing vocabularies such as DC Terms and the W3C PROV-O are domain-independent and general-purpose and they allow and encourage for extensions to cover more specific needs. We identify the specific need for identifying or distinguishing between the various roles assumed by agents manipulating digital artifacts, such as author, contributor and curator. We present the Provenance, Authoring and Versioning ontology (PAV): a lightweight ontology for capturing just enough descriptions essential for tracking the provenance, authoring and versioning of web resources. We argue that such descriptions are essential for digital scientific content. PAV distinguishes between contributors, authors and curators of content and creators of representations in addition to the provenance of originating resources that have been accessed, transformed and consumed. We explore five projects (and communities) that have adopted PAV illustrating their usage through concrete examples. Moreover, we present mappings that show how PAV extends the PROV-O ontology to support broader interoperability. The authors strived to keep PAV lightweight and compact by including only those terms that have demonstrated to be pragmatically useful in existing applications, and by recommending terms from existing ontologies when plausible. We analyze and compare PAV with related approaches, namely Provenance Vocabulary, DC Terms and BIBFRAME. We identify similarities and analyze their differences with PAV, outlining strengths and weaknesses of our proposed model. We specify SKOS mappings that align PAV with DC Terms.
Supervised Heterogeneous Multiview Learning for Joint Association Study and Disease Diagnosis
Venue: arXiv cs.LG 2013
Year: 2013

Given genetic variations and various phenotypical traits, such as Magnetic Resonance Imaging (MRI) features, we consider two important and related tasks in biomedical research: i)to select genetic and phenotypical markers for disease diagnosis and ii) to identify associations between genetic and phenotypical data. These two tasks are tightly coupled because underlying associations between genetic variations and phenotypical features contain the biological basis for a disease. While a variety of sparse models have been applied for disease diagnosis and canonical correlation analysis and its extensions have bee widely used in association studies (e.g., eQTL analysis), these two tasks have been treated separately. To unify these two tasks, we present a new sparse Bayesian approach for joint association study and disease diagnosis. In this approach, common latent features are extracted from different data sources based on sparse projection matrices and used to predict multiple disease severity levels based on Gaussian process ordinal regression; in return, the disease status is used to guide the discovery of relationships between the data sources. The sparse projection matrices not only reveal interactions between data sources but also select groups of biomarkers related to the disease. To learn the model from data, we develop an efficient variational expectation maximization algorithm. Simulation results demonstrate that our approach achieves higher accuracy in both predicting ordinal labels and discovering associations between data sources than alternative methods. We apply our approach to an imaging genetics dataset for the study of Alzheimer's Disease (AD). Our method identifies biologically meaningful relationships between genetic variations, MRI features, and AD status, and achieves significantly higher accuracy for predicting ordinal AD stages than the competing methods.
SBVR vs OCL: A Comparative Analysis of Standards
Venue: arXiv cs.SE 2013
Year: 2013

In software modelling, the designers have to produce UML visual models with software constraints. Similarly, in business modelling, designers have to model business processes using business constraints (business rules). Constraints are the key components in the skeleton of business or software models. A designer has to write constraints to semantically compliment business models or UML models and finally implementing the constraints into business processes or source code. Business constraints/rules can be written using SBVR (Semantics of Business Vocabulary and Rules) while OCL (Object Constraint Language) is the well-known medium for writing software constraints. SBVR and OCL are two significant standards from OMG. Both standards are principally different as SBVR is typically used in business domains and OCL is employed to compliment software models. However, we have identified a few similarities in both standards that are interesting to study. In this paper, we have performed a comparative analysis of both standards as we are looking for a mechanism for automatic transformation of SBVR to OCL. The major emphasis of the study is to highlight principal features of SBVR and OCL such as similarities, differences and key parameters on which these both standards can work together.
Improved Approximation Algorithms for the Min-Max Selecting Items Problem
Venue: arXiv cs.DS 2013
Year: 2013

We give a simple deterministic $O(\log K / \log\log K)$ approximation algorithm for the Min-Max Selecting Items problem, where $K$ is the number of scenarios. While our main goal is simplicity, this result also improves over the previous best approximation ratio of $O(\log K)$ due to Kasperski, Kurpisz, and Zieliński (Information Processing Letters (2013)). Despite using the method of pessimistic estimators, the algorithm has a polynomial runtime also in the RAM model of computation. We also show that the LP formulation for this problem by Kasperski and Zieliński (Annals of Operations Research (2009)), which is the basis for the previous work and ours, has an integrality gap of at least $Ω(\log K / \log\log K)$.
On Integrating Fuzzy Knowledge Using a Novel Evolutionary Algorithm
Venue: arXiv cs.NE 2013
Year: 2013

Fuzzy systems may be considered as knowledge-based systems that incorporates human knowledge into their knowledge base through fuzzy rules and fuzzy membership functions. The intent of this study is to present a fuzzy knowledge integration framework using a Novel Evolutionary Strategy (NES), which can simultaneously integrate multiple fuzzy rule sets and their membership function sets. The proposed approach consists of two phases: fuzzy knowledge encoding and fuzzy knowledge integration. Four application domains, the hepatitis diagnosis, the sugarcane breeding prediction, Iris plants classification, and Tic-tac-toe endgame were used to show the performance ofthe proposed knowledge approach. Results show that the fuzzy knowledge base derived using our approach performs better than Genetic Algorithm based approach.
Counting Hypergraphs in Data Streams
Venue: arXiv cs.DS 2013
Year: 2013

We present the first streaming algorithm for counting an arbitrary hypergraph $H$ of constant size in a massive hypergraph $G$. Our algorithm can handle both edge-insertions and edge-deletions, and is applicable for the distributed setting. Moreover, our approach provides the first family of graph polynomials for the hypergraph counting problem. Because of the close relationship between hypergraphs and set systems, our approach may have applications in studying similar problems.
Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
Venue: arXiv cs.DS 2013
Year: 2013

A skew-symmetric graph $(D=(V,A),σ)$ is a directed graph $D$ with an involution $σ$ on the set of vertices and arcs. In this paper, we introduce a separation problem, $d$-Skew-Symmetric Multicut, where we are given a skew-symmetric graph $D$, a family of $\cal T$ of $d$-sized subsets of vertices and an integer $k$. The objective is to decide if there is a set $X\subseteq A$ of $k$ arcs such that every set $J$ in the family has a vertex $v$ such that $v$ and $σ(v)$ are in different connected components of $D'=(V,A\setminus (X\cup σ(X))$. In this paper, we give an algorithm for this problem which runs in time $O((4d)^{k}(m+n+\ell))$, where $m$ is the number of arcs in the graph, $n$ the number of vertices and $\ell$ the length of the family given in the input. Using our algorithm, we show that Almost 2-SAT has an algorithm with running time $O(4^kk^4\ell)$ and we obtain algorithms for {\sc Odd Cycle Transversal} and {\sc Edge Bipartization} which run in time $O(4^kk^4(m+n))$ and $O(4^kk^5(m+n))$ respectively. This resolves an open problem posed by Reed, Smith and Vetta [Operations Research Letters, 2003] and improves upon the earlier almost linear time algorithm of Kawarabayashi and Reed [SODA, 2010]. We also show that Deletion q-Horn Backdoor Set Detection is a special case of 3-Skew-Symmetric Multicut, giving us an algorithm for Deletion q-Horn Backdoor Set Detection which runs in time $O(12^kk^5\ell)$. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a paper by a superset of the authors [STACS, 2013]. Using this result, we get an algorithm for Satisfiability which runs in time $O(12^kk^5\ell)$ where $k$ is the size of the smallest q-Horn deletion backdoor set, with $\ell$ being the length of the input formula.
Exact Weight Subgraphs and the k-Sum Conjecture
Venue: arXiv cs.DS 2013
Year: 2013

We consider the Exact-Weight-H problem of finding a (not necessarily induced) subgraph H of weight 0 in an edge-weighted graph G. We show that for every H, the complexity of this problem is strongly related to that of the infamous k-Sum problem. In particular, we show that under the k-Sum Conjecture, we can achieve tight upper and lower bounds for the Exact-Weight-H problem for various subgraphs H such as matching, star, path, and cycle. One interesting consequence is that improving on the O(n^3) upper bound for Exact-Weight-4-Path or Exact-Weight-5-Path will imply improved algorithms for 3-Sum, 5-Sum, All-Pairs Shortest Paths and other fundamental problems. This is in sharp contrast to the minimum-weight and (unweighted) detection versions, which can be solved easily in time O(n^2). We also show that a faster algorithm for any of the following three problems would yield faster algorithms for the others: 3-Sum, Exact-Weight-3-Matching, and Exact-Weight-3-Star.