OpenRaiser/Intern-Atlas huggingface dataset:
Measuring digital crime investigation capacity to guide international crime prevention strategies
Venue: arXiv cs.CY 2013
Year: 2013

This work proposes a method for the measurement of a country's digital investigation capacity and saturation for the assessment of future capacity expansion. The focus is on external, or international, partners being a factor that could negatively affect the return on investment when attempting to expand investigation capacity nationally. This work concludes with the argument that when dealing with digital crime, target international partners should be a consideration in expansion, and could potentially be a bottleneck of investigation requests.
Collecting Coupons with Random Initial Stake
Venue: arXiv cs.DM 2013
Year: 2013

Motivated by a problem in the theory of randomized search heuristics, we give a very precise analysis for the coupon collector problem where the collector starts with a random set of coupons (chosen uniformly from all sets). We show that the expected number of rounds until we have a coupon of each type is $nH_{n/2} - 1/2 \pm o(1)$, where $H_{n/2}$ denotes the $(n/2)$th harmonic number when $n$ is even, and $H_{n/2}:= (1/2) H_{\lfloor n/2 \rfloor} + (1/2) H_{\lceil n/2 \rceil}$ when $n$ is odd. Consequently, the coupon collector with random initial stake is by half a round faster than the one starting with exactly $n/2$ coupons (apart from additive $o(1)$ terms). This result implies that classic simple heuristic called \emph{randomized local search} needs an expected number of $nH_{n/2} - 1/2 \pm o(1)$ iterations to find the optimum of any monotonic function defined on bit-strings of length $n$.
Robust L_infinity-induced deconvolution filtering for linear stochastic systems and its application to fault reconstruction
Venue: arXiv cs.SY 2013
Year: 2013

The problem of stationary robust L_infinity-induced deconvolution filtering for the uncertain continuous-time linear stochastic systems is addressed. The state space model of the system contains state- and input-dependent noise and deterministic parameter uncertainties residing in a given polytope. In the presence of input-dependent noise, we extend the derived lemma in Berman and Shaked (2010) characterizing the induced L_infinity norm by linear matrix inequalities (LMIs), according to which we solve the deconvolution problem in the quadratic framework. By decoupling product terms between the Lyapunov matrix and system matrices, an improved version of the proposed L_infinity-induced norm bound lemma for continuous-time stochastic systems is obtained, which allows us to realize exploit parameter-dependent stability idea in the deconvolution filter design. The theories presented are utilized for sensor fault reconstruction in uncertain linear stochastic systems. The effectiveness and advantages of the proposed design methods are shown via two numerical examples.
Using Chip Multithreading to Speed Up Scenario-Based Design Space Exploration
Venue: arXiv cs.PF 2013
Year: 2013

To cope with the complex embedded system design, early design space exploration (DSE) is used to make design decisions early in the design phase. For early DSE it is crucial that the running time of the exploration is as small as possible. In this paper, we describe both the porting of our scenario-based DSE to the SPARC T3-4 server and the analysis of its performance behavior.
A Novel Query-Based Approach for Addressing Summarizability Issues in XOLAP
Venue: arXiv cs.DB 2013
Year: 2013

The business intelligence and decision-support systems used in many application domains casually rely on data warehouses, which are decision-oriented data repositories modeled as multidimensional (MD) structures. MD structures help navigate data through hierarchical levels of detail. In many real-world situations, hierarchies in MD models are complex, which causes data aggregation issues, collectively known as the summarizability problem. This problem leads to incorrect analyses and critically affects decision making. To enforce summarizability, existing approaches alter either MD models or data, and must be applied a priori, on a case-by-case basis, by an expert. To alter neither models nor data, a few query-time approaches have been proposed recently, but they only detect summarizability issues without solving them. Thus, we propose in this paper a novel approach that automatically detects and processes summarizability issues at query time, without requiring any particular expertise from the user. Moreover, while most existing approaches are based on the relational model, our approach focus on an XML MD model, since XML data is customarily used to represent business data and its format better copes with complex hierarchies than the relational model. Finally, our experiments show that our method is likely to scale better than a reference approach for addressing the summarizability problem in the MD context.
Achieving Good Angular Resolution in 3D Arc Diagrams
Venue: arXiv cs.DS 2013
Year: 2013

