OpenRaiser/Intern-Atlas huggingface dataset:
Implementing a Partitioned 2-page Book Embedding Testing Algorithm
Venue: arXiv cs.DS 2012
Year: 2012

In a book embedding the vertices of a graph are placed on the "spine" of a "book" and the edges are assigned to "pages" so that edges on the same page do not cross. In the Partitioned 2-page Book Embedding problem egdes are partitioned into two sets E_1 and E_2, the pages are two, the edges of E_1 are assigned to page 1, and the edges of E_2 are assigned to page 2. The problem consists of checking if an ordering of the vertices exists along the spine so that the edges of each page do not cross. Hong and Nagamochi give an interesting and complex linear time algorithm for tackling Partitioned 2-page Book Embedding based on SPQR-trees. We show an efficient implementation of this algorithm and show its effectiveness by performing a number of experimental tests. Because of the relationships between Partitioned 2-page Book Embedding and clustered planarity we yield as a side effect an implementation of a clustered planarity testing where the graph has exactly two clusters.
Well Placement Optimization under Uncertainty with CMA-ES Using the Neighborhood
Venue: arXiv cs.CE 2012
Year: 2012

In the well placement problem, as well as in other field development optimization problems, geological uncertainty is a key source of risk affecting the viability of field development projects. Well placement problems under geological uncertainty are formulated as optimization problems in which the objective function is evaluated using a reservoir simulator on a number of possible geological realizations. In this paper, we present a new approach to handle geological uncertainty for the well placement problem with a reduced number of reservoir simulations. The proposed approach uses already simulated well configurations in the neighborhood of each well configuration for the objective function evaluation. We use thus only one single reservoir simulation performed on a randomly chosen realization together with the neighborhood to estimate the objective function instead of using multiple simulations on multiple realizations. This approach is combined with the stochastic optimizer CMA-ES. The proposed approach is shown on the benchmark reservoir case PUNQ-S3 to be able to capture the geological uncertainty using a smaller number of reservoir simulations. This approach is compared to the reference approach using all the possible realizations for each well configuration, and shown to be able to reduce significantly the number of reservoir simulations (around 80%).
Invariant Generation through Strategy Iteration in Succinctly Represented Control Flow Graphs
Venue: arXiv cs.PL 2012
Year: 2012

We consider the problem of computing numerical invariants of programs, for instance bounds on the values of numerical program variables. More specifically, we study the problem of performing static analysis by abstract interpretation using template linear constraint domains. Such invariants can be obtained by Kleene iterations that are, in order to guarantee termination, accelerated by widening operators. In many cases, however, applying this form of extrapolation leads to invariants that are weaker than the strongest inductive invariant that can be expressed within the abstract domain in use. Another well-known source of imprecision of traditional abstract interpretation techniques stems from their use of join operators at merge nodes in the control flow graph. The mentioned weaknesses may prevent these methods from proving safety properties. The technique we develop in this article addresses both of these issues: contrary to Kleene iterations accelerated by widening operators, it is guaranteed to yield the strongest inductive invariant that can be expressed within the template linear constraint domain in use. It also eschews join operators by distinguishing all paths of loop-free code segments. Formally speaking, our technique computes the least fixpoint within a given template linear constraint domain of a transition relation that is succinctly expressed as an existentially quantified linear real arithmetic formula. In contrast to previously published techniques that rely on quantifier elimination, our algorithm is proved to have optimal complexity: we prove that the decision problem associated with our fixpoint problem is in the second level of the polynomial-time hierarchy.
Balanced Modulation for Nonvolatile Memories
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a practical writing/reading scheme in nonvolatile memories, called balanced modulation, for minimizing the asymmetric component of errors. The main idea is to encode data using a balanced error-correcting code. When reading information from a block, it adjusts the reading threshold such that the resulting word is also balanced or approximately balanced. Balanced modulation has suboptimal performance for any cell-level distribution and it can be easily implemented in the current systems of nonvolatile memories. Furthermore, we studied the construction of balanced error-correcting codes, in particular, balanced LDPC codes. It has very efficient encoding and decoding algorithms, and it is more efficient than prior construction of balanced error-correcting codes.
Data-Oblivious Graph Drawing Model and Algorithms
Venue: arXiv cs.DS 2012
Year: 2012

