OpenRaiser/Intern-Atlas huggingface dataset:
Variation principle and the universal metric of dynamic routing
Venue: arXiv cs.NI 2011
Year: 2011

In this paper the variation principles from theoretical physics is considered that would describe the process of routing in computer networks. The total traffic which is currently served on all hops of the route has been chosen as the quantity to minimize. Universal metric function has been found for dynamic routing taking into account the packet loss effect. An attempt to derive the metric of the most popular dynamic routing protocols such as RIP, OSPF, EIGRP from universal metric was made.
The Efficiency of MapReduce in Parallel External Memory
Venue: arXiv cs.DC 2011
Year: 2011

Since its introduction in 2004, the MapReduce framework has become one of the standard approaches in massive distributed and parallel computation. In contrast to its intensive use in practise, theoretical footing is still limited and only little work has been done yet to put MapReduce on a par with the major computational models. Following pioneer work that relates the MapReduce framework with PRAM and BSP in their macroscopic structure, we focus on the functionality provided by the framework itself, considered in the parallel external memory model (PEM). In this, we present upper and lower bounds on the parallel I/O-complexity that are matching up to constant factors for the shuffle step. The shuffle step is the single communication phase where all information of one MapReduce invocation gets transferred from map workers to reduce workers. Hence, we move the focus towards the internal communication step in contrast to previous work. The results we obtain further carry over to the BSP* model. On the one hand, this shows how much complexity can be "hidden" for an algorithm expressed in MapReduce compared to PEM. On the other hand, our results bound the worst-case performance loss of the MapReduce approach in terms of I/O-efficiency.
High-Level Multi-Threading in hProlog
Venue: arXiv cs.PL 2011
Year: 2011

A new high-level interface to multi-threading in Prolog, implemented in hProlog, is described. Modern CPUs often contain multiple cores and through high-level multi-threading a programmer can leverage this power without having to worry about low-level details. Two common types of high-level explicit parallelism are discussed: independent and-parallelism and competitive or-parallelism. A new type of explicit parallelism, pipeline parallelism, is proposed. This new type can be used in certain cases where independent and-parallelism and competitive or-parallelism cannot be used.
Approximating Constraint Propagation in Datalog
Venue: arXiv cs.PL 2011
Year: 2011

We present a technique exploiting Datalog with aggregates to improve the performance of programs with arithmetic (in)equalities. Our approach employs a source-to-source program transformation which approximates the propagation technique from Constraint Programming. The experimental evaluation of the approach shows good run time speed-ups on a range of non-recursive as well as recursive programs. Furthermore, our technique improves upon the previously reported in the literature constraint magic set transformation approach.
An Implementation of Bubbling
Venue: arXiv cs.PL 2011
Year: 2011

Non-determinism is of great importance in functional logic programming. It provides expressiveness and efficiency to functional logic computations. In this paper we describe an implementation of the multi-paradigm functional logic language Curry. The evaluation strategy employed by the implementation is based on definitional trees and needed narrowing for deterministic operations, while non-deterministic operations will depend on the graph transformation, bubbling. Bubbling preserves the completeness of non-deterministic operations and avoids unnecessary large-scale reconstruction of expressions done by other approaches.
A Classical Fuzzy Approach for Software Effort Estimation on Machine Learning Technique
Venue: arXiv cs.SE 2011
Year: 2011

Software Cost Estimation with resounding reliability,productivity and development effort is a challenging and onerous task. This has incited the software community to give much needed thrust and delve into extensive research in software effort estimation for evolving sophisticated methods. Estimation by analogy is one of the expedient techniques in software effort estimation field. However, the methodology utilized for the estimation of software effort by analogy is not able to handle the categorical data in an explicit and precise manner. A new approach has been developed in this paper to estimate software effort for projects represented by categorical or numerical data using reasoning by analogy and fuzzy approach. The existing historical data sets, analyzed with fuzzy logic, produce accurate results in comparison to the data set analyzed with the earlier methodologies.
Application of Data Mining Techniques to a Selected Business Organisation with Special Reference to Buying Behaviour
Venue: arXiv cs.DB 2011
Year: 2011

Data mining is a new concept & an exploration and analysis of large data sets, in order to discover meaningful patterns and rules. Many organizations are now using the data mining techniques to find out meaningful patterns from the database. The present paper studies how data mining techniques can be apply to the large database. These data mining techniques give certain behavioral pattern from the database. The results which come after analysis of the database are useful for organization. This paper examines the result after applying association rule mining technique, rule induction technique and Apriori algorithm. These techniques are applied to the database of shopping mall. Market basket analysis is performing by the above mentioned techniques and some important results are found such as buying behavior.
An Adaptive Design Methodology for Reduction of Product Development Risk
Venue: arXiv cs.SE 2011
Year: 2011

