OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Coverage of Mobile Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we study the dynamic aspects of the coverage of a mobile sensor network resulting from continuous movement of sensors. As sensors move around, initially uncovered locations are likely to be covered at a later time. A larger area is covered as time continues, and intruders that might never be detected in a stationary sensor network can now be detected by moving sensors. However, this improvement in coverage is achieved at the cost that a location is covered only part of the time, alternating between covered and not covered. We characterize area coverage at specific time instants and during time intervals, as well as the time durations that a location is covered and uncovered. We further characterize the time it takes to detect a randomly located intruder. For mobile intruders, we take a game theoretic approach and derive optimal mobility strategies for both sensors and intruders. Our results show that sensor mobility brings about unique dynamic coverage properties not present in a stationary sensor network, and that mobility can be exploited to compensate for the lack of sensors to improve coverage.
Combining Neural Networks for Skin Detection
Venue: arXiv cs.CV 2011
Year: 2011

Two types of combining strategies were evaluated namely combining skin features and combining skin classifiers. Several combining rules were applied where the outputs of the skin classifiers are combined using binary operators such as the AND and the OR operators, "Voting", "Sum of Weights" and a new neural network. Three chrominance components from the YCbCr colour space that gave the highest correct detection on their single feature MLP were selected as the combining parameters. A major issue in designing a MLP neural network is to determine the optimal number of hidden units given a set of training patterns. Therefore, a "coarse to fine search" method to find the number of neurons in the hidden layer is proposed. The strategy of combining Cb/Cr and Cr features improved the correct detection by 3.01% compared to the best single feature MLP given by Cb-Cr. The strategy of combining the outputs of three skin classifiers using the "Sum of Weights" rule further improved the correct detection by 4.38% compared to the best single feature MLP.
Segmentation of Camera Captured Business Card Images for Mobile Devices
Venue: arXiv cs.CV 2011
Year: 2011

Due to huge deformation in the camera captured images, variety in nature of the business cards and the computational constraints of the mobile devices, design of an efficient Business Card Reader (BCR) is challenging to the researchers. Extraction of text regions and segmenting them into characters is one of such challenges. In this paper, we have presented an efficient character segmentation technique for business card images captured by a cell-phone camera, designed in our present work towards developing an efficient BCR. At first, text regions are extracted from the card images and then the skewed ones are corrected using a computationally efficient skew correction technique. At last, these skew corrected text regions are segmented into lines and characters based on horizontal and vertical histogram. Experiments show that the present technique is efficient and applicable for mobile devices, and the mean segmentation accuracy of 97.48% is achieved with 3 mega-pixel (500-600 dpi) images. It takes only 1.1 seconds for segmentation including all the preprocessing steps on a moderately powerful notebook (DualCore T2370, 1.73 GHz, 1GB RAM, 1MB L2 Cache).
Good Friends, Bad News - Affect and Virality in Twitter
Venue: arXiv cs.SI 2011
Year: 2011

The link between affect, defined as the capacity for sentimental arousal on the part of a message, and virality, defined as the probability that it be sent along, is of significant theoretical and practical importance, e.g. for viral marketing. A quantitative study of emailing of articles from the NY Times finds a strong link between positive affect and virality, and, based on psychological theories it is concluded that this relation is universally valid. The conclusion appears to be in contrast with classic theory of diffusion in news media emphasizing negative affect as promoting propagation. In this paper we explore the apparent paradox in a quantitative analysis of information diffusion on Twitter. Twitter is interesting in this context as it has been shown to present both the characteristics social and news media. The basic measure of virality in Twitter is the probability of retweet. Twitter is different from email in that retweeting does not depend on pre-existing social relations, but often occur among strangers, thus in this respect Twitter may be more similar to traditional news media. We therefore hypothesize that negative news content is more likely to be retweeted, while for non-news tweets positive sentiments support virality. To test the hypothesis we analyze three corpora: A complete sample of tweets about the COP15 climate summit, a random sample of tweets, and a general text corpus including news. The latter allows us to train a classifier that can distinguish tweets that carry news and non-news information. We present evidence that negative sentiment enhances virality in the news segment, but not in the non-news segment. We conclude that the relation between affect and virality is more complex than expected based on the findings of Berger and Milkman (2010), in short 'if you want to be cited: Sweet talk your friends or serve bad news to the public'.
On Arthur Merlin Games in Communication Complexity
Venue: arXiv cs.CC 2011
Year: 2011

