OpenRaiser/Intern-Atlas huggingface dataset:
Covering and Piercing Disks with Two Centers
Venue: arXiv cs.CG 2012
Year: 2012

We give exact and approximation algorithms for two-center problems when the input is a set $\mathcal{D}$ of disks in the plane. We first study the problem of finding two smallest congruent disks such that each disk in $\mathcal{D}$ intersects one of these two disks. Then we study the problem of covering the set $\mathcal{D}$ by two smallest congruent disks.
Minimizing the Switch and Link Conflicts in an Optical Multi-stage Interconnection Network
Venue: arXiv cs.NI 2012
Year: 2012

Multistage Interconnection Networks (MINs) are very popular in switching and communication applications. A MIN connects N inputs to N outputs and is referred as an N \times N MIN; having size N. Optical Multistage Interconnection Network (OMIN) represents an important class of Interconnection networks. Crosstalk is the basic problem of OMIN. Switch Conflict and Link Conflict are the two main reason of crosstalk. In this paper, we are considering both problems. A number of techniques like Optical window, Improved Window, Heuristic, Genetic, and Zero have been proposed earlier in this research domain. In this paper, we have proposed two algorithms called Address Selection Algorithm and Route Selection Algorithm (RSA). RSA is based on Improved Window Method. We have applied the proposed algorithms on existing Omega network, having shuffle-exchange connection pattern. The main functionality of ASA and RSA is to minimize the number of switch and link conflicts in the network and to provide conflict free routes.
A Thermodynamical Approach for Probability Estimation
Venue: arXiv cs.LG 2012
Year: 2012

The issue of discrete probability estimation for samples of small size is addressed in this study. The maximum likelihood method often suffers over-fitting when insufficient data is available. Although the Bayesian approach can avoid over-fitting by using prior distributions, it still has problems with objective analysis. In response to these drawbacks, a new theoretical framework based on thermodynamics, where energy and temperature are introduced, was developed. Entropy and likelihood are placed at the center of this method. The key principle of inference for probability mass functions is the minimum free energy, which is shown to unify the two principles of maximum likelihood and maximum entropy. Our method can robustly estimate probability functions from small size data.
Interactive Character Posing by Sparse Coding
Venue: arXiv cs.GR 2012
Year: 2012

Character posing is of interest in computer animation. It is difficult due to its dependence on inverse kinematics (IK) techniques and articulate property of human characters . To solve the IK problem, classical methods that rely on numerical solutions often suffer from the under-determination problem and can not guarantee naturalness. Existing data-driven methods address this problem by learning from motion capture data. When facing a large variety of poses however, these methods may not be able to capture the pose styles or be applicable in real-time environment. Inspired from the low-rank motion de-noising and completion model in \cite{lai2011motion}, we propose a novel model for character posing based on sparse coding. Unlike conventional approaches, our model directly captures the pose styles in Euclidean space to provide intuitive training error measurements and facilitate pose synthesis. A pose dictionary is learned in training stage and based on it natural poses are synthesized to satisfy users' constraints . We compare our model with existing models for tasks of pose de-noising and completion. Experiments show our model obtains lower de-noising and completion error. We also provide User Interface(UI) examples illustrating that our model is effective for interactive character posing.
Symbol-Index-Feedback Polar Coding Schemes for Low-Complexity Devices
Venue: arXiv cs.IT 2012
Year: 2012

Recently, a new class of error-control codes, the polar codes, have attracted much attention. The polar codes are the first known class of capacity-achieving codes for many important communication channels. In addition, polar codes have low-complexity encoding algorithms. Therefore, these codes are favorable choices for low-complexity devices, for example, in ubiquitous computing and sensor networks. However, the polar codes fall short in terms of finite-length error probabilities, compared with the state-of-the-art codes, such as the low-density parity-check codes. In this paper, in order to improve the error probabilities of the polar codes, we propose novel interactive coding schemes using receiver feedbacks based on polar codes. The proposed coding schemes have very low computational complexities at the transmitter side. By experimental results, we show that the proposed coding schemes achieve significantly lower error probabilities.
Exact Symbolic-Numeric Computation of Planar Algebraic Curves
Venue: arXiv cs.CG 2012
Year: 2012

