OpenRaiser/Intern-Atlas huggingface dataset:
Online Packet Scheduling under Adversarial Jamming
Venue: arXiv cs.DC 2013
Year: 2013

We consider the problem of scheduling packets of different lengths via a directed communication link prone to jamming errors. Dynamic packet arrivals and errors are modelled by an adversary. We focus on estimating relative throughput of online scheduling algorithms, that is, the ratio between the throughputs achieved by the algorithm and the best scheduling for the same arrival and error patterns. This framework allows more accurate analysis of performance of online scheduling algorithms, even in worst-case arrival and error scenarios. We design an online algorithm for scheduling packets of arbitrary lengths, achieving optimal relative throughput in the range (1/3,1/2] (the exact value depends on packet lengths). In other words, for any arrival and jamming patterns, our solution gives throughput which is no more than c times worse than the best possible scheduling for these patters, where c in [2; 3) is the inverse of relative throughput. Another algorithm we design makes use of additional resources in order to achieve relative throughput 1, that is, it achieves at least as high throughput as the best schedule without such resources, for any arrival and jamming patterns. More precisely, we show that if the algorithm can run with double speed, i.e., with twice higher frequency, then its relative throughput is 1. This demonstrates that throughput of the best online scheduling algorithms scales well with resource augmentation. Keywords: Packet scheduling, Dynamic packet arrivals, Adversarial jamming, Online algorithms, Relative throughput, Resource augmentation.
Acceptance conditions for omega-languages and the Borel hierarchy
Venue: arXiv cs.FL 2013
Year: 2013

This paper investigates acceptance conditions for finite automata recognizing omega-regular languages. As a first result, we show that, under any acceptance condition that can be defined in the MSO logic, a finite automaton can recognize at most omega-regular languages. Starting from this, the paper aims at classifying acceptance conditions according to their expressive power and at finding the exact position of the classes of omega-languages they induced according to the Borel hierarchy. A new interesting acceptance condition is introduced and fully characterized. A step forward is also made in the understanding of the expressive power of (fin, =).
On the Suitable Domain for SVM Training in Image Coding
Venue: arXiv cs.CV 2013
Year: 2013

Conventional SVM-based image coding methods are founded on independently restricting the distortion in every image coefficient at some particular image representation. Geometrically, this implies allowing arbitrary signal distortions in an $n$-dimensional rectangle defined by the $\varepsilon$-insensitivity zone in each dimension of the selected image representation domain. Unfortunately, not every image representation domain is well-suited for such a simple, scalar-wise, approach because statistical and/or perceptual interactions between the coefficients may exist. These interactions imply that scalar approaches may induce distortions that do not follow the image statistics and/or are perceptually annoying. Taking into account these relations would imply using non-rectangular $\varepsilon$-insensitivity regions (allowing coupled distortions in different coefficients), which is beyond the conventional SVM formulation. In this paper, we report a condition on the suitable domain for developing efficient SVM image coding schemes. We analytically demonstrate that no linear domain fulfills this condition because of the statistical and perceptual inter-coefficient relations that exist in these domains. This theoretical result is experimentally confirmed by comparing SVM learning in previously reported linear domains and in a recently proposed non-linear perceptual domain that simultaneously reduces the statistical and perceptual relations (so it is closer to fulfilling the proposed condition). These results highlight the relevance of an appropriate choice of the image representation before SVM learning.
Crowdsourced Task Routing via Matrix Factorization
Venue: arXiv cs.CY 2013
Year: 2013

We describe methods to predict a crowd worker's accuracy on new tasks based on his accuracy on past tasks. Such prediction provides a foundation for identifying the best workers to route work to in order to maximize accuracy on the new task. Our key insight is to model similarity of past tasks to the target task such that past task accuracies can be optimally integrated to predict target task accuracy. We describe two matrix factorization (MF) approaches from collaborative filtering which not only exploit such task similarity, but are known to be robust to sparse data. Experiments on synthetic and real-world datasets provide feasibility assessment and comparative evaluation of MF approaches vs. two baseline methods. Across a range of data scales and task similarity conditions, we evaluate: 1) prediction error over all workers; and 2) how well each method predicts the best workers to use for each task. Results show the benefit of task routing over random assignment, the strength of probabilistic MF over baseline methods, and the robustness of methods under different conditions.
Multi-Task Regularization with Covariance Dictionary for Linear Classifiers
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we propose a multi-task linear classifier learning problem called D-SVM (Dictionary SVM). D-SVM uses a dictionary of parameter covariance shared by all tasks to do multi-task knowledge transfer among different tasks. We formally define the learning problem of D-SVM and show two interpretations of this problem, from both the probabilistic and kernel perspectives. From the probabilistic perspective, we show that our learning formulation is actually a MAP estimation on all optimization variables. We also show its equivalence to a multiple kernel learning problem in which one is trying to find a re-weighting kernel for features from a dictionary of basis (despite the fact that only linear classifiers are learned). Finally, we describe an alternative optimization scheme to minimize the objective function and present empirical studies to valid our algorithm.
Distributed Computation of Sparse Cuts
Venue: arXiv cs.DC 2013
Year: 2013

