OpenRaiser/Intern-Atlas huggingface dataset:
A Longitudinal Study of Non-Voice Mobile Phone Usage by Teens from an Underserved Urban Community
Venue: arXiv cs.HC 2010
Year: 2010

We report a user study of over four months on the non-voice usage of mobile phones by teens from an underserved urban community in the USA where a community-wide, open-access Wi-Fi network exists. We instrumented the phones to record quantitative information regarding their usage and location in a privacy-respecting manner. We conducted focus group meetings and interviewed participants regularly for qualitative data. We present our findings on what applications our participants used and how their usage changed over time. The findings highlight the challenges to evaluating the usability of mobile systems and the value of long-term methodologies. Based on our findings, we analyze the unique values of mobile phones, as a platform technology. Our study shows that the usage is highly mobile, location-dependent, and serves multiple social purposes for the participants. Furthermore, we present concrete findings on how to perform and analyze similar user studies on mobile phones, including four contributing factors to usage evolution, and provide guidelines for their design and evaluation.
Digital watermarking : An approach based on Hilbert transform
Venue: arXiv cs.MM 2010
Year: 2010

Most of the well known algorithms for watermarking of digital images involve transformation of the image data to Fourier or singular vector space. In this paper, we introduce watermarking in Hilbert transform domain for digital media. Generally, if the image is a matrix of order $m$ by $n$, then the transformed space is also an image of the same order. However, with Hilbert transforms, the transformed space is of order $2m$ by $2n$. This allows for more latitude in storing the watermark in the host image. Based on this idea, we propose an algorithm for embedding and extracting watermark in a host image and analytically obtain a parameter related to this procedure. Using extensive simulations, we show that the algorithm performs well even if the host image is corrupted by various attacks.
A Study on Recent Approaches in Handling DDoS Attacks
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we present a study on the recent approaches in handling Distributed Denial of Service (DDoS) attacks. DDoS attack is a fairly new type of attack to cripple the availability of Internet services and resources. A DDos attack can originate from anywhere in the network and typically overwhelms the victim server by sending a huge number of packets. Several remedial measures have been proposed by various researchers. This paper attempts to discuss the recent offerings to handle the DDoS attacks.
A Proof Carrying Code Framework for Inlined Reference Monitors in Java Bytecode
Venue: arXiv cs.LO 2010
Year: 2010

We propose a light-weight approach for certification of monitor inlining for sequential Java bytecode using proof-carrying code. The goal is to enable the use of monitoring for quality assurance at development time, while minimizing the need for post-shipping code rewrites as well as changes to the end-host TCB. Standard automaton-based security policies express constraints on allowed API call/return sequences. Proofs are represented as JML-style program annotations. This is adequate in our case as all proofs generated in our framework are recognized in time polynomial in the size of the program. Policy adherence is proved by comparing the transitions of an inlined monitor with those of a trusted "ghost" monitor represented using JML-style annotations. At time of receiving a program with proof annotations, it is sufficient for the receiver to plug in its own trusted ghost monitor and check the resulting verification conditions, to verify that inlining has been performed correctly, of the correct policy. We have proved correctness of the approach at the Java bytecode level and formalized the proof of soundness in Coq. An implementation, including an application loader running on a mobile device, is available, and we conclude by giving benchmarks for two sample applications.
On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms
Venue: arXiv cs.NE 2010
Year: 2010

The interplay between mutation and selection plays a fundamental role in the behaviour of evolutionary algorithms (EAs). However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitist population-based EA that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter $η$, controlling the selection pressure in linear ranking, and parameter $χ$ controlling the bit-wise mutation rate, impacts the runtime of the algorithm. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which can only be solved in polynomial time if the ratio between parameters $η$ and $χ$ is within a narrow critical interval, and where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown quantitatively how the appropriate parameter choice depends on the characteristics of the fitness function. In addition to the original results on the runtime of EAs, this paper also introduces a very useful analytical tool, i.e., multi-type branching processes, to the runtime analysis of non-elitist population-based EAs.
Short collusion-secure fingerprint codes against three pirates
Venue: arXiv cs.CR 2010
Year: 2010

In this article, we propose a new construction of probabilistic collusion-secure fingerprint codes against up to three pirates and give a theoretical security evaluation. Our pirate tracing algorithm combines a scoring method analogous to Tardos codes (J. ACM, 2008) with an extension of parent search techniques of some preceding 2-secure codes. Numerical examples show that our code lengths are significantly shorter than (about 30% to 40% of) the shortest known c-secure codes by Nuida et al. (Des. Codes Cryptogr., 2009) with c = 3. Some preliminary proposal for improving efficiency of our tracing algorithm is also given.
On the CNF encoding of cardinality constraints and beyond
Venue: arXiv cs.AI 2010
Year: 2010

