OpenRaiser/Intern-Atlas huggingface dataset:
Online Adaptive Fault Tolerant based Feedback Control Scheduling Algorithm for Multiprocessor Embedded Systems
Venue: arXiv cs.SY 2012
Year: 2012

Since some years ago, use of Feedback Control Scheduling Algorithm (FCSA) in the control scheduling co-design of multiprocessor embedded system has increased. FCSA provides Quality of Service (QoS) in terms of overall system performance and resource allocation in open and unpredictable environment. FCSA uses quality control feedback loop to keep CPU utilization under desired unitization bound by avoiding overloading and deadline miss ratio. Integrated Fault tolerance (FT) based FCSA design methodology guarantees that the Safety Critical (SC) tasks will meet their deadlines in the presence of faults. However, current FCSA design model does not provide the optimal solution with dynamic load fluctuation. This paper presented a novel methodology of designing an online adaptive fault tolerant based feedback control algorithm for multiprocessor embedded systems. This procedure is important for control scheduling co-design for multiprocessor embedded systems.
Scheduling Resources for Executing a Partial Set of Jobs
Venue: arXiv cs.DS 2012
Year: 2012

In this paper, we consider the problem of choosing a minimum cost set of resources for executing a specified set of jobs. Each input job is an interval, determined by its start-time and end-time. Each resource is also an interval determined by its start-time and end-time; moreover, every resource has a capacity and a cost associated with it. We consider two versions of this problem. In the partial covering version, we are also given as input a number k, specifying the number of jobs that must be performed. The goal is to choose k jobs and find a minimum cost set of resources to perform the chosen k jobs (at any point of time the capacity of the chosen set of resources should be sufficient to execute the jobs active at that time). We present an O(log n)-factor approximation algorithm for this problem. We also consider the prize collecting version, wherein every job also has a penalty associated with it. The feasible solution consists of a subset of the jobs, and a set of resources, to perform the chosen subset of jobs. The goal is to find a feasible solution that minimizes the sum of the costs of the selected resources and the penalties of the jobs that are not selected. We present a constant factor approximation algorithm for this problem
Regular and Singular Boundary Problems in Maple
Venue: arXiv cs.SC 2012
Year: 2012

We describe a new Maple package for treating boundary problems for linear ordinary differential equations, allowing two-/multipoint as well as Stieltjes boundary conditions. For expressing differential operators, boundary conditions, and Green's operators, we employ the algebra of integro-differential operators. The operations implemented for regular boundary problems include computing Green's operators as well as composing and factoring boundary problems. Our symbolic approach to singular boundary problems is new; it provides algorithms for computing compatibility conditions and generalized Green's operators.
Coding for Fast Content Download
Venue: arXiv cs.IT 2012
Year: 2012

We study the fundamental trade-off between storage and content download time. We show that the download time can be significantly reduced by dividing the content into chunks, encoding it to add redundancy and then distributing it across multiple disks. We determine the download time for two content access models - the fountain and fork-join models that involve simultaneous content access, and individual access from enqueued user requests respectively. For the fountain model we explicitly characterize the download time, while in the fork-join model we derive the upper and lower bounds. Our results show that coding reduces download time, through the diversity of distributing the data across more disks, even for the total storage used.
Using Orthogonal Channels for Supporting Multicast Service in Multi-channel Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

Unlike wired networks, the capacity of a wireless network is interference limited due to the broadcast nature of wireless medium. Some multicast wireless network protocols do not consider channel assignment issue, that they cause interference at transmission nodes, hence do not use full capacity of the network. Interference can be reduced and throughput improved with the use of multichannel features. Therefore, this paper used orthogonal channels for sending and receiving nodes in the network. We propose EWM (Efficient Wireless Multicast) method that is distributed scheme for constructing multicast tree in multi-channel multi-interface wireless mesh networks (MIMC-WMN) which selects relay nodes and in distributed form assign orthogonal radio channels to them. To more decrease of interference in adding a branch to the tree, the route with minimum end-to-end delay from the source to the multicast receiver will be chosen. Thus, the tree is suitable for multimedia applicants. We also employ the broadcast nature of the wireless media to reduce the number of relay nodes. The proposed algorithm is compared with MCM algorithm in NS2.
A Survey on Web Spam Detection Methods: Taxonomy
Venue: arXiv cs.IR 2012
Year: 2012