Finding sparse cuts is an important tool in analyzing large-scale distributed networks such as the Internet and Peer-to-Peer networks, as well as large-scale graphs such as the web graph, online social communities, and VLSI circuits. In distributed communication networks, they are useful for topology maintenance and for designing better search and routing algorithms. In this paper, we focus on developing fast distributed algorithms for computing sparse cuts in networks. Given an undirected $n$-node network $G$ with conductance $ϕ$, the goal is to find a cut set whose conductance is close to $ϕ$. We present two distributed algorithms that find a cut set with sparsity $\tilde O(\sqrtϕ)$ ($\tilde{O}$ hides $\polylog{n}$ factors). Both our algorithms work in the CONGEST distributed computing model and output a cut of conductance at most $\tilde O(\sqrtϕ)$ with high probability, in $\tilde O(\frac{1}{b}(\frac{1}ϕ + n))$ rounds, where $b$ is balance of the cut of given conductance. In particular, to find a sparse cut of constant balance, our algorithms take $\tilde O(\frac{1}ϕ + n)$ rounds. Our algorithms can also be used to output a {\em local} cluster, i.e., a subset of vertices near a given source node, and whose conductance is within a quadratic factor of the best possible cluster around the specified node. Both our distributed algorithm can work without knowledge of the optimal $ϕ$ value and hence can be used to find approximate conductance values both globally and with respect to a given source node. We also give a lower bound on the time needed for any distributed algorithm to compute any non-trivial sparse cut --- any distributed approximation algorithm (for any non-trivial approximation ratio) for computing sparsest cut will take $\tilde Ω(\sqrt{n} + D)$ rounds, where $D$ is the diameter of the graph.
Interactive Employment Model to Assimilate the Deaf persons in workplace by using ICT
Venue: arXiv cs.CY 2013
Year: 2013

The rate of disability is increase day by day all over the world .There are various type of Disabilities but the deaf persons are on second number among all types of disabilities.. In most of the countries disabled persons are supposed to be social liability on their family and in the society as awhile. Now days in developing countries it is difficult for normal persons to get suitable jobs. Whenever we are talking about disabled, it is more difficult to assimilate deaf persons in workplace. Threats of unemployment of disabled person are almost double that of people without disabilities. Number of able deaf persons is unable to get suitable job due to several reasons like lack of facilities for deaf persons and lack of awareness from normal persons side which create barrier in searching job for deaf persons. This research work emphasis on the special need and training required for the deaf individual sand to make and train them how to move in workplace with different social and technical barrier. In recent era technology play important role in each and every part of life. Using the facility of Information and communication Technology we can easily assimilate deaf in workplace. The proposed model helps deaf persons to adjust in their jobs.
Flickers Forecasting In CRT Using Stochastic Analysis
Venue: arXiv cs.OH 2013
Year: 2013

Videos are composed of sequence of interrelated frames. There is a minute difference among frames. Flicker is an error which is found in every video. It is like a checker box in a video, there are several reasons behind flickers generation, one of the main reasons is refresh rate of the monitor and second reason is number of frames per second in a video. The main objective of this study is to propose and develop a framework that identifies flicker location and minimizes the flickers rate. Analysis shows that flickers can be minimize by adjusting the persistence of pixel and higher refresh rate of CRT monitor. Further we have compared different isotopes of phosphorous pixels and generate its graphs. This paper highlighted the cause of flicker and its avoidance .Statistical research proves that proposed algorithm improves the video quality and reduce flickers ratio up to 90%.
TCC, with History
Venue: arXiv cs.PL 2013
Year: 2013

