OpenRaiser/Intern-Atlas huggingface dataset:
An Algorithm to Reduce the Time Complexity of Earliest Deadline First Scheduling Algorithm in Real-Time System
Venue: arXiv cs.DS 2010
Year: 2010

In this paper I have study to Reduce the time Complexity of Earliest Deadline First (EDF), a global scheduling scheme for Earliest Deadline First in Real Time System tasks on a Multiprocessors system. Several admission control algorithms for Earliest Deadline First (EDF) are presented, both for hard and soft real-time tasks. The average performance of these admission control algorithms is compared with the performance of known partitioning schemes. I have applied some modification to the global Earliest Deadline First (EDF) algorithms to decrease the number of task migration and also to add predictability to its behavior. The Aim of this work is to provide a sensitivity analysis for task deadline context of multiprocessor system by using a new approach of EFDF (Earliest Feasible Deadline First) algorithm. In order to decrease the number of migrations we prevent a job from moving one processor to another processor if it is among the m higher priority jobs. Therefore, a job will continue its execution on the same processor if possible (processor affinity). The result of these comparisons outlines some situations where one scheme is preferable over the other. Partitioning schemes are better suited for hard real-time systems, while a global scheme is preferable for soft real-time systems.
Integration of Communication Analysis and the OO Method: Manual derivation of the Conceptual Model. The SuperStationery Co. lab demo
Venue: arXiv cs.SE 2010
Year: 2010

This document presents a lab demo that exemplifies the manual derivation of an OO Method conceptual model, taking as input a Communication Analysis requirements model. In addition, it is described how the conceptual model is created in the OLIVANOVA Modeler tool. The lab demo corresponds to part of the business processes of a fictional small and medium enterprise named SuperStationery Co. This company provides stationery and office material to its clients. The company acts as a as intermediary: the company has a catalogue of products that are bought from suppliers and sold to clients. This lab demo, besides illustrating the derivation technique, demonstrates that the technique is feasible in practice. Also, the results of this lab demo provide a valuable feedback in order to improve the derivation technique.
Analysis of Using Browser-native Technology to Build Rich Internet Applications for Image Manipulation
Venue: arXiv cs.HC 2010
Year: 2010

In this work we investigate whether browser-native technologies can be used to perform photo manipulation tasks e.g cropping, resizing or rotating an image within the current mainstream browser. By the use of a case study we will analyze problems that have occurred during the implementation of a prototype web application that utilizes browser-native web technology in order to create an online version of a real world photo scrapbook. Implementation of a prototype will allows us to analyze the strengths and weaknesses of current web technology when it comes to browser-based image manipulation. Furthermore we explore the possibilities of the Ajax in combination Canvas, SVG and VML to provide a more interactive graphical user interface to perform image manipulation tasks on the web.
A Robust and Fault-Tolerant Distributed Intrusion Detection System
Venue: arXiv cs.CR 2010
Year: 2010

Since it is impossible to predict and identify all the vulnerabilities of a network, and penetration into a system by malicious intruders cannot always be prevented, intrusion detection systems (IDSs) are essential entities for ensuring the security of a networked system. To be effective in carrying out their functions, the IDSs need to be accurate, adaptive, and extensible. Given these stringent requirements and the high level of vulnerabilities of the current days' networks, the design of an IDS has become a very challenging task. Although, an extensive research has been done on intrusion detection in a distributed environment, distributed IDSs suffer from a number of drawbacks e.g., high rates of false positives, low detection efficiency etc. In this paper, the design of a distributed IDS is proposed that consists of a group of autonomous and cooperating agents. In addition to its ability to detect attacks, the system is capable of identifying and isolating compromised nodes in the network thereby introducing fault-tolerance in its operations. The experiments conducted on the system have shown that it has high detection efficiency and low false positives compared to some of the currently existing systems.
High Speed and Area Efficient 2D DWT Processor based Image Compression" Signal & Image Processing
Venue: arXiv cs.GR 2010
Year: 2010

This paper presents a high speed and area efficient DWT processor based design for Image Compression applications. In this proposed design, pipelined partially serial architecture has been used to enhance the speed along with optimal utilization and resources available on target FPGA. The proposed model has been designed and simulated using Simulink and System Generator blocks, synthesized with Xilinx Synthesis tool (XST) and implemented on Spartan 2 and 3 based XC2S100-5tq144 and XC3S500E-4fg320 target device. The results show that proposed design can operate at maximum frequency 231 MHz in case of Spartan 3 by consuming power of 117mW at 28 degree/c junction temperature. The result comparison has shown an improvement of 15% in speed.
"On the engineers' new toolbox" or Analog Circuit Design, using Symbolic Analysis, Computer Algebra, and Elementary Network Transformations
Venue: arXiv cs.SC 2010
Year: 2010

