OpenRaiser/Intern-Atlas huggingface dataset:
Inference on the Network Evolution in BitTorrent Mainline DHT
Venue: arXiv cs.NI 2014
Year: 2014

Network size is a fundamental statistic for a peer-to-peer system but is generally considered to contain too little information to be useful. However, most existing work only considers the metric by itself and does not explore what features could be extracted from this seem- ingly trivial metric. In this paper, we show that Fourier transform allows us to extract frequency features from such time series data, which can further be used to characterize user behaviors and detect system anoma- lies in a peer-to-peer system automatically without needing to resort to visual comparisons. By using the proposed algorithm, our system suc- cessfully discovers and clusters countries of similar user behavior and captures the anomalies like Sybil attacks and other real-world events with high accuracy. Our work in this paper highlights the usefulness of more advanced time series processing techniques in analyzing network measurements.
Color image quality assessment measure using multivariate generalized Gaussian distribution
Venue: arXiv cs.CV 2014
Year: 2014

This paper deals with color image quality assessment in the reduced-reference framework based on natural scenes statistics. In this context, we propose to model the statistics of the steerable pyramid coefficients by a Multivariate Generalized Gaussian distribution (MGGD). This model allows taking into account the high correlation between the components of the RGB color space. For each selected scale and orientation, we extract a parameter matrix from the three color components subbands. In order to quantify the visual degradation, we use a closed-form of Kullback-Leibler Divergence (KLD) between two MGGDs. Using "TID 2008" benchmark, the proposed measure has been compared with the most influential methods according to the FRTV1 VQEG framework. Results demonstrates its effectiveness for a great variety of distortion type. Among other benefits this measure uses only very little information about the original image.
Heuristic for Network Coverage Optimization Applied in Finding Organizational Change Agents
Venue: arXiv cs.SI 2014
Year: 2014

Authors compare different ways of selecting change agents within network analysis paradigm and propose a new algorithm of doing so. All methods are evaluated against network coverage measure that calculates how many network members can be directly reached by selected nodes. Results from the analysis of organizational network show that compared to other methods the proposed algorithm provides better network coverage, at the same time selecting change agents that are well connected, influential opinion leaders.
Seeding the Initial Population of Multi-Objective Evolutionary Algorithms: A Computational Study
Venue: arXiv cs.NE 2014
Year: 2014

Most experimental studies initialize the population of evolutionary algorithms with random genotypes. In practice, however, optimizers are typically seeded with good candidate solutions either previously known or created according to some problem-specific method. This "seeding" has been studied extensively for single-objective problems. For multi-objective problems, however, very little literature is available on the approaches to seeding and their individual benefits and disadvantages. In this article, we are trying to narrow this gap via a comprehensive computational study on common real-valued test functions. We investigate the effect of two seeding techniques for five algorithms on 48 optimization problems with 2, 3, 4, 6, and 8 objectives. We observe that some functions (e.g., DTLZ4 and the LZ family) benefit significantly from seeding, while others (e.g., WFG) profit less. The advantage of seeding also depends on the examined algorithm.
Node Failure Time and Coverage Loss Time Analysis for Maximum Stability Vs Minimum Distance Spanning Tree based Data Gathering in Mobile Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

A mobile sensor network is a wireless network of sensor nodes that move arbitrarily. In this paper, we explore the use of a maximum stability spanning tree-based data gathering (Max.Stability-DG) algorithm and a minimum-distance spanning tree-based data gathering (MST-DG) algorithm for mobile sensor networks. We analyze the impact of these two algorithms on the node failure times and the resulting coverage loss due to node failures. Both the Max.Stability-DG and MST-DG algorithms are based on a greedy strategy of determining a data gathering tree when one is needed and using that tree as long as it exists. The Max.Stability-DG algorithm assumes the availability of the complete knowledge of future topology changes and determines a data gathering tree whose corresponding spanning tree would exist for the longest time since the current time instant; whereas, the MST-DG algorithm determines a data gathering tree whose corresponding spanning tree is the minimum distance tree at the current time instant. We observe the Max.Stability-DG trees to incur a longer network lifetime (time of disconnection of the network of live sensor nodes due to node failures), a larger coverage loss time for a particular fraction of loss of coverage as well as a lower fraction of coverage loss at any time. The tradeoff is that the Max.Stability-DG trees incur a lower node lifetime (the time of first node failure) due to repeated use of a data gathering tree for a longer time.
Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
Venue: arXiv cs.CC 2014
Year: 2014

In this paper, we will show dichotomy theorems for the computation of polynomials corresponding to evaluation of graph homomorphisms in Valiant's model. We are given a fixed graph $H$ and want to find all graphs, from some graph class, homomorphic to this $H$. These graphs will be encoded by a family of polynomials. We give dichotomies for the polynomials for cycles, cliques, trees, outerplanar graphs, planar graphs and graphs of bounded genus.
Group Discounts Compatible with Buyer Privacy
Venue: arXiv cs.CR 2014
Year: 2014