In this report, we propose a quick survey of the currently known techniques for encoding a Boolean cardinality constraint into a CNF formula, and we discuss about the relevance of these encodings. We also propose models to facilitate analysis and design of CNF encodings for Boolean constraints.
PhyloGrid: a development for a workflow in Phylogeny
Venue: arXiv cs.CE 2010
Year: 2010

In this work we present the development of a workflow based on Taverna which is going to be implemented for calculations in Phylogeny by means of the MrBayes tool. It has a friendly interface developed with the Gridsphere framework. The user is able to define the parameters for doing the Bayesian calculation, determine the model of evolution, check the accuracy of the results in the intermediate stages as well as do a multiple alignment of the sequences previously to the final result. To do this, no knowledge from his/her side about the computational procedure is required.
Artificial Intelligence in Reverse Supply Chain Management: The State of the Art
Venue: arXiv cs.AI 2010
Year: 2010

Product take-back legislation forces manufacturers to bear the costs of collection and disposal of products that have reached the end of their useful lives. In order to reduce these costs, manufacturers can consider reuse, remanufacturing and/or recycling of components as an alternative to disposal. The implementation of such alternatives usually requires an appropriate reverse supply chain management. With the concepts of reverse supply chain are gaining popularity in practice, the use of artificial intelligence approaches in these areas is also becoming popular. As a result, the purpose of this paper is to give an overview of the recent publications concerning the application of artificial intelligence techniques to reverse supply chain with emphasis on certain types of product returns.
A fast divide-and-conquer algorithm for indexing human genome sequences
Venue: arXiv cs.DB 2010
Year: 2010

Since the release of human genome sequences, one of the most important research issues is about indexing the genome sequences, and the suffix tree is most widely adopted for that purpose. The traditional suffix tree construction algorithms have severe performance degradation due to the memory bottleneck problem. The recent disk-based algorithms also have limited performance improvement due to random disk accesses. Moreover, they do not fully utilize the recent CPUs with multiple cores. In this paper, we propose a fast algorithm based on 'divide-and-conquer' strategy for indexing the human genome sequences. Our algorithm almost eliminates random disk accesses by accessing the disk in the unit of contiguous chunks. In addition, our algorithm fully utilizes the multi-core CPUs by dividing the genome sequences into multiple partitions and then assigning each partition to a different core for parallel processing. Experimental results show that our algorithm outperforms the previous fastest DIGEST algorithm by up to 3.5 times.
Employing Coded Relay in Multi-hop Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we study Coded relay (Crelay) in multi-hop wireless networks. Crelay exploits both partial packets and overhearing capabilities of the wireless nodes, and uses Forward Error Correction code in packet forwarding. When a node overhears a partial packet from an upstream node, it informs the upstream node about the number of parity bytes needed to correct the errors, such that the upstream node need only send a small amount of parity bytes instead of the complete packet, hence improving the network efficiency. Our main contributions include the following. First, we propose an efficient network protocol that can exploit partial packets and overhearing. Second, we study the routing problem in networks with Crelay and propose a greedy algorithm for finding the paths. Third, we propose an error ratio estimator, called AMPS, that can estimate the number of byte errors in a received frame with good accuracy at a low overhead of only 8 bytes per frame, where the estimator is needed for a node to find the number of needed parity bytes. Fourth, we implement the proposed protocol and algorithm within the Click modular router, and our experiments show that Crelay can significantly improve the performance of wireless networks.
A Self-Organising Neural Network for Processing Data from Multiple Sensors
Venue: arXiv cs.NE 2010
Year: 2010

This paper shows how a folded Markov chain network can be applied to the problem of processing data from multiple sensors, with an emphasis on the special case of 2 sensors. It is necessary to design the network so that it can transform a high dimensional input vector into a posterior probability, for which purpose the partitioned mixture distribution network is ideally suited. The underlying theory is presented in detail, and a simple numerical simulation is given that shows the emergence of ocular dominance stripes.
A New Technique for Text Data Compression
Venue: arXiv cs.CR 2010
Year: 2010

In this paper we use ternary representation of numbers for compressing text data. We use a binary map for ternary digits and introduce a way to use the binary 11-pair, which has never been use for coding data before, and we futher use 4-Digits ternary representation of alphabet with lowercase and uppercase with some extra symbols that are most commonly used in day to day life. We find a way to minimize the length of the bits string, which is only possible in ternary representation thus drastically reducing the length of the code. We also find some connection between this technique of coding dat and Fibonacci numbers.
Lightweight LCP-Array Construction in Linear Time
Venue: arXiv cs.DS 2010
Year: 2010