Modern computer systems are awash in a sea of asynchronous events. There is an increasing need for a declarative language that can permit business users to specify complex event-processing rules. Such rules should be able to correlate different event streams, detect absence of events (negative information), permit aggregations over sliding windows, specify dependent sliding windows etc. For instance it should be possible to precisely state a rule such as "Every seventh trading session that DowJones has risen consecutively, and IBM's stock is off 3% over its average in this period, evaluate IBM position", "Declare the sensor as faulty if no reading has been received for 500 ms", etc. Further, the language should be implementable efficiently in an event-driven fashion. We propose the Timed (Default) Concurrent Constraint, TCC, programming framework as a foundation for such complex event processing. While very rich, the TCC framework "forgets" information from one instant to the next. We make two extensions. First, we extend the TCC model to carry the store from previous time instants as "past" information in the current time instant. This permits rules to to be written with rich queries over the past. Second, we show that many of the powerful properties of the agent language can be folded into the query language by permitting agents and queries to be defined mutually recursively, building on the testing interpretation of intuitionistic logic described in RCC \cite{radha-fsttcs05}. We show that this permits queries to move "back and forth" in the past, e.g.{} "Order a review if the last time that IBM stock price dropped by 10% in a day, there was more than 20% increase in trading volume for Oracle the following day." We provide a formal semantics for TCC + Histories and establish some basic properties.
The Energetic Reasoning Checker Revisited
Venue: arXiv cs.OH 2013
Year: 2013

Energetic Reasoning (ER) is a powerful filtering algorithm for the Cumulative constraint. Unfortunately, ER is generally too costly to be used in practice. One reason of its bad behavior is that many intervals are considered as relevant by the checker of ER, although most of them should be ignored. In this paper, we provide a sharp characterization that allows to reduce the number of intervals by a factor seven. Our experiments show that associating this checker with a Time-Table filtering algorithm leads to promising results.
Products of effective topological spaces and a uniformly computable Tychonoff Theorem
Venue: arXiv cs.LO 2013
Year: 2013

This article is a fundamental study in computable analysis. In the framework of Type-2 effectivity, TTE, we investigate computability aspects on finite and infinite products of effective topological spaces. For obtaining uniform results we introduce natural multi-representations of the class of all effective topological spaces, of their points, of their subsets and of their compact subsets. We show that the binary, finite and countable product operations on effective topological spaces are computable. For spaces with non-empty base sets the factors can be retrieved from the products. We study computability of the product operations on points, on arbitrary subsets and on compact subsets. For the case of compact sets the results are uniformly computable versions of Tychonoff's Theorem (stating that every Cartesian product of compact spaces is compact) for both, the cover multi-representation and the "minimal cover" multi-representation.
IAX-Based Peer-to-Peer VoIP Architecture
Venue: arXiv cs.NI 2013
Year: 2013

Nowadays, Voice over IP (VoIP) constitutes a privileged field of service innovation. One benefit of the VoIP technology is that it may be deployed using a centralized or a distributed architecture. One of the most efficient approaches used in the deployment of centralized VoIP systems is based on the use of IAX (Inter-Asterisk Exchange), an open-source signaling/data exchange protocol. Even though they are currently widely used, client-server VoIP systems suffer from many weaknesses such as the presence of single points of failure, an inefficient resources management, and system non-scalability. In order to help the development of scalable and reliable VoIP systems, the development community starts tending towards the deployment of the VoIP service using a peer-to-peer distributed architecture. The aim of this paper is to develop an IAX-based peer-to-peer VoIP architecture, an optimized VoIP architecture that takes advantage of the benefits of the IAX protocol and those of the peer-to-peer distribution model.
Ontology based data warehouses federation management system
Venue: arXiv cs.DB 2013
Year: 2013

Data warehouses are nowadays an important component in every competitive system, it's one of the main components on which business intelligence is based. We can even say that many companies are climbing to the next level and use a set of Data warehouses to provide the complete information or it's generally due to fusion of two or many companies. these Data warehouses can be heterogeneous and geographically separated, this structure is what we call federation, and even if the components are physically separated, they are logically seen as a single component. generally, these items are heterogeneous which make it difficult to create the logical federation schema,and the execution of user queries a complicated mission. In this paper, we will fill this gap by proposing an extension of an existent algorithm in order to treat different schema types (star, snow flack) including the treatment of hierarchies dimension using ontology
Optimizing Device-to-Device Communications in Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this report, we consider how to dynamically select transmission bands and multi-hop routes for device-to-device (D2D) communications in co-existence with a cellular network overlay. Firstly, we consider different wireless routing algorithms, i.e. broadcasting-routing (BR) method, and shortest-path-routing (SPR) method. The results show that depending on the co-existence cellular users' outage constraint, different routing strategies have different merits. BR is acceptable at the low D2D user density but is terrible at high density. We also consider the channel band performance (Uplink band and Downlink band). The results show that the multi-hop D2D can achieve a low outage probability using the uplink band (approximately 5%), and D2D in the downlink band performs a little poorly (approximately 12%) outage with SPR.
Vehicular Inter-Networking via Named Data
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we apply the Named Data Networking, a newly proposed Internet architecture, to networking vehicles on the run. Our initial design, dubbed V-NDN, illustrates NDN's promising potential in providing a unifying architecture that enables networking among all computing devices independent from whether they are connected through wired infrastructure, ad hoc, or intermittent DTN. This paper describes the prototype implementation of V-NDN and its preliminary performance assessment.
Adaptive Push-Then-Pull Gossip Algorithm for Scale-free Networks
Venue: arXiv cs.NI 2013
Year: 2013