We show how group discounts can be offered without forcing buyers to surrender their anonymity, as long as buyers can use their own computing devices (e.g. smartphone, tablet or computer) to perform a purchase. Specifically, we present a protocol for privacy-preserving group discounts. The protocol allows a group of buyers to prove how many they are without disclosing their identities. Coupled with an anonymous payment system, this makes group discounts compatible with buyer privacy (that is, buyer anonymity).
On Streaming String Transducers and HDT0L Systems
Venue: arXiv cs.FL 2014
Year: 2014

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. Cerny in 2010 as a one-way deterministic automata model to define transformations of finite strings. Copyless SST extend deterministic finite state automata with a set of registers in which to store intermediate output strings, and those registers can be combined and updated all along the run, in a linear manner, i.e., no register content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string transformations, as defined by B. Courcelle, and are equi-expressive to deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decidable equivalence problem (in PSpace). In this paper, we show that they still have decidable equivalence problem even without the copyless restriction. The proof reduces to the HDT0L sequence equivalence problem, which is known to be decidable. We also show that this latter problem is as difficult as the SST equivalence problem, modulo linear time reduction.
Strategic deployment in graphs
Venue: arXiv cs.DS 2014
Year: 2014

Conquerors of old (like, e.g., Alexander the Great or Ceasar) had to solve the following deployment problem. Sufficiently strong units had to be stationed at locations of strategic importance, and the moving forces had to be strong enough to advance to the next location. To the best of our knowledge we are the first to consider the (off-line) graph version of this problem. While being NP-hard for general graphs, for trees the minimum number of agents and an optimal deployment can be computed in optimal polynomial time. Moreover, the optimal solution for the minimum spanning tree of an arbitrary graph G results in a 2-approximation of the optimal solution for G.
Computationally-efficient stochastic cluster dynamics method for modeling damage accumulation in irradiated materials
Venue: arXiv cs.DS 2014
Year: 2014

An improved version of a recently developed stochastic cluster dynamics (SCD) method {[}Marian, J. and Bulatov, V. V., {\it J. Nucl. Mater.} \textbf{415} (2014) 84-95{]} is introduced as an alternative to rate theory (RT) methods for solving coupled ordinary differential equation (ODE) systems for irradiation damage simulations. SCD circumvents by design the curse of dimensionality of the variable space that renders traditional ODE-based RT approaches inefficient when handling complex defect population comprised of multiple (more than two) defect species. Several improvements introduced here enable efficient and accurate simulations of irradiated materials up to realistic (high) damage doses characteristic of next-generation nuclear systems. The first improvement is a procedure for efficiently updating the defect reaction-network and event selection in the context of a dynamically expanding reaction-network. Next is a novel implementation of the $τ$-leaping method that speeds up SCD simulations by advancing the state of the reaction network in large time increments when appropriate. Lastly, a volume rescaling procedure is introduced to control the computational complexity of the expanding reaction-network through occasional reductions of the defect population while maintaining accurate statistics. The enhanced SCD method is then applied to model defect cluster accumulation in iron thin films subjected to triple ion-beam ($\text{Fe}^{3+}$, $\text{He}^{+}$ and $ $$\text{H\ensuremath{{}^{+}}}$$ $) irradiations, for which standard RT or spatially-resolved kinetic Monte Carlo simulations are prohibitively expensive.
The Emptiness Problem for Tree Automata with at Least One Disequality Constraint is NP-hard
Venue: arXiv cs.FL 2014
Year: 2014

The model of tree automata with equality and disequality constraints was introduced in 2007 by Filiot, Talbot and Tison. In this paper we show that if there is at least one disequality constraint, the emptiness problem is NP-hard.
Optimizing user selection schemes in vector broadcast channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we focus on the ergodic downlink sum-rate performance of a system consisting of a set of heterogeneous users. We study three user selection schemes to group near-orthogonal users for simultaneous transmission. The first scheme is a random selection policy that achieves fairness, but does not exploit multi-user diversity. The second scheme is a greedy selection policy that fully exploits multi-user diversity, but does not achieve fairness, and the third scheme achieves fairness while partially exploiting multi-user diversity. We also consider two beamforming methods for data transmission, namely, maximum-ratio transmission and zero-forcing beamforming. In all scheduling schemes studied in the paper, there is a key parameter that controls the degrees of orthogonality of channel directions between co-scheduled users. We focus on optimally setting this parameter for each scheduling scheme such that the ergodic downlink sum-rate is maximized. To this end, we derive analytical expressions for the ergodic downlink sum-rate considering each scheduling scheme. Numerical results are also presented to provide further insights.
Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
Venue: arXiv cs.GT 2014
Year: 2014

Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowledge, the last remaining open problem of this sort is the following; it was stated by Papadimitriou in 2007: find a non-symmetric Nash equilibrium (NE) in a symmetric game. We show that this problem is NP-complete and the problem of counting the number of non-symmetric NE in a symmetric game is #P-complete. In 2005, Kannan and Theobald defined the "rank of a bimatrix game" represented by matrices (A, B) to be rank(A+B) and asked whether a NE can be computed in rank 1 games in polynomial time. Observe that the rank 0 case is precisely the zero sum case, for which a polynomial time algorithm follows from von Neumann's reduction of such games to linear programming. In 2011, Adsul et. al. obtained an algorithm for rank 1 games; however, it does not solve the case of symmetric rank 1 games. We resolve this problem.
Easy Hyperparameter Search Using Optunity
Venue: arXiv cs.LG 2014
Year: 2014