We study a three-dimensional analogue to the well-known graph visualization approach known as arc diagrams. We provide several algorithms that achieve good angular resolution for 3D arc diagrams, even for cases when the arcs must project to a given 2D straight-line drawing of the input graph. Our methods make use of various graph coloring algorithms, including an algorithm for a new coloring problem, which we call localized edge coloring.
Many-to-One Boundary Labeling with Backbones
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we study \emph{many-to-one boundary labeling with backbone leaders}. In this new many-to-one model, a horizontal backbone reaches out of each label into the feature-enclosing rectangle. Feature points that need to be connected to this label are linked via vertical line segments to the backbone. We present dynamic programming algorithms for label number and total leader length minimization of crossing-free backbone labelings. When crossings are allowed, we aim to obtain solutions with the minimum number of crossings. This can be achieved efficiently in the case of fixed label order, however, in the case of flexible label order we show that minimizing the number of leader crossings is NP-hard.
Accelerating a Cloud-Based Software GNSS Receiver
Venue: arXiv cs.PF 2013
Year: 2013

In this paper we discuss ways to reduce the execution time of a software Global Navigation Satellite System (GNSS) receiver that is meant for offline operation in a cloud environment. Client devices record satellite signals they receive, and send them to the cloud, to be processed by this software. The goal of this project is for each client request to be processed as fast as possible, but also to increase total system throughput by making sure as many requests as possible are processed within a unit of time. The characteristics of our application provided both opportunities and challenges for increasing performance. We describe the speedups we obtained by enabling the software to exploit multi-core CPUs and GPGPUs. We mention which techniques worked for us and which did not. To increase throughput, we describe how we control the resources allocated to each invocation of the software to process a client request, such that multiple copies of the application can run at the same time. We use the notion of effective running time to measure the system's throughput when running multiple instances at the same time, and show how we can determine when the system's computing resources have been saturated.
Turing Instability in Reaction-Diffusion Systems with a Single Diffuser: Characterization Based on Root Locus
Venue: arXiv cs.SY 2013
Year: 2013

Cooperative behaviors arising from bacterial cell-to-cell communication can be modeled by reaction-diffusion equations having only a single diffusible component. This paper presents the following three contributions for the systematic analysis of Turing instability in such reaction-diffusion systems. (i) We first introduce a unified framework to formulate the reaction-diffusion system as an interconnected multi-agent dynamical system. (ii) Then, we mathematically classify biologically plausible and implausible Turing instabilities and characterize them by the root locus of each agent's dynamics, or the local reaction dynamics. (iii) Using this characterization, we derive analytic conditions for biologically plausible Turing instability, which provide useful guidance for the design and the analysis of biological networks. These results are demonstrated on an extended Gray-Scott model with a single diffuser.
Generating Keys in Elliptic Curve Cryptosystems
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we will present how to find keys elliptic curve cryptosystems (ECC) with simple tools of Delphi 7 console application, using the software problem solving of the scalar point multiplication in the field GF(p), where p is an arbitrary prime number.
Designing Efficient Resource Sharing For Impatient Players Using Limited Monitoring
Venue: arXiv cs.GT 2013
Year: 2013

