OpenRaiser/Intern-Atlas huggingface dataset:
Sub-Classifier Construction for Error Correcting Output Code Using Minimum Weight Perfect Matching
Venue: arXiv cs.LG 2013
Year: 2013

Multi-class classification is mandatory for real world problems and one of promising techniques for multi-class classification is Error Correcting Output Code. We propose a method for constructing the Error Correcting Output Code to obtain the suitable combination of positive and negative classes encoded to represent binary classifiers. The minimum weight perfect matching algorithm is applied to find the optimal pairs of subset of classes by using the generalization performance as a weighting criterion. Based on our method, each subset of classes with positive and negative labels is appropriately combined for learning the binary classifiers. Experimental results show that our technique gives significantly higher performance compared to traditional methods including the dense random code and the sparse random code both in terms of accuracy and classification times. Moreover, our method requires significantly smaller number of binary classifiers while maintaining accuracy compared to the One-Versus-One.
Distributed and Parallel Algorithms for Set Cover Problems with Small Neighborhood Covers
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we study a class of set cover problems that satisfy a special property which we call the {\em small neighborhood cover} property. This class encompasses several well-studied problems including vertex cover, interval cover, bag interval cover and tree cover. We design unified distributed and parallel algorithms that can handle any set cover problem falling under the above framework and yield constant factor approximations. These algorithms run in polylogarithmic communication rounds in the distributed setting and are in NC, in the parallel setting.
A Novel Carrier Waveform Inter-Displacement Modulation Method in Underwater Communication Channel
Venue: arXiv cs.OH 2013
Year: 2013

As the main way of underwater wireless communication, underwater acoustic communication is one of the focuses of ocean research. Compared with the free space wireless communication channel, the underwater acoustic channel suffers from more severe multipath effect, the less available bandwidth and the even complex noise. The underwater acoustic channel is one of the most complicated wireless communication channels. To achieve a reliable underwater acoustic communication, Phase Shift Keying (PSK) modulation and Passive Time Reversal Mirror (PTRM) equalization are considered to be a suitable scheme. However, due to the serious distortion of the received signal caused by the channel, this scheme suffers from a high Bit Error Rate (BER) under the condition of the low Signal to Noise Ratio (SNR). To solve this problem, we proposes a Carrier Waveform Inter-Displacement (CWID) modulation method based on the Linear Frequency Modulation (LFM) PSK and PTRM scheme. The new communication scheme reduces BER by increasing the difference from the carrier waveform for different symbols. Simulation results show the effectiveness and superiority of the proposed method.
Evaluating the Performance of IPTV over Fixed WiMAX
Venue: arXiv cs.MM 2013
Year: 2013

IEEE specifies different modulation techniques for WiMAX; namely, BPSK, QPSK, 16 QAM and 64 QAM. This paper studies the performance of Internet Protocol Television (IPTV) over Fixed WiMAX system considering different combinations of digital modulation. The performance is studied taking into account a number of key system parameters which include the variation in the video coding, path-loss, scheduling service classes different rated codes in FEC channel coding. The performance study was conducted using OPNET simulation. The performance is studied in terms of packet lost, packet jitter delay, end-to-end delay, and network throughput. Simulation results show that higher order modulation and coding schemes (namely, 16 QAM and 64 QAM) yield better performance than that of QPSK.
Containment Control of Linear Multi-Agent Systems with Multiple Leaders of Bounded Inputs Using Distributed Continuous Controllers
Venue: arXiv cs.SY 2013
Year: 2013

This paper considers the containment control problem for multi-agent systems with general linear dynamics and multiple leaders whose control inputs are possibly nonzero and time varying. Based on the relative states of neighboring agents, a distributed static continuous controller is designed, under which the containment error is uniformly ultimately bounded and the upper bound of the containment error can be made arbitrarily small, if the subgraph associated with the followers is undirected and for each follower there exists at least one leader that has a directed path to that follower. It is noted that the design of the static controller requires the knowledge of the eigenvalues of the Laplacian matrix and the upper bounds of the leaders' control inputs. In order to remove these requirements, a distributed adaptive continuous controller is further proposed, which can be designed and implemented by each follower in a fully distributed fashion. Extensions to the case where only local output information is available are discussed.
Minimum order of graphs with given coloring parameters
Venue: arXiv cs.DM 2013
Year: 2013

