OpenRaiser/Intern-Atlas huggingface dataset:
Footprint Tracker: reviewing lifelogs and reconstructing daily experiences
Venue: arXiv cs.HC 2012
Year: 2012

With the increasing emphasis on how mobile technologies are experienced in everyday life, researchers are increasingly emphasizing the use of in-situ methods such as Experience Sampling and Day Reconstruction. In our line of research we explore the concept of Technology-Assisted Reconstruction, in which passively logged behavior data assist in the later reconstruction of daily experiences. In this paper we introduce Footprint tracker, a web application that supports participants in reviewing lifelogs and reconstructing their daily experiences. We focus on three kinds of data: visual (as captured through Microsoft's sensecam), location, and context (i.e., SMS and calls received and made). We describe how Footprint Tracker supports the user in reviewing these lifelogs and outline a field study that attempts to inquire into whether and how this data support reconstruction from memory.
Beyond Experience Sampling: Evaluating Personal Informatics with Technology-Assisted Reconstruction
Venue: arXiv cs.HC 2012
Year: 2012

Experience Sampling has been considered the golden standard of in-situ measurement, yet, at the expense of high burden to participants. In this paper we propose Technology-Assisted Reconstruction (TAR), a methodological approach that combines passive logging of users' behaviors with use of these data in assisting the reconstruction of behaviors and experiences. Through a number of recent and ongoing projects we will discuss how TAR may be employed for the evaluation of personal informatics systems, but also, conversely, how ideas from the field of personal informatics may contribute towards the development of new methodologies for in-situ evaluation.
Finding Structure in Text, Genome and Other Symbolic Sequences
Venue: arXiv cs.CL 2012
Year: 2012

The statistical methods derived and described in this thesis provide new ways to elucidate the structural properties of text and other symbolic sequences. Generically, these methods allow detection of a difference in the frequency of a single feature, the detection of a difference between the frequencies of an ensemble of features and the attribution of the source of a text. These three abstract tasks suffice to solve problems in a wide variety of settings. Furthermore, the techniques described in this thesis can be extended to provide a wide range of additional tests beyond the ones described here. A variety of applications for these methods are examined in detail. These applications are drawn from the area of text analysis and genetic sequence analysis. The textually oriented tasks include finding interesting collocations and cooccurent phrases, language identification, and information retrieval. The biologically oriented tasks include species identification and the discovery of previously unreported long range structure in genes. In the applications reported here where direct comparison is possible, the performance of these new methods substantially exceeds the state of the art. Overall, the methods described here provide new and effective ways to analyse text and other symbolic sequences. Their particular strength is that they deal well with situations where relatively little data are available. Since these methods are abstract in nature, they can be applied in novel situations with relative ease.
Error Free Perfect Secrecy Systems
Venue: arXiv cs.IT 2012
Year: 2012

Shannon's fundamental bound for perfect secrecy says that the entropy of the secret message cannot be larger than the entropy of the secret key initially shared by the sender and the legitimate receiver. Massey gave an information theoretic proof of this result, however this proof does not require independence of the key and ciphertext. By further assuming independence, we obtain a tighter lower bound, namely that the key entropy is not less than the logarithm of the message sample size in any cipher achieving perfect secrecy, even if the source distribution is fixed. The same bound also applies to the entropy of the ciphertext. The bounds still hold if the secret message has been compressed before encryption. This paper also illustrates that the lower bound only gives the minimum size of the pre-shared secret key. When a cipher system is used multiple times, this is no longer a reasonable measure for the portion of key consumed in each round. Instead, this paper proposes and justifies a new measure for key consumption rate. The existence of a fundamental tradeoff between the expected key consumption and the number of channel uses for conveying a ciphertext is shown. Optimal and nearly optimal secure codes are designed.
Tight Cell-Probe Bounds for Online Hamming Distance Computation
Venue: arXiv cs.DS 2012
Year: 2012

We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. The task is to output the Hamming distance between a fixed string of length n and the last n symbols of a stream. We give a lower bound of Omega((d/w)*log n) time on average per output, where d is the number of bits needed to represent an input symbol. We argue that this bound is tight within the model. The lower bound holds under randomisation and amortisation.
Hycon2 Benchmark: Power Network System
Venue: arXiv cs.SY 2012
Year: 2012

As a benchmark exercise for testing software and methods developed in Hycon2 for decentralized and distributed control, we address the problem of designing the Automatic Generation Control (AGC) layer in power network systems. In particular, we present three different scenarios and discuss performance levels that can be reached using Centralized Model Predictive Control (MPC). These results can be used as a milestone for comparing the performance of alternative control schemes. Matlab software for simulating the scenarios is also provided in an accompanying file.
Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction
Venue: arXiv cs.IT 2012
Year: 2012

Compressed sensing is designed to measure sparse signals directly in a compressed form. However, most signals of interest are only "approximately sparse", i.e. even though the signal contains only a small fraction of relevant (large) components the other components are not strictly equal to zero, but are only close to zero. In this paper we model the approximately sparse signal with a Gaussian distribution of small components, and we study its compressed sensing with dense random matrices. We use replica calculations to determine the mean-squared error of the Bayes-optimal reconstruction for such signals, as a function of the variance of the small components, the density of large components and the measurement rate. We then use the G-AMP algorithm and we quantify the region of parameters for which this algorithm achieves optimality (for large systems). Finally, we show that in the region where the GAMP for the homogeneous measurement matrices is not optimal, a special "seeding" design of a spatially-coupled measurement matrix allows to restore optimality.
Distributed Estimation in Multi-Agent Networks
Venue: arXiv cs.IT 2012
Year: 2012

A problem of distributed state estimation at multiple agents that are physically connected and have competitive interests is mapped to a distributed source coding problem with additional privacy constraints. The agents interact to estimate their own states to a desired fidelity from their (sensor) measurements which are functions of both the local state and the states at the other agents. For a Gaussian state and measurement model, it is shown that the sum-rate achieved by a distributed protocol in which the agents broadcast to one another is a lower bound on that of a centralized protocol in which the agents broadcast as if to a virtual CEO converging only in the limit of a large number of agents. The sufficiency of encoding using local measurements is also proved for both protocols.
Not Too Delayed CSIT Achieves the Optimal Degrees of Freedom
Venue: arXiv cs.IT 2012
Year: 2012

Channel state information at the transmitter (CSIT) aids interference management in many communication systems. Due to channel state information (CSI) feedback delay and time-variation in the wireless channel, perfect CSIT is not realistic. In this paper, the CSI feedback delay-DoF gain trade-off is characterized for the multi-user vector broadcast channel. A major insight is that it is possible to achieve the optimal degrees of freedom (DoF) gain if the delay is less than a certain fraction of the channel coherence time. This precisely characterizes the intuition that a small delay should be negligeable. To show this, a new transmission method called space-time interference alignment is proposed, which actively exploits both the current and past CSI.
Using Constraints for Equivalent Mutant Detection
Venue: arXiv cs.SE 2012
Year: 2012

In mutation testing the question whether a mutant is equivalent to its program is important in order to compute the correct mutation score. Unfortunately, answering this question is not always possible and can hardly be obtained just by having a look at the program's structure. In this paper we introduce a method for solving the equivalent mutant problem using a constraint representation of the program and its mutant. In particularly the approach is based on distinguishing test cases, i.e., test inputs that force the program and its mutant to behave in a different way. Beside the foundations of the approach, in this paper we also present the algorithms and first empirical results.
Verified System Development with the AutoFocus Tool Chain
Venue: arXiv cs.SE 2012
Year: 2012

This work presents a model-based development methodology for verified software systems as well as a tool support for it: an applied AutoFocus tool chain and its basic principles emphasizing the verification of the system under development as well as the check mechanisms we used to raise the level of confidence in the correctness of the implementation of the automatic generators.
On Formal Specification of Maple Programs
Venue: arXiv cs.MS 2012
Year: 2012

This paper is an example-based demonstration of our initial results on the formal specification of programs written in the computer algebra language MiniMaple (a substantial subset of Maple with slight extensions). The main goal of this work is to define a verification framework for MiniMaple. Formal specification of MiniMaple programs is rather complex task as it supports non-standard types of objects, e.g. symbols and unevaluated expressions, and additional functions and predicates, e.g. runtime type tests etc. We have used the specification language to specify various computer algebra concepts respective objects of the Maple package DifferenceDifferential developed at our institute.
Arabic CALL system based on pedagogically indexed text
Venue: arXiv cs.AI 2012
Year: 2012

This article introduces the benefits of using computer as a tool for foreign language teaching and learning. It describes the effect of using Natural Language Processing (NLP) tools for learning Arabic. The technique explored in this particular case is the employment of pedagogically indexed corpora. This text-based method provides the teacher the advantage of building activities based on texts adapted to a particular pedagogical situation. This paper also presents ARAC: a Platform dedicated to language educators allowing them to create activities within their own pedagogical area of interest.
Scalable Minimization Algorithm for Partial Bisimulation
Venue: arXiv cs.LO 2012
Year: 2012

We present an efficient algorithm for computing the partial bisimulation preorder and equivalence for labeled transitions systems. The partial bisimulation preorder lies between simulation and bisimulation, as only a part of the set of actions is bisimulated, whereas the rest of the actions are simulated. Computing quotients for simulation equivalence is more expensive than for bisimulation equivalence, as for simulation one has to account for the so-called little brothers, which represent classes of states that can simulate other classes. It is known that in the absence of little brother states, (partial bi)simulation and bisimulation coincide, but still the complexity of existing minimization algorithms for simulation and bisimulation does not scale. Therefore, we developed a minimization algorithm and an accompanying tool that scales with respect to the bisimulated action subset.
An XML-Format for Conjectures in Geometry (Work-in-Progress)
Venue: arXiv cs.CG 2012
Year: 2012

With a large number of software tools dedicated to the visualisation and/or demonstration of properties of geometric constructions and also with the emerging of repositories of geometric constructions, there is a strong need of linking them, and making them and their corpora, widely usable. A common setting for interoperable interactive geometry was already proposed, the i2g format, but, in this format, the conjectures and proofs counterparts are missing. A common format capable of linking all the tools in the field of geometry is missing. In this paper an extension of the i2g format is proposed, this extension is capable of describing not only the geometric constructions but also the geometric conjectures. The integration of this format into the Web-based GeoThms, TGTP and Web Geometry Laboratory systems is also discussed.
DQSB: A Reliable Broadcast Protocol Based on Distributed Quasi-Synchronized Mechanism for Low Duty-Cycled Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

In duty-cycled wireless sensor networks, deployed sensor nodes are usually put to sleep for energy efficiency according to sleep scheduling approaches. Any sleep scheduling scheme with its supporting protocols ensures that data can always be routed from source to sink. In this paper, we investigate a problem of multi-hop broadcast and routing in random sleep scheduling scheme, and propose a novel protocol, called DQSB, by quasi-synchronization mechanism to achieve reliable broadcast and less latency routing. DQSB neither assumes time synchronization which requires all neighboring nodes wake up at the same time, nor assumes duty-cycled awareness which makes it difficult to use in asynchronous WSNs. Furthermore, the benefit of quasi-synchronized mechanism for broadcast from sink to other nodes is the less latency routing paths for reverse data collection to sink because of no or less sleep waiting time. Simulation results show that DQSB outperforms the existing protocols in broadcast times performance and keeps relative tolerant broadcast latency performance, even in the case of unreliable links. The proposed DQSB protocol, in this paper, can be recognized as a tradeoff between broadcast times and broadcast latency. We also explore the impact of parameters in the assumption and the approach to get proper values for supporting DQSB.
Ontology for Mobile Phone Operating Systems
Venue: arXiv cs.SE 2012
Year: 2012

This ongoing study deals with an important part of a line of research that constitutes a challenging burden. It is an initial investigation into the development of a Holistic Framework for Cellular Communication (HFCC). The main purpose is to establish mechanisms by which existing wireless cellular communication components and models can work holistically together. It demonstrates that establishing a mathematical framework that allows existing cellular communication technologies (and tools supporting those technologies) to seamlessly interact is technically feasible. The longer-term future goals are to actually improve the interoperability, the efficiency of mobile communication, calls quality, and reliability by applying the framework to specific development efforts.
Survey of Extended LEACH-Based Clustering Routing Protocols for Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

An energy efficient routing protocol is the major concern in Wireless Sensor Networks (WSNs). In this survey paper, we present energy efficient hierarchical routing protocols, developed from conventional LEACH routing protocol. Main focus of our study is how these extended protocols work in order to increase the life time and how quality routing protocol are improved for WSNs. Furthermore, this paper also highlights some of the issues faced by LEACH and also explains how these issues are tackled by extended versions of LEACH. We compare the features and performance issues of the selected hierarchal routing protocols.
Multimedia Steganographic Scheme using Multiresolution Analysis
Venue: arXiv cs.CR 2012
Year: 2012

Digital steganography or data hiding has emerged as a new area of research in connection to the communication in secured channel as well as intellectual property protection for multimedia signals. The redundancy in image representation can be exploited successfully to embed specified characteristic information with a good quality of imperceptibility. The hidden multimedia information will be communicated to the authentic user through secured channel as a part of the data. This article deals with a transform domain, block-based and signal non-adaptive/adaptive technique for inserting multimedia signals into an RGB image. The robustness of the proposed method has been tested compared to the other transform domain techniques. Proposed algorithm also shows improvement in visual and statistical invisibility of the hidden information.
Discrete Chaotic Sequence based on Logistic Map in Digital Communications
Venue: arXiv cs.DM 2012
Year: 2012

The chaotic systems have been found applications in diverse fields such as pseudo random number generator, coding, cryptography, spread spectrum (SS) communications etc. The inherent capability of generating a large space of PN sequences due to sensitive dependence on initial conditions has been the main reason for exploiting chaos in spread spectrum communication systems. This behaviour suggests that it is straightforward to generate a variety of initial condition induced PN sequences with nice statistical properties by quantising the output of an iterated chaotic map. In the present paper the study has been carried out for the feasibility and usefulness of chaotic sequence in SS based applications like communication and watermarking.
Genetic agent approach for improving on-the-fly web map generalization
Venue: arXiv cs.MA 2012
Year: 2012

The utilization of web mapping becomes increasingly important in the domain of cartography. Users want access to spatial data on the web specific to their needs. For this reason, different approaches were appeared for generating on-the-fly the maps demanded by users, but those not suffice for guide a flexible and efficient process. Thus, new approach must be developed for improving this process according to the user needs. This work focuses on defining a new strategy which improves on-the-fly map generalization process and resolves the spatial conflicts. This approach uses the multiple representation and cartographic generalization. The map generalization process is based on the implementation of multi- agent system where each agent was equipped with a genetic patrimony.
Cascade Source Coding with a Side Information "Vending Machine"
Venue: arXiv cs.IT 2012
Year: 2012

The model of a side information "vending machine" (VM) accounts for scenarios in which the measurement of side information sequences can be controlled via the selection of cost-constrained actions. In this paper, the three-node cascade source coding problem is studied under the assumption that a side information VM is available and the intermediate and/or at the end node of the cascade. A single-letter characterization of the achievable trade-off among the transmission rates, the distortions in the reconstructions at the intermediate and at the end node, and the cost for acquiring the side information is derived for a number of relevant special cases. It is shown that a joint design of the description of the source and of the control signals used to guide the selection of the actions at downstream nodes is generally necessary for an efficient use of the available communication links. In particular, for all the considered models, layered coding strategies prove to be optimal, whereby the base layer fulfills two network objectives: determining the actions of downstream nodes and simultaneously providing a coarse description of the source. Design of the optimal coding strategy is shown via examples to depend on both the network topology and the action costs. Examples also illustrate the involved performance trade-offs across the network.
Guard Zones and the Near-Far Problem in DS-CDMA Ad Hoc Networks
Venue: arXiv cs.IT 2012
Year: 2012

The central issue in direct-sequence code-division multiple-access (DS-CDMA) ad hoc networks is the prevention of a near-far problem. This paper considers two types of guard zones that may be used to control the near-far problem: a fundamental exclusion zone and an additional CSMA guard zone that may be established by the carrier-sense multiple-access (CSMA) protocol. In the exclusion zone, no mobiles are physically present, modeling the minimum physical separation among mobiles that is always present in actual networks. Potentially interfering mobiles beyond a transmitting mobile's exclusion zone, but within its CSMA guard zone, are deactivated by the protocol. This paper provides an analysis of DS-CSMA networks with either or both types of guard zones. A network of finite extent with a finite number of mobiles is modeled as a uniform clustering process. The analysis uses a closed-form expression for the outage probability in the presence of Nakagami fading, conditioned on the network geometry. By using the analysis developed in this paper, the tradeoffs between exclusion zones and CSMA guard zones are explored for DS-CDMA and unspread networks.
ROI Segmentation for Feature Extraction from Human Facial Images
Venue: arXiv cs.CV 2012
Year: 2012

Human Computer Interaction (HCI) is the biggest goal of computer vision researchers. Features form the different facial images are able to provide a very deep knowledge about the activities performed by the different facial movements. In this paper we presented a technique for feature extraction from various regions of interest with the help of Skin color segmentation technique, Thresholding, knowledge based technique for face recognition.
Super-Fast 3-Ruling Sets
Venue: arXiv cs.DC 2012
Year: 2012

A $t$-ruling set of a graph $G = (V, E)$ is a vertex-subset $S \subseteq V$ that is independent and satisfies the property that every vertex $v \in V$ is at a distance of at most $t$ from some vertex in $S$. A \textit{maximal independent set (MIS)} is a 1-ruling set. The problem of computing an MIS on a network is a fundamental problem in distributed algorithms and the fastest algorithm for this problem is the $O(\log n)$-round algorithm due to Luby (SICOMP 1986) and Alon et al. (J. Algorithms 1986) from more than 25 years ago. Since then the problem has resisted all efforts to yield to a sub-logarithmic algorithm. There has been recent progress on this problem, most importantly an $O(\log Δ\cdot \sqrt{\log n})$-round algorithm on graphs with $n$ vertices and maximum degree $Δ$, due to Barenboim et al. (Barenboim, Elkin, Pettie, and Schneider, April 2012, arxiv 1202.1983; to appear FOCS 2012). We approach the MIS problem from a different angle and ask if O(1)-ruling sets can be computed much more efficiently than an MIS? As an answer to this question, we show how to compute a 2-ruling set of an $n$-vertex graph in $O((\log n)^{3/4})$ rounds. We also show that the above result can be improved for special classes of graphs such as graphs with high girth, trees, and graphs of bounded arboricity. Our main technique involves randomized sparsification that rapidly reduces the graph degree while ensuring that every deleted vertex is close to some vertex that remains. This technique may have further applications in other contexts, e.g., in designing sub-logarithmic distributed approximation algorithms. Our results raise intriguing questions about how quickly an MIS (or 1-ruling sets) can be computed, given that 2-ruling sets can be computed in sub-logarithmic rounds.