The problem of efficient sharing of a resource is nearly ubiquitous. Except for pure public goods, each agent's use creates a negative externality; often the negative externality is so strong that efficient sharing is impossible in the short run. We show that, paradoxically, the impossibility of efficient sharing in the short run enhances the possibility of efficient sharing in the long run, even if outcomes depend stochastically on actions, monitoring is limited and users are not patient. We base our analysis on the familiar framework of repeated games with imperfect public monitoring, but we extend the framework to view the monitoring structure as chosen by a designer who balances the benefits and costs of more accurate observations and reports. Our conclusions are much stronger than in the usual folk theorems: we do not require a rich signal structure or patient users and provide an explicit online construction of equilibrium strategies.
Traffic analyzer for differentiating BitTorrent handshake failures from port-scans
Venue: arXiv cs.NI 2013
Year: 2013

This paper aims to improve the accuracy of port-scan detectors by analyzing traffic of BitTorrent hosts and differentiating their respective BitTorrent connection (attempts) from port-scans. It is shown that by looking at BitTorrent coordination traffic and modelling port-scanning behavior the number of BitTorrent-related false positives can be reduced by 80% without any loss of IDS accuracy.
On the performance of a cavity method based algorithm for the Prize-Collecting Steiner Tree Problem on graphs
Venue: arXiv cs.DS 2013
Year: 2013

We study the behavior of an algorithm derived from the cavity method for the Prize-Collecting Steiner Tree (PCST) problem on graphs. The algorithm is based on the zero temperature limit of the cavity equations and as such is formally simple (a fixed point equation resolved by iteration) and distributed (parallelizable). We provide a detailed comparison with state-of-the-art algorithms on a wide range of existing benchmarks networks and random graphs. Specifically, we consider an enhanced derivative of the Goemans-Williamson heuristics and the DHEA solver, a Branch and Cut Linear/Integer Programming based approach. The comparison shows that the cavity algorithm outperforms the two algorithms in most large instances both in running time and quality of the solution. Finally we prove a few optimality properties of the solutions provided by our algorithm, including optimality under the two post-processing procedures defined in the Goemans-Williamson derivative and global optimality in some limit cases.
Sigma Point Belief Propagation
Venue: arXiv cs.AI 2013
Year: 2013

The sigma point (SP) filter, also known as unscented Kalman filter, is an attractive alternative to the extended Kalman filter and the particle filter. Here, we extend the SP filter to nonsequential Bayesian inference corresponding to loopy factor graphs. We propose sigma point belief propagation (SPBP) as a low-complexity approximation of the belief propagation (BP) message passing scheme. SPBP achieves approximate marginalizations of posterior distributions corresponding to (generally) loopy factor graphs. It is well suited for decentralized inference because of its low communication requirements. For a decentralized, dynamic sensor localization problem, we demonstrate that SPBP can outperform nonparametric (particle-based) BP while requiring significantly less computations and communications.
Optimizing the performance of Lattice Gauge Theory simulations with Streaming SIMD extensions
Venue: arXiv cs.CE 2013
Year: 2013

Two factors, which affect simulation quality are the amount of computing power and implementation. The Streaming SIMD (single instruction multiple data) extensions (SSE) present a technique for influencing both by exploiting the processor's parallel functionalism. In this paper, we show how SSE improves performance of lattice gauge theory simulations. We identified two significant trends through an analysis of data from various runs. The speed-ups were higher for single precision than double precision floating point numbers. Notably, though the use of SSE significantly improved simulation time, it did not deliver the theoretical maximum. There are a number of reasons for this: architectural constraints imposed by the FSB speed, the spatial and temporal patterns of data retrieval, ratio of computational to non-computational instructions, and the need to interleave miscellaneous instructions with computational instructions. We present a model for analyzing the SSE performance, which could help factor in the bottlenecks or weaknesses in the implementation, the computing architecture, and the mapping of software to the computing substrate while evaluating the improvement in efficiency. The model or framework would be useful in evaluating the use of other computational frameworks, and in predicting the benefits that can be derived from future hardware or architectural improvements.
On Throughput and Decoding Delay Performance of Instantly Decodable Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a comprehensive study of packet-based instantly decodable network coding (IDNC) for single-hop wireless broadcast is presented. The optimal IDNC solution in terms of throughput is proposed and its packet decoding delay performance is investigated. Lower and upper bounds on the achievable throughput and decoding delay performance of IDNC are derived and assessed through extensive simulations. Furthermore, the impact of receivers' feedback frequency on the performance of IDNC is studied and optimal IDNC solutions are proposed for scenarios where receivers' feedback is only available after and IDNC round, composed of several coded transmissions. However, since finding these IDNC optimal solutions is computational complex, we further propose simple yet efficient heuristic IDNC algorithms. The impact of system settings and parameters such as channel erasure probability, feedback frequency, and the number of receivers is also investigated and simple guidelines for practical implementations of IDNC are proposed.
Feedback Communication Systems with Limitations on Incremental Redundancy
Venue: arXiv cs.IT 2013
Year: 2013