Optunity is a free software package dedicated to hyperparameter optimization. It contains various types of solvers, ranging from undirected methods to direct search, particle swarm and evolutionary optimization. The design focuses on ease of use, flexibility, code clarity and interoperability with existing software in all machine learning environments. Optunity is written in Python and contains interfaces to environments such as R and MATLAB. Optunity uses a BSD license and is freely available online at http://www.optunity.net.
IPMACC: Open Source OpenACC to CUDA/OpenCL Translator
Venue: arXiv cs.PL 2014
Year: 2014

In this paper we introduce IPMACC, a framework for translating OpenACC applications to CUDA or OpenCL. IPMACC is composed of set of translators translating OpenACC for C applications to CUDA or OpenCL. The framework uses the system compiler (e.g. nvcc) for generating final accelerator's binary. The framework can be used for extending the OpenACC API, executing OpenACC applications, or obtaining CUDA or OpenCL code which is equivalent to OpenACC code. We verify correctness of our framework under several benchmarks included from Rodinia Benchmark Suit and CUDA SDK. We also compare the performance of CUDA version of the benchmarks to OpenACC version which is compiled by our framework. By comparing CUDA and OpenACC versions, we discuss the limitations of OpenACC in achieving a performance near to highly-optimized CUDA version.
Detector Discovery in the Wild: Joint Multiple Instance and Representation Learning
Venue: arXiv cs.CV 2014
Year: 2014

We develop methods for detector learning which exploit joint training over both weak and strong labels and which transfer learned perceptual representations from strongly-labeled auxiliary tasks. Previous methods for weak-label learning often learn detector models independently using latent variable optimization, but fail to share deep representation knowledge across classes and usually require strong initialization. Other previous methods transfer deep representations from domains with strong labels to those with only weak labels, but do not optimize over individual latent boxes, and thus may miss specific salient structures for a particular category. We propose a model that subsumes these previous approaches, and simultaneously trains a representation and detectors for categories with either weak or strong labels present. We provide a novel formulation of a joint multiple instance learning method that includes examples from classification-style data when available, and also performs domain transfer learning to improve the underlying detector representation. Our model outperforms known methods on ImageNet-200 detection with weak labels.
Sphynx: A Shared Instruction Cache Exporatory Study
Venue: arXiv cs.AR 2014
Year: 2014

The Sphynx project was an exploratory study to discover what might be done to improve the heavy replication of in- structions in independent instruction caches for a massively parallel machine where a single program is executing across all of the cores. While a machine with only many cores (fewer than 50) might not have any issues replicating the instructions for each core, as we approach the era where thousands of cores can be placed on one chip, the overhead of instruction replication may become unacceptably large. We believe that a large amount of sharing should be possible when the ma- chine is configured for all of the threads to issue from the same set of instructions. We propose a technique that allows sharing an instruction cache among a number of independent processor cores to allow for inter-thread sharing and reuse of instruction memory. While we do not have test cases to demonstrate the potential magnitude of performance gains that could be achieved, the potential for sharing reduces the die area required for instruction storage on chip.
An Implementation Framework (IF) for the National Information Assurance and Cyber Security Strategy (NIACSS) of Jordan
Venue: arXiv cs.SE 2014
Year: 2014

This paper proposes an implementation framework that lays out the ground for a coherent, systematic, and comprehensive approach to implement the National Information Assurance and Cyber Security Strategy (NIACSS) of Jordan. The Framework 1). Suggests a methodology to analyze the NIACSS, 2). Illustrates how the NIACSS analysis can be utilized to design strategic moves and develop an appropriate functional structure, and 3). proposes a set of adaptable strategic controls that govern the NIACSS implementation and allow achieving excellence, innovation, efficiency, and quality.The framework, if adopted, is expected to harvest several advantages within the following areas: information security implementation management, control and guidance, efforts consolidation, resource utilization, productive collaboration, and completeness. The framework is flexible and expandable; therefore, it can be generalized.
Horn Clauses for Communicating Timed Systems
Venue: arXiv cs.LO 2014
Year: 2014

