OpenRaiser/Intern-Atlas huggingface dataset:
Significance Relations for the Benchmarking of Meta-Heuristic Algorithms
Venue: arXiv cs.DS 2013
Year: 2013

The experimental analysis of meta-heuristic algorithm performance is usually based on comparing average performance metric values over a set of algorithm instances. When algorithms getting tight in performance gains, the additional consideration of significance of a metric improvement comes into play. However, from this moment the comparison changes from an absolute to a relative mode. Here the implications of this paradigm shift are investigated. Significance relations are formally established. Based on this, a trade-off between increasing cycle-freeness of the relation and small maximum sets can be identified, allowing for the selection of a proper significance level and resulting ranking of a set of algorithms. The procedure is exemplified on the CEC'05 benchmark of real parameter single objective optimization problems. The significance relation here is based on awarding ranking points for relative performance gains, similar to the Borda count voting method or the Wilcoxon signed rank test. In the particular CEC'05 case, five ranks for algorithm performance can be clearly identified.
Simulation-Based Performance Evaluation of Routing Protocols in Vehicular Ad-hoc Network
Venue: arXiv cs.NI 2013
Year: 2013

A Vehicular Ad-hoc Network (VANET) is a collection of wireless vehicle nodes forming a temporary network without using any centralized Road Side Unit (RSU). VANET protocols have to face high challenges due to dynamically changing topologies and symmetric links of networks. A suitable and effective routing mechanism helps to extend the successful deployment of vehicular ad-hoc networks. An attempt has been made to compare the performance of two On-demand reactive routing protocols namely AODV and DSR which works on gateway discovery algorithms and a geographical routing protocol namely GPSR which works on an algorithm constantly geographical based updates network topology information available to all nodes in VANETs for different scenarios. Comparison is made on the basis of different metrics like throughput, packet loss, packet delivery ratio and end-to-end delay using SUMO and NS2 simulator. In this paper we have taken different types of scenarios for simulation and then analysed the performance results.
Increasing Compression Ratio of Low Complexity Compressive Sensing Video Encoder with Application-Aware Configurable Mechanism
Venue: arXiv cs.MM 2013
Year: 2013

With the development of embedded video acquisition nodes and wireless video surveillance systems, traditional video coding methods could not meet the needs of less computing complexity any more, as well as the urgent power consumption. So, a low-complexity compressive sensing video encoder framework with application-aware configurable mechanism is proposed in this paper, where novel encoding methods are exploited based on the practical purposes of the real applications to reduce the coding complexity effectively and improve the compression ratio (CR). Moreover, the group of processing (GOP) size and the measurement matrix size can be configured on the encoder side according to the post-analysis requirements of an application example of object tracking to increase the CR of encoder as best as possible. Simulations show the proposed framework of encoder could achieve 60X of CR when the tracking successful rate (SR) is still keeping above 90%.
Adaptive Measurement-Based Policy-Driven QoS Management with Fuzzy-Rule-based Resource Allocation
Venue: arXiv cs.NI 2013
Year: 2013

Fixed and wireless networks are increasingly converging towards common connectivity with IP-based core networks. Providing effective end-to-end resource and QoS management in such complex heterogeneous converged network scenarios requires unified, adaptive and scalable solutions to integrate and co-ordinate diverse QoS mechanisms of different access technologies with IP-based QoS. Policy-Based Network Management (PBNM) is one approach that could be employed to address this challenge. Hence, a policy-based framework for end-to-end QoS management in converged networks, CNQF (Converged Networks QoS Management Framework) has been proposed within our project. In this paper, the CNQF architecture, a Java implementation of its prototype and experimental validation of key elements are discussed. We then present a fuzzy-based CNQF resource management approach and study the performance of our implementation with real traffic flows on an experimental testbed. The results demonstrate the efficacy of our resource-adaptive approach for practical PBNM systems.
Experiences and Insights from Applying GQM+Strategies in a Systems Product Development Organisation
Venue: arXiv cs.SE 2013
Year: 2013

Aligning software-related activities with corporate strategies and goals is increasingly important for several reasons such as increasing the customer satisfaction in software-based products and services. Several approaches have been proposed to create such an alignment. GQM+Strategies is an approach that applies measurement principles to link goals and strategies on different levels of an organisation. In this paper, we describe experiences from applying GQM+Strategies to elicit, link, and align the goals of an integrated systems product development organisation across multiple organisational levels. We provide insights into how GQM+Strategies was applied during a five- month period. The paper presents the enacted application process and main lessons learnt. In addition, related approaches are described and an outlook on future work is given.
Biometric Signature Processing & Recognition Using Radial Basis Function Network
Venue: arXiv cs.CV 2013
Year: 2013