Embedded systems interaction with environment inherently complicates understanding of requirements and their correct implementation. However, product uncertainty is highest during early stages of development. Design verification is an essential step in the development of any system, especially for Embedded System. This paper introduces a novel adaptive design methodology, which incorporates step-wise prototyping and verification. With each adaptive step product-realization level is enhanced while decreasing the level of product uncertainty, thereby reducing the overall costs. The back-bone of this frame-work is the development of Domain Specific Operational (DOP) Model and the associated Verification Instrumentation for Test and Evaluation, developed based on the DOP model. Together they generate functionally valid test-sequence for carrying out prototype evaluation. With the help of a case study 'Multimode Detection Subsystem' the application of this method is sketched. The design methodologies can be compared by defining and computing a generic performance criterion like Average design-cycle Risk. For the case study, by computing Average design-cycle Risk, it is shown that the adaptive method reduces the product development risk for a small increase in the total design cycle time.
A Reduced Reference Image Quality Measure Using Bessel K Forms Model for Tetrolet Coefficients
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we introduce a Reduced Reference Image Quality Assessment (RRIQA) measure based on the natural image statistic approach. A new adaptive transform called "Tetrolet" is applied to both reference and distorted images. To model the marginal distribution of tetrolet coefficients Bessel K Forms (BKF) density is proposed. Estimating the parameters of this distribution allows to summarize the reference image with a small amount of side information. Five distortion measures based on the BKF parameters of the original and processed image are used to predict quality scores. A comparison between these measures is presented showing a good consistency with human judgment.
A closed-form expression for the Sharma-Mittal entropy of exponential families
Venue: arXiv cs.IT 2011
Year: 2011

The Sharma-Mittal entropies generalize the celebrated Shannon, Rényi and Tsallis entropies. We report a closed-form formula for the Sharma-Mittal entropies and relative entropies for arbitrary exponential family distributions. We instantiate explicitly the formula for the case of the multivariate Gaussian distributions and discuss on its estimation.
Vertex-centroid finite volume scheme on tetrahedral grids for conservation laws
Venue: arXiv cs.NA 2011
Year: 2011

Vertex-centroid schemes are cell-centered finite volume schemes for conservation laws which make use of vertex values to construct high resolution schemes. The vertex values must be obtained through a consistent averaging (interpolation) procedure. A modified interpolation scheme is proposed which is better than existing schemes in giving positive weights in the interpolation formula. A simplified reconstruction scheme is also proposed which is also more accurate and efficient. For scalar conservation laws, we develop limited versions of the schemes which are stable in maximum norm by constructing suitable limiters. The schemes are applied to compressible flows governed by the Euler equations of inviscid gas dynamics.
Computing Bits of Algebraic Numbers
Venue: arXiv cs.CC 2011
Year: 2011

We initiate the complexity theoretic study of the problem of computing the bits of (real) algebraic numbers. This extends the work of Yap on computing the bits of transcendental numbers like π, in Logspace. Our main result is that computing a bit of a fixed real algebraic number is in C=NC1\subseteq Logspace when the bit position has a verbose (unary) representation and in the counting hierarchy when it has a succinct (binary) representation. Our tools are drawn from elementary analysis and numerical analysis, and include the Newton-Raphson method. The proof of our main result is entirely elementary, preferring to use the elementary Liouville's theorem over the much deeper Roth's theorem for algebraic numbers. We leave the possibility of proving non-trivial lower bounds for the problem of computing the bits of an algebraic number given the bit position in binary, as our main open question. In this direction we show very limited progress by proving a lower bound for rationals.
Between theory and practice: guidelines for an optimization scheme with genetic algorithms - Part I: single-objective continuous global optimization
Venue: arXiv cs.NE 2011
Year: 2011

The rapid advances in the field of optimization methods in many pure and applied science pose the difficulty of keeping track of the developments as well as selecting an appropriate technique that best suits the problem in-hand. From a practitioner point of view is rightful to wander "which optimization method is the best for my problem?". Looking at the optimization process as a "system" of intercon- nected parts, in this paper are collected some ideas about how to tackle an optimization problem using a class of tools from evolutionary computations called Genetic Algorithms. Despite the number of optimization techniques available nowadays the author of this paper thinks that Genetic Algorithms still play a central role for their versatility, robustness, theoretical framework and simplicity of use. The paper can be considered a "collection of tips" (from literature and personal experience) for the non-computer-scientist that has to deal with optimization problems both in the science and engineering practice. No original methods or algorithms are proposed.
Towards realistic modeling of IP-level routing topology dynamics
Venue: arXiv cs.NI 2011
Year: 2011