A complete $k$-coloring of a graph $G=(V,E)$ is an assignment $φ:V\to\{1,\ldots,k\}$ of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number $χ(G)$ and achromatic number $ψ(G)$, respectively), and the Grundy number $Γ(G)$ defined as the largest $k$ admitting a complete coloring $φ$ with exactly $k$ colors such that every vertex $v\in V$ of color $φ(v)$ has a neighbor of color $i$ for all $1\le i<φ(v)$. The inequality chain $χ(G)\le Γ(G)\le ψ(G)$ obviously holds for all graphs $G$. A triple $(f,g,h)$ of positive integers at least 2 is called realizable if there exists a connected graph $G$ with $χ(G)=f$, $Γ(G)=g$, and $ψ(G)=h$. Chartrand et al. (A note on graphs with prescribed complete coloring numbers, J. Combin. Math. Combin. Comput. LXXIII (2010) 77-84) found the list of realizable triples. In this paper we determine the minimum number of vertices in a connected graph with chromatic number $f$, Grundy number $g$, and achromatic number $h$, for all realizable triples $(f,g,h)$ of integers. Furthermore, for $f=g=3$ we describe the (two) extremal graphs for each $h \geq 6$. For $h=4$ and $5$, there are more extremal graphs, their description is contained as well.
A Novel Retinal Vessel Segmentation Based On Histogram Transformation Using 2-D Morlet Wavelet and Supervised Classification
Venue: arXiv cs.CV 2013
Year: 2013

The appearance and structure of blood vessels in retinal images have an important role in diagnosis of diseases. This paper proposes a method for automatic retinal vessel segmentation. In this work, a novel preprocessing based on local histogram equalization is used to enhance the original image then pixels are classified as vessel and non-vessel using a classifier. For this classification, special feature vectors are organized based on responses to Morlet wavelet. Morlet wavelet is a continues transform which has the ability to filter existing noises after preprocessing. Bayesian classifier is used and Gaussian mixture model (GMM) is its likelihood function. The probability distributions are approximated according to training set of manual that has been segmented by a specialist. After this, morphological transforms are used in different directions to make the existing discontinuities uniform on the DRIVE database, it achieves the accuracy about 0.9571 which shows that it is an accurate method among the available ones for retinal vessel segmentation.
Weighted Well-Covered Claw-Free Graphs
Venue: arXiv cs.DM 2013
Year: 2013

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space. Given an input claw-free graph G, we present an O(n^6)algortihm, whose input is a claw-free graph G, and output is the vector space of weight functions w, for which G is w-well-covered. A graph G is equimatchable if all its maximal matchings are of the same cardinality. Assume that a weight function w is defined on the edges of G. Then G is w-equimatchable if all its maximal matchings are of the same weight. For every graph G, the set of weight functions w such that G is w-equimatchable is a vector space. We present an O(m*n^4 + n^5*log(n)) algorithm which receives an input graph G, and outputs the vector space of weight functions w such that G is w-equimatchable.
An Easy-to-use Scalable Framework for Parallel Recursive Backtracking
Venue: arXiv cs.DC 2013
Year: 2013

Supercomputers are equipped with an increasingly large number of cores to use computational power as a way of solving problems that are otherwise intractable. Unfortunately, getting serial algorithms to run in parallel to take advantage of these computational resources remains a challenge for several application domains. Many parallel algorithms can scale to only hundreds of cores. The limiting factors of such algorithms are usually communication overhead and poor load balancing. Solving NP-hard graph problems to optimality using exact algorithms is an example of an area in which there has so far been limited success in obtaining large scale parallelism. Many of these algorithms use recursive backtracking as their core solution paradigm. In this paper, we propose a lightweight, easy-to-use, scalable framework for transforming almost any recursive backtracking algorithm into a parallel one. Our framework incurs minimal communication overhead and guarantees a load-balancing strategy that is implicit, i.e., does not require any problem-specific knowledge. The key idea behind this framework is the use of an indexed search tree approach that is oblivious to the problem being solved. We test our framework with parallel implementations of algorithms for the well-known Vertex Cover and Dominating Set problems. On sufficiently hard instances, experimental results show linear speedups for thousands of cores, reducing running times from days to just a few minutes.
Interactive Sensing in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

This paper presents models and algorithms for interactive sensing in social networks where individuals act as sensors and the information exchange between individuals is exploited to optimize sensing. Social learning is used to model the interaction between individuals that aim to estimate an underlying state of nature. In this context the following questions are addressed: How can self-interested agents that interact via social learning achieve a tradeoff between individual privacy and reputation of the social group? How can protocols be designed to prevent data incest in online reputation blogs where individuals make recommendations? How can sensing by individuals that interact with each other be used by a global decision maker to detect changes in the underlying state of nature? When individual agents possess limited sensing, computation and communication capabilities, can a network of agents achieve sophisticated global behavior? Social and game theoretic learning are natural settings for addressing these questions. This article presents an overview, insights and discussion of social learning models in the context of data incest propagation, change detection and coordination of decision making.
Process Based Unification for Multi-Model Software Process Improvement
Venue: arXiv cs.SE 2013
Year: 2013