Real life networks are generally modelled as scale free networks. Information diffusion in such networks in decentralised environment is a difficult and resource consuming affair. Gossip algorithms have come up as a good solution to this problem. In this paper, we have proposed Adaptive First Push Then Pull gossip algorithm. We show that algorithm works with minimum cost when the transition round to switch from Adaptive Push to Adaptive Pull is close to Round(log(N)). Furthermore, we compare our algorithm with Push, Pull and First Push Then Pull and show that the proposed algorithm is the most cost efficient in Scale Free networks.
Skin Segmentation based Elastic Bunch Graph Matching for efficient multiple Face Recognition
Venue: arXiv cs.CV 2013
Year: 2013

This paper is aimed at developing and combining different algorithms for face detection and face recognition to generate an efficient mechanism that can detect and recognize the facial regions of input image. For the detection of face from complex region, skin segmentation isolates the face-like regions in a complex image and following operations of morphology and template matching rejects false matches to extract facial region. For the recognition of the face, the image database is now converted into a database of facial segments. Hence, implementing the technique of Elastic Bunch Graph matching (EBGM) after skin segmentation generates Face Bunch Graphs that acutely represents the features of an individual face enhances the quality of the training set. This increases the matching probability significantly.
A Ray-based Approach for Boundary Estimation of Fiber Bundles Derived from Diffusion Tensor Imaging
Venue: arXiv cs.CV 2013
Year: 2013

Diffusion Tensor Imaging (DTI) is a non-invasive imaging technique that allows estimation of the location of white matter tracts in-vivo, based on the measurement of water diffusion properties. For each voxel, a second-order tensor can be calculated by using diffusion-weighted sequences (DWI) that are sensitive to the random motion of water molecules. Given at least 6 diffusion-weighted images with different gradients and one unweighted image, the coefficients of the symmetric diffusion tensor matrix can be calculated. Deriving the eigensystem of the tensor, the eigenvectors and eigenvalues can be calculated to describe the three main directions of diffusion and its magnitude. Using DTI data, fiber bundles can be determined, to gain information about eloquent brain structures. Especially in neurosurgery, information about location and dimension of eloquent structures like the corticospinal tract or the visual pathways is of major interest. Therefore, the fiber bundle boundary has to be determined. In this paper, a novel ray-based approach for boundary estimation of tubular structures is presented.
Logic in the Lab
Venue: arXiv cs.AI 2013
Year: 2013

This file summarizes the plenary talk on laboratory experiments on logic at the TARK 2013 - 14th Conference on Theoretical Aspects of Rationality and Knowledge.
On the Complexity of Dynamic Epistemic Logic
Venue: arXiv cs.LO 2013
Year: 2013

Although Dynamic Epistemic Logic (DEL) is an influential logical framework for representing and reasoning about information change, little is known about the computational complexity of its associated decision problems. In fact, we only know that for public announcement logic, a fragment of DEL, the satisfiability problem and the model-checking problem are respectively PSPACE-complete and in P. We contribute to fill this gap by proving that for the DEL language with event models, the model-checking problem is, surprisingly, PSPACE-complete. Also, we prove that the satisfiability problem is NEXPTIME-complete. In doing so, we provide a sound and complete tableau method deciding the satisfiability problem.
Barrier Certificates Revisited
Venue: arXiv cs.SY 2013
Year: 2013

A barrier certificate can separate the state space of a con- sidered hybrid system (HS) into safe and unsafe parts ac- cording to the safety property to be verified. Therefore this notion has been widely used in the verification of HSs. A stronger condition on barrier certificates means that less expressive barrier certificates can be synthesized. On the other hand, synthesizing more expressive barrier certificates often means high complexity. In [9], Kong et al consid- ered how to relax the condition of barrier certificates while still keeping their convexity so that one can synthesize more expressive barrier certificates efficiently using semi-definite programming (SDP). In this paper, we first discuss how to relax the condition of barrier certificates in a general way, while still keeping their convexity. Particularly, one can then utilize different weaker conditions flexibly to synthesize dif- ferent kinds of barrier certificates with more expressiveness efficiently using SDP. These barriers give more opportuni- ties to verify the considered system. We also show how to combine two functions together to form a combined barrier certificate in order to prove a safety property under consid- eration, whereas neither of them can be used as a barrier certificate separately, even according to any relaxed condi- tion. Another contribution of this paper is that we discuss how to discover certificates from the general relaxed condi- tion by SDP. In particular, we focus on how to avoid the unsoundness because of numeric error caused by SDP with symbolic checking