OpenRaiser/Intern-Atlas huggingface dataset:
Open Cores for Digital Signal Processing
Venue: arXiv cs.AR 2014
Year: 2014

This paper presents the design and implementation of three System on Chip (SoC) cores, which implement the Digital Signal Processing (DSP) functions: Finite Impulse Response (FIR) filter, Infinite Impulse Response (IIR) filter and Fast Fourier Transform (FFT). The FIR filter core is based on the symmetrical realization form, the IIR filter core is based on the Second Order Sections (SOS) architecture and the FFT core is based on the Radix $2^2$ Single Delay Feedback (R$2^2$SDF) architecture. The three cores are compatible with the Wishbone SoC bus and they were described using generic and structural VHDL. In system hardware verification was performed by using an OpenRisc-based SoC synthesized on an Altera FPGA, the tests showed that the designed DSP cores are suitable for building SoC based on the OpenRisc processor and the Wishbone bus.
Multi-Agent Distributed Optimization via Inexact Consensus ADMM
Venue: arXiv cs.SY 2014
Year: 2014

Multi-agent distributed consensus optimization problems arise in many signal processing applications. Recently, the alternating direction method of multipliers (ADMM) has been used for solving this family of problems. ADMM based distributed optimization method is shown to have faster convergence rate compared with classic methods based on consensus subgradient, but can be computationally expensive, especially for problems with complicated structures or large dimensions. In this paper, we propose low-complexity algorithms that can reduce the overall computational cost of consensus ADMM by an order of magnitude for certain large-scale problems. Central to the proposed algorithms is the use of an inexact step for each ADMM update, which enables the agents to perform cheap computation at each iteration. Our convergence analyses show that the proposed methods converge well under some convexity assumptions. Numerical results show that the proposed algorithms offer considerably lower computational complexity than the standard ADMM based distributed optimization methods.
The Complexity of Repairing, Adjusting, and Aggregating of Extensions in Abstract Argumentation
Venue: arXiv cs.DS 2014
Year: 2014

We study the computational complexity of problems that arise in abstract argumentation in the context of dynamic argumentation, minimal change, and aggregation. In particular, we consider the following problems where always an argumentation framework F and a small positive integer k are given. - The Repair problem asks whether a given set of arguments can be modified into an extension by at most k elementary changes (i.e., the extension is of distance k from the given set). - The Adjust problem asks whether a given extension can be modified by at most k elementary changes into an extension that contains a specified argument. - The Center problem asks whether, given two extensions of distance k, whether there is a "center" extension that is a distance at most (k-1) from both given extensions. We study these problems in the framework of parameterized complexity, and take the distance k as the parameter. Our results covers several different semantics, including admissible, complete, preferred, semi-stable and stable semantics.
Differential Privacy in Metric Spaces: Numerical, Categorical and Functional Data Under the One Roof
Venue: arXiv cs.DB 2014
Year: 2014

We study Differential Privacy in the abstract setting of Probability on metric spaces. Numerical, categorical and functional data can be handled in a uniform manner in this setting. We demonstrate how mechanisms based on data sanitisation and those that rely on adding noise to query responses fit within this framework. We prove that once the sanitisation is differentially private, then so is the query response for any query. We show how to construct sanitisations for high-dimensional databases using simple 1-dimensional mechanisms. We also provide lower bounds on the expected error for differentially private sanitisations in the general metric space setting. Finally, we consider the question of sufficient sets for differential privacy and show that for relaxed differential privacy, any algebra generating the Borel $σ$-algebra is a sufficient set for relaxed differential privacy.
Improving Collaborative Filtering based Recommenders using Topic Modelling
Venue: arXiv cs.IR 2014
Year: 2014

Standard Collaborative Filtering (CF) algorithms make use of interactions between users and items in the form of implicit or explicit ratings alone for generating recommendations. Similarity among users or items is calculated purely based on rating overlap in this case,without considering explicit properties of users or items involved, limiting their applicability in domains with very sparse rating spaces. In many domains such as movies, news or electronic commerce recommenders, considerable contextual data in text form describing item properties is available along with the rating data, which could be utilized to improve recommendation quality.In this paper, we propose a novel approach to improve standard CF based recommenders by utilizing latent Dirichlet allocation (LDA) to learn latent properties of items, expressed in terms of topic proportions, derived from their textual description. We infer user's topic preferences or persona in the same latent space,based on her historical ratings. While computing similarity between users, we make use of a combined similarity measure involving rating overlap as well as similarity in the latent topic space. This approach alleviates sparsity problem as it allows calculation of similarity between users even if they have not rated any items in common. Our experiments on multiple public datasets indicate that the proposed hybrid approach significantly outperforms standard user Based and item Based CF recommenders in terms of classification accuracy metrics such as precision, recall and f-measure.
Globally Optimal Cooperation in Dense Cognitive Radio Networks
Venue: arXiv cs.NI 2014
Year: 2014