Many works have studied the Internet topology, but few have investigated the question of how it evolves over time. This paper focuses on the Internet routing IP-level topology and proposes a first step towards realistic modeling of its dynamics. We study periodic measurements of routing trees from a single monitor to a fixed destination set and identify invariant properties of its dynamics. We then propose a simple model for the underlying mechanisms of the topology dynamics. Simulations show that it effectively captures the observed behaviors, thus providing key insights of relevant mechanisms governing the Internet routing dynamics.
Abstracting Path Conditions for Effective Symbolic Execution
Venue: arXiv cs.SC 2011
Year: 2011

We present an algorithm for tests generation tools based on symbolic execution. The algorithm is supposed to help in situations, when a tool is repeatedly failing to cover some code by tests. The algorithm then provides the tool a necessary condition strongly narrowing space of program paths, which must be checked for reaching the uncovered code. We also discuss integration of the algorithm into the tools and we provide experimental results showing a potential of the algorithm to be valuable in the tools, when properly implemented there.
Lazy Pointer Analysis
Venue: arXiv cs.PL 2011
Year: 2011

Flow- and context-sensitive pointer analysis is generally considered too expensive for large programs; most tools relax one or both of the requirements for scalability. We formulate a flow- and context-sensitive points-to analysis that is lazy in the following sense: points-to information is computed only for live pointers and its propagation is sparse (restricted to live ranges of respective pointers). Further, our analysis (a) uses strong liveness, effectively including dead code elimination; (b) afterwards calculates must-points-to information from may-points-to information instead of using a mutual fixed-point; and (c) uses value-based termination of call strings during interprocedural analysis (which reduces the number of call strings significantly). A naive implementation of our analysis within GCC-4.6.0 gave analysis time and size of points-to measurements for SPEC2006. Using liveness reduced the amount of points-to information by an order of magnitude with no loss of precision. For all programs under 30kLoC we found that the results were much more precise than gcc's analysis. What comes as a pleasant surprise however, is the fact that below this cross-over point, our naive linked-list implementation is faster than a flow- and context-insensitive analysis which is primarily used for efficiency. We speculate that lazy flow- and context-sensitive analyses may be not only more precise, but also more efficient, than current approaches.
Automata finiteness criterion in terms of van der Put series of automata functions
Venue: arXiv cs.FL 2011
Year: 2011

In the paper we develop the $p$-adic theory of discrete automata. Every automaton $\mathfrak A$ (transducer) whose input/output alphabets consist of $p$ symbols can be associated to a continuous (in fact, 1-Lipschitz) map from $p$-adic integers to $p$ integers, the automaton function $f_\mathfrak A$. The $p$-adic theory (in particular, the $p$-adic ergodic theory) turned out to be very efficient in a study of properties of automata expressed via properties of automata functions. In the paper we prove a criterion for finiteness of the number of states of automaton in terms of van der Put series of the automaton function. The criterion displays connections between $p$-adic analysis and the theory of automata sequences.
Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU
Venue: arXiv cs.CR 2011
Year: 2011

In this paper we present a new pseudorandom number generator (PRNG) on graphics processing units (GPU). This PRNG is based on the so-called chaotic iterations. It is firstly proven to be chaotic according to the Devaney's formulation. We thus propose an efficient implementation for GPU that successfully passes the BigCrush tests, deemed to be the hardest battery of tests in TestU01. Experiments show that this PRNG can generate about 20 billion of random numbers per second on Tesla C1060 and NVidia GTX280 cards. It is then established that, under reasonable assumptions, the proposed PRNG can be cryptographically secure. A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is finally proposed.
A Complexity Approach for Steganalysis
Venue: arXiv cs.CR 2011
Year: 2011

In this proposal for the Journèes Codes et Stéganographie 2012, we define a new rigorous approach for steganalysis based on the complexity theory. It is similar to the definitions of security that can be found for hash functions, PRNG, and so on. We propose here a notion of \emph{secure hiding} and we give a first secure hiding scheme.
Improving the Efficiency of Approximate Inference for Probabilistic Logical Models by means of Program Specialization
Venue: arXiv cs.AI 2011
Year: 2011

We consider the task of performing probabilistic inference with probabilistic logical models. Many algorithms for approximate inference with such models are based on sampling. From a logic programming perspective, sampling boils down to repeatedly calling the same queries on a knowledge base composed of a static part and a dynamic part. The larger the static part, the more redundancy there is in these repeated calls. This is problematic since inefficient sampling yields poor approximations. We show how to apply logic program specialization to make sampling-based inference more efficient. We develop an algorithm that specializes the definitions of the query predicates with respect to the static part of the knowledge base. In experiments on real-world data we obtain speedups of up to an order of magnitude, and these speedups grow with the data-size.
Quantum Control Experiments as a Testbed for Evolutionary Multi-Objective Algorithms
Venue: arXiv cs.NE 2011
Year: 2011