We show several results related to interactive proof modes of communication complexity. First we show lower bounds for the QMA-communication complexity of the functions Inner Product and Disjointness. We describe a general method to prove lower bounds for QMA-communication complexity, and show how one can 'transfer' hardness under an analogous measure in the query complexity model to the communication model using Sherstov's pattern matrix method. Combining a result by Vereshchagin and the pattern matrix method we find a communication problem with AM-communication complexity $O(\log n)$, PP-communication complexity $Ω(n^{1/3})$, and QMA-communication complexity $Ω(n^{1/6})$. Hence in the world of communication complexity noninteractive quantum proof systems are not able to efficiently simulate co-nondeterminism or interaction. These results imply that the related questions in Turing machine complexity theory cannot be resolved by 'algebrizing' techniques. Finally we show that in MA-protocols there is an exponential gap between one-way protocols and two-way protocols (this refers to the interaction between Alice and Bob). This is in contrast to nondeterministic, AM-, and QMA-protocols, where one-way communication is essentially optimal.
Channel Optimized Distributed Multiple Description Coding
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, channel optimized distributed multiple description vector quantization (CDMD) schemes are presented for distributed source coding in symmetric and asymmetric settings. The CDMD encoder is designed using a deterministic annealing approach over noisy channels with packet loss. A minimum mean squared error asymmetric CDMD decoder is proposed for effective reconstruction of a source, utilizing the side information (SI) and its corresponding received descriptions. The proposed iterative symmetric CDMD decoder jointly reconstructs the symbols of multiple correlated sources. Two types of symmetric CDMD decoders, namely the estimated-SI and the soft-SI decoders, are presented which respectively exploit the reconstructed symbols and a posteriori probabilities of other sources as SI in iterations. In a multiple source CDMD setting, for reconstruction of a source, three methods are proposed to select another source as its SI during the decoding. The methods operate based on minimum physical distance (in a wireless sensor network setting), maximum mutual information and minimum end-to-end distortion. The performance of the proposed systems and algorithms are evaluated and compared in detail.
Coordinates for a new triangular tiling of the hyperbolic plane
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we define an infinite family of triangular tilings of the hyperbolic plane defined by two parameters ranging in the natural nummbers and we give a uniform way to define coordinates for locating the triangles of the tiling.
High Performance Gravitational N-body Simulations on a Planet-wide Distributed Supercomputer
Venue: arXiv cs.DC 2011
Year: 2011

We report on the performance of our cold-dark matter cosmological N-body simulation which was carried out concurrently using supercomputers across the globe. We ran simulations on 60 to 750 cores distributed over a variety of supercomputers in Amsterdam (the Netherlands, Europe), in Tokyo (Japan, Asia), Edinburgh (UK, Europe) and Espoo (Finland, Europe). Regardless the network latency of 0.32 seconds and the communication over 30.000 km of optical network cable we are able to achieve about 87% of the performance compared to an equal number of cores on a single supercomputer. We argue that using widely distributed supercomputers in order to acquire more compute power is technically feasible, and that the largest obstacle is introduced by local scheduling and reservation policies.
Distributed Collections of Web Pages in the Wild
Venue: arXiv cs.DL 2011
Year: 2011

As the Distributed Collection Manager's work on building tools to support users maintaining collections of changing web-based resources has progressed, questions about the characteristics of people's collections of web pages have arisen. Simultaneously, work in the areas of social bookmarking, social news, and subscription-based technologies have been taking the existence, usage, and utility of this data for granted with neither investigation into what people are doing with their collections nor how they are trying to maintain them. In order to address these concerns, we performed an online user study of 125 individuals from a variety of online and offline communities, such as the reddit social news user community and the graduate student body in our department. From this study we were able to examine a user's needs for a system to manage their web-based distributed collections, how their current tools affect their ability to maintain their collections, and what the characteristics of their current practices and problems in maintaining their web-based collections were. We also present extensions and improvements being made to the system both in order to adapt DCM for usage in the Ensemble project and to meet the requirements found by our user study.
Best Effort and Practice Activation Codes
Venue: arXiv cs.CR 2011
Year: 2011

Activation Codes are used in many different digital services and known by many different names including voucher, e-coupon and discount code. In this paper we focus on a specific class of ACs that are short, human-readable, fixed-length and represent value. Even though this class of codes is extensively used there are no general guidelines for the design of Activation Code schemes. We discuss different methods that are used in practice and propose BEPAC, a new Activation Code scheme that provides both authenticity and confidentiality. The small message space of activation codes introduces some problems that are illustrated by an adaptive chosen-plaintext attack (CPA-2) on a general 3-round Feis- tel network of size 2^(2n) . This attack recovers the complete permutation from at most 2^(n+2) plaintext-ciphertext pairs. For this reason, BEPAC is designed in such a way that authenticity and confidentiality are in- dependent properties, i.e. loss of confidentiality does not imply loss of authenticity.
On a linear programming approach to the discrete Willmore boundary value problem and generalizations
Venue: arXiv cs.CG 2011
Year: 2011