This paper explores feedback systems using incremental redundancy (IR) with noiseless transmitter confirmation (NTC). For IR-NTC systems based on {\em finite-length} codes (with blocklength $N$) and decoding attempts only at {\em certain specified decoding times}, this paper presents the asymptotic expansion achieved by random coding, provides rate-compatible sphere-packing (RCSP) performance approximations, and presents simulation results of tail-biting convolutional codes. The information-theoretic analysis shows that values of $N$ relatively close to the expected latency yield the same random-coding achievability expansion as with $N = \infty$. However, the penalty introduced in the expansion by limiting decoding times is linear in the interval between decoding times. For binary symmetric channels, the RCSP approximation provides an efficiently-computed approximation of performance that shows excellent agreement with a family of rate-compatible, tail-biting convolutional codes in the short-latency regime. For the additive white Gaussian noise channel, bounded-distance decoding simplifies the computation of the marginal RCSP approximation and produces similar results as analysis based on maximum-likelihood decoding for latencies greater than 200. The efficiency of the marginal RCSP approximation facilitates optimization of the lengths of incremental transmissions when the number of incremental transmissions is constrained to be small or the length of the incremental transmissions is constrained to be uniform after the first transmission. Finally, an RCSP-based decoding error trajectory is introduced that provides target error rates for the design of rate-compatible code families for use in feedback communication systems.
Discrete and Continuous, Probabilistic Anticipation for Autonomous Robots in Urban Environments
Venue: arXiv cs.RO 2013
Year: 2013

This paper develops a probabilistic anticipation algorithm for dynamic objects observed by an autonomous robot in an urban environment. Predictive Gaussian mixture models are used due to their ability to probabilistically capture continuous and discrete obstacle decisions and behaviors; the predictive system uses the probabilistic output (state estimate and covariance) of a tracking system, and map of the environment to compute the probability distribution over future obstacle states for a specified anticipation horizon. A Gaussian splitting method is proposed based on the sigma-point transform and the nonlinear dynamics function, which enables increased accuracy as the number of mixands grows. An approach to caching elements of this optimal splitting method is proposed, in order to enable real-time implementation. Simulation results and evaluations on data from the research community demonstrate that the proposed algorithm can accurately anticipate the probability distributions over future states of nonlinear systems.
Guard Your Daggers and Traces: On The Equational Properties of Guarded (Co-)recursion
Venue: arXiv cs.LO 2013
Year: 2013

Motivated by the recent interest in models of guarded (co-)recursion we study its equational properties. We formulate axioms for guarded fixpoint operators generalizing the axioms of iteration theories of Bloom and Esik. Models of these axioms include both standard (e.g., cpo-based) models of iteration theories and models of guarded recursion such as complete metric spaces or the topos of trees studied by Birkedal et al. We show that the standard result on the satisfaction of all Conway axioms by a unique dagger operation generalizes to the guarded setting. We also introduce the notion of guarded trace operator on a category, and we prove that guarded trace and guarded fixpoint operators are in one-to-one correspondence. Our results are intended as first steps leading to the description of classifying theories for guarded recursion and hence completeness results involving our axioms of guarded fixpoint operators in future work.
Łukasiewicz mu-Calculus
Venue: arXiv cs.LO 2013
Year: 2013