Web spam refers to some techniques, which try to manipulate search engine ranking algorithms in order to raise web page position in search engine results. In the best case, spammers encourage viewers to visit their sites, and provide undeserved advertisement gains to the page owner. In the worst case, they use malicious contents in their pages and try to install malware on the victims machine. Spammers use three kinds of spamming techniques to get higher score in ranking. These techniques are Link based techniques, hiding techniques and content-based techniques. Existing spam pages cause distrust to search engine results. This not only wastes the time of visitors, but also wastes lots of search engine resources. Hence spam detection methods have been proposed as a solution for web spam in order to reduce negative effects of spam pages. Experimental results show that some of these techniques are working well and can find spam pages more accurate than the others. This paper classifies web spam techniques and the related detection methods.
A Benchmark to Select Data Mining Based Classification Algorithms For Business Intelligence And Decision Support Systems
Venue: arXiv cs.DB 2012
Year: 2012

DSS serve the management, operations, and planning levels of an organization and help to make decisions, which may be rapidly changing and not easily specified in advance. Data mining has a vital role to extract important information to help in decision making of a decision support system. Integration of data mining and decision support systems (DSS) can lead to the improved performance and can enable the tackling of new types of problems. Artificial Intelligence methods are improving the quality of decision support, and have become embedded in many applications ranges from ant locking automobile brakes to these days interactive search engines. It provides various machine learning techniques to support data mining. The classification is one of the main and valuable tasks of data mining. Several types of classification algorithms have been suggested, tested and compared to determine the future trends based on unseen data. There has been no single algorithm found to be superior over all others for all data sets. The objective of this paper is to compare various classification algorithms that have been frequently used in data mining for decision support systems. Three decision trees based algorithms, one artificial neural network, one statistical, one support vector machines with and without ada boost and one clustering algorithm are tested and compared on four data sets from different domains in terms of predictive accuracy, error rate, classification index, comprehensibility and training time. Experimental results demonstrate that Genetic Algorithm (GA) and support vector machines based algorithms are better in terms of predictive accuracy. SVM without adaboost shall be the first choice in context of speed and predictive accuracy. Adaboost improves the accuracy of SVM but on the cost of large training time.
Grid Computing: The Next Decade -- Report and Summary
Venue: arXiv cs.DC 2012
Year: 2012

The evolution of the global scientific cyberinfrastructure (CI) has, over the last 10+ years, led to a large diversity of CI instances. While specialized, competing and alternative CI building blocks are inherent to a healthy ecosystem, it also becomes apparent that the increasing degree of fragmentation is hindering interoperation, and thus limiting collaboration, which is essential for modern science communities often spanning international groups and multiple disciplines (but even 'small sciences', with smaller and localized communities, are often embedded into the larger scientific ecosystem, and are increasingly dependent on the availability of CI.) There are different reasons why fragmentation occurs, on technical and social level. But also, it is apparent that the current funding model for creating CI components largely fails to aid the transition from research to production, by mixing CS research and IT engineering challenges into the same funding strategies. The 10th anniversary of the EU funded project 'Grid Lab' (which was an early and ambitious attempt on providing a consolidated and science oriented cyberinfrastructure software stack to a specific science community) was taken as an opportunity to invite international leaders and early stage researchers in grid computing and e-Science from Europe, America and Asia, and, together with representatives of the EU and US funding agencies, to discuss the fundamental aspects of CI evolution, and to contemplate the options for a more coherent, more coordinated approach to the global evolution of CI. This open document represents the results of that workshop - including a draft of a mission statement and a proposal for a blueprint process - to inform the wider community as well as to encourage external experts to provide their feedback and comments.
Artex is AnotheR TEXt summarizer
Venue: arXiv cs.IR 2012
Year: 2012

This paper describes Artex, another algorithm for Automatic Text Summarization. In order to rank sentences, a simple inner product is calculated between each sentence, a document vector (text topic) and a lexical vector (vocabulary used by a sentence). Summaries are then generated by assembling the highest ranked sentences. No ruled-based linguistic post-processing is necessary in order to obtain summaries. Tests over several datasets (coming from Document Understanding Conferences (DUC), Text Analysis Conferences (TAC), evaluation campaigns, etc.) in French, English and Spanish have shown that summarizer achieves interesting results.
Multiple Service providers sharing Spectrum using Cognitive Radio in Wireless Communication Networks
Venue: arXiv cs.NI 2012
Year: 2012

The current utilization of the spectrum is quite inefficient; consequently, if properly used, there is no shortage of the spectrum that is at present available. Therefore, it is anticipated that more flexible use of spectrum and spectrum sharing between radio systems will be key enablers to facilitate the successful implementation of future systems. Cognitive radio, however, is known as the most intelligent and promising technique in solving the problem of spectrum sharing. In this paper, we consider the technique of spectrum sharing among users of service providers to share the licensed spectrum of licensed service providers. It is shown that the proposed technique reduces the call blocking rate and improves the spectrum utilization.
Varactor-Based Dynamic Load Modulation of High Power Amplifiers
Venue: arXiv cs.OH 2012
Year: 2012