The suffix tree is a very important data structure in string processing, but it suffers from a huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of three (compressed) components: the suffix array, the LCP-array, and data structures for simulating navigational operations on the suffix tree. The LCP-array stores the lengths of the longest common prefixes of lexicographically adjacent suffixes, and it can be computed in linear time. In this paper, we present new LCP-array construction algorithms that are fast and very space efficient. In practice, our algorithms outperform the currently best algorithms.
Using virtual human for an interactive customer-oriented constrained environment design
Venue: arXiv cs.RO 2010
Year: 2010

For industrial product design, it is very important to take into account assembly/disassembly and maintenance operations during the conceptual and prototype design stage. For these operations or other similar operations in a constrained environment, trajectory planning is always a critical and difficult issue for evaluating the design or for the users' convenience. In this paper, a customer-oriented approach is proposed to partially solve ergonomic issues encountered during the design stage of a constrained environment. A single objective optimization based method is taken from the literature to generate the trajectory in a constrained environment automatically. A motion capture based method assists to guide the trajectory planning interactively if a local minimum is encountered within the single objective optimization. At last, a multi-objective evaluation method is proposed to evaluate the operations generated by the algorithm
Régularisation et optimisation pour l'imagerie sismique des fondations de pylônes
Venue: arXiv cs.CE 2010
Year: 2010