A number of differences among quality approaches exist and there can be various situations in which the usage of multiple approaches is required, e.g. to strengthen a particular process with multiple quality approaches or to reach certification of the compliance to a number of standards. First of all it has to be decided which approaches have potential for the organization. In many cases one approach does not contain enough information for process implementation. Consequently, the organization may need to use several approaches and the decision has to be made how the chosen approaches can be used simultaneously. This area is called Multi-model Software Process Improvement (MSPI). The simultaneous usage of multiple quality approaches is called the multi-model problem. In this dissertation we propose a solution for the multi-model problem which we call the Process Based Unification (PBU) framework. The PBU framework consists of the PBU concept, a PBU process and the PBU result. We call PBU concept the mapping of quality approaches to a unified process. The PBU concept is operationalized by a PBU process. The PBU result includes the resulting unified process and the mapping of quality approaches to the unified process.
A Subband-Based SVM Front-End for Robust ASR
Venue: arXiv cs.CL 2013
Year: 2013

This work proposes a novel support vector machine (SVM) based robust automatic speech recognition (ASR) front-end that operates on an ensemble of the subband components of high-dimensional acoustic waveforms. The key issues of selecting the appropriate SVM kernels for classification in frequency subbands and the combination of individual subband classifiers using ensemble methods are addressed. The proposed front-end is compared with state-of-the-art ASR front-ends in terms of robustness to additive noise and linear filtering. Experiments performed on the TIMIT phoneme classification task demonstrate the benefits of the proposed subband based SVM front-end: it outperforms the standard cepstral front-end in the presence of noise and linear filtering for signal-to-noise ratio (SNR) below 12-dB. A combination of the proposed front-end with a conventional front-end such as MFCC yields further improvements over the individual front ends across the full range of noise levels.
An efficient playout smoothing mechanism for layered streaming in P2P networks
Venue: arXiv cs.NI 2013
Year: 2013

Layered video streaming in peer-to-peer (P2P) networks has drawn great interest, since it can not only accommodate large numbers of users, but also handle peer heterogeneity. However, there's still a lack of comprehensive studies on chunk scheduling for the smooth playout of layered streams in P2P networks. In these situations, a playout smoothing mechanism can be used to ensure the uniform delivery of the layered stream. This can be achieved by reducing the quality changes that the stream undergoes when adapting to changing network conditions. This paper complements previous efforts in throughput maximization and delay minimization for P2P streaming by considering the consequences of playout smoothing on the scheduling mechanisms for stream layer acquisition. The two main problems to be considered when designing a playout smoothing mechanism for P2P streaming are the fluctuation in available bandwidth between peers and the unreliability of user-contributed resources--particularly peer churn. Since the consideration of these two factors in the selection and scheduling of stream layers is crucial to maintain smooth stream playout, the main objective of our smoothing mechanism becomes the determination of how many layers
Info-computational constructivism in modelling of life as cognition
Venue: arXiv cs.AI 2013
Year: 2013

This paper addresses the open question formulated as: Which levels of abstraction are appropriate in the synthetic modelling of life and cognition? within the framework of info-computational constructivism, treating natural phenomena as computational processes on informational structures. At present we lack the common understanding of the processes of life and cognition in living organisms with the details of co-construction of informational structures and computational processes in embodied, embedded cognizing agents, both living and artifactual ones. Starting with the definition of an agent as an entity capable of acting on its own behalf, as an actor in Hewitt Actor model of computation, even so simple systems as molecules can be modelled as actors exchanging messages (information). We adopt Kauffmans view of a living agent as something that can reproduce and undergoes at least one thermodynamic work cycle. This definition of living agents leads to the Maturana and Varelas identification of life with cognition. Within the info-computational constructive approach to living beings as cognizing agents, from the simplest to the most complex living systems, mechanisms of cognition can be studied in order to construct synthetic model classes of artifactual cognizing agents on different levels of organization.
Beyond Reuse Distance Analysis: Dynamic Analysis for Characterization of Data Locality Potential
Venue: arXiv cs.OH 2013
Year: 2013