In this paper, by way of three examples - a fourth order low pass active RC filter, a rudimentary BJT amplifier, and an LC ladder - we show, how the algebraic capabilities of modern computer algebra systems can, or in the last example, might be brought to use in the task of designing analog circuits.
Specular holography
Venue: arXiv cs.GR 2010
Year: 2010

By tooling an spot-illuminated surface to control the flow of specular glints under motion, one can produce holographic view-dependent imagery. This paper presents the differential equation that governs the shape of the specular surfaces, and illustrates how solutions can be constructed for different kinds of motion, lighting, host surface geometries, and fabrication constraints, leading to some novel forms of holography.
Mutual Information, Relative Entropy, and Estimation in the Poisson Channel
Venue: arXiv cs.IT 2010
Year: 2010

Let $X$ be a non-negative random variable and let the conditional distribution of a random variable $Y$, given $X$, be ${Poisson}(γ\cdot X)$, for a parameter $γ\geq 0$. We identify a natural loss function such that: 1) The derivative of the mutual information between $X$ and $Y$ with respect to $γ$ is equal to the \emph{minimum} mean loss in estimating $X$ based on $Y$, regardless of the distribution of $X$. 2) When $X \sim P$ is estimated based on $Y$ by a mismatched estimator that would have minimized the expected loss had $X \sim Q$, the integral over all values of $γ$ of the excess mean loss is equal to the relative entropy between $P$ and $Q$. For a continuous time setting where $X^T = \{X_t, 0 \leq t \leq T \}$ is a non-negative stochastic process and the conditional law of $Y^T=\{Y_t, 0\le t\le T\}$, given $X^T$, is that of a non-homogeneous Poisson process with intensity function $γ\cdot X^T$, under the same loss function: 1) The minimum mean loss in \emph{causal} filtering when $γ= γ_0$ is equal to the expected value of the minimum mean loss in \emph{non-causal} filtering (smoothing) achieved with a channel whose parameter $γ$ is uniformly distributed between 0 and $γ_0$. Bridging the two quantities is the mutual information between $X^T$ and $Y^T$. 2) This relationship between the mean losses in causal and non-causal filtering holds also in the case where the filters employed are mismatched, i.e., optimized assuming a law on $X^T$ which is not the true one. Bridging the two quantities in this case is the sum of the mutual information and the relative entropy between the true and the mismatched distribution of $Y^T$. Thus, relative entropy quantifies the excess estimation loss due to mismatch in this setting. These results parallel those recently found for the Gaussian channel.
Concrete Sentence Spaces for Compositional Distributional Models of Meaning
Venue: arXiv cs.CL 2010
Year: 2010

Coecke, Sadrzadeh, and Clark (arXiv:1003.4394v1 [cs.CL]) developed a compositional model of meaning for distributional semantics, in which each word in a sentence has a meaning vector and the distributional meaning of the sentence is a function of the tensor products of the word vectors. Abstractly speaking, this function is the morphism corresponding to the grammatical structure of the sentence in the category of finite dimensional vector spaces. In this paper, we provide a concrete method for implementing this linear meaning map, by constructing a corpus-based vector space for the type of sentence. Our construction method is based on structured vector spaces whereby meaning vectors of all sentences, regardless of their grammatical structure, live in the same vector space. Our proposed sentence space is the tensor product of two noun spaces, in which the basis vectors are pairs of words each augmented with a grammatical role. This enables us to compare meanings of sentences by simply taking the inner product of their vectors.
Emotionally Colorful Reflexive Games
Venue: arXiv cs.MA 2010
Year: 2010

This study addresses the matter of reflexive control of the emotional states by means of Reflexive Game Theory (RGT). It is shown how to build a bridge between RGT and emotions. For this purpose the Pleasure-Arousal-Dominance (PAD) model is adopted. The major advantages of RGT are its ability to predict human behavior and unfold the entire spectra of reflexion in the human mind. On the other hand, PAD provides ultimate approach to model emotions. It is illustrated that emotions are reflexive processes and, consequently, RGT fused with PAD model is natural solution to model emotional interactions between people. The fusion of RGT and PAD, called Emotional Reflexive Games (ERG), inherits the key features of both components. Using ERG, we show how reflexive control can be successfully applied to model human emotional states. Up to date, EGR is a unique methodology capable of modeling human reflexive processes and emotional aspects simultaneously.
Guaranteeing the diversity of number generators
Venue: arXiv cs.CR 2010
Year: 2010

