OpenRaiser/Intern-Atlas huggingface dataset:
Parallelizing Deadlock Resolution in Symbolic Synthesis of Distributed Programs
Venue: arXiv cs.DC 2009
Year: 2009

Previous work has shown that there are two major complexity barriers in the synthesis of fault-tolerant distributed programs: (1) generation of fault-span, the set of states reachable in the presence of faults, and (2) resolving deadlock states, from where the program has no outgoing transitions. Of these, the former closely resembles with model checking and, hence, techniques for efficient verification are directly applicable to it. Hence, we focus on expediting the latter with the use of multi-core technology. We present two approaches for parallelization by considering different design choices. The first approach is based on the computation of equivalence classes of program transitions (called group computation) that are needed due to the issue of distribution (i.e., inability of processes to atomically read and write all program variables). We show that in most cases the speedup of this approach is close to the ideal speedup and in some cases it is superlinear. The second approach uses traditional technique of partitioning deadlock states among multiple threads. However, our experiments show that the speedup for this approach is small. Consequently, our analysis demonstrates that a simple approach of parallelizing the group computation is likely to be the effective method for using multi-core computing in the context of deadlock resolution.
Set Systems and Families of Permutations with Small Traces
Venue: arXiv cs.DM 2009
Year: 2009

We study the maximum size of a set system on $n$ elements whose trace on any $b$ elements has size at most $k$. We show that if for some $b \ge i \ge 0$ the shatter function $f_R$ of a set system $([n],R)$ satisfies $f_R(b) < 2^i(b-i+1)$ then $|R| = O(n^i)$; this generalizes Sauer's Lemma on the size of set systems with bounded VC-dimension. We use this bound to delineate the main growth rates for the same problem on families of permutations, where the trace corresponds to the inclusion for permutations. This is related to a question of Raz on families of permutations with bounded VC-dimension that generalizes the Stanley-Wilf conjecture on permutations with excluded patterns.
Interference Alignment and a Noisy Interference Regime for Many-to-One Interference Channels
Venue: arXiv cs.IT 2009
Year: 2009

We study the capacity of discrete memoryless many-to-one interference channels, i.e., K user interference channels where only one receiver faces interference. For a class of many-to-one interference channels, we identify a noisy interference regime, i.e., a regime where random coding and treating interference as noise achieves sum-capacity. Specializing our results to the Gaussian MIMO many-to-one interference channel, which is a special case of the class of channels considered, we obtain new capacity results. Firstly, we extend the noisy interference regime, previously studied for (many-to-one) interference channels with average power constraints on the inputs, to a more general class of inputs. This more general class includes the practical scenario of inputs being restricted to fixed finite-size constellations such as PSK or QAM. Secondly, we extend noisy interference results previously studied in SISO interference channels with full channel state information (CSI) at all nodes, to MIMO and parallel Gaussian many-to-one interference channels, and to fading Gaussian many-to-one interference channels without CSI at the transmitters. While the many-to-one interference channel requires interference alignment, which in turn requires structured codes in general, we argue that in the noisy interference regime, interference is implicitly aligned by random coding irrespective of the input distribution. As a byproduct of our study, we identify a second class of many-to-one interference channels (albeit deterministic) where random coding is optimal (though interference is not treated as noise). The optimality of random coding in this second class of channels is due to an interference resolvability condition which precludes interference alignment and hence obviates the need of structured codes.
NetEvo: A computational framework for the evolution of dynamical complex networks
Venue: arXiv cs.MS 2009
Year: 2009

NetEvo is a computational framework designed to help understand the evolution of dynamical complex networks. It provides flexible tools for the simulation of dynamical processes on networks and methods for the evolution of underlying topological structures. The concept of a supervisor is used to bring together both these aspects in a coherent way. It is the job of the supervisor to rewire the network topology and alter model parameters such that a user specified performance measure is minimised. This performance measure can make use of current topological information and simulated dynamical output from the system. Such an abstraction provides a suitable basis in which to study many outstanding questions related to complex system design and evolution.
Matching 2-D Ellipses to 3-D Circles with Application to Vehicle Pose Estimation
Venue: arXiv cs.CV 2009
Year: 2009