Experimental multi-objective Quantum Control is an emerging topic within the broad physics and chemistry applications domain of controlling quantum phenomena. This realm offers cutting edge ultrafast laser laboratory applications, which pose multiple objectives, noise, and possibly constraints on the high-dimensional search. In this study we introduce the topic of Multi-Observable Quantum Control (MOQC), and consider specific systems to be Pareto optimized subject to uncertainty, either experimentally or by means of simulated systems. The latter include a family of mathematical test-functions with a practical link to MOQC experiments, which are introduced here for the first time. We investigate the behavior of the multi-objective version of the Covariance Matrix Adaptation Evolution Strategy (MO-CMA-ES) and assess its performance on computer simulations as well as on laboratory closed-loop experiments. Overall, we propose a comprehensive study on experimental evolutionary Pareto optimization in high-dimensional continuous domains, draw some practical conclusions concerning the impact of fitness disturbance on algorithmic behavior, and raise several theoretical issues in the broad evolutionary multi-objective context.
High-Rank Matrix Completion and Subspace Clustering with Missing Data
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the problem of completing a matrix with many missing entries under the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. This generalizes the standard low-rank matrix completion problem to situations in which the matrix rank can be quite high or even full rank. Since the columns belong to a union of subspaces, this problem may also be viewed as a missing-data version of the subspace clustering problem. Let X be an n x N matrix whose (complete) columns lie in a union of at most k subspaces, each of rank <= r < n, and assume N >> kn. The main result of the paper shows that under mild assumptions each column of X can be perfectly recovered with high probability from an incomplete version so long as at least CrNlog^2(n) entries of X are observed uniformly at random, with C>1 a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces. The result is illustrated with numerical experiments and an application to Internet distance matrix completion and topology identification.
A Comprehensive Performance Analysis of Proactive, Reactive and Hybrid MANETs Routing Protocols
Venue: arXiv cs.NI 2011
Year: 2011

A mobile Ad-hoc network (MANET) is a dynamic multi hop wireless network established by a group of nodes in which there is no central administration. Due to mobility of nodes and dynamic network topology, the routing is one of the most important challenges in ad-hoc networks. Several routing algorithms for MANETs have been proposed by the researchers which have been classified into various categories, however, the most prominent categories are proactive, reactive and hybrid. The performance comparison of routing protocols for MANETs has been presented by other researcher also, however, none of these works considers proactive, reactive and hybrid protocols together. In this paper, the performance of proactive (DSDV), reactive (DSR and AODV) and hybrid (ZRP) routing protocols has been compared. The performance differentials are analyzed on the basis of throughput, average delay, routing overhead and number of packets dropped with a variation of number of nodes, pause time and mobility.
A Sparsity-Aware Adaptive Algorithm for Distributed Learning
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, a sparsity-aware adaptive algorithm for distributed learning in diffusion networks is developed. The algorithm follows the set-theoretic estimation rationale. At each time instance and at each node of the network, a closed convex set, known as property set, is constructed based on the received measurements; this defines the region in which the solution is searched for. In this paper, the property sets take the form of hyperslabs. The goal is to find a point that belongs to the intersection of these hyperslabs. To this end, sparsity encouraging variable metric projections onto the hyperslabs have been adopted. Moreover, sparsity is also imposed by employing variable metric projections onto weighted $\ell_1$ balls. A combine adapt cooperation strategy is adopted. Under some mild assumptions, the scheme enjoys monotonicity, asymptotic optimality and strong convergence to a point that lies in the consensus subspace. Finally, numerical examples verify the validity of the proposed scheme, compared to other algorithms, which have been developed in the context of sparse adaptive learning.
An Overview of Context-Aware Vertical Handover Schemes in Heterogeneous Networks
Venue: arXiv cs.NI 2011
Year: 2011

As wireless access technologies grow rapidly, the recent studies have focused on granting mobile users the ability of roaming across different wireless networks in a seamless manner thus offering seamless mobility. The different characteristics of each wireless technology with regards to QoS brought many challenges for provisioning the continuous services (audio/video streaming) in a seamless way. In this paper, we intend to review the existing context-aware methods which offered solutions for service continuity. We looked at the types of context information used in each solution. Through this study, it is clear that context awareness plays a significant role in handover process in order to satisfy users demanding seamless services. Therefore, the goal of this paper is to compare the existing methods grouped as general, IMS based, and WLAN/WiMAX solutions in terms of several criteria, such as interworking architecture, service continuity, and QoS provisioning.