Automatic recognition of signature is a challenging problem which has received much attention during recent years due to its many applications in different fields. Signature has been used for long time for verification and authentication purpose. Earlier methods were manual but nowadays they are getting digitized. This paper provides an efficient method to signature recognition using Radial Basis Function Network. The network is trained with sample images in database. Feature extraction is performed before using them for training. For testing purpose, an image is made to undergo rotation-translation-scaling correction and then given to network. The network successfully identifies the original image and gives correct output for stored database images also. The method provides recognition rate of approximately 80% for 200 samples.
Image Steganography using Karhunen-Loeve Transform and Least Bit Substitution
Venue: arXiv cs.MM 2013
Year: 2013

As communication channels are increasing in number, reliability of faithful communication is reducing. Hacking and tempering of data are two major issues for which security should be provided by channel. This raises the importance of steganography. In this paper, a novel method to encode the message information inside a carrier image has been described. It uses Karhunen-Loève Transform for compression of data and Least Bit Substitution for data encryption. Compression removes redundancy and thus also provides encoding to a level. It is taken further by means of Least Bit Substitution. The algorithm used for this purpose uses pixel matrix which serves as a best tool to work on. Three different sets of images were used with three different numbers of bits to be substituted by message information. The experimental results show that algorithm is time efficient and provides high data capacity. Further, it can decrypt the original data effectively. Parameters such as carrier error and message error were calculated for each set and were compared for performance analysis.
Une représentation en graphe pour l'enseignement de XML
Venue: arXiv cs.OH 2013
Year: 2013

Currently, XML is a format widely used. In the context of computer science teaching, it is necessary to introduce students to this format and, especially, at its eco-system. We have developed a model to support the teaching of XML. We propose to represent an XML schema as a graph highlighting the structural characteristics of the valide documents. We present in this report different graphic elements of the model and the improvements it brings to data modeling in XML.---XML est un format actuellement très utilisé. Dans le cadre des formations en informatique, il est indispensable d'initier les étudiants à ce format et, surtout, à tout son éco-système. Nous avons donc mis au point un modèle permettant d'appuyer l'enseignement de XML. Ce modèle propose de représenter un schéma XML sous la forme d'un graphe mettant en valeur les caractéristiques structurelles des documents valides. Nous présentons dans ce rapport les différents éléments graphique du modèle et les améliorations qu'il apporte à la modélisation de données en XML.
Symmetric Interconnection Networks from Cubic Crystal Lattices
Venue: arXiv cs.DC 2013
Year: 2013

Torus networks of moderate degree have been widely used in the supercomputer industry. Tori are superb when used for executing applications that require near-neighbor communications. Nevertheless, they are not so good when dealing with global communications. Hence, typical 3D implementations have evolved to 5D networks, among other reasons, to reduce network distances. Most of these big systems are mixed-radix tori which are not the best option for minimizing distances and efficiently using network resources. This paper is focused on improving the topological properties of these networks. By using integral matrices to deal with Cayley graphs over Abelian groups, we have been able to propose and analyze a family of high-dimensional grid-based interconnection networks. As they are built over $n$-dimensional grids that induce a regular tiling of the space, these topologies have been denoted \textsl{lattice graphs}. We will focus on cubic crystal lattices for modeling symmetric 3D networks. Other higher dimensional networks can be composed over these graphs, as illustrated in this research. Easy network partitioning can also take advantage of this network composition operation. Minimal routing algorithms are also provided for these new topologies. Finally, some practical issues such as implementability and preliminary performance evaluations have been addressed.
Spectral Generalized Multi-Dimensional Scaling
Venue: arXiv cs.CG 2013
Year: 2013

Multidimensional scaling (MDS) is a family of methods that embed a given set of points into a simple, usually flat, domain. The points are assumed to be sampled from some metric space, and the mapping attempts to preserve the distances between each pair of points in the set. Distances in the target space can be computed analytically in this setting. Generalized MDS is an extension that allows mapping one metric space into another, that is, multidimensional scaling into target spaces in which distances are evaluated numerically rather than analytically. Here, we propose an efficient approach for computing such mappings between surfaces based on their natural spectral decomposition, where the surfaces are treated as sampled metric-spaces. The resulting spectral-GMDS procedure enables efficient embedding by implicitly incorporating smoothness of the mapping into the problem, thereby substantially reducing the complexity involved in its solution while practically overcoming its non-convex nature. The method is compared to existing techniques that compute dense correspondence between shapes. Numerical experiments of the proposed method demonstrate its efficiency and accuracy compared to state-of-the-art approaches.
A Quantitative Evaluation Framework for Missing Value Imputation Algorithms
Venue: arXiv cs.LG 2013
Year: 2013

