OpenRaiser/Intern-Atlas huggingface dataset:
Fast computation of the performance evaluation of biometric systems: application to multibiometric
Venue: arXiv cs.DS 2012
Year: 2012

The performance evaluation of biometric systems is a crucial step when designing and evaluating such systems. The evaluation process uses the Equal Error Rate (EER) metric proposed by the International Organization for Standardization (ISO/IEC). The EER metric is a powerful metric which allows easily comparing and evaluating biometric systems. However, the computation time of the EER is, most of the time, very intensive. In this paper, we propose a fast method which computes an approximated value of the EER. We illustrate the benefit of the proposed method on two applications: the computing of non parametric confidence intervals and the use of genetic algorithms to compute the parameters of fusion functions. Experimental results show the superiority of the proposed EER approximation method in term of computing time, and the interest of its use to reduce the learning of parameters with genetic algorithms. The proposed method opens new perspectives for the development of secure multibiometrics systems by speeding up their computation time.
Compressed Beamforming in Ultrasound Imaging
Venue: arXiv cs.IT 2012
Year: 2012

Emerging sonography techniques often require increasing the number of transducer elements involved in the imaging process. Consequently, larger amounts of data must be acquired and processed. The significant growth in the amounts of data affects both machinery size and power consumption. Within the classical sampling framework, state of the art systems reduce processing rates by exploiting the bandpass bandwidth of the detected signals. It has been recently shown, that a much more significant sample-rate reduction may be obtained, by treating ultrasound signals within the Finite Rate of Innovation framework. These ideas follow the spirit of Xampling, which combines classic methods from sampling theory with recent developments in Compressed Sensing. Applying such low-rate sampling schemes to individual transducer elements, which detect energy reflected from biological tissues, is limited by the noisy nature of the signals. This often results in erroneous parameter extraction, bringing forward the need to enhance the SNR of the low-rate samples. In our work, we achieve SNR enhancement, by beamforming the sub-Nyquist samples obtained from multiple elements. We refer to this process as "compressed beamforming". Applying it to cardiac ultrasound data, we successfully image macroscopic perturbations, while achieving a nearly eight-fold reduction in sample-rate, compared to standard techniques.
Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs - Part II: Synchronous and Asynchronous Systems
Venue: arXiv cs.DC 2012
Year: 2012

This report contains two related sets of results with different assumptions on synchrony. The first part is about iterative algorithms in synchronous systems. Following our previous work on synchronous iterative approximate Byzantine consensus (IABC) algorithms, we provide a more intuitive tight necessary and sufficient condition for the existence of such algorithms in synchronous networks1. We believe this condition and the previous results also hold in partially asynchronous algorithmic model. In the second part of the report, we explore the problem in asynchronous networks. While the traditional Byzantine consensus is not solvable in asynchronous systems, approximate Byzantine consensus can be solved using iterative algorithms.
Applying SMT Solvers to the Test Template Framework
Venue: arXiv cs.SE 2012
Year: 2012

The Test Template Framework (TTF) is a model-based testing method for the Z notation. In the TTF, test cases are generated from test specifications, which are predicates written in Z. In turn, the Z notation is based on first-order logic with equality and Zermelo-Fraenkel set theory. In this way, a test case is a witness satisfying a formula in that theory. Satisfiability Modulo Theory (SMT) solvers are software tools that decide the satisfiability of arbitrary formulas in a large number of built-in logical theories and their combination. In this paper, we present the first results of applying two SMT solvers, Yices and CVC3, as the engines to find test cases from TTF's test specifications. In doing so, shallow embeddings of a significant portion of the Z notation into the input languages of Yices and CVC3 are provided, given that they do not directly support Zermelo-Fraenkel set theory as defined in Z. Finally, the results of applying these embeddings to a number of test specifications of eight cases studies are analysed.
Distributed Power Allocation with SINR Constraints Using Trial and Error Learning
Venue: arXiv cs.GT 2012
Year: 2012