Finding the three-dimensional representation of all or a part of a scene from a single two dimensional image is a challenging task. In this paper we propose a method for identifying the pose and location of objects with circular protrusions in three dimensions from a single image and a 3d representation or model of the object of interest. To do this, we present a method for identifying ellipses and their properties quickly and reliably with a novel technique that exploits intensity differences between objects and a geometric technique for matching an ellipse in 2d to a circle in 3d. We apply these techniques to the specific problem of determining the pose and location of vehicles, particularly cars, from a single image. We have achieved excellent pose recovery performance on artificially generated car images and show promising results on real vehicle images. We also make use of the ellipse detection method to identify car wheels from images, with a very high successful match rate.
Robust Principal Component Analysis?
Venue: arXiv cs.IT 2009
Year: 2009

This paper is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the L1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.
On uniform sampling simple directed graph realizations of degree sequences
Venue: arXiv cs.DM 2009
Year: 2009

Choosing a uniformly sampled simple directed graph realization of a degree sequence has many applications, in particular in social networks where self-loops are commonly not allowed. It has been shown in the past that one can perform a Markov chain arc-switching algorithm to sample a simple directed graph uniformly by performing two types of switches: a 2-switch and a directed 3-cycle reorientation. This paper discusses under what circumstances a directed 3-cycle reorientation is required. In particular, the class of degree sequences where this is required is a subclass of the directed 3-cycle anchored degree sequences. An important implication of this result is a reduced Markov chain algorithm that uses only 2-switches.
Science overlay maps: a new tool for research policy and library management
Venue: arXiv cs.DL 2009
Year: 2009

We present a novel approach to visually locate bodies of research within the sciences, both at each moment of time and dynamically. This article describes how this approach fits with other efforts to locally and globally map scientific outputs. We then show how these science overlay maps help benchmark, explore collaborations, and track temporal changes, using examples of universities, corporations, funding agencies, and research topics. We address conditions of application, with their advantages, downsides and limitations. Overlay maps especially help investigate the increasing number of scientific developments and organisations that do not fit within traditional disciplinary categories. We make these tools accessible to help researchers explore the ongoing socio-cognitive transformation of science and technology systems.
Design of an Automated Intrusion Detection System incorporating an Alarm
Venue: arXiv cs.CR 2009
Year: 2009

Security and safety are two intertwined terms. It is a common belief that when a place or system is secure, it is safe. This paper shows a means of integrating three devices for physical intrusion detection. This paper thus suggests a means of increasing the level of security in an enclosed area with the use three of the four security layers necessary for optimum security. This paper intends to show that a system with more than one security device in place tends to prevent unauthorized access. This paper would be illustrating the implementation of this in an enclosed area whose security level must be kept on the high at all times.
A Study on Feature Selection Techniques in Educational Data Mining
Venue: arXiv cs.DB 2009
Year: 2009

Educational data mining (EDM) is a new growing research area and the essence of data mining concepts are used in the educational field for the purpose of extracting useful information on the behaviors of students in the learning process. In this EDM, feature selection is to be made for the generation of subset of candidate variables. As the feature selection influences the predictive accuracy of any performance model, it is essential to study elaborately the effectiveness of student performance model in connection with feature selection techniques. In this connection, the present study is devoted not only to investigate the most relevant subset features with minimum cardinality for achieving high predictive performance by adopting various filtered feature selection techniques in data mining but also to evaluate the goodness of subsets with different cardinalities and the quality of six filtered feature selection algorithms in terms of F-measure value and Receiver Operating Characteristics (ROC) value, generated by the NaiveBayes algorithm as base-line classifier method. The comparative study carried out by us on six filter feature section algorithms reveals the best method, as well as optimal dimensionality of the feature subset. Benchmarking of filter feature selection method is subsequently carried out by deploying different classifier models. The result of the present study effectively supports the well known fact of increase in the predictive accuracy with the existence of minimum number of features. The expected outcomes show a reduction in computational time and constructional cost in both training and classification phases of the student performance model.
Analysis on the Study of QoS-Aware Web Services Discovery
Venue: arXiv cs.OH 2009
Year: 2009