The paper explores properties of Łukasiewicz mu-calculus, a version of the quantitative/probabilistic modal mu-calculus containing both weak and strong conjunctions and disjunctions from Łukasiewicz (fuzzy) logic. We show that this logic encodes the well-known probabilistic temporal logic PCTL. And we give a model-checking algorithm for computing the rational denotational value of a formula at any state in a finite rational probabilistic nondeterministic transition system.
Conscript Your Friends into Larger Anonymity Sets with JavaScript
Venue: arXiv cs.CR 2013
Year: 2013

We present the design and prototype implementation of ConScript, a framework for using JavaScript to allow casual Web users to participate in an anonymous communication system. When a Web user visits a cooperative Web site, the site serves a JavaScript application that instructs the browser to create and submit "dummy" messages into the anonymity system. Users who want to send non-dummy messages through the anonymity system use a browser plug-in to replace these dummy messages with real messages. Creating such conscripted anonymity sets can increase the anonymity set size available to users of remailer, e-voting, and verifiable shuffle-style anonymity systems. We outline ConScript's architecture, we address a number of potential attacks against ConScript, and we discuss the ethical issues related to deploying such a system. Our implementation results demonstrate the practicality of ConScript: a workstation running our ConScript prototype JavaScript client generates a dummy message for a mix-net in 81 milliseconds and it generates a dummy message for a DoS-resistant DC-net in 156 milliseconds.
Minutiae Based Thermal Face Recognition using Blood Perfusion Data
Venue: arXiv cs.CV 2013
Year: 2013

This paper describes an efficient approach for human face recognition based on blood perfusion data from infra-red face images. Blood perfusion data are characterized by the regional blood flow in human tissue and therefore do not depend entirely on surrounding temperature. These data bear a great potential for deriving discriminating facial thermogram for better classification and recognition of face images in comparison to optical image data. Blood perfusion data are related to distribution of blood vessels under the face skin. A distribution of blood vessels are unique for each person and as a set of extracted minutiae points from a blood perfusion data of a human face should be unique for that face. There may be several such minutiae point sets for a single face but all of these correspond to that particular face only. Entire face image is partitioned into equal blocks and the total number of minutiae points from each block is computed to construct final vector. Therefore, the size of the feature vectors is found to be same as total number of blocks considered. For classification, a five layer feed-forward backpropagation neural network has been used. A number of experiments were conducted to evaluate the performance of the proposed face recognition system with varying block sizes. Experiments have been performed on the database created at our own laboratory. The maximum success of 91.47% recognition has been achieved with block size 8X8.
Statistiques et visibilité des bibliothèques numériques : quelles stratégies de diffusion ?
Venue: arXiv cs.DL 2013
Year: 2013

We compared statistics of major digital libraries and we tried to see if there is a relationship between the volume of digital libraries and online visibility of each digitized document. Finally, we analyzed the consequences of the diffusion strategies of French digital libraries. The statistics were obtained by survey, gray literature, alexa.com, and Google Trends.
Simplifying the Development, Use and Sustainability of HPC Software
Venue: arXiv cs.DC 2013
Year: 2013

Developing software to undertake complex, compute-intensive scientific processes requires a challenging combination of both specialist domain knowledge and software development skills to convert this knowledge into efficient code. As computational platforms become increasingly heterogeneous and newer types of platform such as Infrastructure-as-a-Service (IaaS) cloud computing become more widely accepted for HPC computations, scientists require more support from computer scientists and resource providers to develop efficient code and make optimal use of the resources available to them. As part of the libhpc stage 1 and 2 projects we are developing a framework to provide a richer means of job specification and efficient execution of complex scientific software on heterogeneous infrastructure. The use of such frameworks has implications for the sustainability of scientific software. In this paper we set out our developing understanding of these challenges based on work carried out in the libhpc project.