We consider the problem of quantitatively evaluating missing value imputation algorithms. Given a dataset with missing values and a choice of several imputation algorithms to fill them in, there is currently no principled way to rank the algorithms using a quantitative metric. We develop a framework based on treating imputation evaluation as a problem of comparing two distributions and show how it can be used to compute quantitative metrics. We present an efficient procedure for applying this framework to practical datasets, demonstrate several metrics derived from the existing literature on comparing distributions, and propose a new metric called Neighborhood-based Dissimilarity Score which is fast to compute and provides similar results. Results are shown on several datasets, metrics, and imputations algorithms.
Applying quantitative semantics to higher-order quantum computing
Venue: arXiv cs.LO 2013
Year: 2013

Finding a denotational semantics for higher order quantum computation is a long-standing problem in the semantics of quantum programming languages. Most past approaches to this problem fell short in one way or another, either limiting the language to an unusably small finitary fragment, or giving up important features of quantum physics such as entanglement. In this paper, we propose a denotational semantics for a quantum lambda calculus with recursion and an infinite data type, using constructions from quantitative semantics of linear logic.
Anatomy of Graph Matching based on an XQuery and RDF Implementation
Venue: arXiv cs.DB 2013
Year: 2013

Graphs are becoming one of the most popular data modeling paradigms since they are able to model complex relationships that cannot be easily captured using traditional data models. One of the major tasks of graph management is graph matching, which aims to find all of the subgraphs in a data graph that match a query graph. In the literature, proposals in this context are classified into two different categories: graph-at-a-time, which process the whole query graph at the same time, and vertex-at-a-time, which process a single vertex of the query graph at the same time. In this paper, we propose a new vertex-at-a-time proposal that is based on graphlets, each of which comprises a vertex of a graph, all of the immediate neighbors of that vertex, and all of the edges that relate those neighbors. Furthermore, we also use the concept of minimum hub covers, each of which comprises a subset of vertices in the query graph that account for all of the edges in that graph. We present the algorithms of our proposal and describe an implementation based on XQuery and RDF. Our evaluation results show that our proposal is appealing to perform graph matching.
Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP
Venue: arXiv cs.CC 2013
Year: 2013

We show that derandomizing polynomial identity testing over an arbitrary finite field implies that NEXP does not have polynomial size boolean circuits. In other words, for any finite field F(q) of size q, $PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where $PIT_q$ is the polynomial identity testing problem over F(q), and NSUBEXP is the nondeterministic subexpoential time class of languages. Our result is in contract to Kabanets and Impagliazzo's existing theorem that derandomizing the polynomial identity testing in the integer ring Z implies that NEXP does have polynomial size boolean circuits or permanent over Z does not have polynomial size arithmetic circuits.
Efficient Runtime Monitoring with Metric Temporal Logic: A Case Study in the Android Operating System
Venue: arXiv cs.LO 2013
Year: 2013

We present a design and an implementation of a security policy specification language based on metric linear-time temporal logic (MTL). MTL features temporal operators that are indexed by time intervals, allowing one to specify timing-dependent security policies. The design of the language is driven by the problem of runtime monitoring of applications in mobile devices. A main case the study is the privilege escalation attack in the Android operating system, where an app gains access to certain resource or functionalities that are not explicitly granted to it by the user, through indirect control flow. To capture these attacks, we extend MTL with recursive definitions, that are used to express call chains betwen apps. We then show how the metric operators of MTL, in combination with recursive definitions, can be used to specify policies to detect privilege escalation, under various fine grained constraints. We present a new algorithm, extending that of linear time temporal logic, for monitoring safety policies written in our specification language. The monitor does not need to store the entire history of events generated by the apps, something that is crucial for practical implementations. We modified the Android OS kernel to allow us to insert our generated monitors modularly. We have tested the modified OS on an actual device, and show that it is effective in detecting policy violations.
Motility at the origin of life: Its characterization and a model
Venue: arXiv cs.AI 2013
Year: 2013