Languages based on the theory of timed automata are a well established approach for modelling and analysing real-time systems, with many applications both in industrial and academic context. Model checking for timed automata has been studied extensively during the last two decades; however, even now industrial-grade model checkers are available only for few timed automata dialects (in particular Uppaal timed automata), exhibit limited scalability for systems with large discrete state space, or cannot handle parametrised systems. We explore the use of Horn constraints and off-the-shelf model checkers for analysis of networks of timed automata. The resulting analysis method is fully symbolic and applicable to systems with large or infinite discrete state space, and can be extended to include various language features, for instance Uppaal-style communication/broadcast channels and BIP-style interactions, and systems with infinite parallelism. Experiments demonstrate the feasibility of the method.
Runtime Verification Through Forward Chaining
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we present a novel rule-based approach for Runtime Verification of FLTL properties over finite but expanding traces. Our system exploits Horn clauses in implication form and relies on a forward chaining-based monitoring algorithm. This approach avoids the branching structure and exponential complexity typical of tableaux-based formulations, creating monitors with a single state and a fixed number of rules. This allows for a fast and scalable tool for Runtime Verification: we present the technical details together with a working implementation.
The domination number of on-line social networks and random geometric graphs
Venue: arXiv cs.SI 2014
Year: 2014

We consider the domination number for on-line social networks, both in a stochastic network model, and for real-world, networked data. Asymptotic sublinear bounds are rigorously derived for the domination number of graphs generated by the memoryless geometric protean random graph model. We establish sublinear bounds for the domination number of graphs in the Facebook 100 data set, and these bounds are well-correlated with those predicted by the stochastic model. In addition, we derive the asymptotic value of the domination number in classical random geometric graphs.
Gradient Boundary Histograms for Action Recognition
Venue: arXiv cs.CV 2014
Year: 2014

This paper introduces a high efficient local spatiotemporal descriptor, called gradient boundary histograms (GBH). The proposed GBH descriptor is built on simple spatio-temporal gradients, which are fast to compute. We demonstrate that it can better represent local structure and motion than other gradient-based descriptors, and significantly outperforms them on large realistic datasets. A comprehensive evaluation shows that the recognition accuracy is preserved while the spatial resolution is greatly reduced, which yields both high efficiency and low memory usage.
Enjeux et propositions sur les architectures RF pour l'homme connecté à la société numérique
Venue: arXiv cs.NI 2014
Year: 2014

This article presents an overview of the challenges of increasing development of wireless links to enable a more consistent and transparent interconnection between people and the digital world. These issues are in the domain of high performance architectures for conventional applications of wireless Internet, but also in the field of sensor networks and connected objects. Beyond the constraints of the various applications push to develop architectures with high digital capabilities like software defined radio. In each of these categories, examples of approaches proposed by INRIA Socrate team are presented.
Studying and Modeling the Connection between People's Preferences and Content Sharing
Venue: arXiv cs.HC 2014
Year: 2014

People regularly share items using online social media. However, people's decisions around sharing---who shares what to whom and why---are not well understood. We present a user study involving 87 pairs of Facebook users to understand how people make their sharing decisions. We find that even when sharing to a specific individual, people's own preference for an item (individuation) dominates over the recipient's preferences (altruism). People's open-ended responses about how they share, however, indicate that they do try to personalize shares based on the recipient. To explain these contrasting results, we propose a novel process model of sharing that takes into account people's preferences and the salience of an item. We also present encouraging results for a sharing prediction model that incorporates both the senders' and the recipients' preferences. These results suggest improvements to both algorithms that support sharing in social media and to information diffusion models.
Metric Learning Driven Multi-Task Structured Output Optimization for Robust Keypoint Tracking
Venue: arXiv cs.CV 2014
Year: 2014

As an important and challenging problem in computer vision and graphics, keypoint-based object tracking is typically formulated in a spatio-temporal statistical learning framework. However, most existing keypoint trackers are incapable of effectively modeling and balancing the following three aspects in a simultaneous manner: temporal model coherence across frames, spatial model consistency within frames, and discriminative feature construction. To address this issue, we propose a robust keypoint tracker based on spatio-temporal multi-task structured output optimization driven by discriminative metric learning. Consequently, temporal model coherence is characterized by multi-task structured keypoint model learning over several adjacent frames, while spatial model consistency is modeled by solving a geometric verification based structured learning problem. Discriminative feature construction is enabled by metric learning to ensure the intra-class compactness and inter-class separability. Finally, the above three modules are simultaneously optimized in a joint learning scheme. Experimental results have demonstrated the effectiveness of our tracker.