We study graph drawing in a cloud-computing context where data is stored externally and processed using a small local working storage. We show that a number of classic graph drawing algorithms can be efficiently implemented in such a framework where the client can maintain privacy while constructing a drawing of her graph.
Progress on Partial Edge Drawings
Venue: arXiv cs.CG 2012
Year: 2012

Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction $δ$ of the edge lengths ($δ$-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub. We show that, for a fixed stub--edge length ratio $δ$, not all graphs have a $δ$-SHPED. Specifically, we show that $K_{241}$ does not have a 1/4-SHPED, while bandwidth-$k$ graphs always have a $Θ(1/\sqrt{k})$-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.
Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+
Venue: arXiv cs.SI 2012
Year: 2012

Understanding social network structure and evolution has important implications for many aspects of network and system design including provisioning, bootstrapping trust and reputation systems via social networks, and defenses against Sybil attacks. Several recent results suggest that augmenting the social network structure with user attributes (e.g., location, employer, communities of interest) can provide a more fine-grained understanding of social networks. However, there have been few studies to provide a systematic understanding of these effects at scale. We bridge this gap using a unique dataset collected as the Google+ social network grew over time since its release in late June 2011. We observe novel phenomena with respect to both standard social network metrics and new attribute-related metrics (that we define). We also observe interesting evolutionary patterns as Google+ went from a bootstrap phase to a steady invitation-only stage before a public release. Based on our empirical observations, we develop a new generative model to jointly reproduce the social structure and the node attributes. Using theoretical analysis and empirical evaluations, we show that our model can accurately reproduce the social and attribute structure of real social networks. We also demonstrate that our model provides more accurate predictions for practical application contexts.
On Solving the Oriented Two-Dimensional Bin Packing Problem under Free Guillotine Cutting: Exploiting the Power of Probabilistic Solution Construction
Venue: arXiv cs.AI 2012
Year: 2012

Two-dimensional bin packing problems are highly relevant combinatorial optimization problems. They find a large number of applications, for example, in the context of transportation or warehousing, and for the cutting of different materials such as glass, wood or metal. In this work we deal with the oriented two-dimensional bin packing problem under free guillotine cutting. In this specific problem a set of oriented rectangular items is given which must be packed into a minimum number of bins of equal size. The first algorithm proposed in this work is a randomized multi-start version of a constructive one-pass heuristic from the literature. Additionally we propose the use of this randomized one-pass heuristic within an evolutionary algorithm. The results of the two proposed algorithms are compared to the best approaches from the literature. In particular the evolutionary algorithm compares very favorably to current state-of-the-art approaches. The optimal solution for 4 previously unsolved instances could be found.
Conquering the rating bound problem in neighborhood-based collaborative filtering: a function recovery approach
Venue: arXiv cs.IR 2012
Year: 2012

As an important tool for information filtering in the era of socialized web, recommender systems have witnessed rapid development in the last decade. As benefited from the better interpretability, neighborhood-based collaborative filtering techniques, such as item-based collaborative filtering adopted by Amazon, have gained a great success in many practical recommender systems. However, the neighborhood-based collaborative filtering method suffers from the rating bound problem, i.e., the rating on a target item that this method estimates is bounded by the observed ratings of its all neighboring items. Therefore, it cannot accurately estimate the unobserved rating on a target item, if its ground truth rating is actually higher (lower) than the highest (lowest) rating over all items in its neighborhood. In this paper, we address this problem by formalizing rating estimation as a task of recovering a scalar rating function. With a linearity assumption, we infer all the ratings by optimizing the low-order norm, e.g., the $l_1/2$-norm, of the second derivative of the target scalar function, while remaining its observed ratings unchanged. Experimental results on three real datasets, namely Douban, Goodreads and MovieLens, demonstrate that the proposed approach can well overcome the rating bound problem. Particularly, it can significantly improve the accuracy of rating estimation by 37% than the conventional neighborhood-based methods.
Visual Exploration of Simulated and Measured Blood Flow
Venue: arXiv cs.GR 2012
Year: 2012

Morphology of cardiovascular tissue is influenced by the unsteady behavior of the blood flow and vice versa. Therefore, the pathogenesis of several cardiovascular diseases is directly affected by the blood-flow dynamics. Understanding flow behavior is of vital importance to understand the cardiovascular system and potentially harbors a considerable value for both diagnosis and risk assessment. The analysis of hemodynamic characteristics involves qualitative and quantitative inspection of the blood-flow field. Visualization plays an important role in the qualitative exploration, as well as the definition of relevant quantitative measures and its validation. There are two main approaches to obtain information about the blood flow: simulation by computational fluid dynamics, and in-vivo measurements. Although research on blood flow simulation has been performed for decades, many open problems remain concerning accuracy and patient-specific solutions. Possibilities for real measurement of blood flow have recently increased considerably by new developments in magnetic resonance imaging which enable the acquisition of 3D quantitative measurements of blood-flow velocity fields. This chapter presents the visualization challenges for both simulation and real measurements of unsteady blood-flow fields.
On Scalable Video Streaming over Cognitive Radio Cellular and Ad Hoc Networks
Venue: arXiv cs.IT 2012
Year: 2012

Video content delivery over wireless networks is expected to grow drastically in the coming years. In this paper, we investigate the challenging problem of video over cognitive radio (CR) networks. Although having high potential, this problem brings about a new level of technical challenges. After reviewing related work, we first address the problem of video over infrastructure-based CR networks, and then extend the problem to video over non-infrastructure-based ad hoc CR networks. We present formulations of cross-layer optimization problems as well as effective algorithms to solving the problems. The proposed algorithms are analyzed with respect to their optimality and validate with simulations.
Performance Analysis Of Neuro Genetic Algorithm Applied On Detecting Proportion Of Components In Manhole Gas Mixture
Venue: arXiv cs.NE 2012
Year: 2012

The article presents performance analysis of a real valued neuro genetic algorithm applied for the detection of proportion of the gases found in manhole gas mixture. The neural network (NN) trained using genetic algorithm (GA) leads to concept of neuro genetic algorithm, which is used for implementing an intelligent sensory system for the detection of component gases present in manhole gas mixture Usually a manhole gas mixture contains several toxic gases like Hydrogen Sulfide, Ammonia, Methane, Carbon Dioxide, Nitrogen Oxide, and Carbon Monoxide. A semiconductor based gas sensor array used for sensing manhole gas components is an integral part of the proposed intelligent system. It consists of many sensor elements, where each sensor element is responsible for sensing particular gas component. Multiple sensors of different gases used for detecting gas mixture of multiple gases, results in cross-sensitivity. The cross-sensitivity is a major issue and the problem is viewed as pattern recognition problem. The objective of this article is to present performance analysis of the real valued neuro genetic algorithm which is applied for multiple gas detection.
A New Mechanism For Mutual Authentication In SIP
Venue: arXiv cs.CR 2012
Year: 2012

The greatest threat in the new generation network which is called ngn is unsafe authentication. Communication between new servers in ngn world is done based on Session Initiation Protocol. SIP is an application layer control operating on top of a transport protocol which allows creating modifying and terminating sessions among more agents. For authentication SIP relies on HTTP Digest by default the client is authenticated to the SIP proxy server called one way authentication because in this approach we can authenticate client to server and the client cant do any authentication in server side. In this paper we propose a mutual authentication mechanism that is not based on HTTP Digest and then we implement our method in IMS and start to do authentication client to server is done in first step and server to client next.
On Learning with Finite Memory
Venue: arXiv cs.GT 2012
Year: 2012

We consider an infinite collection of agents who make decisions, sequentially, about an unknown underlying binary state of the world. Each agent, prior to making a decision, receives an independent private signal whose distribution depends on the state of the world. Moreover, each agent also observes the decisions of its last K immediate predecessors. We study conditions under which the agent decisions converge to the correct value of the underlying state. We focus on the case where the private signals have bounded information content and investigate whether learning is possible, that is, whether there exist decision rules for the different agents that result in the convergence of their sequence of individual decisions to the correct state of the world. We first consider learning in the almost sure sense and show that it is impossible, for any value of K. We then explore the possibility of convergence in probability of the decisions to the correct state. Here, a distinction arises: if K equals 1, learning in probability is impossible under any decision rule, while for K greater or equal to 2, we design a decision rule that achieves it. We finally consider a new model, involving forward looking strategic agents, each of which maximizes the discounted sum (over all agents) of the probabilities of a correct decision. (The case, studied in previous literature, of myopic agents who maximize the probability of their own decision being correct is an extreme special case.) We show that for any value of K, for any equilibrium of the associated Bayesian game, and under the assumption that each private signal has bounded information content, learning in probability fails to obtain.
Capacity achieving multiwrite WOM codes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we give an explicit construction of a capacity achieving family of binary t-write WOM codes for any number of writes t, that have a polynomial time encoding and decoding algorithms. The block length of our construction is N=(t/ε)^{O(t/(δε))} when εis the gap to capacity and encoding and decoding run in time N^{1+δ}. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets.
Coordination of autonomic functionalities in communications networks
Venue: arXiv cs.NI 2012
Year: 2012

Future communication networks are expected to feature autonomic (or self-organizing) mechanisms to ease deployment (self-configuration), tune parameters automatically (self-optimization) and repair the network (self-healing). Self-organizing mechanisms have been designed as stand-alone entities, even though multiple mechanisms will run in parallel in operational networks. An efficient coordination mechanism will be the major enabler for large scale deployment of self-organizing networks. We model self-organizing mechanisms as control loops, and study the conditions for stability when running control loops in parallel. Based on control theory and Lyapunov stability, we propose a coordination mechanism to stabilize the system, which can be implemented in a distributed fashion. The mechanism remains valid in the presence of measurement noise via stochastic approximation. Instability and coordination in the context of wireless networks are illustrated with two examples and the influence of network geometry is investigated. We are essentially concerned with linear systems, and the applicability of our results for non-linear systems is discussed.
The degrees of freedom of MIMO networks with full-duplex receiver cooperation but no CSIT
Venue: arXiv cs.IT 2012
Year: 2012

The question of whether the degrees of freedom (DoF) of multi-user networks can be enhanced even under isotropic fading and no channel state information (or output feedback) at the transmitters (CSIT) is investigated. Toward this end, the two-user MIMO (multiple-input, multiple-output) broadcast and interference channels are studied with no side-information whatsoever at the transmitters and with receivers equipped with full-duplex radios. The full-duplex feature allows for receiver cooperation because each receiver, in addition to receiving the signals sent by the transmitters, can also simultaneously transmit a signal in the same band to the other receiver. Unlike the case of MIMO networks with CSIT and full-duplex receivers, for which DoF are known, it is shown that for MIMO networks with no CSIT, full-duplex receiver cooperation is beneficial to such an extent that even the DoF region is enhanced. Indeed, for important classes of two-user MIMO broadcast and interference channels, defined by certain relationships on numbers of antennas at different terminals, the exact DoF regions are established. The key to achieving DoF-optimal performance for such networks are new retro-cooperative interference alignment schemes. Their optimality is established via the DoF analysis of certain genie-aided or enhanced version of those networks.
Period Distribution of Inversive Pseudorandom Number Generators Over Finite Fields
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we focus on analyzing the period distribution of the inversive pseudorandom number generators (IPRNGs) over finite field $({\rm Z}_{N},+,\times)$, where $N>3$ is a prime. The sequences generated by the IPRNGs are transformed to 2-dimensional linear feedback shift register (LFSR) sequences. By employing the generating function method and the finite field theory, the period distribution is obtained analytically. The analysis process also indicates how to choose the parameters and the initial values such that the IPRNGs fit specific periods. The analysis results show that there are many small periods if $N$ is not chosen properly. The experimental examples show the effectiveness of the theoretical analysis.
Evaluation of Computational Grammar Formalisms for Indian Languages
Venue: arXiv cs.CL 2012
Year: 2012

Natural Language Parsing has been the most prominent research area since the genesis of Natural Language Processing. Probabilistic Parsers are being developed to make the process of parser development much easier, accurate and fast. In Indian context, identification of which Computational Grammar Formalism is to be used is still a question which needs to be answered. In this paper we focus on this problem and try to analyze different formalisms for Indian languages.
Finding and Recommending Scholarly Articles
Venue: arXiv cs.IR 2012
Year: 2012

The rate at which scholarly literature is being produced has been increasing at approximately 3.5 percent per year for decades. This means that during a typical 40 year career the amount of new literature produced each year increases by a factor of four. The methods scholars use to discover relevant literature must change. Just like everybody else involved in information discovery, scholars are confronted with information overload. Two decades ago, this discovery process essentially consisted of paging through abstract books, talking to colleagues and librarians, and browsing journals. A time-consuming process, which could even be longer if material had to be shipped from elsewhere. Now much of this discovery process is mediated by online scholarly information systems. All these systems are relatively new, and all are still changing. They all share a common goal: to provide their users with access to the literature relevant to their specific needs. To achieve this each system responds to actions by the user by displaying articles which the system judges relevant to the user's current needs. Recently search systems which use particularly sophisticated methodologies to recommend a few specific papers to the user have been called "recommender systems". These methods are in line with the current use of the term "recommender system" in computer science. We do not adopt this definition, rather we view systems like these as components in a larger whole, which is presented by the scholarly information systems themselves. In what follows we view the recommender system as an aspect of the entire information system; one which combines the massive memory capacities of the machine with the cognitive abilities of the human user to achieve a human-machine synergy.