A major problem in using iterative number generators of the form x_i=f(x_{i-1}) is that they can enter unexpectedly short cycles. This is hard to analyze when the generator is designed, hard to detect in real time when the generator is used, and can have devastating cryptanalytic implications. In this paper we define a measure of security, called_sequence_diversity_, which generalizes the notion of cycle-length for non-iterative generators. We then introduce the class of counter assisted generators, and show how to turn any iterative generator (even a bad one designed or seeded by an adversary) into a counter assisted generator with a provably high diversity, without reducing the quality of generators which are already cryptographically strong.
Permutation graphs, fast forward permutations, and sampling the cycle structure of a permutation
Venue: arXiv cs.CR 2010
Year: 2010

A permutation P on {1,..,N} is a_fast_forward_permutation_ if for each m the computational complexity of evaluating P^m(x)$ is small independently of m and x. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation on {1,..,N} is Theta(N) if one does not use queries of the form P^m(x), but is only Theta(1) if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form P^m(x) are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.
A New Computational Framework For 2D Shape-Enclosing Contours
Venue: arXiv cs.CV 2010
Year: 2010

In this paper, a new framework for one-dimensional contour extraction from discrete two-dimensional data sets is presented. Contour extraction is important in many scientific fields such as digital image processing, computer vision, pattern recognition, etc. This novel framework includes (but is not limited to) algorithms for dilated contour extraction, contour displacement, shape skeleton extraction, contour continuation, shape feature based contour refinement and contour simplification. Many of the new techniques depend strongly on the application of a Delaunay tessellation. In order to demonstrate the versatility of this novel toolbox approach, the contour extraction techniques presented here are applied to scientific problems in material science, biology and heavy ion physics.
Maximum gradient embeddings and monotone clustering
Venue: arXiv cs.DS 2010
Year: 2010

Let (X,d_X) be an n-point metric space. We show that there exists a distribution D over non-contractive embeddings into trees f:X-->T such that for every x in X, the expectation with respect to D of the maximum over y in X of the ratio d_T(f(x),f(y)) / d_X(x,y) is at most C (log n)^2, where C is a universal constant. Conversely we show that the above quadratic dependence on log n cannot be improved in general. Such embeddings, which we call maximum gradient embeddings, yield a framework for the design of approximation algorithms for a wide range of clustering problems with monotone costs, including fault-tolerant versions of k-median and facility location.
Evolution of the Internet AS-Level Ecosystem
Venue: arXiv cs.NI 2010
Year: 2010

We present an analytically tractable model of Internet evolution at the level of Autonomous Systems (ASs). We call our model the multiclass preferential attachment (MPA) model. As its name suggests, it is based on preferential attachment. All of its parameters are measurable from available Internet topology data. Given the estimated values of these parameters, our analytic results predict a definitive set of statistics characterizing the AS topology structure. These statistics are not part of the model formulation. The MPA model thus closes the "measure-model-validate-predict" loop, and provides further evidence that preferential attachment is a driving force behind Internet evolution.
Fast Computation of Small Cuts via Cycle Space Sampling
Venue: arXiv cs.DC 2010
Year: 2010

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph. In the model of distributed computing in a graph G=(V, E) with O(log V)-bit messages, our approach yields faster algorithms for several problems. The diameter of G is denoted by Diam, and the maximum degree by Delta. We obtain simple O(Diam)-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal --- i.e. a Omega(Diam)-time lower bound holds on every graph. We obtain a O(Diam+Delta/log V)-time distributed algorithm for finding cut vertices; this is faster than the best previous algorithm when Delta, Diam = O(sqrt(V)). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity. In the model of parallel computing on the EREW PRAM our approach yields a simple algorithm with optimal time complexity O(log V) for finding cut pairs and 3-edge-connected components.
On-line Chain Partitions of Up-growing Semi-orders
Venue: arXiv cs.DM 2011
Year: 2011

On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents a partially ordered set, point by point. Algorithm assigns incoming points (immediately and irrevocably) to the chains which constitute a chain partition of the order. The value of the game for orders of width $w$ is a minimum number $\fVal(w)$ such that Algorithm has a strategy using at most $\fVal(w)$ chains on orders of width at most $w$. We analyze the chain partition game for up-growing semi-orders. Surprisingly, the golden ratio comes into play and the value of the game is $\lfloor\frac{1+\sqrt{5}}{2}\; w \rfloor$.
Iterative Rounding for the Closest String Problem
Venue: arXiv cs.DS 2011
Year: 2011