Emerging computer architectures will feature drastically decreased flops/byte (ratio of peak processing rate to memory bandwidth) as highlighted by recent studies on Exascale architectural trends. Further, flops are getting cheaper while the energy cost of data movement is increasingly dominant. The understanding and characterization of data locality properties of computations is critical in order to guide efforts to enhance data locality. Reuse distance analysis of memory address traces is a valuable tool to perform data locality characterization of programs. A single reuse distance analysis can be used to estimate the number of cache misses in a fully associative LRU cache of any size, thereby providing estimates on the minimum bandwidth requirements at different levels of the memory hierarchy to avoid being bandwidth bound. However, such an analysis only holds for the particular execution order that produced the trace. It cannot estimate potential improvement in data locality through dependence preserving transformations that change the execution schedule of the operations in the computation. In this article, we develop a novel dynamic analysis approach to characterize the inherent locality properties of a computation and thereby assess the potential for data locality enhancement via dependence preserving transformations. The execution trace of a code is analyzed to extract a computational directed acyclic graph (CDAG) of the data dependences. The CDAG is then partitioned into convex subsets, and the convex partitioning is used to reorder the operations in the execution trace to enhance data locality. The approach enables us to go beyond reuse distance analysis of a single specific order of execution of the operations of a computation in characterization of its data locality properties. It can serve a valuable role in identifying promising code regions for manual transformation, as well as assessing the effectiveness of compiler transformations for data locality enhancement. We demonstrate the effectiveness of the approach using a number of benchmarks, including case studies where the potential shown by the analysis is exploited to achieve lower data movement costs and better performance.
Efficient Image Encryption and Decryption Using Discrete Wavelet Transform and Fractional Fourier Transform
Venue: arXiv cs.CR 2013
Year: 2013

Fractional Fourier transform and chaos functions play a key role in many of encryption-decryption algorithms. In this work performance of image encryption-decryption algorithms is quantified and compared using the computation time i.e. the time consumption of encryption-decryption process and resemblance of input image to the restored image, quantified by MSE. This work proposes an improvement in computation-time of image encryptiondecryption algorithms by utilizing image compression properties of the 2-dimensional Discrete Wavelet Transform (DWT2). Initially, computation complexity of the algorithms is evaluated and compared with that of existing algorithms. This analysis claims the proposed algorithms to be nearly 8 times faster than the existing algorithms. Further, simulations are performed using MATLAB7.7 to quantify performance of existing algorithms and the proposed algorithms using MSE and computation time. The results obtained in these simulations prove that for the proposed algorithms MSE between restored and original images is lesser than that of existing algorithms thereby maintaining the robustness of the existing algorithms. These algorithms are found sensitive to a variation of 1x10-1 in the fractional orders used in encryption-decryption process.
Delegating Custom Object Detection Tasks to a Universal Classification System
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, a concept of multipurpose object detection system, recently introduced in our previous work, is clarified. The business aspect of this method is transformation of a classifier into an object detector/locator via an image grid. This is a universal framework for locating objects of interest through classification. The framework standardizes and simplifies implementation of custom systems by doing only a custom analysis of the classification results on the image grid.
Differenciated Bandwidth Allocation in P2P Layered Streaming
Venue: arXiv cs.NI 2013
Year: 2013

There is an increasing demand for P2P streaming in particular for layered video. In this category of applications, the stream is composed of hierarchically encoded sub-streams layers namely the base layer and enhancements layers. We consider a scenario where the receiver peer uses the pull-based approach to adjust the video quality level to their capability by subscribing to different number of layers. We note that higher layers received without their corresponding lower layers are considered as useless and cannot be played, consequently the throughput of the system will drastically degrade. To avoid this situation, we propose an economical model based on auction mechanisms to optimize the allocation of sender peers' upload bandwidth. The upstream peers organize auctions to "sell" theirs items (links' bandwidth) according to bids submitted by the downstream peers taking into consideration the peers priorities and the requested layers importance. The ultimate goal is to satisfy the quality level requirement for each peer, while reducing the overall streaming cost. Through theoretical study and performance evaluation we show the effectiveness of our model in terms of users and network's utility.
Inductive-data-type Systems
Venue: arXiv cs.LO 2013
Year: 2013

In a previous work ("Abstract Data Type Systems", TCS 173(2), 1997), the last two authors presented a combined language made of a (strongly normalizing) algebraic rewrite system and a typed lambda-calculus enriched by pattern-matching definitions following a certain format, called the "General Schema", which generalizes the usual recursor definitions for natural numbers and similar "basic inductive types". This combined language was shown to be strongly normalizing. The purpose of this paper is to reformulate and extend the General Schema in order to make it easily extensible, to capture a more general class of inductive types, called "strictly positive", and to ease the strong normalization proof of the resulting system. This result provides a computation model for the combination of an algebraic specification language based on abstract data types and of a strongly typed functional language with strictly positive inductive types.