In this work, dynamic load modulation of high power amplifiers using a varactor-based tunable matching network is presented. The feasibility of dynamic tuning and efficiency enhancement of this technique is demonstrated using a modular design approach for two existing high efficiency power amplifiers (PA), a 7-W class-E, and a 10-W class-J power amplifier PA at 1 GHz. For this purpose and for each of the PAs, a simple quasi-static inverse model is developed allowing an efficiency-optimized control of the PA and the varactor-based tunable matching network. Modulated measurements using a single carrier WCDMA signal with 11.3 dB peak-to-average ratio (PAR) indicate about 10 to 14 percentage units improvements in the average power-added efficiency (PAE) for the complete architecture.
Degrees of Freedom of Multi-hop MIMO Broadcast Networks with Delayed CSIT
Venue: arXiv cs.IT 2012
Year: 2012

We study the sum degrees of freedom (DoF) of a class of multi-layer relay-aided MIMO broadcast networks with delayed channel state information at transmitters (CSIT). In the assumed network a K-antenna source intends to communicate to K single-antenna destinations, with the help of N-2 layers of K full-duplex single-antenna relays. We consider two practical delayed CSIT feedback scenarios. If the source can obtain the CSI feedback signals from all layers, we prove the optimal sum DoF of the network to be K/(1+1/2+...+1/K). If the CSI feedback is only within each hop, we show that when K=2 the optimal sum DoF is 4/3, and when K >= 3 the sum DoF 3/2 is achievable. Our results reveal that the sum DoF performance in the considered class of N-layer MIMO broadcast networks with delayed CSIT may depend not on N, the number of layers in the network, but only on K, the number of antennas/terminals in each layer.
Plane-Sweep Incremental Algorithm: Computing Delaunay Tessellations of Large Datasets
Venue: arXiv cs.CG 2012
Year: 2012

We present the plane-sweep incremental algorithm, a hybrid approach for computing Delaunay tessellations of large point sets whose size exceeds the computer's main memory. This approach unites the simplicity of the incremental algorithms with the comparatively low memory requirements of plane-sweep approaches. The procedure is to first sort the point set along the first principal component and then to sequentially insert the points into the tessellation, essentially simulating a sweeping plane. The part of the tessellation that has been passed by the sweeping plane can be evicted from memory and written to disk, limiting the memory requirement of the program to the "thickness" of the data set along its first principal component. We implemented the algorithm and used it to compute the Delaunay tessellation and Voronoi partition of the Sloan Digital Sky Survey magnitude space consisting of 287 million points.
On verification of software components
Venue: arXiv cs.SE 2012
Year: 2012

Utilizing third party software components in the development of new systems became somewhat unfavourable approach among many organizations nowadays. This reluctance is primarily built due to the lack of support to verify the quality attributes of software components in order to avoid potential mismatches with systems requirements. This paper presents an approach to overcome this problem by providing a tool support to check component compatibility to a specification provided by developers. So, components compatibility can be checked and developers can verify components that match their quality attributes prior of integrating them into their system.
Image Processing using Smooth Ordering of its Patches
Venue: arXiv cs.CV 2012
Year: 2012

We propose an image processing scheme based on reordering of its patches. For a given corrupted image, we extract all patches with overlaps, refer to these as coordinates in high-dimensional space, and order them such that they are chained in the "shortest possible path", essentially solving the traveling salesman problem. The obtained ordering applied to the corrupted image, implies a permutation of the image pixels to what should be a regular signal. This enables us to obtain good recovery of the clean image by applying relatively simple 1D smoothing operations (such as filtering or interpolation) to the reordered set of pixels. We explore the use of the proposed approach to image denoising and inpainting, and show promising results in both cases.
Exploiting Network Cooperation in Green Wireless Communication
Venue: arXiv cs.IT 2012
Year: 2012

There is a growing interest in energy efficient or so-called "green" wireless communication to reduce the energy consumption in cellular networks. Since today's wireless terminals are typically equipped with multiple network access interfaces such as Bluetooth, Wi-Fi, and cellular networks, this paper investigates user terminals cooperating with each other in transmitting their data packets to the base station (BS), by exploiting the multiple network access interfaces, called inter-network cooperation. We also examine the conventional schemes without user cooperation and with intra-network cooperation for comparison. Given target outage probability and data rate requirements, we analyze the energy consumption of conventional schemes as compared to the proposed inter-network cooperation by taking into account both physical-layer channel impairments (including path loss, fading, and thermal noise) and upper-layer protocol overheads. It is shown that distances between different network entities (i.e., user terminals and BS) have a significant influence on the energy efficiency of proposed inter-network cooperation scheme. Specifically, when the cooperating users are close to BS or the users are far away from each other, the inter-network cooperation may consume more energy than conventional schemes without user cooperation or with intra-network cooperation. However, as the cooperating users move away from BS and the inter-user distance is not too large, the inter-network cooperation significantly reduces the energy consumption over conventional schemes.
Getting Feasible Variable Estimates From Infeasible Ones: MRF Local Polytope Study
Venue: arXiv cs.NA 2012
Year: 2012