Due to recent advances in synthetic biology and artificial life, the origin of life is currently a hot topic of research. We review the literature and argue that the two traditionally competing "replicator-first" and "metabolism-first" approaches are merging into one integrated theory of individuation and evolution. We contribute to the maturation of this more inclusive approach by highlighting some problematic assumptions that still lead to an impoverished conception of the phenomenon of life. In particular, we argue that the new consensus has so far failed to consider the relevance of intermediate timescales. We propose that an adequate theory of life must account for the fact that all living beings are situated in at least four distinct timescales, which are typically associated with metabolism, motility, development, and evolution. On this view, self-movement, adaptive behavior and morphological changes could have already been present at the origin of life. In order to illustrate this possibility we analyze a minimal model of life-like phenomena, namely of precarious, individuated, dissipative structures that can be found in simple reaction-diffusion systems. Based on our analysis we suggest that processes in intermediate timescales could have already been operative in prebiotic systems. They may have facilitated and constrained changes occurring in the faster- and slower-paced timescales of chemical self-individuation and evolution by natural selection, respectively.
A doubling construction for self-orthogonal codes
Venue: arXiv cs.IT 2013
Year: 2013

A simple construction of quaternary hermitian self-orthogonal codes with parameters $[2n+1,k+1]$ and $[2n+2,k+2]$ from a given pair of self-orthogonal $[n,k]$ codes, and its link to quantum codes is considered. As an application, an optimal quaternary linear $[28,20,6]$ dual containing code is found that yields a new optimal $[[28,12,6]]$ quantum code.
Social Networks and Collective Intelligence: A Return to the Agora
Venue: arXiv cs.SI 2013
Year: 2013

Nowadays, acquisition of trustable information is increasingly important in both professional and private contexts. However, establishing what information is trustable and what is not, is a very challenging task. For example, how can information quality be reliably assessed? How can sources? credibility be fairly assessed? How can gatekeeping processes be found trustworthy when filtering out news and deciding ranking and priorities of traditional media? An Internet-based solution to a human-based ancient issue is being studied, and it is called Polidoxa, from Greek "poly", meaning "many" or "several" and "doxa", meaning "common belief" or "popular opinion". This old problem will be solved by means of ancient philosophies and processes with truly modern tools and technologies. This is why this work required a collaborative and interdisciplinary joint effort from researchers with very different backgrounds and institutes with significantly different agendas. Polidoxa aims at offering: 1) a trust-based search engine algorithm, which exploits stigmergic behaviours of users? network, 2) a trust-based social network, where the notion of trust derives from network activity and 3) a holonic system for bottom-up self-protection and social privacy. By presenting the Polidoxa solution, this work also describes the current state of traditional media as well as newer ones, providing an accurate analysis of major search engines such as Google and social network (e.g., Facebook). The advantages that Polidoxa offers, compared to these, are also clearly detailed and motivated. Finally, a Twitter application (Polidoxa@twitter) which enables experimentation of basic Polidoxa principles is presented.
Performing edge detection by difference of Gaussians using q-Gaussian kernels
Venue: arXiv cs.CV 2013
Year: 2013

In image processing, edge detection is a valuable tool to perform the extraction of features from an image. This detection reduces the amount of information to be processed, since the redundant information (considered less relevant) can be unconsidered. The technique of edge detection consists of determining the points of a digital image whose intensity changes sharply. This changes are due to the discontinuities of the orientation on a surface for example. A well known method of edge detection is the Difference of Gaussians (DoG). The method consists of subtracting two Gaussians, where a kernel has a standard deviation smaller than the previous one. The convolution between the subtraction of kernels and the input image results in the edge detection of this image. This paper introduces a method of extracting edges using DoG with kernels based on the q-Gaussian probability distribution, derived from the q-statistic proposed by Constantino Tsallis. To demonstrate the method's potential, we compare the introduced method with the traditional DoG using Gaussians kernels. The results showed that the proposed method can extract edges with more accurate details.
Primal Beats Dual on Online Packing LPs in the Random-Order Model
Venue: arXiv cs.DS 2013
Year: 2013

We study packing LPs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a $1-O(\sqrt{(\log{d})/B})$-competitive online algorithm, where $d$ denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and $B$ denotes the capacity ratio $B$, i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a $(1 - ε)$-approximation if the capacity ratio satisfies $B=Ω((\log d)/ε^2)$, which is known to be best-possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources. Instead, it simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio: We prove an upper bound on the competitive ratio of $Ω(d^{-1/(B-1)})$, for any $B \ge 2$. In addition, we show that our approach can be combined with VCG payments and obtain an incentive compatible $(1-ε)$-competitive mechanism for packing LPs with $B=Ω((\log m)/ε^2)$, where $m$ is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online algorithm with competitive ratio $O(1)$.