We present a novel certified and complete algorithm to compute arrangements of real planar algebraic curves. It provides a geometric-topological analysis of the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition. From a high-level perspective, the overall method splits into two main subroutines, namely an algorithm denoted Bisolve to isolate the real solutions of a zero-dimensional bivariate system, and an algorithm denoted GeoTop to analyze a single algebraic curve. Compared to existing approaches based on elimination techniques, we considerably improve the corresponding lifting steps in both subroutines. As a result, generic position of the input system is never assumed, and thus our algorithm never demands for any change of coordinates. In addition, we significantly limit the types of involved exact operations, that is, we only use resultant and gcd computations as purely symbolic operations. The latter results are achieved by combining techniques from different fields such as (modular) symbolic computation, numerical analysis and algebraic geometry. We have implemented our algorithms as prototypical contributions to the C++-project CGAL. They exploit graphics hardware to expedite the symbolic computations. We have also compared our implementation with the current reference implementations, that is, LGP and Maple's Isolate for polynomial system solving, and CGAL's bivariate algebraic kernel for analyses and arrangement computations of algebraic curves. For various series of challenging instances, our exhaustive experiments show that the new implementations outperform the existing ones.
Numerical Weather Prediction (NWP) and hybrid ARMA/ANN model to predict global radiation
Venue: arXiv cs.NE 2012
Year: 2012

We propose in this paper an original technique to predict global radiation using a hybrid ARMA/ANN model and data issued from a numerical weather prediction model (ALADIN). We particularly look at the Multi-Layer Perceptron. After optimizing our architecture with ALADIN and endogenous data previously made stationary and using an innovative pre-input layer selection method, we combined it to an ARMA model from a rule based on the analysis of hourly data series. This model has been used to forecast the hourly global radiation for five places in Mediterranean area. Our technique outperforms classical models for all the places. The nRMSE for our hybrid model ANN/ARMA is 14.9% compared to 26.2% for the naïve persistence predictor. Note that in the stand alone ANN case the nRMSE is 18.4%. Finally, in order to discuss the reliability of the forecaster outputs, a complementary study concerning the confidence interval of each prediction is proposed
MultiDendrograms: Variable-Group Agglomerative Hierarchical Clusterings
Venue: arXiv cs.IR 2012
Year: 2012

MultiDendrograms is a Java-written application that computes agglomerative hierarchical clusterings of data. Starting from a distances (or weights) matrix, MultiDendrograms is able to calculate its dendrograms using the most common agglomerative hierarchical clustering methods. The application implements a variable-group algorithm that solves the non-uniqueness problem found in the standard pair-group algorithm. This problem arises when two or more minimum distances between different clusters are equal during the agglomerative process, because then different output clusterings are possible depending on the criterion used to break ties between distances. MultiDendrograms solves this problem implementing a variable-group algorithm that groups more than two clusters at the same time when ties occur.
Error-Correcting Codes for Reliable Communications in Microgravity Platforms
Venue: arXiv cs.IT 2012
Year: 2012

The PAANDA experiment was conceived to characterize the acceleration ambient of a rocket launched microgravity platform, specially the microgravity phase. The recorded data was transmitted to ground stations, leading to loss of telemetry information sent during the reentry period. Traditionally, an error-correcting code for this channel consists of a block code with very large block size to protect against long periods of data loss. Instead, we propose the use of digital fountain codes along with conventional Reed-Solomon block codes to protect against long and short burst error periods, respectively. Aiming to use this approach for a second version of PAANDA to prevent data corruption, we propose a model for the communication channel based on information extracted from Cumã II's telemetry data, and simulate the performance of our proposed error-correcting code under this channel model. Simulation results show that nearly all telemetry data can be recovered, including data from the reentry period.
Morphological methods for design of modular systems (a survey)
Venue: arXiv cs.SE 2012
Year: 2012