Web service technology has gained more important role in developing distributed applications and systems on the Internet. Rapid growth of published Web services makes their discovery more and more difficult. There exist many web services which exhibit similar functional characteristics. It is imperative to provide service consumers with facilities for selecting required web services according to their non-functional characteristics or QoS. The QoS-based web service discovery mechanisms will play an essential role in SOA, as e-Business applications want to use services that most accurately meet their requirements. However, representing and storing the values of QoS attributes are problematic, as the current UDDI was not designed to accommodate these emerging requirements. To solve the problems of storing QoS in UDDI and aggregating QoS values using the tModel approach. The aim is to study these approaches and other existing QoS tModel representation for their efficiency and consistency in service discovery. This paper discusses a broad range of research issues such as web service discovery or web service selection based on QoS in the E-Business domain.
Spherical Layout Implementation using Centroidal Voronoi Tessellations
Venue: arXiv cs.CG 2009
Year: 2009

The 3D tree visualization faces multiple challenges: the election of an appropriate layout, the use of the interactions that make the data exploration easier and a metaphor that helps in the process of information understanding. A good combination of these elements will result in a visualization that effectively conveys the key features of a complex structure or system to a wide range of users and permits the analytical reasoning process. In previous works we presented the Spherical Layout, a technique for 3D tree visualization that provides an excellent base to achieve those key features. The layout was implemented using the TriSphere algorithm, a method that discretized the spheres's surfaces with triangles to achieve a uniform distribution of the nodes. The goal of this work was centered in a new algorithm for the implementation of the Spherical layout; we called it the Weighted Spherical Centroidal Voronoi Tessellations (WSCVT). In this paper we present a detailed description of this new implementation and a comparison with the TriSphere algorithm.
Frame Selected Approach for Hiding Data within MPEG Video Using Bit Plane Complexity Segmentation
Venue: arXiv cs.CR 2009
Year: 2009

Bit Plane Complexity Segmentation (BPCS) digital picture steganography is a technique to hide data inside an image file. BPCS achieves high embedding rates with low distortion based on the theory that noise-like regions in an image's bit-planes can be replaced with noise-like secret data without significant loss in image quality. . In this framework we will propose a collaborate approach for select frame for Hiding Data within MPEG Video Using Bit Plane Complexity Segmentation. This approach will invent high secure data hidden using select frame form MPEG Video and furthermore we will assign the well-built of the approach; during this review the author will answer the question why they used select frame steganography. In additional to the security issues we will use the digital video as a cover to the data hidden. The reason behind opt the video cover in this approach is the huge amount of single frames image per sec which in turn overcome the problem of the data hiding quantity, as the experiment result shows the success of the hidden data within select frame, extract data from the frames sequence. These function without affecting the quality of the video.
Turbo Analog Error Correcting Codes Decodable By Linear Programming
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we present a new Turbo analog error correcting coding scheme for real valued signals that are corrupted by impulsive noise. This Turbo code improves Donoho's deterministic construction by using a probabilistic approach. More specifically, our construction corrects more errors than the matrices of Donoho by allowing a vanishingly small probability of error (with the increase in block size). The problem of decoding the long block code is decoupled into two sets of parallel Linear Programming problems. This leads to a significant reduction in decoding complexity as compared to one-step Linear Programming decoding.
Routing in Wireless Adhoc Networks: A New Horizon
Venue: arXiv cs.NI 2009
Year: 2009

A lot of work has been done on routing protocols for mobile ad hoc networks, but still standardization of them requires some more issues less addressed by the existing routing protocols. In this paper a new paradigm of maintaining multiple connections in adhoc routing protocols has been highlighted which may be crucial for efficient routing in mobile ad hoc networks. The problem of multiple connections has been hardly worked on in adhoc networks. In this paper the solution of route maintenance if nodes are maintaining multiple connections has been proposed. This idea not only helps to solve the multiple connections problem, but also take care of proper bandwidth distribution to different connections as per different traffic types. Study has been incorporated on existing AODV with changes. Simulation studies have been performed over packet delivery ratio, throughput and message overheads. Results show that the proposed solution for multiple connections is efficient and worth implementing in existing as well as new protocols.
Polytool: polynomial interpretations as a basis for termination analysis of Logic programs
Venue: arXiv cs.PL 2009
Year: 2009