This paper proposes a method for construction of approximate feasible primal solutions from dual ones for large-scale optimization problems possessing certain separability properties. Whereas infeasible primal estimates can typically be produced from (sub-)gradients of the dual function, it is often not easy to project them to the primal feasible set, since the projection itself has a complexity comparable to the complexity of the initial problem. We propose an alternative efficient method to obtain feasibility and show that its properties influencing the convergence to the optimum are similar to the properties of the Euclidean projection. We apply our method to the local polytope relaxation of inference problems for Markov Random Fields and demonstrate its superiority over existing methods.
Coalesced communication: a design pattern for complex parallel scientific software
Venue: arXiv cs.DC 2012
Year: 2012

We present a new design pattern for high-performance parallel scientific software, named coalesced communication. This pattern allows for a structured way to improve the communication performance through coalescence of multiple communication needs using two communication management components. We apply the design pattern to several simulations of a lattice-Boltzmann blood flow solver with streaming visualisation which engenders a reduction in the communication overhead of approximately 40%.
Comparing several heuristics for a packing problem
Venue: arXiv cs.NE 2012
Year: 2012

Packing problems are in general NP-hard, even for simple cases. Since now there are no highly efficient algorithms available for solving packing problems. The two-dimensional bin packing problem is about packing all given rectangular items, into a minimum size rectangular bin, without overlapping. The restriction is that the items cannot be rotated. The current paper is comparing a greedy algorithm with a hybrid genetic algorithm in order to see which technique is better for the given problem. The algorithms are tested on different sizes data.
Exploiting Uniform Assignments in First-Order MPE
Venue: arXiv cs.AI 2012
Year: 2012

The MPE (Most Probable Explanation) query plays an important role in probabilistic inference. MPE solution algorithms for probabilistic relational models essentially adapt existing belief assessment method, replacing summation with maximization. But the rich structure and symmetries captured by relational models together with the properties of the maximization operator offer an opportunity for additional simplification with potentially significant computational ramifications. Specifically, these models often have groups of variables that define symmetric distributions over some population of formulas. The maximizing choice for different elements of this group is the same. If we can realize this ahead of time, we can significantly reduce the size of the model by eliminating a potentially significant portion of random variables. This paper defines the notion of uniformly assigned and partially uniformly assigned sets of variables, shows how one can recognize these sets efficiently, and how the model can be greatly simplified once we recognize them, with little computational effort. We demonstrate the effectiveness of these ideas empirically on a number of models.
Toward Large-Scale Agent Guidance in an Urban Taxi Service
Venue: arXiv cs.MA 2012
Year: 2012

Empty taxi cruising represents a wastage of resources in the context of urban taxi services. In this work, we seek to minimize such wastage. An analysis of a large trace of taxi operations reveals that the services' inefficiency is caused by drivers' greedy cruising behavior. We model the existing system as a continuous time Markov chain. To address the problem, we propose that each taxi be equipped with an intelligent agent that will guide the driver when cruising for passengers. Then, drawing from AI literature on multiagent planning, we explore two possible ways to compute such guidance. The first formulation assumes fully cooperative drivers. This allows us, in principle, to compute systemwide optimal cruising policy. This is modeled as a Markov decision process. The second formulation assumes rational drivers, seeking to maximize their own profit. This is modeled as a stochastic congestion game, a specialization of stochastic games. Nash equilibrium policy is proposed as the solution to the game, where no driver has the incentive to singly deviate from it. Empirical result shows that both formulations improve the efficiency of the service significantly.
A Slice Sampler for Restricted Hierarchical Beta Process with Applications to Shared Subspace Learning
Venue: arXiv cs.LG 2012
Year: 2012

Hierarchical beta process has found interesting applications in recent years. In this paper we present a modified hierarchical beta process prior with applications to hierarchical modeling of multiple data sources. The novel use of the prior over a hierarchical factor model allows factors to be shared across different sources. We derive a slice sampler for this model, enabling tractable inference even when the likelihood and the prior over parameters are non-conjugate. This allows the application of the model in much wider contexts without restrictions. We present two different data generative models a linear GaussianGaussian model for real valued data and a linear Poisson-gamma model for count data. Encouraging transfer learning results are shown for two real world applications text modeling and content based image retrieval.