The article addresses morphological approaches to design of modular systems. The following methods are briefly described: (i) basic version of morphological analysis (MA), (ii) modification of MA as method of closeness to ideal point(s), (iii reducing of MA to linear programming, (iv) multiple choice problem, (v) quadratic assignment problem, (vi) Pareto-based MA (i.e., revelation of Pareto-efficient solutions), (vii) Hierarchical Morphological Multicriteria Design (HMMD) approach, and (viii) Hierarchical Morphological Multicriteria Design (HMMD) approach based on fuzzy estimates. The above-mentioned methods are illustrated by schemes, models, and illustrative examples. An additional realistic example (design of GSM network) is presented to illustrate main considered methods.
A Note on Undecidability of Observation Consistency for Non-Regular Languages
Venue: arXiv cs.SY 2012
Year: 2012

One of the most interesting questions concerning hierarchical control of discrete-event systems with partial observations is a condition under which the language observability is preserved between the original and the abstracted plant. Recently, we have characterized two such sufficient conditions---observation consistency and local observation consistency. In this paper, we prove that the condition of observation consistency is undecidable for non-regular (linear, deterministic context-free) languages. The question whether the condition is decidable for regular languages is open.
Graph-Based Random Access for the Collision Channel without Feedback: Capacity Bound
Venue: arXiv cs.IT 2012
Year: 2012

A random access scheme for the collision channel without feedback is proposed. The scheme is based on erasure correcting codes for the recovery of packet segments that are lost in collisions, and on successive interference cancellation for resolving collisions. The proposed protocol achieves reliable communication in the asymptotic setting and attains capacities close to 1 [packets/slot]. A capacity bound as a function of the overall rate of the scheme is derived, and code distributions tightly approaching the bound developed.
Sitting closer to friends than enemies, revisited
Venue: arXiv cs.DS 2012
Year: 2012

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space R^l in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into R^1 can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this particular case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.
Knowledge Ecologies in International Affairs: A New Paradigm for Dialog and Collaboration
Venue: arXiv cs.CY 2012
Year: 2012

To have command over increasingly complicated social, political, economic and environmental challenges, fragmentary knowledge, or rather the simple accumulation of basic research is inadequate (Kim). International affairs professionals operating in government, academia and the private sector are progressively more aware that access to, and the blending of, interdisciplinary policy-related knowledge is critical to effective problem solving and decision-making. But how can one do so effectively?
Low Power Low Voltage Bulk Driven Balanced OTA
Venue: arXiv cs.OH 2012
Year: 2012

The last few decades, a great deal of attention has been paid to low-voltage (LV) low-power (LP) integrated circuits design since the power consumption has become a critical issue. Among many techniques used for the design of LV LP analog circuits, the Bulk-driven principle offers a promising route towards this design for many aspects mainly the simplicity and using the conventional MOS technology to implement these designs. This paper is devoted to the Bulk-driven (BD) principle and utilizing this principle to design LV LP building block of Operational Transconductance Amplifier (OTA) in standard CMOS processes and supply voltage 0.9V. The simulation results have been carried out by the Spice simulator using the 130nm CMOS technology from TSMC.
Dynamic Scope-Based Dijkstra's Algorithm
Venue: arXiv cs.DS 2012
Year: 2012

We briefly report on the current state of a new dynamic algorithm for the route planning problem based on a concept of scope (the static variant presented at ESA'11, HM2011A). We first motivate dynamization of the concept of scope admissibility, and then we briefly describe a modification of the scope-aware query algorithm of HM2011A to dynamic road networks. Finally, we outline our future work on this concept.
Fostering continuous innovation in design with an integrated knowledge management approach
Venue: arXiv cs.OH 2012
Year: 2012

In the global competition, companies are propelled by an immense pressure to innovate. The trend to produce more new knowledge-intensive products or services and the rapid progress of information technologies arouse huge interest on knowledge management for innovation. However the strategy of knowledge management is not widely adopted for innovation in industries due to a lack of an effective approach of their integration. This study aims to help the designers to innovate more efficiently based on an integrated approach of knowledge management. Based on this integrated approach, a prototype of distributed knowledge management system for innovation is developed. An industrial application is presented and its initial results indicate the applicability of the approach and the prototype in practice.
An Active Defense Mechanism for TCP SYN flooding attacks
Venue: arXiv cs.CR 2012
Year: 2012

Distributed denial-of-service attacks on public servers have recently become a serious problem. To assure that network services will not be interrupted and more effective defense mechanisms to protect against malicious traffic, especially SYN floods. One problem in detecting SYN flood traffic is that server nodes or firewalls cannot distinguish the SYN packets of normal TCP connections from those of a SYN flood attack. Another problem is single-point defenses (e.g. firewalls) lack the scalability needed to handle an increase in the attack traffic. We have designed a new defense mechanism to detect the SYN flood attacks. First, we introduce a mechanism for detecting SYN flood traffic more accurately by taking into consideration the time variation of arrival traffic. We investigate the statistics regarding the arrival rates of both normal TCP SYN packets and SYN flood attack packets. We then describe a new detection mechanism based on these statistics. Through the trace driven approach defense nodes which receive the alert messages can identify legitimate traffic and block malicious traffic by delegating SYN/ACK packets.
A Massive Data Parallel Computational Framework for Petascale/Exascale Hybrid Computer Systems
Venue: arXiv cs.DC 2012
Year: 2012

Heterogeneous systems are becoming more common on High Performance Computing (HPC) systems. Even using tools like CUDA and OpenCL it is a non-trivial task to obtain optimal performance on the GPU. Approaches to simplifying this task include Merge (a library based framework for heterogeneous multi-core systems), Zippy (a framework for parallel execution of codes on multiple GPUs), BSGP (a new programming language for general purpose computation on the GPU) and CUDA-lite (an enhancement to CUDA that transforms code based on annotations). In addition, efforts are underway to improve compiler tools for automatic parallelization and optimization of affine loop nests for GPUs and for automatic translation of OpenMP parallelized codes to CUDA. In this paper we present an alternative approach: a new computational framework for the development of massively data parallel scientific codes applications suitable for use on such petascale/exascale hybrid systems built upon the highly scalable Cactus framework. As the first non-trivial demonstration of its usefulness, we successfully developed a new 3D CFD code that achieves improved performance.
A Performance Metric for Discrete-Time Chaos-Based Truly Random Number Generators
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we develop an information entropy based metric that represents the statistical quality of the generated binary sequence in Truly Random Number Generators (TRNG). The metric can be used for the design and optimization of the TRNG circuits as well as the development of efficient post-processing units for recovering the degraded statistical characteristics of the signal due to process variations.
Relationships in Large-Scale Graph Computing
Venue: arXiv cs.DS 2012
Year: 2012

In 2009 Grzegorz Czajkowski from Google's system infrastructure team has published an article which didn't get much attention in the SEO community at the time. It was titled "Large-scale graph computing at Google" and gave an excellent insight into the future of Google's search. This article highlights some of the little known facts which lead to transformation of Google's algorithm in the last two years.
Impact of Dynamic Interactions on Multi-Scale Analysis of Community Structure in Networks
Venue: arXiv cs.SI 2012
Year: 2012

To find interesting structure in networks, community detection algorithms have to take into account not only the network topology, but also dynamics of interactions between nodes. We investigate this claim using the paradigm of synchronization in a network of coupled oscillators. As the network evolves to a global steady state, nodes belonging to the same community synchronize faster than nodes belonging to different communities. Traditionally, nodes in network synchronization models are coupled via one-to-one, or conservative interactions. However, social interactions are often one-to-many, as for example, in social media, where users broadcast messages to all their followers. We formulate a novel model of synchronization in a network of coupled oscillators in which the oscillators are coupled via one-to-many, or non-conservative interactions. We study the dynamics of different interaction models and contrast their spectral properties. To find multi-scale community structure in a network of interacting nodes, we define a similarity function that measures the degree to which nodes are synchronized and use it to hierarchically cluster nodes. We study real-world social networks, including networks of two social media providers. To evaluate the quality of the discovered communities in a social media network we propose a community quality metric based on user activity. We find that conservative and non-conservative interaction models lead to dramatically different views of community structure even within the same network. Our work offers a novel mathematical framework for exploring the relationship between network structure, topology and dynamics.
On Quantification of Anchor Placement
Venue: arXiv cs.NI 2012
Year: 2012

This paper attempts to answer a question: for a given traversal area, how to quantify the geometric impact of anchor placement on localization performance. We present a theoretical framework for quantifying the anchor placement impact. An experimental study, as well as the field test using a UWB ranging technology, is presented. These experimental results validate the theoretical analysis. As a byproduct, we propose a two-phase localization method (TPLM) and show that TPLM outperforms the least-square method in localization accuracy by a huge margin. TPLM performs much faster than the gradient descent method and slightly better than the gradient descent method in localization accuracy. Our field test suggests that TPLM is more robust against noise than the least-square and gradient descent methods.
Flooding attacks to internet threat monitors (ITM): Modeling and counter measures using botnet and honeypots
Venue: arXiv cs.NI 2012
Year: 2012

The Internet Threat Monitoring (ITM),is a globally scoped Internet monitoring system whose goal is to measure, detect, characterize, and track threats such as distribute denial of service(DDoS) attacks and worms. To block the monitoring system in the internet the attackers are targeted the ITM system. In this paper we address flooding attack against ITM system in which the attacker attempt to exhaust the network and ITM's resources, such as network bandwidth, computing power, or operating system data structures by sending the malicious traffic. We propose an information-theoretic frame work that models the flooding attacks using Botnet on ITM. Based on this model we generalize the flooding attacks and propose an effective attack detection using Honeypots.