The problem of calculating the local and global decision thresholds in hard decisions based cooperative spectrum sensing is well known for its mathematical intractability. Previous work relied on simple suboptimal counting rules for decision fusion in order to avoid the exhaustive numerical search required for obtaining the optimal thresholds. However, these simple rules are not globally optimal as they do not maximize the overall global detection probability by jointly selecting local and global thresholds. Instead, they maximize the detection probability for a specific global threshold. In this paper, a globally optimal decision fusion rule for Primary User signal detection based on the Neyman- Pearson (NP) criterion is derived. The algorithm is based on a novel representation for the global performance metrics in terms of the regularized incomplete beta function. Based on this mathematical representation, it is shown that the globally optimal NP hard decision fusion test can be put in the form of a conventional one dimensional convex optimization problem. A binary search for the global threshold can be applied yielding a complexity of O(log2(N)), where N represents the number of cooperating users. The logarithmic complexity is appreciated because we are concerned with dense networks, and thus N is expected to be large. The proposed optimal scheme outperforms conventional counting rules, such as the OR, AND, and MAJORITY rules. It is shown via simulations that, although the optimal rule tends to the simple OR rule when the number of cooperating secondary users is small, it offers significant SNR gain in dense cognitive radio networks with large number of cooperating users.
A categorization scheme for socialbot attacks in online social networks
Venue: arXiv cs.SI 2014
Year: 2014

In the past, online social networks (OSN) like Facebook and Twitter became powerful instruments for communication and networking. Unfortunately, they have also become a welcome target for socialbot attacks. Therefore, a deep understanding of the nature of such attacks is important to protect the Eco-System of OSNs. In this extended abstract we propose a categorization scheme of social bot attacks that aims at providing an overview of the state of the art of techniques in this emerging field. Finally, we demonstrate the usefulness of our categorization scheme by characterizing recent socialbot attacks according to our categorization scheme.
Active spline model: A shape based model-interactive segmentation
Venue: arXiv cs.CV 2014
Year: 2014

Rarely in literature a method of segmentation cares for the edit after the algorithm delivers. They provide no solution when segmentation goes wrong. We propose to formulate point distribution model in terms of centripetal-parameterized Catmull-Rom spline. Such fusion brings interactivity to model-based segmentation, so that edit is better handled. When the delivered segment is unsatisfactory, user simply shifts points to vary the curve. We ran the method on three disparate imaging modalities and achieved an average overlap of 0.879 for automated lung segmentation on chest radiographs. The edit afterward improved the average overlap to 0.945, with a minimum of 0.925. The source code and the demo video are available at http://wp.me/p3vCKy-2S
Formal verification of a software countermeasure against instruction skip attacks
Venue: arXiv cs.CR 2014
Year: 2014

Fault attacks against embedded circuits enabled to define many new attack paths against secure circuits. Every attack path relies on a specific fault model which defines the type of faults that the attacker can perform. On embedded processors, a fault model consisting in an assembly instruction skip can be very useful for an attacker and has been obtained by using several fault injection means. To avoid this threat, some countermeasure schemes which rely on temporal redundancy have been proposed. Nevertheless, double fault injection in a long enough time interval is practical and can bypass those countermeasure schemes. Some fine-grained countermeasure schemes have also been proposed for specific instructions. However, to the best of our knowledge, no approach that enables to secure a generic assembly program in order to make it fault-tolerant to instruction skip attacks has been formally proven yet. In this paper, we provide a fault-tolerant replacement sequence for almost all the instructions of the Thumb-2 instruction set and provide a formal verification for this fault tolerance. This simple transformation enables to add a reasonably good security level to an embedded program and makes practical fault injection attacks much harder to achieve.
A comparative analysis of the statistical properties of large mobile phone calling networks
Venue: arXiv cs.SI 2014
Year: 2014

Mobile phone calling is one of the most widely used communication methods in modern society. The records of calls among mobile phone users provide us a valuable proxy for the understanding of human communication patterns embedded in social networks. Mobile phone users call each other forming a directed calling network. If only reciprocal calls are considered, we obtain an undirected mutual calling network. The preferential communication behavior between two connected users can be statistically tested and it results in two Bonferroni networks with statistically validated edges. We perform a comparative analysis of the statistical properties of these four networks, which are constructed from the calling records of more than nine million individuals in Shanghai over a period of 110 days. We find that these networks share many common structural properties and also exhibit idiosyncratic features when compared with previously studied large mobile calling networks. The empirical findings provide us an intriguing picture of a representative large social network that might shed new lights on the modelling of large social networks.
A Novel Method for the Recognition of Isolated Handwritten Arabic Characters
Venue: arXiv cs.CV 2014
Year: 2014