This research report summarizes the progress of work carried out jointly by the IRCCyN and the École Polytechnique de Montréal about the resolution of the inverse problem for the seismic imaging of transmission overhead line structure foundations. Several methods aimed at mapping the underground medium are considered. More particularly, we focus on methods based on a bilinear formulation of the forward problem on one hand (CSI, modified gradient, etc.) and on methods based on a "primal" formulation on the other hand. The performances of these methods are compared using synthetic data. This work was partially funded by RTE (Réseau de Transport d'Électricité), which has initiated the project, and was carried out in collaboration with EDF R&D (Électricité de France - Recherche et Développement).
Selling Culture: Implementation of e-Commerce and WAP-based Prototypes
Venue: arXiv cs.NI 2010
Year: 2010

Museum stores represent integral parts of the museums that have also a lot to benefit from a successful presence on the web arena. In addition to traditional web sites, carefully designed electronic commerce (e-commerce) sites may increase the potential of museum stores offering possibilities for on-line shopping and other commercial functions. In parallel, the recent convergence of the traditionally separate technologies of the Internet and mobile telephony has brought the concept of 'wireless Internet' into the spotlight. Within this context, 'mobile commerce' (m-commerce) is a relatively new trend that represents a natural extension of e-commerce into the wireless world. M-commerce refers to electronic business transactions and differentiates from e-commerce since it involves the use of mobile devices and wireless medium rather than wired. The unique characteristics of mobile computing bring forward new challenges and opportunities for museum stores. This article presents the design and implementation of an e-commerce and an m-commerce museum shop application. The aim is to evaluate and compare the two applications in terms of several parameters, such as available technologies, strengths and limitations, design requirements, usability, interaction speed, usage cost, etc and also to identify ways for enhancing the potential of such applications and designing successful and profitable business models.
Unification modulo a partial theory of exponentiation
Venue: arXiv cs.SC 2010
Year: 2010

Modular exponentiation is a common mathematical operation in modern cryptography. This, along with modular multiplication at the base and exponent levels (to different moduli) plays an important role in a large number of key agreement protocols. In our earlier work, we gave many decidability as well as undecidability results for multiple equational theories, involving various properties of modular exponentiation. Here, we consider a partial subtheory focussing only on exponentiation and multiplication operators. Two main results are proved. The first result is positive, namely, that the unification problem for the above theory (in which no additional property is assumed of the multiplication operators) is decidable. The second result is negative: if we assume that the two multiplication operators belong to two different abelian groups, then the unification problem becomes undecidable.
Convolutional Goppa codes defined on fibrations
Venue: arXiv cs.IT 2010
Year: 2010

We define a new class of Convolutional Codes in terms of fibrations of algebraic varieties generalizaing our previous constructions of Convolutional Goppa Codes. Using this general construction we can give several examples of Maximum Distance Separable (MDS) Convolutional Codes.
Shortest Paths with Pairwise-Distinct Edge Labels: Finding Biochemical Pathways in Metabolic Networks
Venue: arXiv cs.DS 2010
Year: 2010

A problem studied in Systems Biology is how to find shortest paths in metabolic networks. Unfortunately, simple (i.e., graph theoretic) shortest paths do not properly reflect biochemical facts. An approach to overcome this issue is to use edge labels and search for paths with distinct labels. In this paper, we show that such biologically feasible shortest paths are hard to compute. Moreover, we present solutions to find such paths in networks in reasonable time.
Work-stealing for mixed-mode parallelism by deterministic team-building
Venue: arXiv cs.DC 2010
Year: 2010

We show how to extend classical work-stealing to deal also with data parallel tasks that can require any number of threads r >= 1 for their execution. We explain in detail the so introduced idea of work-stealing with deterministic team-building which in a natural way generalizes classical work-stealing. A prototype C++ implementation of the generalized work-stealing algorithm has been given and is briefly described. Building on this, a serious, well-known contender for a best parallel Quicksort algorithm has been implemented, which naturally relies on both task and data parallelism. For instance, sorting 2^27-1 randomly generated integers we could improve the speed-up from 5.1 to 8.7 on a 32-core Intel Nehalem EX system, being consistently better than the tuned, task-parallel Cilk++ system.
On Hoare-McCarthy algebras
Venue: arXiv cs.LO 2010
Year: 2010

We discuss an algebraic approach to propositional logic with side effects. To this end, we use Hoare's conditional [1985], which is a ternary connective comparable to if-then-else. Starting from McCarthy's notion of sequential evaluation [1963] we discuss a number of valuation congruences and we introduce Hoare-McCarthy algebras as the structures that characterize these congruences.
Extension of the Blahut-Arimoto algorithm for maximizing directed information
Venue: arXiv cs.IT 2010
Year: 2010

We extend the Blahut-Arimoto algorithm for maximizing Massey's directed information. The algorithm can be used for estimating the capacity of channels with delayed feedback, where the feedback is a deterministic function of the output. In order to do so, we apply the ideas from the regular Blahut-Arimoto algorithm, i.e., the alternating maximization procedure, onto our new problem. We provide both upper and lower bound sequences that converge to the optimum value. Our main insight in this paper is that in order to find the maximum of the directed information over causal conditioning probability mass function (PMF), one can use a backward index time maximization combined with the alternating maximization procedure. We give a detailed description of the algorithm, its complexity, the memory needed, and several numerical examples.
Power-Rate Allocation in DS/CDMA Based on Discretized Verhulst Equilibrium
Venue: arXiv cs.CE 2010
Year: 2010

This paper proposes to extend the discrete Verhulst power equilibrium approach, previously suggested in [1], to the power-rate optimal allocation problem. Multirate users associated to different types of traffic are aggregated to distinct user' classes, with the assurance of minimum rate allocation per user and QoS. Herein, Verhulst power allocation algorithm was adapted to the single-input-single-output DS/CDMA jointly power-rate control problem. The analysis was carried out taking into account the convergence time, quality of solution, in terms of the normalized squared error (NSE), when compared with the analytical solution based on interference matrix inverse, and computational complexity. Numerical results demonstrate the validity of the proposed resource allocation methodology.
A Relation between the Protocol Partition Number and the Quasi-Additive Bound
Venue: arXiv cs.CC 2010
Year: 2010

In this note, we show that the linear programming for computing the quasi-additive bound of the formula size of a Boolean function presented by Ueno [MFCS'10] is equivalent to the dual problem of the linear programming relaxation of an integer programming for computing the protocol partition number. Together with the result of Ueno [MFCS'10], our results imply that there exists no gap between our integer programming for computing the protocol partition number and its linear programming relaxation.
Matrix Insertion-Deletion Systems
Venue: arXiv cs.FL 2010
Year: 2010

In this article, we consider for the first time the operations of insertion and deletion working in a matrix controlled manner. We show that, similarly as in the case of context-free productions, the computational power is strictly increased when using a matrix control: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and using only binary matrices.
Efficient Generation of Random Bits from Finite State Markov Chains
Venue: arXiv cs.IT 2010
Year: 2010

The problem of random number generation from an uncorrelated random source (of unknown probability distribution) dates back to von Neumann's 1951 work. Elias (1972) generalized von Neumann's scheme and showed how to achieve optimal efficiency in unbiased random bits generation. Hence, a natural question is what if the sources are correlated? Both Elias and Samuelson proposed methods for generating unbiased random bits in the case of correlated sources (of unknown probability distribution), specifically, they considered finite Markov chains. However, their proposed methods are not efficient or have implementation difficulties. Blum (1986) devised an algorithm for efficiently generating random bits from degree-2 finite Markov chains in expected linear time, however, his beautiful method is still far from optimality on information-efficiency. In this paper, we generalize Blum's algorithm to arbitrary degree finite Markov chains and combine it with Elias's method for efficient generation of unbiased bits. As a result, we provide the first known algorithm that generates unbiased random bits from an arbitrary finite Markov chain, operates in expected linear time and achieves the information-theoretic upper bound on efficiency.