In this paper, we address the problem of global transmit power minimization in a self-congiguring network where radio devices are subject to operate at a minimum signal to interference plus noise ratio (SINR) level. We model the network as a parallel Gaussian interference channel and we introduce a fully decentralized algorithm (based on trial and error) able to statistically achieve a congiguration where the performance demands are met. Contrary to existing solutions, our algorithm requires only local information and can learn stable and efficient working points by using only one bit feedback. We model the network under two different game theoretical frameworks: normal form and satisfaction form. We show that the converging points correspond to equilibrium points, namely Nash and satisfaction equilibrium. Similarly, we provide sufficient conditions for the algorithm to converge in both formulations. Moreover, we provide analytical results to estimate the algorithm's performance, as a function of the network parameters. Finally, numerical results are provided to validate our theoretical conclusions. Keywords: Learning, power control, trial and error, Nash equilibrium, spectrum sharing.
Note on Existence and Non-Existence of Large Subsets of Binary Vectors with Similar Distances
Venue: arXiv cs.DM 2012
Year: 2012

We consider vectors from $\{0,1\}^n$. The weight of such a vector $v$ is the sum of the coordinates of $v$. The distance ratio of a set $L$ of vectors is ${\rm dr}(L):=\max \{ρ(x,y):\ x,y \in L\}/ \min \{ρ(x,y):\ x,y \in L,\ x\neq y\},$ where $ρ(x,y)$ is the Hamming distance between $x$ and $y$. We prove that (a) for every constant $λ>1$ there are no positive constants $α$ and $C$ such that every set $K$ of at least $λ^p$ vectors with weight $p$ contains a subset $K'$ with $|K'|\ge |K|^α$ and ${\rm dr}(K')\le C$, % even when $|K|\ge λ$, (b) For a set $K$ of vectors with weight $p$, and a constant $C>2$, there exists $K'\subseteq K$ such that ${\rm dr}(K')\le C$ and $|K'| \ge |K|^α$, where $α= 1/ \lceil \log(p/2)/\log(C/2) \rceil$.
Coding Scheme for Optimizing Random I/O Performance
Venue: arXiv cs.IT 2012
Year: 2012

Flash memories intended for SSD and mobile applications need to provide high random I/O performance. This requires using efficient schemes for reading small chunks of data (e.g. 0.5KB - 4KB) from random addresses. Furthermore, in order to be cost efficient, it is desirable to use high density Multi-Level Cell (MLC) memories, such as the ones based on 3 or 4 bit per cell technologies. Unfortunately, these two requirements are contradicting, as reading an MLC memory, whose data is coded conventionally, requires multiple sensing operations, resulting in slow reading and degraded random I/O performance. This paper describes a novel coding scheme that optimizes random read throughput, by allowing reading small data chunks from an MLC memory using a single sensing operation.
Eye Pupil Location Using Webcam
Venue: arXiv cs.HC 2012
Year: 2012

Three different algorithms used for eye pupil location were described and tested. Algorithm efficiency comparison was based on human faces images taken from the BioID database. Moreover all the eye localisation methods were implemented in a dedicated application supporting eye movement based computer control. In this case human face images were acquired by a webcam and processed in a real-time.
Password Authentication Scheme with Secured Login Interface
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents a novel solution to the age long problem of password security at input level. In our solution, each of the various characters from which a password could be composed is encoded with a random single digit integer and presented to the user via an input interface form. A legitimate user entering his password only needs to carefully study the sequence of code that describe his password, and then enter these code in place of his actual password characters. This approach does not require the input code to be hidden from anyone or converted to placeholder characters for security reasons. Our solution engine regenerates new code for each character each time the carriage return key is struck, producing a hardened password that is convincingly more secure than conventional password entry system against both online and offline attackers. Using empirical data and a prototype implementation of our scheme, we give evidence that our approach is viable in practice, in terms of ease of use, improved security, and performance.
Sublinear Time Approximate Sum via Uniform Random Sampling
Venue: arXiv cs.DS 2012
Year: 2012

We investigate the approximation for computing the sum $a_1+...+a_n$ with an input of a list of nonnegative elements $a_1,..., a_n$. If all elements are in the range $[0,1]$, there is a randomized algorithm that can compute an $(1+ε)$-approximation for the sum problem in time ${O({n(\log\log n)\over\sum_{i=1}^n a_i})}$, where $ε$ is a constant in $(0,1)$. Our randomized algorithm is based on the uniform random sampling, which selects one element with equal probability from the input list each time. We also prove a lower bound $Ω({n\over \sum_{i=1}^n a_i})$, which almost matches the upper bound, for this problem.
On the Role of Service Concept in IT
Venue: arXiv cs.SE 2012
Year: 2012

Hard times affecting world-wide economy have strong consequences and are challenging IT departments from all sorts of enterprises. Expensive software projects are replaced by component-based agile systems and paradigms like SOA, REST, cloud computing are the new buzz-words. Behind the canvas, the service concept plays a central role, which we try to reveal
On the Distribution of the Fourier Spectrum of Halfspaces
Venue: arXiv cs.CC 2012
Year: 2012

Bourgain showed that any noise stable Boolean function $f$ can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's result under the additional assumption that $f$ is a halfspace.
SharedDB: Killing One Thousand Queries With One Stone
Venue: arXiv cs.DB 2012
Year: 2012

Traditional database systems are built around the query-at-a-time model. This approach tries to optimize performance in a best-effort way. Unfortunately, best effort is not good enough for many modern applications. These applications require response time guarantees in high load situations. This paper describes the design of a new database architecture that is based on batching queries and shared computation across possibly hundreds of concurrent queries and updates. Performance experiments with the TPC-W benchmark show that the performance of our implementation, SharedDB, is indeed robust across a wide range of dynamic workloads.
ReStore: Reusing Results of MapReduce Jobs
Venue: arXiv cs.DB 2012
Year: 2012

Analyzing large scale data has emerged as an important activity for many organizations in the past few years. This large scale data analysis is facilitated by the MapReduce programming and execution model and its implementations, most notably Hadoop. Users of MapReduce often have analysis tasks that are too complex to express as individual MapReduce jobs. Instead, they use high-level query languages such as Pig, Hive, or Jaql to express their complex tasks. The compilers of these languages translate queries into workflows of MapReduce jobs. Each job in these workflows reads its input from the distributed file system used by the MapReduce system and produces output that is stored in this distributed file system and read as input by the next job in the workflow. The current practice is to delete these intermediate results from the distributed file system at the end of executing the workflow. One way to improve the performance of workflows of MapReduce jobs is to keep these intermediate results and reuse them for future workflows submitted to the system. In this paper, we present ReStore, a system that manages the storage and reuse of such intermediate results. ReStore can reuse the output of whole MapReduce jobs that are part of a workflow, and it can also create additional reuse opportunities by materializing and storing the output of query execution operators that are executed within a MapReduce job. We have implemented ReStore as an extension to the Pig dataflow system on top of Hadoop, and we experimentally demonstrate significant speedups on queries from the PigMix benchmark.
Using Barriers to Reduce the Sensitivity to Edge Miscalculations of Casting-Based Object Projection Feature Estimation
Venue: arXiv cs.CV 2012
Year: 2012

3D motion tracking is a critical task in many computer vision applications. Unsupervised markerless 3D motion tracking systems determine the most relevant object in the screen and then track it by continuously estimating its projection features (center and area) from the edge image and a point inside the relevant object projection (namely, inner point), until the tracking fails. Existing reliable object projection feature estimation techniques are based on ray-casting or grid-filling from the inner point. These techniques assume the edge image to be accurate. However, in real case scenarios, edge miscalculations may arise from low contrast between the target object and its surroundings or motion blur caused by low frame rates or fast moving target objects. In this paper, we propose a barrier extension to casting-based techniques that mitigates the effect of edge miscalculations.
Queries with Guarded Negation (full version)
Venue: arXiv cs.DB 2012
Year: 2012

A well-established and fundamental insight in database theory is that negation (also known as complementation) tends to make queries difficult to process and difficult to reason about. Many basic problems are decidable and admit practical algorithms in the case of unions of conjunctive queries, but become difficult or even undecidable when queries are allowed to contain negation. Inspired by recent results in finite model theory, we consider a restricted form of negation, guarded negation. We introduce a fragment of SQL, called GN-SQL, as well as a fragment of Datalog with stratified negation, called GN-Datalog, that allow only guarded negation, and we show that these query languages are computationally well behaved, in terms of testing query containment, query evaluation, open-world query answering, and boundedness. GN-SQL and GN-Datalog subsume a number of well known query languages and constraint languages, such as unions of conjunctive queries, monadic Datalog, and frontier-guarded tgds. In addition, an analysis of standard benchmark workloads shows that most usage of negation in SQL in practice is guarded negation.
The Mind Grows Circuits
Venue: arXiv cs.AI 2012
Year: 2012

There is a vast supply of prior art that study models for mental processes. Some studies in psychology and philosophy approach it from an inner perspective in terms of experiences and percepts. Others such as neurobiology or connectionist-machines approach it externally by viewing the mind as complex circuit of neurons where each neuron is a primitive binary circuit. In this paper, we also model the mind as a place where a circuit grows, starting as a collection of primitive components at birth and then builds up incrementally in a bottom up fashion. A new node is formed by a simple composition of prior nodes when we undergo a repeated experience that can be described by that composition. Unlike neural networks, however, these circuits take "concepts" or "percepts" as inputs and outputs. Thus the growing circuits can be likened to a growing collection of lambda expressions that are built on top of one another in an attempt to compress the sensory input as a heuristic to bound its Kolmogorov Complexity.
Fast Reinforcement Learning with Large Action Sets using Error-Correcting Output Codes for MDP Factorization
Venue: arXiv cs.LG 2012
Year: 2012

The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale. Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the supervised classification framework where the optimal policy is obtained through a multiclass classifier, the set of classes being the set of actions of the problem. We introduce error-correcting output codes (ECOCs) in this setting and propose two new methods for reducing complexity when using rollouts-based approaches. The first method consists in using an ECOC-based classifier as the multiclass classifier, reducing the learning complexity from O(A2) to O(Alog(A)). We then propose a novel method that profits from the ECOC's coding dictionary to split the initial MDP into O(log(A)) seperate two-action MDPs. This second method reduces learning complexity even further, from O(A2) to O(log(A)), thus rendering problems with large action sets tractable. We finish by experimentally demonstrating the advantages of our approach on a set of benchmark problems, both in speed and performance.
Image Fusion and Re-Modified SPIHT for Fused Image
Venue: arXiv cs.CV 2012
Year: 2012

This paper presents the Discrete Wavelet based fusion techniques for combining perceptually important image features. SPIHT (Set Partitioning in Hierarchical Trees) algorithm is an efficient method for lossy and lossless coding of fused image. This paper presents some modifications on the SPIHT algorithm. It is based on the idea of insignificant correlation of wavelet coefficient among the medium and high frequency sub bands. In RE-MSPIHT algorithm, wavelet coefficients are scaled prior to SPIHT coding based on the sub band importance, with the goal of minimizing the MSE.
Weight spectrum of codes associated with the Grassmannian G(3,7)
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we consider the problem of determining the weight spectrum of q-ary codes C(3,m) associated with Grassmann varieties G(3,m). For m=6 this was done by Nogin. We derive a formula for the weight of a codeword of C(3,m), in terms of certain varieties associated with alternating trilinear forms on (F_q)^m. The classification of such forms under the action of the general linear group GL(m,F_q) is the other component that is required to calculate the spectrum of C(3,m). For m=7, we explicitly determine the varieties mentioned above. The classification problem for alternating 3-forms on (F_q)^7 was solved by Cohen and Helminck, which we then use to determine the spectrum of C(3,7).
Bridging the Gap between Technical Heterogeneity of Context-Aware Platforms: Experimenting a Service Based Connectivity between Adaptable Android, WComp and OpenORB
Venue: arXiv cs.SE 2012
Year: 2012

Many companies include in their Information Systems (IS) several communicating heterogeneous middleware according to their technical needs. The need is the same when IS requires using context aware platforms for different aims. Moreover, users may be mobile and want to receive and send services with their PDA that more often supports Android based Human Man Interface. In this paper, we show how we extend Android to make it adaptable and open. We also present how we communicate between different heterogeneous context aware platforms as WComp and OpenORB by using Android and Web Services. We introduce a concrete case study to explain our approach.
SOA-based security governance middleware
Venue: arXiv cs.CR 2012
Year: 2012

Business requirements for rapid operational efficiency, customer responsiveness as well as rapid adaptability are actively driving the need for ever increasing communication and integration apabilities of software assets. In this context, security, although acknowledged as being a necessity, is often perceived as a hindrance. Indeed, dynamic environments require flexible and understandable security that can be customized, adapted and reconfigured dynamically to face changing requirements. In this paper, the authors propose SOA based security governance middleware that handles security requirements on behalf of a resource exposed through it. The middleware aims at providing different security settings through the use of managed compositions of security services called profiles. The main added value of this work compared to existing handlers or centralized approaches lies in its enhanced flexibility and transparency.
Homeomorphic approximation of the intersection curve of two rational surfaces
Venue: arXiv cs.CG 2012
Year: 2012

We present an approach of computing the intersection curve $\mathcal{C}$ of two rational parametric surface $§_1(u,s)$ and $§_2(v,t)$, one being projectable and hence can easily be implicitized. Plugging the parametric surface to the implicit surface yields a plane algebraic curve $G(v,t)=0$. By analyzing the topology graph $\G$ of $G(v,t)=0$ and the singular points on the intersection curve $\mathcal{C}$ we associate a space topology graph to $\mathcal{C}$, which is homeomorphic to $\mathcal{C}$ and therefore leads us to an approximation for $\mathcal{C}$ in a given precision.
Secure & Rapid Composition of Infrastructure Services in the Cloud
Venue: arXiv cs.DC 2012
Year: 2012

A fundamental ambition of grid and distributed systems is to be capable of sustaining evolution and allowing for adaptability ((F. Losavio et al., 2002), (S. Radhakrishnan, 2005)). Furthermore, as the complexity and sophistication of theses structures increases, so does the need for adaptability of each component. One of the primary benefits of service oriented architecture (SOA) is the ability to compose applications, processes or more complex services from other services which increases the capacity for adaptation. This document proposes a novel infrastructure composition model that aims at increasing the adaptability of the capabilities exposed through it by dynamically managing their non functional requirements.
A new methodology for constructing a publication-level classification system of science
Venue: arXiv cs.DL 2012
Year: 2012

Classifying journals or publications into research areas is an essential element of many bibliometric analyses. Classification usually takes place at the level of journals, where the Web of Science subject categories are the most popular classification system. However, journal-level classification systems have two important limitations: They offer only a limited amount of detail, and they have difficulties with multidisciplinary journals. To avoid these limitations, we introduce a new methodology for constructing classification systems at the level of individual publications. In the proposed methodology, publications are clustered into research areas based on citation relations. The methodology is able to deal with very large numbers of publications. We present an application in which a classification system is produced that includes almost ten million publications. Based on an extensive analysis of this classification system, we discuss the strengths and the limitations of the proposed methodology. Important strengths are the transparency and relative simplicity of the methodology and its fairly modest computing and memory requirements. The main limitation of the methodology is its exclusive reliance on direct citation relations between publications. The accuracy of the methodology can probably be increased by also taking into account other types of relations, for instance based on bibliographic coupling.