There are many difficulties facing a handwritten Arabic recognition system such as unlimited variation in human handwriting, similarities of distinct character shapes, interconnections of neighbouring characters and their position in the word. The typical Optical Character Recognition (OCR) systems are based mainly on three stages, preprocessing, features extraction and recognition. This paper proposes new methods for handwritten Arabic character recognition which is based on novel preprocessing operations including different kinds of noise removal also different kind of features like structural, Statistical and Morphological features from the main body of the character and also from the secondary components. Evaluation of the accuracy of the selected features is made. The system was trained and tested by back propagation neural network with CENPRMI dataset. The proposed algorithm obtained promising results as it is able to recognize 88% of our test set accurately. In Comparable with other related works we find that our result is the highest among other published works.
CRISTAL-ISE : Provenance Applied in Industry
Venue: arXiv cs.DB 2014
Year: 2014

This paper presents the CRISTAL-iSE project as a framework for the management of provenance information in industry. The project itself is a research collaboration between academia and industry. A key factor in the project is the use of a system known as CRISTAL which is a mature system based on proven description driven principles. A crucial element in the description driven approach is that the fact that objects (Items) are described at runtime enabling managed systems to be both dynamic and flexible. Another factor is the notion that all Items in CRISTAL are stored and versioned, therefore enabling a provenance collection system. In this paper a concrete application, called Agilium, is briefly described and a future application CIMAG-RA is presented which will harness the power of both CRISTAL and Agilium.
Zenoness for Timed Pushdown Automata
Venue: arXiv cs.FL 2014
Year: 2014

Timed pushdown automata are pushdown automata extended with a finite set of real-valued clocks. Additionaly, each symbol in the stack is equipped with a value representing its age. The enabledness of a transition may depend on the values of the clocks and the age of the topmost symbol. Therefore, dense-timed pushdown automata subsume both pushdown automata and timed automata. We have previously shown that the reachability problem for this model is decidable. In this paper, we study the zenoness problem and show that it is EXPTIME-complete.
Information Evolution in Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Social networks readily transmit information, albeit with less than perfect fidelity. We present a large-scale measurement of this imperfect information copying mechanism by examining the dissemination and evolution of thousands of memes, collectively replicated hundreds of millions of times in the online social network Facebook. The information undergoes an evolutionary process that exhibits several regularities. A meme's mutation rate characterizes the population distribution of its variants, in accordance with the Yule process. Variants further apart in the diffusion cascade have greater edit distance, as would be expected in an iterative, imperfect replication process. Some text sequences can confer a replicative advantage; these sequences are abundant and transfer "laterally" between different memes. Subpopulations of the social network can preferentially transmit a specific variant of a meme if the variant matches their beliefs or culture. Understanding the mechanism driving change in diffusing information has important implications for how we interpret and harness the information that reaches us through our social networks.
Trellis-Extended Codebooks and Successive Phase Adjustment: A Path from LTE-Advanced to FDD Massive MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

It is of great interest to develop efficient ways to acquire accurate channel state information (CSI) for frequency division duplexing (FDD) massive multiple-input multiple-output (MIMO) systems for backward compatibility. It is theoretically well known that the codebook size for CSI quantization should be increased as the number of transmit antennas becomes larger, and 3GPP long term evolution (LTE) and LTE-Advanced codebooks also follow this trend. Thus, in massive MIMO, it is hard to apply the conventional approach of using pre-defined vector-quantized codebooks for CSI quantization mainly because of codeword search complexity. In this paper, we propose a trellis-extended codebook (TEC) that can be easily harmonized with current wireless standards such as LTE or LTE-Advanced by extending standardized codebooks designed for 2, 4, or 8 antennas with trellis structures. TEC exploits a Viterbi decoder and convolutional encoder in channel coding as the CSI quantizer and the CSI reconstructer, respectively. By quantizing multiple channel entries simultaneously using standardized codebooks in a state transition of trellis search, TEC can achieve fractional bits per channel entry quantization to have a practical feedback overhead. Thus, TEC can solve both the complexity and the feedback overhead issues of CSI quantization in massive MIMO systems. We also develop trellis-extended successive phase adjustment (TE-SPA) which works as a differential codebook of TEC. This is similar to the dual codebook concept of LTE-Advanced. TE-SPA can reduce CSI quantization error even with lower feedback overhead in temporally correlated channels. Numerical results verify the effectiveness of the proposed schemes in FDD massive MIMO systems.
Spatial Design of Physical Network Robust against Earthquakes
Venue: arXiv cs.NI 2014
Year: 2014