Our goal is to study the feasibility of porting termination analysis techniques developed for one programming paradigm to another paradigm. In this paper, we show how to adapt termination analysis techniques based on polynomial interpretations - very well known in the context of term rewrite systems (TRSs) - to obtain new (non-transformational) ter- mination analysis techniques for definite logic programs (LPs). This leads to an approach that can be seen as a direct generalization of the traditional techniques in termination analysis of LPs, where linear norms and level mappings are used. Our extension general- izes these to arbitrary polynomials. We extend a number of standard concepts and results on termination analysis to the context of polynomial interpretations. We also propose a constraint-based approach for automatically generating polynomial interpretations that satisfy the termination conditions. Based on this approach, we implemented a new tool, called Polytool, for automatic termination analysis of LPs.
Consensus Dynamics in a non-deterministic Naming Game with Shared Memory
Venue: arXiv cs.MA 2009
Year: 2009

In the naming game, individuals or agents exchange pairwise local information in order to communicate about objects in their common environment. The goal of the game is to reach a consensus about naming these objects. Originally used to investigate language formation and self-organizing vocabularies, we extend the classical naming game with a globally shared memory accessible by all agents. This shared memory can be interpreted as an external source of knowledge like a book or an Internet site. The extended naming game models an environment similar to one that can be found in the context of social bookmarking and collaborative tagging sites where users tag sites using appropriate labels, but also mimics an important aspect in the field of human-based image labeling. Although the extended naming game is non-deterministic in its word selection, we show that consensus towards a common vocabulary is reached. More importantly, we show the qualitative and quantitative influence of the external source of information, i.e. the shared memory, on the consensus dynamics between the agents.
A Necessary and Sufficient Condition for Graph Matching Being Equivalent to the Maximum Weight Clique Problem
Venue: arXiv cs.AI 2009
Year: 2009

This paper formulates a necessary and sufficient condition for a generic graph matching problem to be equivalent to the maximum vertex and edge weight clique problem in a derived association graph. The consequences of this results are threefold: first, the condition is general enough to cover a broad range of practical graph matching problems; second, a proof to establish equivalence between graph matching and clique search reduces to showing that a given graph matching problem satisfies the proposed condition; and third, the result sets the scene for generic continuous solutions for a broad range of graph matching problems. To illustrate the mathematical framework, we apply it to a number of graph matching problems, including the problem of determining the graph edit distance.
Typing rule-based transformations over topological collections
Venue: arXiv cs.PL 2009
Year: 2009

Pattern-matching programming is an example of a rule-based programming style developed in functional languages. This programming style is intensively used in dialects of ML but is restricted to algebraic data-types. This restriction limits the field of application. However, as shown by Giavitto and Michel at RULE'02, case-based function definitions can be extended to more general data structures called topological collections. We show in this paper that this extension retains the benefits of the typed discipline of the functional languages. More precisely, we show that topological collections and the rule-based definition of functions associated with them fit in a polytypic extension of mini-ML where type inference is still possible.
Similarité en intension vs en extension : à la croisée de l'informatique et du théâtre
Venue: arXiv cs.AI 2009
Year: 2009

Traditional staging is based on a formal approach of similarity leaning on dramaturgical ontologies and instanciation variations. Inspired by interactive data mining, that suggests different approaches, we give an overview of computer science and theater researches using computers as partners of the actor to escape the a priori specification of roles.
How Do Interactive Virtual Operas Shift Relationships between Music, Text and Image?
Venue: arXiv cs.MM 2009
Year: 2009

In this paper we present the new genre of interactive operas implemented on personal computers. They differ from traditional ones not only because they are virtual, but mainly because they offer to composers and listeners new perspectives of combinations and interactions between music, text and visual aspects.
Complexity of stochastic branch and bound methods for belief tree search in Bayesian reinforcement learning
Venue: arXiv cs.LG 2009
Year: 2009

There has been a lot of recent work on Bayesian methods for reinforcement learning exhibiting near-optimal online performance. The main obstacle facing such methods is that in most problems of interest, the optimal solution involves planning in an infinitely large tree. However, it is possible to obtain stochastic lower and upper bounds on the value of each tree node. This enables us to use stochastic branch and bound algorithms to search the tree efficiently. This paper proposes two such algorithms and examines their complexity in this setting.