The closest string problem is an NP-hard problem, whose task is to find a string that minimizes maximum Hamming distance to a given set of strings. This can be reduced to an integer program (IP). However, to date, there exists no known polynomial-time algorithm for IP. In 2004, Meneses et al. introduced a branch-and-bound (B & B) method for solving the IP problem. Their algorithm is not always efficient and has the exponential time complexity. In the paper, we attempt to solve efficiently the IP problem by a greedy iterative rounding technique. The proposed algorithm is polynomial time and much faster than the existing B & B IP for the CSP. If the number of strings is limited to 3, the algorithm is provably at most 1 away from the optimum. The empirical results show that in many cases we can find an exact solution. Even though we fail to find an exact solution, the solution found is very close to exact solution.
Recognizing Partial Cubes in Quadratic Time
Venue: arXiv cs.DS 2011
Year: 2011

We show how to test whether a graph with n vertices and m edges is a partial cube, and if so how to find a distance-preserving embedding of the graph into a hypercube, in the near-optimal time bound O(n^2), improving previous O(nm)-time solutions.
A Tighter Analysis of Setcover Greedy Algorithm for Test Set
Venue: arXiv cs.DS 2011
Year: 2011

Setcover greedy algorithm is a natural approximation algorithm for test set problem. This paper gives a precise and tighter analysis of performance guarantee of this algorithm. The author improves the performance guarantee $2\ln n$ which derives from set cover problem to $1.1354\ln n$ by applying the potential function technique. In addition, the author gives a nontrivial lower bound $1.0004609\ln n$ of performance guarantee of this algorithm. This lower bound, together with the matching bound of information content heuristic, confirms the fact information content heuristic is slightly better than setcover greedy algorithm in worst case.
Cointegration of the Daily Electric Power System Load and the Weather
Venue: arXiv cs.CE 2011
Year: 2011

The paper makes a thermal predictive analysis of the electric power system security for a day ahead. This predictive analysis is set as a thermal computation of the expected security. This computation is obtained by cointegrating the daily electric power systen load and the weather, by finding the daily electric power system thermodynamics and by introducing tests for this thermodynamics. The predictive analysis made shows the electricity consumers' wisdom.
Rateless Coding for Gaussian Channels
Venue: arXiv cs.IT 2011
Year: 2011

A rateless code-i.e., a rate-compatible family of codes-has the property that codewords of the higher rate codes are prefixes of those of the lower rate ones. A perfect family of such codes is one in which each of the codes in the family is capacity-achieving. We show by construction that perfect rateless codes with low-complexity decoding algorithms exist for additive white Gaussian noise channels. Our construction involves the use of layered encoding and successive decoding, together with repetition using time-varying layer weights. As an illustration of our framework, we design a practical three-rate code family. We further construct rich sets of near-perfect rateless codes within our architecture that require either significantly fewer layers or lower complexity than their perfect counterparts. Variations of the basic construction are also developed, including one for time-varying channels in which there is no a priori stochastic model.
Minimizing the Maximum Interference is Hard
Venue: arXiv cs.NI 2011
Year: 2011

We consider the following interference model for wireless sensor and ad hoc networks: the receiver interference of a node is the number of transmission ranges it lies in. We model transmission ranges as disks. For this case we show that choosing transmission radii which minimize the maximum interference while maintaining a connected symmetric communication graph is NP-complete.
Search Space Contraction in Canonical Labeling of Graphs
Venue: arXiv cs.DS 2011
Year: 2011

The individualization-refinement paradigm for computing a canonical labeling and the automorphism group of a graph is investigated. A new algorithmic design aimed at reducing the size of the associated search space is introduced, and a new tool, named "Traces", is presented, together with experimental results and comparisons with existing software, such as McKay's "nauty". It is shown that the approach presented here leads to a huge reduction in the search space, thereby making computation feasible for several classes of graphs which are hard for all the main canonical labeling tools in the literature.
Multi-Instance Multi-Label Learning
Venue: arXiv cs.LG 2011
Year: 2011

In this paper, we propose the MIML (Multi-Instance Multi-Label learning) framework where an example is described by multiple instances and associated with multiple class labels. Compared to traditional learning frameworks, the MIML framework is more convenient and natural for representing complicated objects which have multiple semantic meanings. To learn from MIML examples, we propose the MimlBoost and MimlSvm algorithms based on a simple degeneration strategy, and experiments show that solving problems involving complicated objects with multiple semantic meanings in the MIML framework can lead to good performance. Considering that the degeneration process may lose information, we propose the D-MimlSvm algorithm which tackles MIML problems directly in a regularization framework. Moreover, we show that even when we do not have access to the real objects and thus cannot capture more information from real objects by using the MIML representation, MIML is still useful. We propose the InsDif and SubCod algorithms. InsDif works by transforming single-instances into the MIML representation for learning, while SubCod works by transforming single-label examples into the MIML representation for learning. Experiments show that in some tasks they are able to achieve better performance than learning the single-instances or single-label examples directly.