This paper analyzes the survivability of a physical network against earthquakes and proposes spatial network design rules to make a network robust against earthquakes. The disaster area model used is fairly generic and bounded. The proposed design rules for physical networks include: (i) a shorter zigzag route can reduce the probability that a network intersects a disaster area, (ii) an additive performance metric, such as repair cost, is independent of the network shape if the route length is fixed, and (iii) additional routes within a ring network does not decrease the probability that all the routes between a given pair of nodes intersect the disaster area, but a wider detour route decreases it. Formulas for evaluating the probability of disconnecting two given nodes are also derived. An optimal server placement is shown as an application of the theoretical results. These analysis results are validated through empirical earthquake data.
Applications of Structural Balance in Signed Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

We present measures, models and link prediction algorithms based on the structural balance in signed social networks. Certain social networks contain, in addition to the usual 'friend' links, 'enemy' links. These networks are called signed social networks. A classical and major concept for signed social networks is that of structural balance, i.e., the tendency of triangles to be 'balanced' towards including an even number of negative edges, such as friend-friend-friend and friend-enemy-enemy triangles. In this article, we introduce several new signed network analysis methods that exploit structural balance for measuring partial balance, for finding communities of people based on balance, for drawing signed social networks, and for solving the problem of link prediction. Notably, the introduced methods are based on the signed graph Laplacian and on the concept of signed resistance distances. We evaluate our methods on a collection of four signed social network datasets.
CriPS: Critical Dynamics in Particle Swarm Optimization
Venue: arXiv cs.NE 2014
Year: 2014

Particle Swarm Optimisation (PSO) makes use of a dynamical system for solving a search task. Instead of adding search biases in order to improve performance in certain problems, we aim to remove algorithm-induced scales by controlling the swarm with a mechanism that is scale-free except possibly for a suppression of scales beyond the system size. In this way a very promising performance is achieved due to the balance of large-scale exploration and local search. The resulting algorithm shows evidence for self-organised criticality, brought about via the intrinsic dynamics of the swarm as it interacts with the objective function, rather than being explicitly specified. The Critical Particle Swarm (CriPS) can be easily combined with many existing extensions such as chaotic exploration, additional force terms or non-trivial topologies.
Sequential Complexity as a Descriptor for Musical Similarity
Venue: arXiv cs.IR 2014
Year: 2014

We propose string compressibility as a descriptor of temporal structure in audio, for the purpose of determining musical similarity. Our descriptors are based on computing track-wise compression rates of quantised audio features, using multiple temporal resolutions and quantisation granularities. To verify that our descriptors capture musically relevant information, we incorporate our descriptors into similarity rating prediction and song year prediction tasks. We base our evaluation on a dataset of 15500 track excerpts of Western popular music, for which we obtain 7800 web-sourced pairwise similarity ratings. To assess the agreement among similarity ratings, we perform an evaluation under controlled conditions, obtaining a rank correlation of 0.33 between intersected sets of ratings. Combined with bag-of-features descriptors, we obtain performance gains of 31.1% and 10.9% for similarity rating prediction and song year prediction. For both tasks, analysis of selected descriptors reveals that representing features at multiple time scales benefits prediction accuracy.
Tools for dynamics simulation of robots: a survey based on user feedback
Venue: arXiv cs.RO 2014
Year: 2014

The number of tools for dynamics simulation has grown in the last years. It is necessary for the robotics community to have elements to ponder which of the available tools is the best for their research. As a complement to an objective and quantitative comparison, difficult to obtain since not all the tools are open-source, an element of evaluation is user feedback. With this goal in mind, we created an online survey about the use of dynamical simulation in robotics. This paper reports the analysis of the participants' answers and a descriptive information fiche for the most relevant tools. We believe this report will be helpful for roboticists to choose the best simulation tool for their researches.
Classifying the Clique-Width of $H$-Free Bipartite Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Let $G$ be a bipartite graph, and let $H$ be a bipartite graph with a fixed bipartition $(B_H,W_H)$. We consider three different, natural ways of forbidding $H$ as an induced subgraph in $G$. First, $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Second, $G$ is strongly $H$-free if $G$ is $H$-free or else has no bipartition $(B_G,W_G)$ with $B_H\subseteq B_G$ and $W_H\subseteq W_G$. Third, $G$ is weakly $H$-free if $G$ is $H$-free or else has at least one bipartition $(B_G,W_G)$ with $B_H\not\subseteq B_G$ or $W_H\not\subseteq W_G$. Lozin and Volz characterized all bipartite graphs $H$ for which the class of strongly $H$-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of $H$-freeness.