We consider the problem of finding (possibly non connected) discrete surfaces spanning a finite set of discrete boundary curves in the three-dimensional space and minimizing (globally) a discrete energy involving mean curvature. Although we consider a fairly general class of energies, our main focus is on the Willmore energy, i.e. the total squared mean curvature Our purpose is to address the delicate task of approximating global minimizers of the energy under boundary constraints. The main contribution of this work is to translate the nonlinear boundary value problem into an integer linear program, using a natural formulation involving pairs of elementary triangles chosen in a pre-specified dictionary and allowing self-intersection. Our work focuses essentially on the connection between the integer linear program and its relaxation. We prove that: - One cannot guarantee the total unimodularity of the constraint matrix, which is a sufficient condition for the global solution of the relaxed linear program to be always integral, and therefore to be a solution of the integer program as well; - Furthermore, there are actually experimental evidences that, in some cases, solving the relaxed problem yields a fractional solution. Due to the very specific structure of the constraint matrix here, we strongly believe that it should be possible in the future to design ad-hoc integer solvers that yield high-definition approximations to solutions of several boundary value problems involving mean curvature, in particular the Willmore boundary value problem.
Convex Polyhedra Realizing Given Face Areas
Venue: arXiv cs.DM 2011
Year: 2011

Given n >= 4 positive real numbers, we prove in this note that they are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.
Energy-Latency Tradeoff for In-Network Function Computation in Random Networks
Venue: arXiv cs.NI 2011
Year: 2011

The problem of designing policies for in-network function computation with minimum energy consumption subject to a latency constraint is considered. The scaling behavior of the energy consumption under the latency constraint is analyzed for random networks, where the nodes are uniformly placed in growing regions and the number of nodes goes to infinity. The special case of sum function computation and its delivery to a designated root node is considered first. A policy which achieves order-optimal average energy consumption in random networks subject to the given latency constraint is proposed. The scaling behavior of the optimal energy consumption depends on the path-loss exponent of wireless transmissions and the dimension of the Euclidean region where the nodes are placed. The policy is then extended to computation of a general class of functions which decompose according to maximal cliques of a proximity graph such as the $k$-nearest neighbor graph or the geometric random graph. The modified policy achieves order-optimal energy consumption albeit for a limited range of latency constraints.
From joint convexity of quantum relative entropy to a concavity theorem of Lieb
Venue: arXiv cs.IT 2011
Year: 2011

This note provides a succinct proof of a 1973 theorem of Lieb that establishes the concavity of a certain trace function. The development relies on a deep result from quantum information theory, the joint convexity of quantum relative entropy, as well as a recent argument due to Carlen and Lieb.
Provenance for Aggregate Queries
Venue: arXiv cs.DB 2011
Year: 2011

We study in this paper provenance information for queries with aggregation. Provenance information was studied in the context of various query languages that do not allow for aggregation, and recent work has suggested to capture provenance by annotating the different database tuples with elements of a commutative semiring and propagating the annotations through query evaluation. We show that aggregate queries pose novel challenges rendering this approach inapplicable. Consequently, we propose a new approach, where we annotate with provenance information not just tuples but also the individual values within tuples, using provenance to describe the values computation. We realize this approach in a concrete construction, first for "simple" queries where the aggregation operator is the last one applied, and then for arbitrary (positive) relational algebra queries with aggregation; the latter queries are shown to be more challenging in this context. Finally, we use aggregation to encode queries with difference, and study the semantics obtained for such queries on provenance annotated databases.
Scientific data searching, sharing and retrieval
Venue: arXiv cs.IT 2011
Year: 2011

In the recent years, there has been significant advancement in the areas of scientific data management and retrieval techniques, especially in terms of standards and protocols for archiving data. Oak Ridge National Laboratory Distributed Data Archive Center for biogeochemical dynamics is making efforts in building advanced toolsets for these purposes. Mercury is a web-based metadata harvesting, data discovery and access system, built for researchers to search for, share and obtain biogeochemical data. Originally developed for single National Aeronautics and Space Administration (NASA) project, Mercury now used over fourteen different projects across three US federal agencies. Mercury renders various capabilities including metadata management, indexing, searching, data sharing, and also software reusability.
Extending Bron Kerbosch for Solving the Maximum Weight Clique Problem
Venue: arXiv cs.DS 2011
Year: 2011

This contribution extends the Bron Kerbosch algorithm for solving the maximum weight clique problem, where continuous-valued weights are assigned to both, vertices and edges. We applied the proposed algorithm to graph matching problems.
Bounding the Feedback Vertex Number of Digraphs in Terms of Vertex Degrees
Venue: arXiv cs.DM 2011
Year: 2011

The Turan bound is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality, which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex outdegrees and in terms of average outdegree, respectively.
Fast Approximation Algorithms for Art Gallery Problems in Simple Polygons
Venue: arXiv cs.CG 2011
Year: 2011

We present approximation algorithms with O(n^3) processing time for the minimum vertex and edge guard problems in simple polygons. It is improved from previous O(n^4) time algorithms of Ghosh. For simple polygon, there are O(n^3) visibility regions, thus any approximation algorithm for the set covering problem with approximation ratio of log(n) can be used for the approximation of n vertex and edge guard problems with O(n^3) visibility sequence. We prove that the visibility of all points in simple polygons is guaranteed by covering O(n^2) sinks from vertices and edges : It comes to O(n^3) time bound.
On the expressiveness of Parikh automata and related models
Venue: arXiv cs.FL 2011
Year: 2011

The Parikh finite word automaton (PA) was introduced and studied by Klaedtke and Ruess in 2003. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA (APA), that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters (LPA), that restricts the PA by forcing any two transitions on same letter to affect the registers equally. Then we report on the expressiveness, closure, and decidability properties of such PA variants. We note that deterministic PA are strictly weaker than deterministic reversal-bounded counter machines. We develop pumping-style lemmas and identify an explicit PA language recognized by no deterministic PA.
Reversible Region of Non-Interest (RONI) Watermarking for Authentication of DICOM Images
Venue: arXiv cs.CR 2011
Year: 2011

This paper introduces current watermarking techniques available from the literatures. Requirements for medical watermarking will be discussed. We then propose a watermarking scheme that can recover the original image from the watermarked one. The purpose is to verify the integrity and authenticity of DICOM images. We used ultrasound (US) images in our experiment. SHA-256 of the whole image is embedded in the least significant bits of the RONI (Region of Non-Interest). If the image has not been altered, the watermark will be extracted and the original image will be recovered. SHA-256 of the recovered image will be compared with the extracted watermark for authentication.
Multi-Relay Selection Design and Analysis for Multi-Stream Cooperative Communications
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider the problem of multi-relay selection for multi-stream cooperative MIMO systems with $M$ relay nodes. Traditionally, relay selection approaches are primarily focused on selecting one relay node to improve the transmission reliability given a single-antenna destination node. As such, in the cooperative phase whereby both the source and the selected relay nodes transmit to the destination node, it is only feasible to exploit cooperative spatial diversity (for example by means of distributed space time coding). For wireless systems with a multi-antenna destination node, in the cooperative phase it is possible to opportunistically transmit multiple data streams to the destination node by utilizing multiple relay nodes. Therefore, we propose a low overhead multi-relay selection protocol to support multi-stream cooperative communications. In addition, we derive the asymptotic performance results at high SNR for the proposed scheme and discuss the diversity-multiplexing tradeoff as well as the throughput-reliability tradeoff. From these results, we show that the proposed multi-stream cooperative communication scheme achieves lower outage probability compared to existing baseline schemes.
A Logic Programming Approach for Formal Verification of NetBill Security and Transactions Protocol
Venue: arXiv cs.CR 2011
Year: 2011

Use of formal techniques for verifying the security features of electronic commerce protocols would facilitate, the enhancement of reliability of such protocols, thereby increasing their usability. This paper projects the application of logic programming techniques for formal verification of a well referred security and transactions protocol, the NetBill. The paper uses ALSP (Action Language for Security Protocols) as an efficient formal specification language and SMODELS a model generator to formally analyze and plan attacks on the protocol.
Using graphics processing units to generate random numbers
Venue: arXiv cs.DC 2011
Year: 2011

The future of high-performance computing is aligning itself towards the efficient use of highly parallel computing environments. One application where the use of massive parallelism comes instinctively is Monte Carlo simulations, where a large number of independent events have to be simulated. At the core of the Monte Carlo simulation lies the Random Number Generator (RNG). In this paper, the massively parallel implementation of a collection of pseudo-random number generators on a graphics processing unit (GPU) is presented. The results of the GPU implementation, in terms of samples/s, effective bandwidth and operations per second, are presented. A comparison with other implementations on different hardware platforms, in terms of samples/s, power efficiency and cost-benefit, is also presented. Random numbers generation throughput of up to ~18MSamples/s have been achieved on the graphics hardware used. Efficient hardware utilization, in terms of operations per second, has reached ~98% of the possible integer operation throughput.